Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage

In this perspective we discuss conditions under which it would be possible for a modest fault-tolerant quantum computer to realize a runtime advantage by executing a quantum algorithm with only a small polynomial speedup over the best classical alternative. The challenge is that the computation must finish within a reasonable amount of time while being difficult enough that the small quantum scaling advantage would compensate for the large constant factor overheads associated with error correction. We compute several examples of such runtimes using state-of-the-art surface code constructions under a variety of assumptions. We conclude that quadratic speedups will not enable quantum advantage on early generations of such fault-tolerant devices unless there is a significant improvement in how we realize quantum error correction. While this conclusion persists even if we were to increase the rate of logical gates in the surface code by more than an order of magnitude, we also repeat this analysis for speedups by other polynomial degrees and find that quartic speedups look significantly more practical.

Popular Summary

In this perspective we challenge the notion that one can achieve quantum advantage by using an error-corrected quantum computer for a quantum algorithm that realizes only a quadratic speedup. The essential reason is because it would require the solving of problems of impractically large size for such a modest scaling advantage to overcome the extremely large constant factor slowdown associated with quantum error correction. We are able to construct a very general, albeit informal, argument to this effect by comparing best-case bounds on the resources required to implement a quantum primitive for some useful algorithm within the surface code with worst-case bounds on the resources required to implement a corresponding classical primitive that we assume would need to be called quadratically more times than the quantum primitive. Even though our analysis is very optimistic toward the quantum computer, we find that the prospects for quantum advantage in this context are very discouraging, especially if one is able to leverage any amount of parallelism in the classical algorithm. Our findings are significant because quantum algorithms giving a quadratic advantage are perhaps the most broadly applicable class of quantum algorithms, applying to everything from search, to optimization, to Monte Carlo methods, to machine learning. Furthermore, such algorithms are frequently embarrassingly parallel to solve classically. However, we also perform our analysis for higher-order polynomial speedups and find that even quartic speedups have good prospects for overcoming the large constant factors of error correction and for achieving quantum advantage.

Figure 1

The primary obstacle in realizing a runtime advantage for low-degree quantum speedups is the enormous slowdown when one is performing basic logic operations within quantum error correction. (a) A surface code Toffoli factory for distilling Toffoli gates (which act as the nand gate when the target bit is on) requires a space-time volume greater than 10 qubit seconds under reasonable assumptions on the capabilities of an error-corrected superconducting qubit platform [13]. (b) A nand circuit realized in CMOS can be executed with just a few transistors in well under a nanosecond. Thus, there is roughly a difference of 10 orders of magnitude between the space-time volume required for comparable operations on an error-corrected quantum computer and a classical computer.