Claims about quantum computing (including in optimization)
I don’t follow quantum computing, but do try to peek in every so often.
I’ve learned a lot from Gurobi’s Ed Klotz. He’s good at explaining complex topics, such as quantum computing and optimization.
For the big picture on quantum, I like Scott Aaronson. As far as I can tell, he seems to be one of the experts in the field. He runs a popular blog, I can sometimes understand him, and he hits the podcast circuit.
Here is a summary of a recent interview on The Superposition Guy’s Podcast:
The theory that quantum computing should work seems to have been proved out. This leaves a very hard engineering problem in building the machines. My layman’s take is that they’ve proved that as these computers scale. That is, they can correct the errors faster than errors are generated. It now seems that hard work has shifted to building the machines.
As far as I can tell, you need appropriate algorithms to take advantage of quantum computing. One such algorithm can crack the encryption that currently makes the internet secure. We know how to do post-quantum encryption. We should start fixing that now (or yesterday).
Of interest to me (and probably to the readers of this) was his discussion of algorithms for NP-hard problems. By this, he means classic optimization problems such as vehicle routing, airline scheduling, and finance. For these problems, he’s skeptical that quantum computing will help much. We don’t yet have algorithms that are systematically better than what classic computers can do.
He is also disappointed that some people in the industry hide the truth about the performance of quantum computing relative to classical computers for optimization problems. For example, I’ve seen cases where people solve a Traveling Salesman Problem (TSP) with a quantum algorithm and compare the result to brute-force enumeration on a classical computer.
Instead of optimization problems, he’s going to be watching for quantum computing to solve hard physics-chemistry types of problems.
Finally, his advice to students is to study Linear Algebra. It is good for quantum computing, AI, and I’ll add Industrial Engineering/Operations Research. I wasn’t expecting that tip in this interview but will use it with students I talk to.