PaperlayerView exact revision on arXiv

Source-linked AI summary

Assessing requirements to scale to practical quantum advantage

Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, Alexander Vaschillo

arXiv:2211.07629v1quant-phcs.AR

TL;DR

The paper asks how large, fast, and controllable quantum systems must be, and which architecture choices can support practical quantum advantage. It develops a resource-estimation framework across the quantum stack and analyzes requirements including error rates, operation speed, bandwidth, and qubit control.

  • Problem

    The paper asks how large quantum computers must be, how long computations will take, and which architecture choices best support scaled quantum computation.

  • Method

    The authors estimate application resources across stack layers using fault-tolerant architecture models, quantum error-correction schemes, instruction sets, and qubit-technology assumptions.

  • Results

    Error rates below around 0.1% may be needed to avoid prohibitive quantum-error-correction overheads, while supporting parallel operations across millions of qubits.

  • Takeaways & Limitations

    Practical scaling depends critically on qubit size, speed, and controllability, including fast operations, parallel readout, and quantum-classical decoding bandwidth.

  • Takeaways & Limitations

    The resource estimates do not account for the potentially substantial costs of repeatedly sampling probabilistic quantum-algorithm outputs.

Abstract

from arXiv · show

While quantum computers promise to solve some scientifically and commercially valuable problems thought intractable for classical machines, delivering on this promise will require a large-scale quantum machine. Understanding the impact of architecture design choices for a scaled quantum stack for specific applications, prior to full realization of the quantum system, is an important open challenge. To this end, we develop a framework for quantum resource estimation, abstracting the layers of the stack, to estimate resources required across these layers for large-scale quantum applications. Using a tool that implements this framework, we assess three scaled quantum applications and find that hundreds of thousands to millions of physical qubits are needed to achieve practical quantum advantage. We identify three qubit parameters, namely size, speed, and controllability, that are critical at scale to rendering these applications practical. A goal of our work is to accelerate progress towards practical quantum advantage by enabling the broader community to explore design choices across the stack, from algorithms to qubits.

I. TOWARD QUANTUM APPLICATIONS WITH PRACTICAL IMPACT

Practical quantum advantage requires large, fault-tolerant systems, but the necessary scale and architecture choices remain open questions. The proposed framework estimates these requirements across the stack and identifies size, speed, and controllability constraints.

  • Resource estimation: The framework compiles high-level algorithms onto specified architectures and estimates resources across qubit layout, allowed operations, and other design parameters.
  • Applications: The study analyzes a 2D transverse-field Ising model, catalyst activation energy in quantum chemistry, and integer factoring with Shor’s algorithm.
  • Requirements for scale: Reliable error correction requires controlling more than a million well-connected qubits with parallel operations failing less than one part in a thousand.
  • Requirements for scale: Under a month-long practical runtime and roughly one million physical qubits, operations must be performed in under a microsecond.
  • Requirements for scale: Scaling to a million or more qubits constrains qubit diameter to tens of microns to avoid coherent high-bandwidth interconnects between modules.
  • Implications: The work presents its requirements as additions to DiVincenzo’s criteria, based on cross-stack research and empirical end-to-end resource analysis.

II. RESOURCE ESTIMATION FOR CLASSICAL AND QUANTUM COMPUTING

Resource estimation models a computation stack to predict physical costs such as runtime. Quantum estimation adapts classical stack concepts while addressing noise, error correction, and less-established abstractions.

  • Classical stack: Classical programs are repeatedly re-expressed from high-level languages through lower-level representations until electrical signals control transistors.
  • Classical resource estimation: Resource estimation models a stack to estimate physical resources, including the runtime required to implement a high-level program.
  • Modeling strategy: A middle stack layer can serve as the modeling boundary: upper layers are compiled downward, while lower-layer instructions are composed to estimate physical resources.
  • Modeling strategy: The ISA is a natural implementation-independent interface for modeling executions across varied classical processors.
  • Quantum stack: Quantum stacks resemble classical stacks in program instruction sequences but must account for unavoidable physical noise absent from reliable transistor-based systems.
  • Prior work: Earlier quantum stack and estimation proposals either target small near-term systems without QEC or use error mitigation that does not scale to larger systems.

A. A framework for quantum resource estimation

The framework organizes large-scale quantum computing into modular layers linked through a quantum ISA, enabling resource estimates and comparisons across algorithms, software, error correction, and hardware.

  • Framework: The framework separates a full-stack quantum computer into modular layers that support direct comparisons across algorithms, software, QEC codes, and hardware specifications.
  • Upper layers: High-level quantum languages express algorithms while abstracting away quantum error-correction requirements and allowing programs to assume fault-tolerant operations.
  • Upper layers: Quantum IR provides language- and ISA-agnostic program representations, with front-end, optimization, and back-end compiler components.
  • Lower layers: Device-control layers cover hardware platforms and the classical resources needed to bring up, calibrate, and control quantum devices.
  • Lower layers: Physical microarchitecture abstracts devices into qubits and instructions characterized by their actions, durations, and failure probabilities.
  • Lower layers: QEC microcode transforms noisy physical qubits into more reliable logical qubits whose operations form the quantum ISA.
  • Resource estimation: The framework estimates qubit count, runtime, and power for an algorithm, technology, and fixed architectural choices, while allowing layers to be combined or extended.

B. Fault-tolerant design considerations

Fault-tolerant quantum computing requires physical qubits with low error rates, parallel operations, and sufficiently rich connectivity. The framework focuses on practical QEC requirements while acknowledging limitations in its noise and connectivity model.

  • Error rates: Physical Clifford-operation error rates must be below 0.1% to avoid prohibitive QEC overheads.This target is at least an order of magnitude below the highest known thresholds discussed.
  • Parallelism: QEC requires physical operations that can be applied in parallel, because high-threshold schemes rely on parallel operations.The requirement may challenge platforms such as trapped ions.
  • Connectivity: 2D connectivity supports several high-threshold local QEC codes, whereas 1D connectivity leaves few finite-threshold options with thresholds around 0.01% or below.The paper therefore treats 2D connectivity as practical but not 1D connectivity.
  • Scope and limitations: The model omits several realistic noise and connectivity subtleties, including correlated errors, permanent defects, and a complete definition for more general connectivity.These effects can respectively worsen error correction or remain outside the paper’s connectivity formulation.
  • Requirements for scale: The analysis requires well-connected qubits, parallel operations, and error rates below one part in a thousand for all examples.These conditions form one criterion for scale.

III. ESTIMATING RESOURCES FOR THREE QUANTUM APPLICATIONS

The paper implements its quantum resource-estimation framework as a publicly available tool and applies consistent architectural choices to estimate application resources. Estimates combine front-end and back-end compilation with bottom-up physical-resource modeling.

  • Tool implementation: The framework is implemented in the publicly available Azure Quantum Resource Estimator.The tool is introduced to identify architecture features important for practical quantum advantage.
  • Study design: The study estimates resources for three applications using qubit parameters relevant to prominent qubit technologies.A consistent set of architectural options is fixed across the quantum stack.
  • Estimation pipeline: The tool models explicit compilation from a high-level language through quantum IR to a quantum ISA, producing logical-qubit and logical-time-step estimates.A second component uses physical qubit parameters for bottom-up hardware estimation.
  • Implementation resources: The appendices provide a self-contained description of the framework, including modeling assumptions, while application examples are available as samples.

A. Quantum applications

The paper evaluates three applications spanning quantum dynamics, chemistry, and factoring, using explicit algorithmic accuracy requirements. Figure 2 depicts how high-level programs and physical-qubit parameters flow through the estimation stack.

  • Quantum dynamics: A 100-spin 2D transverse-field Ising model is simulated for ten time steps using a fourth-order Trotter algorithm.The model is presented as a small scientifically interesting problem believed to be classically intractable.
  • Quantum chemistry: The chemistry application estimates Complex XVIII’s catalyst energy to chemical accuracy of 1 mHa using double-factorized qubitization.The catalyst is associated with carbon fixation.
  • Resource-estimation flow: Figure 2 shows high-level programs translated to QIR, compiled to a planar quantum ISA, and combined with physical-qubit parameters to estimate physical-qubit and runtime resources.The tool models noisy qubits, protected logical qubits, and fault-tolerant ISA implementation using configurable QEC models.
  • Factoring: The factoring application identifies the prime factors of a 2048-bit integer using a high-level implementation of Shor’s algorithm.The problem relates to attacks on RSA-based encryption schemes.
  • Accuracy assumptions: Quantum dynamics and chemistry use algorithm execution accuracies of 0.999 and 0.99, respectively.Factoring can use lower accuracy because candidate solutions are easy to verify.

B. Requirements at the quantum ISA level

The ISA-level analysis compiles high-level programs into a planar quantum ISA and estimates the logical resources and error tolerances required by three applications. These requirements vary substantially and demand mature QEC for chemistry and factoring.

  • Resource inputs: The model targets ISA-level costs by combining program size with the required quality of ISA operations.Different quality requirements can favor different error-correction solutions.
  • Compilation: High-level implementations are compiled explicitly to QIR before the tool models back-end translation to supported quantum operations.Rust is used for chemistry and factoring, while Q# is used for quantum dynamics.
  • Planar quantum ISA: The planar quantum ISA uses logical surface-code operations with logical qubits stored in patches and ancilla regions on a 2D plane.Only permitted Clifford operations between appropriately connected patches can be applied.
  • Compilation challenges: Back-end compilation must synthesize fine-angle rotations and map unrestricted QIR connectivity onto the planar ISA’s connectivity restrictions.These are identified as two primary conceptual challenges.
  • Estimation procedure: The tool traces QIR and uses formulas to calculate planar-ISA resource requirements after back-end compilation with PSSPC.
  • ISA-level results: 200 logical qubits suffice for the quantum-dynamics example, but their error rates must be below 10^-11.Chemistry and factoring require several thousand logical qubits with logical-qubit error rates from 10^-15 to 10^-18.
  • Reported metrics: Table I reports logical qubits, minimum logical time steps, consumed T states, and allowed logical error rates for the applications.It also estimates the maximum allowed error rate for distilled T states.

C. Requirements at the device level

The framework models qubit technologies through operation times, error rates, instruction sets, and fault-tolerant resource costs. Physical parameters strongly affect logical resources, while T factories add substantial overhead to universal computation.

  • QEC requirements: Increasing surface-code or Hastings-Haah code distance quadratically increases physical-qubit cost and linearly increases logical time, while exponentially reducing logical failure probability.These codes use two-dimensional connectivity and support tunable error suppression through the patch code distance d.
  • T-state generation: Universal ISA execution requires non-Clifford operations supplied by T factories, which distill noisy T states and typically consume more resources than other ISA operations.The factory configuration and code distance are selected to satisfy logical-qubit and T-state error-rate requirements with minimal cost.
  • Parameter impact: Improving physical error rates from 10^-3 to 10^-4 can reduce the number of physical qubits by a factor of four and halve the logical time step.Comparisons across microsecond and nanosecond operation times show that faster physical operations substantially reduce logical time scales.
  • T-state generation: T factories require several thousand physical qubits and produce new T states only once every 10 to 15 logical time steps.Meeting application demand therefore motivates using multiple parallel T factories.

D. Combining the requirements into application resource estimates

The tool combines ISA-level application requirements with architecture-dependent QEC and T-factory choices to estimate physical resources. Across the modeled applications, qubit counts and runtimes vary by orders of magnitude, with a trade-off between algorithm speed and T-factory count.

  • Estimation pipeline: The tool estimates logical qubits, minimum logical time steps, logical T states, and maximum logical error rates before selecting architecture-dependent QEC and T-factory configurations.It chooses configurations with the smallest physical space-time footprints that satisfy the required logical error rates and T-state error rates.
  • Application-scale resources: More than 100K physical qubits are required even for the smallest practical application, quantum dynamics, while chemistry and factoring require upwards of 1M qubits.These estimates use the modeled qubit parameter examples and application-specific resource requirements.
  • Resource trade-off: Slowing the quantum dynamics algorithm can reduce the number of T factories and lower the qubit count when the parallel factory requirement becomes very large.Figure 3 compares a shortest-depth implementation with one that trades runtime for fewer T factories.
  • Runtime sensitivity: Three orders of magnitude longer physical operation times produce about three orders of magnitude longer application runtimes across the modeled applications.For quantum chemistry, the resulting runtime exceeds a century.
  • Scope of estimates: The estimates depend on choices of algorithms, compilation methods, QEC options, approximations, and assumptions, with future refinements expected to improve accuracy.The authors expect the broad conclusions to remain valid despite these choices.

IV. TECHNOLOGICAL IMPLICATIONS AND CONCLUSIONS

The paper identifies size, speed, and controllability as requirements for scaling quantum computers to practical quantum advantage. Its estimates also expose substantial physical, architectural, and classical-control demands.

  • Connectivity: 2D connectivity suffices for fault-tolerant error correction and logical qubits, but can make control and readout wiring challenging.One-dimensional connectivity simplifies wiring but requires prohibitively low error rates, while all-to-all connectivity is difficult to realize.
  • Error correction: Physical operation error rates must remain below fault-tolerance thresholds, with overheads potentially prohibitive unless rates reach roughly 0.1%.The cited thresholds are 3% without connectivity restrictions and 1% with 2D connectivity, while parallel operation at million-qubit scale remains necessary.
  • Controllability: A few million qubits may require several terabytes per second of quantum-classical bandwidth and petascale classical computing for decoding.These resources support parallel syndrome readout and error correction tightly integrated with the quantum machine.
  • Speed: Logical gate times under 10 µs, requiring physical gate times around 100 ns, are needed to complete the quantum chemistry algorithm within a month using a few million physical qubits.Slower qubits may be compensated for through parallelization, likely increasing the required physical-qubit count.
  • Size: A qubit size of around 10 microns is identified as a practical sweet spot when scaling to a million or more physical qubits.This estimate reflects wiring and control/readout requirements in a desirable monolithic, single-wafer architecture.
  • Size: A system with 10M superconducting transmon qubits is estimated to require an area of ∼10 square meters based on current designs.The paper notes that precise size estimates for leading qubit platforms are unavailable in the literature.
  • Conclusions: No currently implemented qubit technology satisfies all identified scaling requirements, although two unimplemented proposals appear to satisfy them from a design perspective.The proposals are electro-acoustic qubits and topological qubits based on Majorana Zero Modes.

APPENDICES

The appendices document the models, assumptions, and application-level calculations used by the resource-estimation tool. The workflow compiles applications into a planar quantum ISA and estimates physical resources under configurable architecture models.

  • Appendices: The appendices provide a detailed description of the choices, assumptions, and approximations used in the first release of the Azure Quantum Resource Estimator.They are intended to make the resource-estimation procedure self-contained.
  • Appendices: Figure 4 summarizes modeled stack examples and options, while Table IV collects inputs, outputs, and intermediate data for each application and qubit-parameter example.These data are used to produce the main-text resource estimates.
  • Modeling assumptions: The tool models selected system components expected to significantly affect performance while abstracting away or neglecting components expected to contribute little to cost.This enables simple, efficient, and effective resource estimation, but leaves the model necessarily incomplete for future systems.
  • Resource estimation: The appendices use component models to estimate physical resources, including qubit counts and runtime, for executing quantum applications.A separate part details the applications and algorithmic optimizations used to reduce resource requirements.
  • Resource estimation: Table IV optimizes error-correction code distance d and T-state-distillation factories F to minimize resources while maintaining reliable computation.It also reports the fraction of physical qubits used for distillation factories and includes a slowed quantum-dynamics implementation that reduces factory overhead.

Appendix A: Physical qubit models

The physical-qubit models specify instruction sets, circuit-noise assumptions, and representative operation-time and error-rate regimes. These models cover gate-based and Majorana architectures across several hardware-relevant parameter examples.

  • Instruction sets: The analysis assumes either a gate-based instruction set with native CNOT or CZ gates, or a Majorana instruction set with native parity-check measurements.Majorana unitary operations are realized through sequences of measurements, and both models use nearest-neighbor connectivity.
  • Instruction sets: Both instruction sets include Pauli-basis preparation and measurement, T-state preparation, and T-gate application, while differing in their additional native operations.The gate-based set adds H, S, CNOT, and CZ operations; the Majorana set adds non-destructive joint Pauli measurements.
  • Noise model: The noise model assumes each physical operation fails independently, with Clifford operations failing at probability p and T-state preparation at probability pT.Failures are modeled using random Pauli operators, with measurement outcomes additionally flipped when measurements fail.
  • Qubit parameters: Microsecond-regime examples use 100 µs gate and measurement times and include two-qubit gate error rates of 10−3 and 10−4 for trapped-ion-relevant models.Single-qubit gates are assigned an error rate of 10−6 in these examples.
  • Qubit parameters: Nanosecond-regime superconducting-transmon or spin-qubit examples use projected 50 ns gate times and 100 ns measurement times with two-qubit error rates of 10−3 or 10−4.The paper characterizes these projections as relatively optimistic, particularly for measurements.
  • Qubit parameters: Majorana examples assume 100 ns measurements and physical T gates, with Clifford error rates of 10−4 or 10−6.The examples are labeled by operation-time unit, error rate, and instruction set for comparison across regimes.

Appendix B: Quantum error correction and the planar quantum ISA

The appendix models fault-tolerant quantum computation using surface-code and Hastings–Haah-code error correction, then estimates the resources and reliability of logical operations and T-state distillation factories.

  • Quantum error correction: Surface code is assumed for gate-based qubits, while Majorana qubits use either surface code or Hastings–Haah code.Hastings–Haah code is included because it offers better space-time costs than surface codes for Majorana qubits in many regimes.
  • Quantum error correction: Code distance d controls logical failure probability, physical-qubit overhead n(d), and logical-time overhead τ(d).The appendix provides formulas for estimating these quantities as functions of qubit design parameters.
  • Planar quantum ISA: The planar quantum ISA uses the same logical patches, operations, and tile/time-step costs for both code families, with differences captured by their formulas.This abstraction supports resource comparisons across the two QEC schemes.
  • T-state distillation: Low-error T states are required because Clifford operations alone are insufficient for universal quantum computation.T states are produced through distillation factories that refine imperfect inputs using Clifford-only distillation units.
  • T-state distillation: Distillation factories run identical units in parallel rounds, feeding higher-quality outputs from each round into the next.The factory model calculates input and output error rates, acceptance probabilities, runtime, and qubit requirements for each round.
  • T-state distillation: M(D) denotes the number of T states a factory outputs in at least 99% of runs, accounting for failures among its distillation units.Factories may over-provision units so enough T states reach the next round despite rejected units.

Appendix D: Compilation from QIR to the planar quantum ISA

The appendix compiles QIR programs into the planar quantum ISA using PSSPC, which delegates rotations to ancillas, eliminates Clifford unitaries, and estimates resulting logical resources.

  • Compilation framework: The planar quantum ISA combines Clifford operations with distilled T states and is sufficient for universal quantum computation.Back-end compilation maps QIR programs onto this instruction set.
  • Compilation framework: PSSPC combines sequential Pauli-based computation with parallel synthesis of diagonal non-Clifford unitaries.The scheme is designed to compile QIR inputs expressed as Clifford and non-Clifford layers.
  • Circuit transformations: PSSPC delegates arbitrary-angle rotations to synthesis qubits, allowing multiple rotations in one layer to be synthesized in parallel.The rotation phase is applied on an ancilla and kicked back to the algorithm qubit through measurement.
  • Circuit transformations: Clifford unitaries are eliminated by commuting them through later Pauli operations, replacing them with multi-qubit Pauli measurements and corrections.This optimization removes Clifford execution from the algorithm-qubit operations.
  • Circuit transformations: PSSPC parallelizes rotation synthesis within a layer, but phase kickback for those rotations remains serial.Compared with SPC, this avoids fully serializing T gates while retaining a serial component.
  • Resource estimation: The resource model tracks Qalg, MR, MT, MTof, Mmeas, and DR to estimate logical-qubit, T-state, and time requirements.The fast-block layout stores each algorithm-qubit pair in a two-tile patch surrounded by ancilla tiles for arbitrary Pauli measurements.
  • Assumptions and limitations: The compilation estimates use a simplified rotation formula for all arbitrary-angle single-qubit rotations and omit synthesis ancillas and T-state transport qubits.The rotation model does not distinguish best, worst, and average cases.
  • Resource estimation: Cmin = (Mmeas + MR + MT) + ⌈A log2(MR/ϵsyn) + B⌉DR + 3MTof.This expression combines measurement, rotation, T-gate, synthesis, and Toffoli contributions to minimum logical time steps.

Appendix F: Applications

The appendix details resource calculations for quantum dynamics, quantum chemistry, and factoring, while noting that algorithm sampling costs and several modeling assumptions are excluded or idealized. Across examples, compilation and fault-tolerance analysis translate algorithm descriptions into logical and physical resource estimates.

  • Scope and assumptions: Resource estimates exclude the potentially substantial cost of repeated algorithm sampling and rely on assumptions including uniform independent physical noise.Sampling may require consecutive reruns, parallel quantum computers, or both; the stated assumptions are not fully justified in the current literature and could increase estimates if relaxed.
  • Quantum dynamics: Quantum dynamics uses fourth-order product formulas to simulate a 2D transverse-field Ising model, reducing evolution to structured exponentials and single-qubit rotations.The example uses N = 100 spins and T = 20 time steps, with Qalg = 100 and MR = 30100 before architecture-level compilation.
  • Quantum dynamics: Quantum dynamics trades qubit count against runtime by increasing C beyond Cmin, rather than using the minimum code-cycle count.At C = Cmin, the analysis first determines code distance and physical-resource parameters before applying the slower, lower-qubit configuration.
  • Quantum chemistry: Quantum chemistry uses double-factorized qubitization to compress the Hamiltonian representation and reduce resources for quantum phase estimation.The compiled program has Qalg = 1318 logical qubits, while the ISA-level executable requires Q = 2740 logical qubits for at least Cmin = 4.10 · 10^11 logical time steps.
  • Factoring: Factoring uses an optimized Shor implementation for RSA-2048, with compilation producing Q = 25481 logical qubits and Cmin = 1.23 · 10^10 logical time steps.For the illustrated (ns, 10^-4) qubit example, the physical analysis gives t = 17 hours 43 mins and q = 8.72M physical qubits.
  • Factoring: The factoring estimate can use reruns because an invalid result is readily detected, so the example permits algorithm failure probability ϵ = 1/3.This assumption is specific to the verifiable factoring application.
Loading 2211.07629v1…