9
The phase kickback trick appears in this paper:
Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca. Quantum Algorithms Revisited. Proceedings of the Royal Society of London A, 454(1969): 339-354, 1998.
The authors credit Alain Tapp for independently discovering the same improvement to Deutsch's algorithm that results from using this trick. (...
7
A first remark
This same phenomenon of 'control' qubits changing states in some circumstances also occurs with controlled-NOT gates; in fact, this is the entire basis of eigenvalue estimation. So not only is it possible, it is an important fact about quantum computation that it is possible. It even has a name: a "phase kick", in which the control qubits (or ...
5
Imagine you have an eigenvector $|u\rangle$ of $U$. If you have a state such as $|1\rangle|u\rangle$ and you apply controlled-$U$ to it, you get out $e^{i\phi}|1\rangle|u\rangle$. The phase isn't attached to a specific register, it's just an overall multiplicative factor.
Now let's use a superposition on the first register:
$$
(|0\rangle+|1\rangle)|u\rangle\...
3
Remember that the states $|+\rangle$ and $|-\rangle$ form a basis. That means that any state $|\psi\rangle$ that you use can be written as
$$
|\psi\rangle=\alpha|+\rangle+\beta|-\rangle.
$$
By linearity, we can basically treat what these two components do separately. The $|+\rangle$ component is basically useless and gives the correct output with probability ...
3
It would still work if you rotated the $|−\rangle$ state, you refer to, by an angle with cosine less than $\frac{1}{L}$ where $L$ is the square root of the size of the search space (which is a power of 2). So it works with a different state which is a small rotation of the $|-\rangle$ state.
2
As to "who discovered/invented the quantum phase estimation algorithm," in his 2011 lecture at Keio University describing the linear equations algorithm, at about the 18 minute mark Lloyd claims that it was inherent in the works of Von Neumann.
That reminds me of the argument that "Gauss discovered the Fast Fourier Transform 160 years before Cooley and ...
1
So, are you asking whether it's possible (in the qubit case) to perform an arbitrary map of the form
$$
ae^{i\theta}|0\rangle+be^{i\phi}|1\rangle\rightarrow \frac{1}{\sqrt{2}}(e^{i\theta}|0\rangle+e^{i\phi}|1\rangle),
$$
if $a$ and $b$ are unknown real numbers satisfying $a^2+b^2=1$? If this is the case, this is impossible.
Consider a simple case where ...
1
You are given a quantum circuit for $U$ compiled into the H/CNOT/T gateset. Derive a controlled version of $U$ by adding a control qubit $q$, replacing every H with a controlled H, every CNOT with a CCNOT, and every T with a controlled T. In all cases the new control goes on the $q$.
Recompile the modified gates down into the H/CNOT/T gate set. Prepend and ...
1
If we express the action of $O_x$ on the basis $\mid i, \pm \rangle$ instead of $\mid i , b \rangle$
\begin{eqnarray*}
O_x \mid i , + \rangle = \mid i , + \rangle\\
O_x \mid i , - \rangle = (-1)^{x_i} \mid i , - \rangle\\
\end{eqnarray*}
Because we say ancillas must be started and ended with $0$,
\begin{eqnarray*}
O_x'' &=& (1 \otimes S_x H) O_x (...
Only top voted, non community-wiki answers of a minimum length are eligible
