Boaz’s inferior classical inferiority FAQ

(For better info, see Scott’s Supreme Quantum Superiority FAQ and also his latest post on the Google paper; also this is not really an FAQ but was inspired by a question about the Google paper from a former CS 121 student)

“Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.“

Paul Erdős (as quoted by Graham and Spencer, 1990, hat tip: Lamaze Tishallishmi)

In a Nature paper published this week, a group of researchers from John Martinis’s lab at Google announced arguably the first demonstration of “quantum supremacy” – a computational task carried out by a 53 qubit quantum computer that would require a prohibitive amount of time to simulate classically.

Google’s calculations of the “classical computation time” might have been overly pessimistic (from the classical point of view), and there has been work from IBM as well as some work of Johnnie Gray suggesting that there are significant savings to be made. Indeed, given the lessons that we learned from private key cryptography, where techniques such as linear and differential cryptanalysis were used to “shave factors from exponents”, we know that even if a problem requires exponential time in general, this does not mean that by being very clever we can’t make significant savings over the naive brute force algorithm. This holds doubly so in this case, where, unlike the designers of block ciphers, the Google researchers were severely constrained by factors of geometry and the kind of gates they can reliably implement.

I would not be terribly surprised if we will see more savings and even an actual classical simulation of the same sampling task that Google achieved. In fact, I very much hope this happens, since it will allow us to independently verify the reliability of Google’s chip and whether it actually did in fact sample from the distribution it is supposed to have sampled from (or at least rule out some “null hypothesis”). But this would not change the main point that the resources for classical simulation, as far as we know, scale exponentially with the number of qubits and their quality. While we could perhaps with great effort simulate a 53 qubit depth 20 circuit classically, once we reach something like 100 qubits and depth then all current approaches will be hopelessly behind.

In the language of my essay on quantum skepticism, I think this latest result, and the rest of the significant experimental progress that has been going on, all but rules out the possibility of “Skepticland” where there would be some fundamental physical reason why it is not possible to build quantum computers that offer exponential advantage in the amount of resources to achieve certain tasks over classical computers.

While the worlds of “Popscitopia” (quantum computers can do everything) and “Classicatopia” (there is an efficient classical algorithm to simulate BQP) remain mathematical possiblities (just as P=NP is), most likely we live in “Superiorita” where quantum computers do offer exponential advantage for some computational problems.

Some people question whether these kind of “special purpose” devices that might be very expensive to build are worth the investment. First of all (and most importantly for me), as I argued in my essay, exploring the limits of physically realizable computation is a grand scientific goal in its own right worthy of investment regardless of applications. Second, technology is now a 3.8 trillion dollar per year industry, and quantum computers are in a very real sense the first qualitatively different computing devices since the days of Babbage and Turing. Spending a fraction of a percent of the industry’s worth to the economy on exploring the potential for quantum computing seems like a good investment, even if there will be no practical application in the next decade or two. (By the same token, spending a fraction of a percent on exploring algorithm design and the limitations of classical algorithms is a very good investment as well.)