Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
When people talk about complexity of an algorithm, say of multiplying two matrices, it is the really basic operations they count; multiplication of the entries and so on, and this depends on the size of your matrices. Otherwise people could define a 'step' to be 'raise this N x N matrix to the 100Nth power', or something similarly outrageous. The computer time taken to implement an algorithm depends on the number of elementary arithmetic operations, rather than high-level formulas. –  David Roberts Nov 2 '10 at 5:24
    
See en.wikipedia.org/wiki/Time_complexity for a discussion –  David Roberts Nov 2 '10 at 5:34
    
David Roberts: Thanks for this, but it leaves me equally confused. Assuming I'm going to implement this algorithm many times, I can compute the matrix U^100, or U^1000, or whatever I need, and amortize the cost of that over those many times. In other words, even if I need to use U^1000, that doesn't mean I have to compute it --- I should just be able to look it up someplace, since the very same matrix U^1000 would come up in every application of Grover's algorithm. It seems then, that the cost of all those multiplications shouldn't count against me. –  Steven Landsburg Nov 2 '10 at 14:19
    
But for different N, it takes different times to compute $U^Q|s\rangle$, and it is not the cost to you, but the cost to compute it from scratch. I could look up the first billion digits of pi, and claim that the only cost to me is to recall them to my computer screen, but in actual fact it took some time for some computer to calculate them, according to an algorithm. Which algorithm that is determines the cost in time/operations. Some formulas for pi converge slowly, some fast... Recalling the first billion digits of pi to my screen thousands of times doesn't make it quicker in the first place –  David Roberts Nov 3 '10 at 3:09
    
You might be interested in this question on cstheory for a more thorough discussion which decomposes $U$ into gates of finite width. –  Artem Kaznatcheev Feb 17 at 7:27
show 1 more comment

3 Answers 3

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Artem: But as I said in response to David --- the matrix U does not differ from one application of Grover's algorithm to another, so it seems like someone should be able to compute the various matrices U^Q, for many values of Q, once for all, and simply look them up rather than re-computing them each time. Given that, why are these not among the universal set of gates that I'm allowed to count as single steps? –  Steven Landsburg Nov 2 '10 at 14:21
1  
The U depends on the oracle... i.e. it depends on which item(s) are marked. Thus it does differ over various instances of Grover's algorithm.... –  Artem Kaznatcheev Nov 2 '10 at 18:07
    
More specifically, U depends on $|S\rangle$ (and $N$, but that's a bit different) which is not always in the same relation to $|E\rangle$ in different concrete instances of the problem. Also, complexity is roughly an asymptotic measure, taken at worst case. Clearly if $|S\rangle = |E\rangle$ and $N=2$ then $U$ is a lot simpler than if $N=100$ and $|S\rangle$ is the result of some measurement on a real system. You can't count as a single step a matrix that could be one of an uncountable number of alternatives, because you can't store them all in a hash table and look up the appropriate one. –  David Roberts Nov 3 '10 at 3:15
    
Even if you restricted yourself somewhat to a finite number of $U$, then there would be the computational cost of looking up your $U^Q$ in a table, but this is a bit silly. Algorithmic complexity is just not measured like this. –  David Roberts Nov 3 '10 at 3:16
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.