3
$\begingroup$

I am a little confused by parts of Quantum Computation and Quantum Information by Nielsen and Chuang on Grover's algorithm:

Grover's algorithm searches a number of quantum states for a "marked element" $|x_0 \rangle $. The algorithm uses the following unitary operators, acting on an initial state $|0 \rangle ^{\otimes n}$:

$$(-H^{\otimes n}U_0H^{\otimes n}U_f)^TH^{\otimes n}|0 \rangle ^{\otimes n}$$

where it can be shown, that $U_f=I_{|x_0 \rangle}$ corresponds to an inversion about the vector $|x_0 \rangle$ and $H^{\otimes n}U_0H^{\otimes n}= I_{|+ \rangle}$.

Geometrically, the algorithms can thus be understood as a series of inversions/reflections about vectors in the plane spanned by the vectors $|+ \rangle$ that result from the first operation of the quantum circuit $$H^{\otimes n}|0 \rangle ^{\otimes n}= |+ \rangle ^{\otimes n}$$

enter image description here

Geometrical representation of a Grover iteration. The algorithm starts in state $|\xi \rangle$, which coincides with state $H^{\otimes n}|0 \rangle^{\otimes n}=|+ \rangle$. The state is rotated by the unitary operations $U_f=-R_{|x_0 \rangle}=I_{|x_0 \rangle}$ and $H^{\otimes n}U_0H^{\otimes n}= -R_{|+ \rangle} = I_{|+ \rangle}$. Every iteration moves the state closer to the solution $|x_0 \rangle$ by an angle of $2 \gamma$.

But where in the algorithm does the "database" come in that we actually want to search? After all, the computer is initially prepared in $|0\rangle ^{\otimes n}$.

$\endgroup$
4
$\begingroup$

This seems to be a common misunderstanding about Grover's algorithm. It is not about querying a magically encoded database. Rather, you have an efficiently computable function $f(x)\in\{0,1\}$ and you want to find some $x_0$ for which $f(x_0)=1$. Since you know how to realize $f(x)$ (i.e., you have a circuit), you can run $f$ on a quantum computer and use Grover to find such an $x_0$. This function can be seen as returning entries of a "database", which is encoded in a specific function, though I don't particularly like this picture.

The relevance is in the fact that a large number of interesting problems (namely, the class NP) are such that solutions might be hard to find, but they are easy to verify. Thus, Grover gives a square-root speed-up on any brute-force method to solve such a problem (i.e., any method which does not make use of any special structural property of $f$).


(Note: This is a slightly edited version of my answer https://physics.stackexchange.com/a/358166/4888, as it was argued in the comments that the corresponding question is not a duplicate.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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