There's so much more to CS theory than big O notation and you're in for a treat if you check out any of the below - happy to share more if people are interested.

I'm currently on the Free Will chapter of Aaronson's Quantum Computing Since Democritus [0], where he treats this question directly in the context of computational complexity theory. Highly recommended to anyone interested in this stuff!

Aaronson is fabulous. In my opinion, possibly the best technical author around these days. If you haven't already, his new book[1] is absolutely worth checking out, especially if you're unfamiliar with quantum.

Ha, this immediately calls to mind Scott Aaronson's approach to teaching Quantum Mechanics in one of his lectures:

> 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.

> Today, in the quantum information age, the fact that all the physicists had to learn quantum this way seems increasingly humorous. 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. That's like Andrew Wiles asking 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 undeserved reputation for being 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. -- and also learned that they shouldn't even try to understand such things without years of painstaking work.

> The second way to teach quantum mechanics leaves a blow-by-blow account of its discovery to the historians, and instead starts directly from the conceptual core -- namely, a certain generalization of probability theory to allow minus signs. Once you know what the theory is actually about, 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.

Here's the full lecture.[0] The approach was interesting enough that I bought his full book[1], but unfortunately it was a little over my head.

1. https://www.amazon.com/Computational-Complexity-Approach-San...

2. https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

3. https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

4. https://www.amazon.com/Introduction-Theory-Computation-Micha...

* https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

This reference also looks solid and I'm looking forward to reading it in more depth.

[0] https://smile.amazon.com/Quantum-Computing-since-Democritus-...

---

[1] : http://www.amazon.com/Quantum-Computing-since-Democritus-Aar...

>

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.>

Today, in the quantum information age, the fact that all the physicists had to learn quantum this way seems increasingly humorous. 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. That's like Andrew Wiles asking 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 undeserved reputation for being 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. -- and also learned that they shouldn't even try to understand such things without years of painstaking work.>

The second way to teach quantum mechanics leaves a blow-by-blow account of its discovery to the historians, and instead starts directly from the conceptual core -- namely, a certain generalization of probability theory to allow minus signs. Once you know what the theory is actually about, 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.Here's the full lecture.[0] The approach was interesting enough that I bought his full book[1], but unfortunately it was a little over my head.

[0] http://www.scottaaronson.com/democritus/lec9.html [1] https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...