MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 edited tags
1

# Grover's Quantum Search Algorithm

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.