This action will delete this post on this instance and on all federated instances, and it cannot be undone. Are you certain you want to delete this post?
#review 1 hashtag
Todd Sundsted posted Mar 7, 2021
I recently stumbled across Scott Aaronson's lecture notes for PHYS771 Quantum Computing Since Democritus. (I haven't yet read the book.)
Scott Aaronson is a computational complexity researcher/thinker first and foremost, and I love his particular style/peculiar style. En route to quantum computing, he talks a lot about computational complexity, reflects on free will, and manages to loop in time travel, as he does. But the notes (and presumably the book) are not a primer on quantum computing (which was what I was looking for).
The questions Scott’s trying to answer are, generally, what kind of problems can you solve with quantum computing, and, specifically, will we be able to solve NP complete problems in polynomial time with quantum computing. These are very important questions, because Shor’s algorithm (a quantum algorithm) can factor integer primes in polynomial time, which threatens to reduce the effectiveness of a lot of the cryptography on which we all depend. So there are real world consequences.
Factoring integer primes is in NP but it's not known/believed to be NP complete, but if a polynomial time algorithm is discovered for a known NP complete problem, like the traveling salesperson problem, an entire class of difficult problems becomes very much easier to solve, because a solution for one NP complete problem is a solution for any NP complete problem.
How much easier? For reasonably large problems it's the difference between solvable and solvable but not in the lifetime of the universe, because the only known algorithm amounts to trying every possible solution.