3 ms·

I'm halfway through the first chapter of Neilsen and Chuang's book. I'm enjoying reading about the subject and am at the quantum parallelism part. Can you expl

I'm halfway through the first chapter of Neilsen and Chuang's book. I'm enjoying reading about the subject and am at the quantum parallelism part. Can you explain why Grover's algorithm has a runtime of root N? It seems like the runtime should be log2(n) because of exponential qubits or 1 because there must be a way for all the qubits to interfere. Also, What resources do you reccomend for self study? Are there quantum computing meetups in San Francisco that you can recommend?

ScottAaronson 8y ago
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.
- TrinaryWorksToo 8y ago
  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!
wzeng 8y ago
There is a Bay Area Quantum Computing meetup (I'm one of the organizers!) https://www.meetup.com/Bay-Area-Quantum-Computing-Meetup/ https://www.meetup.com/Bay-Area-Quantum-Computing-Meetup/ Next one will likely be at the end of July. Hope to see you there!
- TrinaryWorksToo 8y ago
  Looks like I went to the Bloomberg one. Was both really over my head and very fascinating.

ScottAaronson 8y ago

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.

TrinaryWorksToo 8y ago
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!

wzeng 8y ago

There is a Bay Area Quantum Computing meetup (I'm one of the organizers!) https://www.meetup.com/Bay-Area-Quantum-Computing-Meetup/ https://www.meetup.com/Bay-Area-Quantum-Computing-Meetup/ Next one will likely be at the end of July. Hope to see you there!

TrinaryWorksToo 8y ago
Looks like I went to the Bloomberg one. Was both really over my head and very fascinating.