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

Question

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

Answer 1

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.

Answer 2

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)