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}$. 
 A: 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.)
