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$
  • 1
    $\begingroup$ Possible duplicate of The Grover algorithm in real life $\endgroup$ – Norbert Schuch Mar 19 '19 at 8:14
  • 1
    $\begingroup$ I don't think it is a duplicate but the answers might be helpful for your understanding.... Concerning the question: The database is the quantum system itself, the one that you initially prepare in the starting state. You are looking for a certain eigenstate and the corresponding eigenvalue, i.e. your system will be in that state after you completed Grover's algorithm. Thus, your quantum system is your "database". $\endgroup$ – lmr Mar 19 '19 at 10:32
  • $\begingroup$ @lmr I'd certainly say my answer from there answers this question. Do you think I should re-post it? $\endgroup$ – Norbert Schuch Mar 19 '19 at 12:23
  • $\begingroup$ @NorbertSchuch I agree that your answer is highly valuable for the understanding of Grover's algorithm in general. But I would rephrase it for this question so that it becomes obvious where the actual "database" is found. $\endgroup$ – lmr Mar 19 '19 at 14:36
  • 1
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.)

| cite | improve this answer | |
$\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.