# Where's the Database in Grover's Algorithm

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}$$

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}$$.

• Possible duplicate of The Grover algorithm in real life – Norbert Schuch Mar 19 '19 at 8:14
• 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". – lmr Mar 19 '19 at 10:32
• @lmr I'd certainly say my answer from there answers this question. Do you think I should re-post it? – Norbert Schuch Mar 19 '19 at 12:23
• @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. – lmr Mar 19 '19 at 14:36
• – S.D. Mar 19 '19 at 16:54

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$$).