## Tuesday, 10 September 2013

### Phase 'Kick-back' Algorithms

Consider some black-box that encodes some function $f$ that is implemented as a controlled$-U_f$  gate acting on the state space $\mathcal{H}_A\otimes\mathcal{H}_B$ consisting of two registers $A$ and $B$ of qubits. Generally, when a controlled$-U_f$ gate is applied it is thought of as only affecting the target register $B$ leaving the control register $A$ unchanged. Therefore, the action of the $c-U_f$ gate is of the form
$c-U_f: \left|x\right>\left|\phi\right>\mapsto \left|x\right>\left|\phi'\right>,$
For some state $\left|\phi'\right>\in\mathcal{H}_B$. Suppose some state $\left|\psi\right>\in\mathcal{H}_B$ is chosen to satisfy
$c-U_f(\left|x\right>\left|\psi\right>)= v_x\left|x\right>\left|\psi\right>,$
where  $v_x$ is some complex number that could depends on $x$. In this case, the state $\left|x\right>\left|\psi\right>$ is called an eigenstate of the operator $c-U_f$,  and $v_x$ is called the eigenvalue of the eigenstate. Moreover, the state $\left|\psi\right>$ may also satisfy
$c-U_f(\left|y\right>\left|\psi\right>)= v_y\left|y\right>\left|\psi\right>,$
for some other state $\left|y\right>\in\mathcal{H}_B$ and eigenvalue $v_y$.

This situation is more interesting when the control register is in some superposition of states such as $\alpha\left|x\right>+\beta\left|y\right>\in\mathcal{H}_A$. Then
$\begin{array}{r l} c-U_f\big((\alpha\left|x\right>+\beta\left|y\right>)\left|\psi\right>\big) & =c-U_f(\alpha\left|x\right>\left|\psi\right>)+c-U_f(\beta\left|y\right>\left|\psi\right>) \\ &= v_x\alpha\left|x\right>\left|\psi\right>+v_y\beta\left|y\right>\left|\psi\right> \\ &=\big(v_x\alpha\left|x\right>+v_y\beta\left|y\right>\big)\left|\psi\right>, \end{array}$
and depending on the eigenvalues the state in the control register may contain a relative phase factor between the states $\left|x\right>$ and $\left|y\right>$. In this context, by associating the eigenvalue to the state in the control register, the action of the controlled$-U_f$ gate can effectively be thought of as changing the state in the control register instead of the target register. Then by performing a measurement on the states, the existence of this phase factor may contain relevant information about the function $f$ encoded in the black box.

This technique of preparing the input in an eigenstate of a controlled$-U$ gate, and then associating the eigenvalue to the control register is referred to as phase kick-back. A whole class of quantum algorithms exploits this technique in order to learn some property of a function $f$ encoded in a black-box with fewer queries than would be needed in the classical case.