4
$\begingroup$

$\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?

$\endgroup$
1
  • 1
    $\begingroup$ The state $|-\rangle$ is not called a Bell state. $\endgroup$
    – DaftWullie
    Feb 7, 2019 at 6:46

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\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$
    – R. Chopin
    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
  • $\begingroup$ Hi. Please use MathJax to properly typeset the mathematical expressions. I've edited the post on your behalf this time. $\endgroup$ Feb 7, 2019 at 13:34
3
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.