Quantum Supremacy

By now you've probably heard the rumors of Google achieving quantum supremacy. I don't have inside information outside of Scott's blog post but it looks like the news should be embargoed until the release of a Science or Nature paper. These things usually happen on a Tuesday and you'd think they would avoid the news of the Nobel Prize announcements October 7-14.

Since for now the Google paper doesn't officially exist, we live in an era of Classical Dominance. Any problem that can be solved on a quantum computer today, can be solved just as fast or faster on a traditional computer. Quantum Supremacy, despite its lofty name, is just the negation of Classical Dominance, that there is some problem that a current quantum machine can solve that all our regular machines would require a considerably longer time to solve. This isn't a formal mathematical or scientific definition, so one can debate when or if we cross this threshold and I'm sure people will.

Quantum Supremacy might not even be a monotone concept. Future classical algorithms might solve the problem quickly, leading us back to Classical Dominance but leaving open the possibility of returning to Quantum Supremacy with another problem.

Quantum Supremacy is a long way from Quantum Usefulness, where quantum machines can solve problems we care about faster that traditional machines. Quantum computing will truly reach its potential when we can run general quantum algorithms like Shor's algorithm to factor products of large primes. We'll probably never see Quantum Dominance where classical transistors go the way of vacuum tubes.

Nevertheless, quantum supremacy is an important step and whether or not you think Google has gotten there, I'm sure it's an incredible achievement of science and engineering.