$\newcommand{\qr}[1]{|#1\rangle}$Grover algorithm's input is a superposition, representing the haystack, and the Bell state $\qr{-}$. The $\qr{-}$ seems utterly important: when I replaced $\qr{-}$ by, say, $\qr{+}$, the oracle became the identity operator and so Grover's algorithm couldn't work with it. So it seems that we need $\qr{-}$ so that $$U_f\qr{i}\qr{-} = (-1)^{f(i)}\qr{i}\qr{-},$$ which is the phase kickback tricky. Is $\qr{-}$ the only state that can do the trick for Grover's algorithm?
2 Answers
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.
-
$\begingroup$ Interesting. So $|−\rangle$ is not the only state, but it's essentially the only state because only some rotations of it could work. Would you say it's $|−\rangle$ that allows the desired state to be marked by the oracle? With $|+\rangle$, we get no literally no way to mark the desired state. Also, do you agree that it's the phase kickback trick at play in Grover's algorithm? $\endgroup$ Feb 7, 2019 at 0:14
-
$\begingroup$ could you add a reference in support of this statement (or even better, a proof)? $\endgroup$– glS ♦Feb 7, 2019 at 10:44
-
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 $1/N$ if there are $N$ items in the database, while the $|-\rangle$ component returns the marked item with a probability close to 1. Hence the overall success probability of a single run is approximately $$ p=\frac{|\alpha|^2}{N}+|\beta|^2. $$ With, on average $1/p$ repetitions, we'll find the answer we're looking for. So long as $1/p<\sqrt{N}$, we still get a speed-up over the classical case. Hence, roughly, we want $|\beta|^2>1/\sqrt{N}$.
A similar analysis can be repeated whenever the phase kickback trick is used (with the caveat that you never do anything to that qubit that should be in $|-\rangle$ except do the operation that creates the phase kickback, but I believe that is always the case)