Grover's Quantum Search Algorithm - MathOverflow

Grover's Quantum Search Algorithm

2010-11-02T05:05:57Z

I am confused about an extremely basic point concerning Grover's quantum search algorithm; my confusion suggests to me that maybe I've missed the entire point.

My understanding of the algorithm is this: I've got an observable with N eigenstates, and I am looking for an object that is in a particular eigenstate (call it |E>). I prepare (or am given) an object in state |S>, |S> being the average of the N eigenstates.

I consider the operator $U = -(1 - 2 |S> <S|) (1-2 |E> <E|)$ . I apply this operator Q times, where Q is a specific integer depending on N, and asympotically equal to a constant times sqrt(N). This converts the state |S> into a state very close to |E>. I understand all this, including how to find Q and the proof that it works.

What I don't understand is this: Why is this algorithm described as requiring roughly sqrt(N) steps? Why can't I equally well describe it as requiring exactly one step, where the step is multiplication by U^Q ? What's special about U that makes its application count as "one step"?

For that matter, instead of using the operator U^Q, I could choose an operator V that takes |S> to |E>, as opposed to U^Q, which only takes |S> to some approximation to |E>. Why isn't this a "one-step" algorithm that gets an even better result than Grover's does?

Sorry for the naivete of this question. I hope for an answer that will make me embarrassed to have asked.

Answer by Artem Kaznatcheev for Grover's Quantum Search Algorithm

2010-11-02T05:36:30Z

When talking about the complexity of an algorithm (classical or quantum) you usually talk about complexity with regards to a specific model of computation. In the case of the circuit model of quantum computing a specific model corresponds to a universal finite set of gates (4.5 of Nielsen and Chuang has more info). Alternatively, in query models of computation, the complexity corresponds to the number of calls made to the special 'query' operator or oracle. In this case, the rotation towards $|E\rangle$ is implicit in the call to the oracle that specifies the input. Classically, you would need to make $N$ calls to such an oracle, but in the case of a quantum computer you only need on the order of $\sqrt{N}$. Thus, Grover's search provides a great example of a quantum speed-up... or more technically of the power of quantum queries over classical queries.

Answer by Greg Kuperberg for Grover's Quantum Search Algorithm

2010-11-02T07:37:35Z

David and Artem give a good summary of the "rules" for time complexity in the oracle model. I can say a little bit about the motivation for this model.

Grover's search algorithm is sometimes described as a "database" search, but this is misleading. It is really meant for an unstructured computational search. I.e., it is for solving an equation $f(x) = y$ for $x$, when $y$ and $f$ are both given and $f$ is so complicated that you can't think of anything better than to guess $x$ arbitrarily. On the other hand, we suppose that evaluating $f$ is reasonably fast. An example application could be searching for a point on a complicated algebraic variety over a finite field, or searching for a password that you already have in encrypted form. Or more generally, searching for a solution to a combinatorial problem that is not only NP-complete, but devoid of any known shortcuts to exhaustive search. But the problem has to be in NP, meaning again, the ability to evaluate $f$ quickly.

In this case the "oracle" means the function $f$, which is put into a black box because you don't have any particular understanding of it anyway. (On the other hand, in any relevant quantum algorithm, this conceptual "black box" has to be implemented with quantum gates inside the computer; it cannot be a physically separate black box.) The total time cost is now in two parts. The query cost is the number of times you have to evaluate $f$; the additional time cost is the number of other gate operations outside of evaluating $f$. In Grover's algorithm, the query cost dominates if you realistically assume that $f$ takes at least linear time to evaluate, because one stage of the rest of the algorithm only uses a linear number of gates with a low constant factor. On the other hand, since you don't have a precise conversion from queries to time, you can count queries and report that as the total work.

Answer by Sebastian Meznaric for Grover's Quantum Search Algorithm

2011-06-13T16:42:55Z

The complexity here refers to roughly how many times you need to call the oracle. If you put the operations together like you suggest you would get a single operator that would contain roughly $\sqrt{N}$ oracle calls.