Focus beyond quadratic speedups for error-corrected quantum advantage

One of the most important goals of the field of quantum computing is to eventually build a fault-tolerant quantum computer. But what valuable and classically challenging problems could we actually solve on such a device? Among the most compelling applications are quantum simulation Feynman (1982); Lloyd (1996) and prime factoring Shor (1994). Quantum algorithms for these tasks give exponential speedups over known classical alternatives but would have limited impact compared to significant improvements in our ability to address problems in broad areas of industrial relevance such as optimization and machine learning. However, while quantum algorithms exist for these applications, the most rigorous results have only been able to show a large speedup in contrived settings or a smaller speedup across a broad range of problems. For example, many quantum algorithms (often based on amplitude amplification Brassard et al. (2002)) give quadratic speedups for tasks such as search Grover (1996), optimization Grover (1996); Somma et al. (2008a); Campbell et al. (2019), Monte Carlo Brassard et al. (2002); Montanaro (2015); Rebentrost et al. (2018), various areas of machine learning Aïmeur et al. (2006); Wiebe et al. (2015) and more. However, attempts Sanders et al. (2020); Campbell et al. (2019) to assess the overheads of some such applications within fault-tolerance have come up with discouraging predictions for what would be required to achieve practical advantage against classical algorithms.

The central issue is that quantum error-correction and device operation time introduce significant constant factor slowdowns to the algorithm runtime (see Figure 1). These large overheads present many challenges for the practical realization of useful fault-tolerant devices. However, for applications that benefit from an exponential speedup relative to classical algorithms, the exponential scaling of the classical approach quickly catches up to the large constant factors of the quantum approach so that one can achieve a practical runtime advantage for even modest problem sizes. This is borne out through numerous studies on the cost of error-correcting applications with exponential scaling advantage in areas such as quantum chemistry Kivlichan et al. (2020); von Burg et al. (2020); Lee et al. (2020), quantum simulation of lattice models Lemieux et al. (2020a); Childs et al. (2018) and prime factoring Gidney and Ekerå (2019).

In this perspective we discuss when it would be practical for a modest fault-tolerant quantum computer to realize a quantum advantage with quantum algorithms giving only a small polynomial speedup over their classical competition. We will see that with only a low order (e.g., quadratic) speedup, exorbitantly long runtimes are sometimes required in order for the slightly worse scaling of the classical algorithm to catch up to the slightly better scaling (but worse constant factors) of the quantum algorithm. We will argue that the problem is especially pronounced when the best classical algorithms for a problem can also be easily parallelized.

Our analysis will emphasize current projections within the surface code Kitaev (2003) since it has the highest threshold error rate for a two-dimensional quantum computing architecture and is generally regarded as the most practical quantum error-correcting code Fowler et al. (2012). We will focus on a modest realization of the surface code that would involve enough resources to perform classically intractable calculations but only support a few state distillation factories. Our analysis differs from results analyzing the viability of error-correcting quadratic speedups for combinatorial optimization such as Campbell et al. (2019); Sanders et al. (2020), by addressing the prospects for achieving quantum advantage via polynomial speedup for a broad class of algorithms, rather than for specific problems. Note that Campbell et al. (2019) was the first study to detail poor prospects for error-correcting an algorithm achieving a quadratic speedup with a small fault-tolerant processor.

Here we will assume that there is some problem which can be solved by a classical computer that makes $M^{d}$ calls to a “classical primitive” circuit or by a quantum computer which makes $M$ calls to a “quantum primitive” circuit (which is often, but not always, related to the classical primitive circuit). This corresponds to an order $d$ polynomial quantum speedup in the number of queries to these subroutines. For $d=2$, this is especially evocative of a common class of quantum algorithms leveraging amplitude amplification. This generously assumes no prefactor overhead in a quantum implementation of an algorithm with respect to the number of calls required and along with other crude assumptions, allows us to bound the crossover time.

Our back-of-the-envelope analysis makes many assumptions which are overly optimistic towards the quantum computer and yet we still conclude that the prospects look poor for quadratic speedups with current error-correcting codes and architectures to outperform classical computers in time-to-solution. It seems that to realize a quantum advantage with reasonable fault-tolerant resources, one must either focus beyond quadratic speedups, dramatically improve techniques for error-correction, or do both. Our conclusion is already “folk wisdom” among some in the small community that studies quantum algorithms and error-correction with an eye towards practical realization; however, this reality is not widely appreciated in the broader community that studies algorithms and applications of quantum computers more generally and there is value in presenting a specific argument to this effect in written form. An encouraging finding is that the prospects for error-corrected quantum advantage look significantly better with quartic speedups. Of course, there might exist use cases involving quadratic speedups that defy the framework of this analysis. Either way, we hope this perspective will encourage the field to critically examine the prospects for quantum advantage with error-corrected quadratic speedups and either produce examples where it is feasible, or focus more effort on algorithms with larger speedups.

Many quantum algorithms are built on coherent access to primitives implemented with classical logic. For example, this classical logic might be required to compute the value of a classical cost function for optimization Sanders et al. (2020), to evaluate a function of a trajectory of some security that one is pricing with Monte Carlo Rebentrost et al. (2018), or to compute some classical criteria that flags a marked state for which one might be searching Grover (1996). We will define the runtime of the quantum and classical algorithms as

where ${\cal T}$ gives the total runtime of the algorithm, $M$ is the number of primitive calls required, $d$ is the order of the polynomial speedup the quantum computer achieves and $t$ is the time required to perform a call. Throughout this perspective the subscripts $Q$ and $C$ will denote “quantum” and “classical” implementations.

The condition for quantum advantage is

We see then that whenever a problem will require enough calls $M$ that a quantum advantage is possible,

where ${\cal T}^{\star}$ is the “breakeven time” which occurs when ${\cal T}_{Q}={\cal T}_{C}$, corresponding to onset of quantum advantage. As emphasized in Figure 1, we will see that the fundamental challenge in realizing this runtime advantage against classical computers (for small $d$) is that $t_{Q}\gg t_{C}$ in error-corrected contexts, making ${\cal T}^{\star}$ very large.

Rather than use a single CPU for the classical approach, one might instead parallelize the algorithm using $P$ classical CPUs. This will reduce the total classical runtime to

where $\alpha$ is the fraction of the algorithm which must be executed in serial and $S$ is the speedup factor due to parallelization consistent with the “Amdahl’s law” Amdahl (1967). Note that Amdahl’s law scaling is considered somewhat pessimistic as one can often adjust the size of problems to fully exploit the computing power that becomes available with more parallelism (e.g., see “Gustafson’s law” Gustafson (1988) for a more optimistic formula for $S$). But it also seems that in most situations where one might hope to find a quadratic speedup with a quantum computer (e.g. applications such as search, optimization, Monte Carlo, regression, etc.) the corresponding classical approach is embarrassingly parallel (suggesting that $\alpha$ is small enough that $S\approx P$ for reasonable values of $P$). Regardless of the form of $S$, classical parallelism leads to the following revised conditions for quantum advantage:

While parallel efficiency might be limited for some applications, any implementation of an error-correcting code will also require substantial classical co-processing in order to perform decoding, and this is likely to require thousands of classical cores. Although many quantum algorithms can also benefit from various forms of parallelism, we are considering an early fault tolerance setting where there is likely an insufficient number of logical qubits to exploit a space-time tradeoff to the same extent.

We will now explain the principle overheads believed to be required for the best candidate for quantum error-correction on a two-dimensional lattice: the surface code. Toffolis are the most commonly used gate for implementing classical logic on a quantum computer but cannot be implemented transversally within practical implementations of the surface code. Instead, one must implement these gates by first distilling resource states. In particular, to implement a Toffoli gate one requires a CCZ state ($\mathinner{|{\rm CCZ}\rangle}={\rm CCZ}\mathinner{|{+++}\rangle}$) and these states are consumed during the implementation of the gate. Distilling CCZ states requires a substantial amount of both time and hardware and thus, they are usually the bottleneck in realizing quantum algorithms within the surface code.

Here, we will focus on the state-of-the-art Toffoli factory constructions of Gidney and Fowler (2019a) which are based on applying the lattice surgery constructions of Fowler and Gidney (2018) to the fault-tolerant Toffoli protocols of Jones (2013); Eastin (2013). Using that approach one Toffoli gate requires $5.5\times d$ surface code cycles, where $d$ is the code distance. The time per round of the surface code, including decoding time is expected to be around $1\,\mu s$ in superconducting qubits. Our analysis will assume a code distance in the vicinity of $d=30$. This would be sufficient for an algorithm with billions of gates and physical gate error rates on the order of $10^{-3}$ (as our analysis will reveal, even more than a billion gates would likely be required to obtain quantum advantage with a modest polynomial speedup). With these assumptions, our model predicts a Toffoli gate time of

This rough approximation matches the more detailed resource estimate of Ref. Gidney and Fowler (2019a). We discuss these estimates in more detail in Appendix A.

Under the aforementioned assumptions which are specific to contemporary realizations of the surface code using superconducting qubits we could express the quantum primitive runtime as

where $G$ is the number of Toffoli gates required to implement the quantum primitive. Although we have focused on superconducting qubits, we can also contextualize the performance of ion traps — another leading architecture for quantum advantage. Ion qubits enjoy hour-long coherence times Wang et al. (2017), but are typically gated by the performance of their two-qubit gate Bruzewicz et al. (2019). Gate times within a single ion crystal can range from hundreds of microseconds to sub-microsecond speeds Mølmer and Sørensen (1999); García-Ripoll et al. (2003); Wong-Campos et al. (2017); Schäfer et al. (2018); Torrontegui et al. (2020), and can be efficiently parallelized Grzesiak et al. (2020); Landsman et al. (2019).

Multiple ion crystals can be connected to form a networked quantum computer, either through a charge-coupled device Kielpinski et al. (2002); Pino et al. (2020) or via photonic interfaces Monroe et al. (2014); Hucul et al. (2015). While a charge-coupled device may support thousands of qubits, millions of qubits will likely require photonic interconnects, although large shuttling-based traps have been proposed Lekitsch et al. (2017). For either architecture, a $\sim 10\,\text{kHz}$ cycle frequency has been identified as an ambitious but attainable goal Brown et al. (2016); Lekitsch et al. (2017); Nickerson et al. (2014). Consequently, we can roughly estimate that such a device will be limited by a clockspeed about $100\times$ slower than the $1\,\mu\text{s}$ decoding throughput limit, commensurate with typical high-fidelity two-qubit gate times Ballance et al. (2016); Gaebler et al. (2016) and corresponding to a $t_{G}\approx 17\,\text{ms}$. However, in trade, such a device may support the requisite connectivity for non-2D error-corrected codes and fault-tolerant gates. While the advantages of such approaches are speculative, we touch on some of these alternate proposals in Appendix B.

On a very large surface code quantum computer one could instead use multiple Toffoli factories (at a high cost in the number of physical qubits required) in order to reduce $t_{Q}$ by performing state distillation in parallel. However, the Toffoli gates are only about two orders of magnitude slower than the Clifford gates and when using multiple factories one needs to account for routing overhead. Thus, while $t_{Q}$ can be reduced at the cost of using many more qubits, only by a factor that is between about ten and one-hundred.

If $N$ is the number of qubits on which this problem is defined then a sensible lower bound would seem to be $G\geq N$ and thus, $t_{Q}\geq 170\,\mu{\rm s}\cdot N$. For example, in Grover’s algorithm Grover (1996) one must perform a reflection that requires ${\cal O}(N)$ Toffoli gates. In order to achieve a quantum advantage we would need to focus on problem sizes that are sufficiently large that enough calls can be made so that Eq. (2) is satisfied. We find it difficult to imagine satisfying this condition for problem sizes less than one-hundred qubits. Thus, an approximate “lower bound” (using $N=100$) would be

In addition to this lower bound, we will also consider a specific, realistic example to keep our estimates grounded. We will focus on the quantum accelerated simulated annealing by qubitized quantum walk algorithm studied in Somma et al. (2008b); Lemieux et al. (2020b), which appears to provide a quadratic speedup over classical simulated annealing (at least in terms of the best known bounds) in terms of the mixing time of the Markov chain under certain assumptions Boixo et al. (2009). This is among the most efficient algorithms compiled in Sanders et al. (2020) and for the Sherrington-Kirkpatrick model Kirkpatrick et al. (1983), the implementation complexity is $5N+{\cal O}(\log N)$ (neglecting some subdominant scalings that depend on precision), which is only worse than the scaling of our lower bound by a factor of five. For example, for an $N=512$ qubit instance, the work of Sanders et al. (2020) shows that only about $2.6\!\times\!10^{3}$ Toffoli gates are required to make an update. Thus, for that problem size (which we choose to facilitate a comparison to classical algorithms that we will discuss later) we have that

Classical computers are very fast; a typical 3 GHz CPU can perform several billion 64 bit operations (e.g., floating point multiplications) per second. We might crudely write that the classical primitive time is $t_{C}=330\,{\rm ps}\cdot L$ where $L$ is the number of classical clock cycles required to implement the classical primitive. For our first example comparison of quantum and classical primitives we will assume that any classical logic operation that would require one Toffoli in the quantum primitive can be executed during one classical clock cycle in the classical primitive. This seems generous to the quantum computer since many operations that would take a single clock cycle on a classical computer would actually require thousands of Toffolis. (Note that we are not assuming any scaling advantage for the quantum computer in the primitive implementations.) One might worry about memory-bound classical primitives (since calls to main memory can take hundreds of clock cycles) but since problems defined on more than thousands of logical bits would be infeasible to process on a small fault-tolerant quantum computer we expect that the memory required for the corresponding classical primitives can be held in cache.

Thus, a corresponding bound on the time to realize a classical primitive for a problem where a quantum computer could realize a quantum primitive with anywhere near the lower bound time given in the prior section ($t_{Q}\geq 170\,\mu{\rm s}\cdot N$) is $t_{C}\leq 330\,{\rm ps}\cdot N$, and for $N=100$,

Even though the equivalence we make between Toffolis and classical compute cycles is seemingly generous to the quantum computer, the assumption of such a cheap primitive on the quantum side (only 100 Toffolis) results in what appears to be a fairly cheap primitive on the classical side. However, because Eq. (5) scales worse with $t_{Q}$ than with $t_{C}$, this assumption is ultimately optimistic towards the overall crossover time.

Consistent with the prior section, we will also discuss the classical primitive time required to apply simulated annealing to an instance of the Sherrington-Kirkpatrick model. Using the techniques developed in Isakov et al. (2015), a performant implementation of classical simulated annealing code for an $N=512$ instance of the Sherrington-Kirkpatrick model can perform a simulated annealing step in roughly 7 CPU-nanoseconds Sanders et al. (2020) (this accounts for the fact that most updates for the Sherrington-Kirkpatrick model are rejected); thus in that case,

But given the high costs of quantum computing it is unclear that we should compare to a single classical core.

Here we discuss the ramifications that the primitive runtimes discussed in the prior two sections have for the minimum time to achieve advantage according to Eq. (3) in the case of a quadratic quantum speedup. First, we will compare the example of a quantum primitive requiring only $N=100$ Toffolis and $t_{Q}=17\,{\rm ms}$. We argued that any such primitive could likely be computed in $t_{C}=33\,{\rm ns}$ on a single core. For this example, ${\cal T}^{\star}=t_{Q}^{2}/t_{C}=2.4\,\,{\rm hours}$. One might object to this minimal example on the grounds that it seems unlikely any interesting primitive would require only 100 Toffolis. While this is true, we point out that because quantum runtime is quadratic in the quantum primitive time and only inversely proportional to the classical primitive time, the overall crossover time can only get worse by assuming that more than 100 Toffolis would be required.

Next, we will compare to the example of quantum accelerated simulated annealing. We focus on this example because the steps of the quantum algorithm have been concretely compiled, appear quite efficient, and have a clear classical analogue. Here, for an $N=512$ qubit instance we have that $t_{Q}^{2}/t_{C}=320\,{\rm days}$, reproducing the finding in Sanders et al. (2020). We note that quantum advantage in this case would occur when $M>t_{Q}/t_{C}=6.3\times 10^{7}$. This means that $4.0\times 10^{15}$ calls would need to be required for the classical algorithm. However, most $N=512$ Sherrington-Kirkpatrick model instances would require many fewer calls to solve with classical simulated annealing and so one would need to focus on an even bigger system for which the numbers will look yet worse for the quantum computer. Notice that our simulated annealing example gave a quantum runtime that is much longer than the resources required for the quantum primitive with $N=100$ Toffolis. This is because the notion that it would take a classical computer an entire clock cycle to do what a quantum computer could accomplish with a single Toffoli is very generous to the quantum computer.

At first glance, the quantum runtime of 2.4 hours to achieve advantage for the primitive with just 100 Toffolis seems encouraging. Unfortunately, this was just for a single classical core. Even most laptops have on the order of ten cores these days and again, most of the problems where quantum computers display a quadratic advantage are classically embarrassingly parallel problems. Furthermore, error-corrected quantum computers are likely to use thousands of classical CPUs just for decoding. When using $P$ different classical CPUs in parallel then the breakeven time is given by Eq. (5). Using that equation, if we take $P=3,\!000$ CPUs for the classical task (rather than using them for error-correction), and if the classical algorithm is sufficiently parallelizable ($\alpha^{-1}\ll P$ so $S\approx P$), we see that the breakeven time even in this still quantum-generous example becomes one year. As we discuss in the next section there are also ways of parallelizing the quantum computations; e.g., by using multiple quantum computers or distillation factories.

We report values of both $M$ and ${\cal T}^{\star}$ assuming quantum speedups by different polynomial degrees under different amounts of classical parallelism in Table 1. While the viability of quantum advantage with cubic speedups is still a bit ambiguous, the prospects of achieving quantum advantage given a quartic speedup are promising. Even the simulated annealing example run with a classical adversary with $S=10^{6}$ parallelism would give quantum advantage after five hours of runtime if we assume a quartic speedup (while we do not expect a quartic speedup in that case, the comparison is still instructive).

It is rather surprising just how much of a difference there is for this example between assuming a quadratic speedup (requiring 880 millennia of runtime for advantage) and a quartic speedup (requiring just 4.9 hours of runtime for advantage). There are not as many examples of quartic speedups in quantum computing but there are a few, such as the tensor principle component analysis algorithm of Hastings Hastings (2020). Another example is the quartic query complexity reductions of Ambainis et al. Ambainis et al. (2015) and Aaronson et al. Aaronson et al. (2020). We also expect that certain applications of quantum algorithms for linear systems Harrow et al. (2009) (such as for solving linear differential equations in high dimension Berry (2014)) might lead to modest polynomial speedups higher than quadratic. It is also possible that some heuristic quantum algorithms for optimization might give larger than quadratic improvements for some class of problems, although this is still speculative.

Another question we might ask is, what happens if we were somehow able to implement Toffoli gates much faster in the surface code? For example, we might achieve this by fanning out and using more physical qubits per factory, more Toffoli factories, by inventing significantly more efficient protocols for Toffoli state distillation, or even by switching to a different technology with an intrinsically faster cycle time. We will perform this analysis for the case of quadratic speedups; there, the quantum runtime is reduced to ${\cal T}_{Q}=M\,t_{Q}/R$ where $R\geq 1$ is a speedup factor corresponding to performing Toffoli distillation in time $170\,\mu{\rm s}/R$. In analogy to Eq. (5) this leads to the equations for a quadratic quantum speedup

In Table 2 we compute Eq. (12) for our example problems with $R=10$, $R=10^{2}$ and $R=10^{3}$, assuming a classical adversary capable of achieving an $S=10^{3}$ parallelism. We restrict ourselves to $S=10^{3}$ due to the general difficulty in achieving high parallel efficiency described by Amdahl’s law. However, note that for simulated annealing we can achieve $S=10^{6}$ in practice (and so these numbers are overly optimistic for that case).

Unfortunately, even if Toffoli distillation rates improve by an order of magnitude it would not be enough to make quantum advantage with a quadratic speedup viable. If Toffoli distillation rates improve by two orders magnitude (making them essentially as cheap as Clifford gates) then it would still be challenging to obtain quantum advantage with a quadratic speedup (it would take more than a month for the simulated annealing example despite limiting the classical parallelism to $S=10^{3}$) but we cannot categorically rule it out for all algorithms. At three orders of magnitude speedup the story would be materially different but this would likely require a significant breakthrough. Even if classical processing and signal propagation were instantaneous, and we could adapt measurements to take advantage feedforward single-qubit gates only being applied half the time, a single layer of non-Clifford gates would still take a hard limit of the measurement time plus half the single qubit gate time.

We have investigated simple conditions that must be satisfied to realize a quantum advantage through polynomial speedups on a small fault-tolerant quantum computer. Our ultimate finding is that the prospects are generally poor for a quadratic speedup, consistent with folk knowledge in the error-correction community and recent work such as Sanders et al. (2020); Campbell et al. (2019). The comparison to parallel classical resources is particularly damning for quantum computing and unfortunately, many quadratic quantum speedups (especially those leveraging amplitude amplification) apply to problems that are highly parallelizeable. The strongest conclusions in this work assume that one can achieve classical parallelism speedups on the order of $10^{3}$ or more. But if one can produce a quadratic speedup for a problem where that is not the case, the prospects of quantum advantage would be improved.

These findings do not apply to all polynomial speedups. We found that while one would need to very significantly improve the rate of an error-corrected processor to help the case of quadratic speedups, having a quartic speedup rather than a quadratic speedup is often sufficient to restore the viability of achieving quantum advantage on a modest processor. Thus, we believe that these results suggest that the field should focus beyond quadratic speedups to find viable applications that might produce a quantum advantage on the first several generations of fault-tolerant quantum computers.

We expect this conclusion will persist under a variety of different cost models (e.g., were we to focus on the energy consumption of a computation rather than the runtime). However, we also expect that the community will make progress on some of the challenges described here, or perhaps identify circumstances under which the assumptions of this analysis do not apply. Either way, we hope that these arguments will foster further discussion about how we might develop broadly applicable algorithms that can achieve quantum advantage on small error-corrected quantum computers.

The authors thank Dave Bacon, Dominic Berry, Ken Brown, Eddie Farhi, Austin Fowler, Bill Huggins, Sergei Isakov, Evan Jeffrey, Cody Jones, John Platt, Rolando Somma, Nathan Wiebe and Will Zeng for helpful discussions and feedback on earlier drafts.