- By any objective standard, the theory of computational complexity ranks as one of the greatest intellectual achievements of humankind - along with fire, the wheel, and computability theory. That it isn't taught in high schools is really just an accident of history. [s 44]
- There are two ways to teach quantum mechanics. The first way - which for most physicists today is still the only way - follows the historical order in which the ideas were discovered. So, you start with classical mechanics and electrodynamics, solving lots of grueling differential equations at every step. Then you learn about the "blackbody paradox" and various strange experimental results, and the great crisis these things posed for physics. Next you learn a complicated patchwork of ideas that physicists invented between 1900 and 1926 to try to make the crisis go away. Then, if you're lucky, after years of study you finally get around to the central conceptual point: that nature is described not by probabilities (which are always nonnegative), but by numbers called amplitudes that can be positive, negative, or even complex.
Look, obviously the physicists had their reasons for teaching quantum mechanics this way, and it works great for a certain kind of student. But the "historical" approach also has disadvantages, which in the quantum information age becomes increasingly apparent. For example, I've had experts in quantum field theory - people who've spent years calculating path integrals of mind-boggling complexity - ask me to explain the Bell inequality to them, or other simple conceptual things like Grover's algorithm. I felt as if Andrew Wiles had asked me to explain the Pythagorean Theorem.
As a direct result of this "QWERTY" approach to explaining quantum mechanics - which you can see reflected in almost every popular book and article, down to the present - the subject acquired an unnecessary reputation for being complicated and hard. Educated people memorized the slogans - "light is both a wave and a particle," "the cat is neither dead nor alive until you look," "you can ask about the position or the momentum, but not both," "one particle instantly learns the spin of the other through spooky action-at-a-distance," etc. But they also learned that they shouldn't even try to understand such things without years of painstaking work.
The second way to teach quantum mechanics eschews a blow-by-blow account of its discovery, and instead starts directly from the conceptual core - namely, a certain generalization of probability theory to allow minus signs (and more generally, complex numbers). Once you understand that core, you can then sprinkle in physics to taste, and calculate the spectrum of whatever atom you want. This second approach is the one I'll be following here. [s 109-110]
- From reading newspapers, magazines, and so on, one would think a quantum computer could "solve NP-complete problems in a heartbeat" by "trying every possible solution in parallell," and then instantly picking the correct one.
Well, arguably that's the central misconception about quantum computing among laypeople. [s 145]
- Over the course of my life, I must've met at least two dozen people who "knew" that factoring is NP-complete, and therefore that Shor's algorithm - since it lets us factor on a quantum computer - also lets us solve NP-complete problems on a quantum computer. Often these people were supremely confident of their "knowledge". [s 64-65]