Quantum Computing
It is January 2023. I have finished reading Q is for Quantum, along with an online course Introduction to Quantum Computing for Everyone, part 1. I will not try to summarize what I learned. Together, these two resources provide an accessible introduction to a field that is, according to them, often misunderstood. Although they minimize the use of math, the underlying physics is, to say the least, technically challenging, still controversial among professionals in the field, and basically incomprehensible.
For close to 50 years, I have tried to reach a basic understanding of this field. It always seems to come down to a highly respected authority, such as a famous professor or a Nobel Prize winner, saying they don’t understand it either, no one does, so just learn what experiments have been done, what the results are, and how to treat it mathematically, even though it makes no sense. That hasn’t changed.
The book features an imagined dialog between Einstein and Winnie-the-Pooh, which I enjoyed, because I like that sort of thing.
The course spent considerable time explaining the Traveling Salesman problem, which I knew from computer science to be a classic example of an NP-complete problem. This class of problems is considered to be intractable for standard, Turing machine computers. I won’t explain the problem here either. It is simple to understand, but as it scales up to larger amounts of data, the need to do comparisons among all the many combinations of possible answers makes it impractical to resolve with brute force in the most general case, even with the fastest computers. The appeal of quantum computing is that it promises to make such problems tractable; that is, solvable in reasonable time and memory space. Computer science teaches that all NP-complete problems are in principle equivalent. So a computer that can solve the generalize Traveling Salesman problem can also solve the Knapsack problem and other famous problems that can only be solved by existing computers for fairly small data sets.
What I hoped to learn from the course and the book was the quantum computing algorithm for solving the Traveling Salesman problem. But the course never came back to it. Apparently not in Part 2, either, which does cover some quantum algorithms.
