# Is the $|-\rangle$ state the only one that can do the trick for Grover's algorithm?

$$\newcommand{\qr}{|#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?

• The state $|-\rangle$ is not called a Bell state. – DaftWullie Feb 7 '19 at 6:46

## 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.

• 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? – R. Chopin Feb 7 '19 at 0:14
• could you add a reference in support of this statement (or even better, a proof)? – glS Feb 7 '19 at 10:44
• Hi. Please use MathJax to properly typeset the mathematical expressions. I've edited the post on your behalf this time. – Sanchayan Dutta Feb 7 '19 at 13:34

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)