The reason why the running time of Grover’s algorithm involves sqrt(n) has to do with the Pythagorean theorem—or if you like, the fact that quantum mechanics is based on the 2-norm, in contrast to classical probability theory which is based on the 1-norm. Classically, each time you pick one item out of N to query, you can add ~1/N probability to the marked item—so the probability of having found the marked item after T queries goes like T/N. Quantumly, you can add ~1/sqrt(N) amplitude to the marked item with each query, so the amplitude on the marked item after T queries goes like ~T/sqrt(N), and hence the probability of observing the marked item when you measure goes like ~T^2/N.
A fundamental result from the 1990s, called the BBBV Theorem, shows that not even a quantum computer can solve the unordered search problem any faster than Grover’s algorithm solves it. I won’t prove the theorem in this comment :-), but the intuition is simply that quantum mechanics is a norm-preserving and linear theory. So you actually need to do something to gradually put more and more amplitude onto the marked item; you can’t just instantly and magically give an amplitude of 1 to whichever branch of your superposition happened to hit the marked item.
I’m not sure if there are QC meetups in SF (does anyone else?). But certainly nearby Berkeley is one of the centers of the world for QC—home to Umesh Vazirani’s group, the Simons Institute for Theory of Computing, and now also the startup Rigetti.
That makes some sense with the extra dimension providing more space to store information about all the information. I appreciate the detailed response with some jumping off points. Thank you!
A fundamental result from the 1990s, called the BBBV Theorem, shows that not even a quantum computer can solve the unordered search problem any faster than Grover’s algorithm solves it. I won’t prove the theorem in this comment :-), but the intuition is simply that quantum mechanics is a norm-preserving and linear theory. So you actually need to do something to gradually put more and more amplitude onto the marked item; you can’t just instantly and magically give an amplitude of 1 to whichever branch of your superposition happened to hit the marked item.
I’m not sure if there are QC meetups in SF (does anyone else?). But certainly nearby Berkeley is one of the centers of the world for QC—home to Umesh Vazirani’s group, the Simons Institute for Theory of Computing, and now also the startup Rigetti.