As Wikipedia says, in a quantum computer, you have a quantum register (a bunch of entangled qubits) that holds the result of your computation. The contents of

As Wikipedia says, in a quantum computer, you have a quantum register (a bunch of entangled qubits) that holds the result of your computation. The contents of this register can be visualized as a high-dimensional vector of length 1 -- think of this as a line with one endpoint at the origin and the other restricted to the radius-1 hypersphere around the origin. Each axis of the space that this sphere lives in corresponds to one classical value of the register -- in an 8-qubit register, one axis corresponds to 00000000, another corresponds to 00000001, etc. The real problem you solve with Grover's algorithm is this: you have a black box (usually called an "Oracle operator", but I think the term "Oracle" in this case is misleading) that negates the value of your register along exactly one axis (i.e., if the coordinate on the 00010111 axis is .2 - .1i, it becomes -.2+.1i). You want to figure out which of the 2^n axes in the n-qubit register your black box negates. Unfortunately, you don't have the luxury of picking the vector that has a coordinate of 1/sqrt(2^n) in each direction, and observing what the black box does to that after a single application, since when you observe your quantum register you always observe a classical state. In contrast, one solution that would work would be to solve the problem the classical-computing way: march through each of the 2^n axes until you find the one you're looking for. Grover's algorithm gives you a better way. What Grover's algorithm does is repeatedly apply an operation that nudges your register towards the desired state -- basically applying a small rotation. After some number of iterations, the vector representing your register should be pointing in almost the same direction as the vector representing the state you're searching for. Then you can measure the contents of the register and, with high probability, get the answer you were searching for. It turns out you only need O(sqrt(2^n)) queries (rotations), so it's a substantial improvement over the classical case. I've probably oversimplified a few things, but hopefully this makes things clearer than they were before.