PaperlayerView exact revision on arXiv

Source-linked AI summary

Focus beyond quadratic speedups for error-corrected quantum advantage

Ryan Babbush, Jarrod McClean, Michael Newman, Craig Gidney, Sergio Boixo, Hartmut Neven

arXiv:2011.04149v2quant-ph

TL;DR

The paper asks when modest fault-tolerant quantum computers could obtain practical runtime advantages from small polynomial speedups despite large error-correction overheads. It estimates runtimes using surface-code constructions and finds poor prospects for quadratic speedups on early devices, while quartic speedups often restore viability. The conclusion is conditioned by assumptions about error correction, classical parallelism, and the runtime cost model.

  • Problem

    Small polynomial quantum speedups must compensate for large constant-factor slowdowns from fault-tolerant error correction, especially against parallelizable classical algorithms.

  • Method

    The paper analyzes primitive-call runtimes under polynomial speedups, surface-code resource estimates, and classical parallelism assumptions.

  • Results

    Quadratic speedups generally have poor prospects on current fault-tolerant architectures, whereas quartic speedups are often sufficient to restore viability on modest processors.

  • Takeaways & Limitations

    The findings suggest focusing beyond quadratic speedups, improving quantum error correction, or pursuing both for early fault-tolerant quantum advantage.

  • Takeaways & Limitations

    The conclusions depend on assumptions that favor the quantum computer and may not apply to all quadratic-speedup use cases or cost models.

Abstract

from arXiv · show

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 would 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.

Introduction

The perspective examines whether modest fault-tolerant quantum computers can achieve practical advantage from small polynomial speedups despite large error-correction overheads. It argues that quadratic speedups face especially severe runtime challenges, motivating attention to larger speedups and improved error correction.

  • Motivation: Fault-tolerant quantum computing could have broad industrial impact beyond exponential-speedup applications, but rigorous results for optimization and machine learning remain limited.The perspective contrasts compelling exponential-speedup applications with the broader industrial relevance of problems where only smaller speedups are established.
  • Motivation: Large constant-factor slowdowns from quantum error correction can be overcome by exponential classical scaling at modest problem sizes, but not necessarily by small polynomial speedups.This runtime comparison is the central distinction between exponential and low-degree polynomial quantum advantages.
  • Motivation: Classical parallelization makes quadratic quantum advantage especially difficult when the best classical algorithms are easily parallelized.The perspective identifies embarrassingly parallel classical alternatives as a particularly challenging comparison for low-degree quantum speedups.
  • Approach: The analysis focuses on a modest surface-code realization with enough resources for classically intractable calculations but only a few state-distillation factories.It uses current surface-code projections and deliberately modest fault-tolerant resources as the main setting.
  • Approach: The perspective calls for critically examining quadratic-speedup prospects and, where they are infeasible, directing effort toward algorithms with larger speedups.This is presented as the paper’s motivating contribution and research direction.

Relationship between primitive times and runtime

The paper models runtime through primitive-call counts and primitive execution times, then derives quantum-advantage conditions including classical parallelism. The key obstacle is that error-corrected quantum primitives can be much slower than classical primitives, making the breakeven time very large.

  • Primitive-runtime model: Runtime is modeled using M primitive calls, with classical complexity M^d and quantum complexity M for an order-d polynomial speedup.The model assumes no prefactor overhead for the quantum number of calls.
  • Primitive-runtime model: Quantum advantage requires T_Q < T_C, so the number of primitive calls must exceed a threshold determined by the primitive times and speedup degree.The paper uses this inequality to identify the problem sizes at which a quantum runtime advantage can begin.
  • Primitive-runtime model: The breakeven time T⋆ occurs when T_Q = T_C and becomes very large when t_Q ≫ t_C for small d.This captures how constant-factor quantum overheads can dominate low-degree scaling advantages.
  • Classical parallelism: Classical parallelization reduces runtime according to Amdahl’s law, using serial fraction α and parallel speedup S.The model allows comparison against P classical CPUs through the resulting speedup factor S.
  • Classical parallelism: Many candidate quadratic-speedup applications appear embarrassingly parallel, suggesting S ≈ P for reasonable numbers of classical processors.The paper lists search, optimization, Monte Carlo, and regression as examples.

Implementing error-corrected quantum primitives

The paper estimates error-corrected quantum primitive costs using surface-code Toffoli factories and examines how gate times, factory parallelism, and problem size constrain quantum advantage. It also grounds the analysis in a quantum-accelerated simulated-annealing example.

  • Surface-code primitives: Surface-code Toffoli gates require distilled resource states because practical surface-code implementations do not support transversal Toffolis.CCZ-state distillation is identified as a major time and hardware bottleneck.
  • Surface-code primitives: 170 µs is the estimated Toffoli gate time using 5.5d surface-code cycles, d = 30, and a 1 µs cycle time.The estimate uses state-of-the-art Toffoli-factory constructions and is consistent with a more detailed resource estimate.
  • Surface-code primitives: The quantum primitive runtime is t_Q = 170 µs · G, where G is the number of Toffoli gates required by the primitive.This connects the physical Toffoli estimate to the runtime model.
  • Resource trade-offs: Multiple Toffoli factories can reduce t_Q through parallel distillation, but routing overhead and the high physical-qubit cost limit the reduction.The paper notes that Toffolis are only about two orders of magnitude slower than Clifford gates, so factory parallelism does not remove all overhead.
  • Resource trade-offs: For N problem qubits, the paper gives the lower bound G ≥ N and finds it difficult to imagine satisfying the advantage condition below one-hundred-qubit problem sizes.Grover reflections provide an example requiring O(N) Toffoli gates.
  • Concrete example: Quantum-accelerated simulated annealing is used as a concrete example of an algorithm with a quadratic speedup in mixing time under stated assumptions.The example is based on a qubitized quantum walk and is selected to ground the estimates in a specific algorithm.

Implementing classical primitives

The analysis compares quantum and classical primitive runtimes using assumptions favorable to quantum computing, while accounting for classical hardware speed and parallel resources. Even with these assumptions, classical primitives can be extremely inexpensive, and the resulting crossover analysis remains optimistic toward quantum advantage.

  • Primitive-time assumptions: 330 ps · L bounds the classical primitive time on a typical 3 GHz CPU, where L is the number of classical clock cycles.The comparison assumes one classical clock cycle can implement logic corresponding to one quantum Toffoli, favoring the quantum side.
  • Primitive-time assumptions: 100 Toffolis can correspond to a classical primitive time of 33 ns under the stated Toffoli-to-cycle equivalence.The paper notes that many single-cycle classical operations would actually require thousands of Toffolis, making this assumption generous to the quantum computer.
  • Primitive-time assumptions: Eq. (5) scales worse with tQ than with tC, so the cheap classical primitive assumption is optimistic for the overall crossover time.A faster assumed classical primitive makes the comparison less favorable to quantum computing, but the equation's scaling makes the stated setup optimistic overall.
  • Simulated annealing: A performant simulated-annealing implementation for an N = 512 Sherrington-Kirkpatrick instance performs one step in roughly 7 CPU-nanoseconds.This provides a concrete classical analogue for the quantum-accelerated simulated-annealing comparison.
  • Classical baseline: Because quantum computing is costly, the analysis questions whether a single classical core is the appropriate comparison baseline.This motivates considering classical parallelism rather than only single-core runtimes.

Minimum runtime for quadratic quantum advantage

For quadratic speedups, the minimum runtime needed for quantum advantage is already substantial for very small primitives and becomes far worse for simulated annealing. Accounting for thousands of classical CPUs used for decoding further shifts the breakeven point against the quantum computer.

  • Single-core comparison: More than 100 Toffolis can only worsen the quadratic-speedup crossover time because quantum runtime is quadratic in tQ and inversely proportional to tC.The paper uses this scaling to argue that the 100-Toffoli example is a lower-bound-style optimistic case.
  • Simulated annealing: 320 days is the crossover time for the N = 512 simulated-annealing example, reproducing the prior finding cited by the authors.Quantum advantage would require M > tQ/tC = 6.3 × 10^7, corresponding to 4.0 × 10^15 classical calls.
  • Simulated annealing: The simulated-annealing comparison is less favorable because equating one Toffoli with one classical clock cycle is especially generous to the quantum computer.The paper explicitly identifies this primitive-cost assumption as a source of optimism.
  • Classical parallelism: 3,000 parallel classical CPUs increase the one-core 2.4-hour breakeven time to one year when the classical algorithm is sufficiently parallelizable.The example uses α^-1 ≪ P so S ≈ P, and notes that quantum error-corrected systems may themselves use thousands of CPUs for decoding.

The viability of higher polynomial speedups

Higher-degree polynomial speedups substantially improve the prospects for runtime advantage, whereas faster Toffoli distillation alone does not make quadratic speedups practical at modest improvements. Quartic speedups can reduce crossover times from impractically long durations to hours in the examples considered.

  • Higher polynomial degrees: Quartic speedups are promising, while the viability of cubic speedups remains ambiguous under varying classical parallelism.The analysis reports both M and T ⋆ for different polynomial degrees and levels of classical parallelism.
  • Higher polynomial degrees: 880 millennia for quadratic versus 4.9 hours for quartic speedup demonstrates the large runtime difference in one example.The paper cites tensor principal component analysis and other quartic query-complexity reductions as examples of higher-degree speedups.
  • Faster error-correction: R ≥ 1 reduces quadratic quantum runtime to TQ = M tQ/R by accelerating Toffoli distillation.The proposed sources include fanning out, more physical qubits per factory, more factories, improved distillation protocols, or faster hardware cycle times.
  • Faster error-correction: S = 10^3 classical parallelism is used for Table II because high parallel efficiency is generally difficult, although simulated annealing can achieve S = 10^6 in practice.The larger practical parallelism makes the reported simulated-annealing estimates overly optimistic for quantum computing.
  • Faster error-correction: A one-order-of-magnitude improvement in Toffoli distillation is insufficient for viable quadratic quantum advantage.Two orders of magnitude remain challenging in the simulated-annealing example, while three orders would materially change the outlook but likely require a significant breakthrough.

Conclusion

The analysis finds generally poor prospects for quadratic quantum speedups on small fault-tolerant processors, especially against highly parallel classical algorithms. Quartic speedups are often sufficient to restore viability, while the conclusions may persist across cost models.

  • Conclusion: Quadratic speedups generally have poor prospects for achieving quantum advantage on small fault-tolerant processors.The strongest conclusions assume classical parallelism speedups of 10^3 or more.
  • Conclusion: Highly parallelizable classical problems make the comparison particularly unfavorable for quantum computing.A quadratic speedup would have better prospects when the classical problem does not benefit substantially from parallelism.
  • Conclusion: Quartic speedups are often sufficient to restore the viability of quantum advantage on a modest processor.The paper therefore considers speedups beyond quadratic as more practical for early fault-tolerant devices.
  • Conclusion: The conclusion is expected to persist under a variety of cost models, including energy consumption rather than runtime.The authors also note that future progress or different assumptions could change the analysis.

Appendix A: Accounting for error-correction costs

The appendix decomposes surface-code error-correction costs into physical operation, syndrome measurement, decoding, distillation, and hardware-resource overheads. Under optimistic superconducting-qubit assumptions, a Toffoli gate takes about 170 µs and requires roughly 130,000 physical qubits, while the resulting error-correction overhead is 1,700.

  • Accounting for error-correction costs: Syndrome measurement is the realistic lower bound on round speed, with superconducting-qubit estimates of τ ≈10 ns and τm ≈100 ns.The appendix assumes τs > τ because two-qubit operations are used to build measurement circuits.
  • Accounting for error-correction costs: Syndrome measurement speeds of τs ≈100 µs appear ambitious for networked ion traps because multiple components must act together during each syndrome round.Current high-fidelity ion-trap operations and measurements are substantially slower, and inter-crystal communication adds overhead.
  • Accounting for error-correction costs: The analysis separates device operation time from syndrome extraction, decoding, correction, and error-correction overheads.For d rounds, the processing time is lower bounded approximately by dτs + lr, with latency potentially reduced through classical parallelization.
  • Accounting for error-correction costs: Surface-code Toffoli gates require distilled CCZ resource states because Toffolis cannot be implemented transversally in practical implementations.CCZ distillation is therefore a major time and hardware bottleneck for surface-code algorithms.
  • Accounting for error-correction costs: A state-of-the-art Toffoli factory uses 5.5d surface-code cycles and a data-qubit footprint of about 12d × 6d.The construction is based on lattice surgery and fault-tolerant Toffoli protocols.
  • Accounting for error-correction costs: 170 µs is the estimated Toffoli gate time under the model, using about 130,000 physical qubits.This estimate uses CG(dτs + lr) ≈ 5.5 × 30 µs and aligns with an approximately 23 qubit-second spacetime volume.
  • Accounting for error-correction costs: 1,700 is the estimated unitless error-correction overhead when the overall d-round time is 30 µs and physical syndrome measurement takes 100 ns.The overhead is expressed as CG(dτs + lr)/τs.
  • Accounting for error-correction costs: Reducing decoding time, distillation-factory time, and the number of protective measurement rounds are identified as the most fruitful current improvements.Reducing physical syndrome extraction time is presented as a later milestone after these advances.

Appendix B: Alternative approaches

The appendix examines alternatives to surface-code implementations, emphasizing that reducing time or space overhead often introduces stricter connectivity, error-rate, qubit, or gate-implementation requirements. These alternatives may lower memory use or mitigate non-Clifford overheads, but their practical advantage remains uncertain.

  • Surface-code baseline: Surface codes operate efficiently with physical gate infidelities near 10^-3, but their non-Clifford gates are costly in time.The analysis focuses on surface-code implementations of non-Clifford gates because their expense has been highly optimized under superconducting-device connectivity constraints.
  • Two-dimensional limitations: Constant-depth circuits on 2D-local stabilizer codes are Clifford, so universal non-Clifford computation often incurs code-distance-dependent time costs.Additional device connectivity can enable more fault-tolerant logic, but likely requires lower physical error rates.
  • Alternative approaches: Alternative constructions include 3D local codes, code switching, gauge fixing, concatenated codes, and pieceable fault tolerance.These approaches seek complementary transversal gate sets or fault-tolerant decompositions of nontransversal gates.
  • Overhead tradeoffs: Non-Clifford overhead can be mitigated by spending many more qubits, but whether this achieves lower space and time overhead at reasonable error rates remains speculative.Numerical studies of alternative schemes have not yet shown a convincing advantage.
  • Space overhead: Block codes may encode hundreds of logical qubits using 10^3–10^4 physical qubits instead of the surface-code footprint of 10^5–10^6, but their computational role remains unclear.Required physical error rates may be untenably low, and efficient gate implementation is difficult.
Loading 2011.04149v2…