PaperlayerView exact revision on arXiv

Source-linked AI summary

Early Fault-Tolerant Quantum Computing

Amara Katabarwa, Katerina Gratsea, Athena Caesura, Peter D. Johnson

arXiv:2311.14814v1quant-ph

TL;DR

Limited-scalability quantum computing raises questions about how to model improving devices and how to use them effectively. The paper proposes a scalability model and examines algorithms suited to finite scalability; for the same resources, randomized Fourier estimation extends the problem-size limit from around 90 to around 130 logical qubits, with runtime increasing roughly 100 times. The authors present this as a first attempt to bridge NISQ and FTQC.

  • Problem

    The paper asks how to characterize device performance as physical-qubit counts grow and how algorithms can use quantum computers in the transition between NISQ and FTQC.

    Source: §I · p. 2, §IV · p. 20

  • Method

    The authors introduce a model of physical error versus physical-qubit count and assess algorithms suited to finite scalability, including randomized Fourier estimation.

    Source: A. Introduction to the scalability model · p. 6, §IV · p. 18

  • Results

    For the same quantum resources, the problem-size limit extends from around 90 logical qubits for QPE to around 130 using randomized Fourier estimation, at roughly 100 times the runtime.

    Source: §IV · p. 19

  • Takeaways & Limitations

    The framework suggests EFTQC may support a larger number of logical qubits than QPE with the same physical resources and scalability model, with possible relevance to problems requiring over 100 logical qubits.

    Source: §IV · p. 19

    The scalability model is a first attempt to bridge NISQ and FTQC while how devices will scale to millions or billions of physical qubits remains unclear.

    Source: §IV · p. 20

Abstract

from arXiv · show

Over the past decade, research in quantum computing has tended to fall into one of two camps: near-term intermediate scale quantum (NISQ) and fault-tolerant quantum computing (FTQC). Yet, a growing body of work has been investigating how to use quantum computers in transition between these two eras. This envisions operating with tens of thousands to millions of physical qubits, able to support fault-tolerant protocols, though operating close to the fault-tolerant threshold. Two challenges emerge from this picture: how to model the performance of devices that are continually improving and how to design algorithms to make the most use of these devices? In this work we develop a model for the performance of early fault-tolerant quantum computing (EFTQC) architectures and use this model to elucidate the regimes in which algorithms suited to such architectures are advantageous. As a concrete example, we show that, for the canonical task of phase estimation, in a regime of moderate scalability and using just over one million physical qubits, the ``reach'' of the quantum computer can be extended (compared to the standard approach) from 90-qubit instances to over 130-qubit instances using a simple early fault-tolerant quantum algorithm, which reduces the number of operations per circuit by a factor of 100 and increases the number of circuit repetitions by a factor of 10,000. This clarifies the role that such algorithms might play in the era of limited-scalability quantum computing.

I. INTRODUCTION

The introduction asks whether limited-scale quantum computers can exist meaningfully and deliver quantum value at scale, given open questions about NISQ algorithms and utility-scale tasks. It proposes a quantitative framework for finite scalability and examines algorithms that trade smaller circuits for more sampling.

I. INTRODUCTION

  • Whether NISQ devices and algorithms can realize quantum advantage at utility scale remains an open question, while proposed advantages for QAOA under noise at scale remain unconfirmed.The introduction contrasts resource estimates that suggest VQE is not up to large-molecule tasks with QAOA claims that still need confirmation under noise at scale.Source: §I · p. 2
  • EFTQC algorithms trade smaller quantum circuits for more sampling, a trade-off suited to settings where fault-tolerant protocols become less efficient as systems scale.With arbitrarily scalable, efficient fault tolerance, the introduction says circuit-size growth through amplitude amplification could make the added overhead negligible relative to runtime reduction.Source: §I · p. 2
  • The authors propose a quantitative framework to track hardware, error-correction, algorithm, and classical-computing advances rather than predict when they will occur.Its scalability model describes how physical gate error changes with physical-qubit count and assesses the ability of a vendor to supply useful qubits across regimes.Source: §I · p. 2
  • The model predicts an optimal physical-qubit count as a function of scalability and a maximum problem size measured by the largest logical-qubit count.The introduction identifies scalability parameter s and the fault-tolerance burden factor Aα as governing capabilities and maximum reach.Source: §I · pp. 3–4
  • The fault-tolerance burden factor pC combines gate count, error correction, and algorithm robustness parameters to describe ways to improve computations in the finite-scalability regime.The framework uses these factors to elucidate multiple routes toward utility-scale instances.Source: §I · p. 4

A. Introduction to the scalability model

The section frames early fault-tolerant quantum computing as a transition from scale-dependent to scale-independent error, and introduces scalability as a way to model how device error changes with architecture size. It uses that model to examine limits on fault-tolerant computation as systems scale.

A. Introduction to the scalability model

  • Fault-tolerant scaling requires each operation to remain below threshold as architectures grow, but engineering demands can introduce size-dependent errors.Examples include frequency crowding and unwanted control-line interactions in superconducting systems, and cross-mode coupling in ion traps.Source: A. Introduction to the scalability model · pp. 4–5
  • Early fault tolerance marks a transition from scale-dependent errors toward scale-independent error, and the paper asks how error dependence shapes architecture capabilities.Scale-independent, sub-threshold error rates are described as a possible future enabled by modular architectures.Source: A. Introduction to the scalability model · p. 5
  • For a vendor assessed at one moment, a scalability profile gives worst-case elementary-operation error versus requested physical-qubit count; the proposed power-law model approximates this profile.The model’s parameters represent base error rate and scalability; s = ∞ denotes scale-independent error, while finite s denotes limited scalability.Source: A. Introduction to the scalability model · pp. 5–6
  • Finite scalability limits physical-qubit growth before fault-tolerant protocols yield diminishing returns, thereby limiting the problem sizes an architecture can accommodate.These considerations concern fault-tolerant computations using logical qubits, unlike NISQ computation using physical qubits.Source: A. Introduction to the scalability model · p. 6
  • With a distance-3 surface code, the minimum viable EFTQC example requires at least 540 qubits for lower-quality and 826 for high-quality operations; magic-state factories dominate the count.The estimate uses computation qubits plus magic-state-distillation qubits, and the smallest distillation widgets described do not greatly improve the physical error rate.Source: A. Introduction to the scalability model · pp. 6–7
  • The lower-bound estimate may be refined by accounting for smaller factories, improved injection protocols, or eliminating distillation, which the authors identify as future work.The authors expect early EFTQC demonstrations to employ some of these techniques rather than the “pure FTQC” calculation.Source: A. Introduction to the scalability model · p. 7

B. Example: quantum phase estimation compiled to the surface code

The section applies the scalability model to surface-code quantum phase estimation, relating physical-qubit counts to the logical error rates needed for an accurate estimate. For finite scalability, the model predicts a maximum instance size; with s=3.5, the reported reach is about 90 logical qubits.

B. Example: quantum phase estimation compiled to the surface code

  • QPE resource estimates require logical error rates low enough for the circuit to succeed, linking algorithm operation count to physical-qubit requirements.The analysis compares the scalability model with the idealized s→∞ case.Source: B. Example: quantum phase estimation… · pp. 7, 9
  • With circuit error tolerance pC=0.1, a sufficient condition is pL≤pC/GC, where GC counts elementary logical operations, including idling.The passage notes that literature values for tolerable circuit error rates range from 0.1 to 0.01, with lower values possible using alternative algorithms.Source: B. Example: quantum phase estimation… · p. 7
  • QPE’s operation count depends on target accuracy and c-U cost; the section fits a power law to prior data to model GC.An estimate accurate to within ε requires 1/ε applications of c-U.Source: B. Example: quantum phase estimation… · p. 7
  • The surface-code estimate uses 2(d+1)^2 physical qubits per logical qubit and assumes factory overhead is accounted for in the model.The physical-qubit overhead is treated as captured by the data-qubit code distance, although factories may use multiple concatenation layers and code distances.Source: B. Example: quantum phase estimation… · pp. 8–9
  • The scalability model places a maximum on warranted physical qubits: the minimum physical error rate occurs at pphys=pth, where Qphys=(pth/p0)^s.The passage contrasts this with qubit-independent physical error rates, under which logical error rates can be made arbitrarily small by increasing code distance.Source: B. Example: quantum phase estimation… · p. 9
  • The section treats Qopt as the physical-qubit count that permits the largest number of logical qubits, and relates scalability parameters to the NISQ-to-EFTQC transition.The transition range is described as 100 to 10,000 physical qubits.Source: B. Example: quantum phase estimation… · p. 10
  • Reducing the burden factor can lower the physical-qubit requirement or increase logical-qubit capacity at fixed physical qubits, but the methods incur higher runtime.The section characterizes EFTQC as limited by the architecture’s maximum warranted physical-qubit count; runtime can also constrain problem sizes, with a one-month example requiring on the order of 10^7 physical qubits.Source: B. Example: quantum phase estimation… · p. 10
  • At s=3.5, p0=0.0001, and pth=0.01, the largest accommodated QPE instance has about 90 logical qubits.For finite scalability values, the model predicts a maximum instance size; the section uses this as the architecture’s reach.Source: Figure 4 · p. 8, B. Example: quantum phase estimation… · p. 10

A. Review of methods

The review surveys algorithms developed for early fault-tolerant devices, which trade reduced circuit or qubit costs and increased robustness against more sampling, runtime, or classical processing. Across amplitude and ground-state estimation, the methods offer tunable operation–sampling trade-offs, while overlap dependence and realistic runtime estimates remain important considerations.

A. Review of methods

  • The review spans phase, multiple-eigenvalue, ground-state property, amplitude, and ground-state energy estimation, plus ground-state preparation.It includes some works that do not use the EFTQC label because of their influence or similar motivation.Source: A. Review of methods · p. 12
  • EFTQC algorithms target fewer logical qubits, fewer operations per circuit, fewer expensive operations, or greater robustness to error.These improvements often cost more circuit repetitions and runtime, or additional classical processing.Source: A. Review of methods · p. 12
  • The α-VQE method trades O(1/ε^α) operations per circuit against approximately O(1/ε^2(1−α)) circuit repetitions using tunable α.Variable-depth amplitude estimation methods were also developed to tolerate substantial circuit error.Source: A. Review of methods · p. 12
  • Ground-state energy methods also reduce expensive non-Clifford operations, remove QPE’s ancilla overhead, or use postprocessing to improve runtime scaling.The review describes Heisenberg-limit O(1/ε) runtime for versus O(1/ε^4) for the cited earlier approach [115].Source: A. Review of methods · p. 12
  • Circuit trading for ground-state energy estimation reduces operations per circuit from Õ(1/ε) to Õ(log 1/ε), at the cost of repetitions increasing from Õ(log 1/ε) to Õ(1/ε^2).The cited methods include [106] and QCELS [57]; QCELS can make circuit depth arbitrarily small while retaining Heisenberg-limit scaling if ground-state overlap is sufficiently close to 1.Source: A. Review of methods · p. 13
  • Earlier ground-state energy methods with reduced operations per circuit had runtime and repetition scaling O(1/γ^4), while some higher-operation methods achieved O(1/γ^2) or O(1/γ).This motivated algorithms seeking few operations per circuit with improved overlap scaling.Source: A. Review of methods · p. 13
  • A sampling-based ground-state energy method tunes operations per circuit from O(1/ε) to O(1/Δ), broadening the Gaussian peak and requiring more samples for equal accuracy.A Gaussian-filter variant [107] uses O(1/Δ) operations per circuit and O(1/γ^2) repetitions.Source: A. Review of methods · p. 13
  • Ground-state energy estimation runtime depends on trial-state overlap γ, and the review identifies empirical runtime, circuit-operation, and robustness studies as future work.It also notes robustness methods and algorithms designed to trade gate count for sample cost as ways to reduce fault-tolerant overhead.Source: A. Review of methods · pp. 13–14

B. Example: randomized Fourier estimation under finite scalability

The section uses randomized Fourier estimation (RFE) to examine how an early fault-tolerant algorithm can extend computation reach under finite scalability. It presents circuit-depth and robustness trade-offs, alongside runtime costs and a caveat about deviations from the assumed noise model.

RFE features

  • RFE is presented as a prototypical EFTQC algorithm with one ancilla, tunable circuit trading, and robustness to circuit error.The section also describes robustness through a signal corrupted by a noise floor.Source: B. Example: randomized Fourier… · p. 14

a. RFE Intro

  • RFE estimates phase θ by finding the tallest peak in a discrete Fourier transform of measurement data from circuits parameterized by k and φ.The expected measurement signal is g(k) = cos(kθ + φ), and repetitions are used to estimate its Fourier transform.Source: B. Example: randomized Fourier… · p. 15

b. Circuit trading

  • Reducing K lowers operations per circuit but broadens the Fourier peak, so more circuit repetitions are needed to control sampling noise.K can be set below the approximately 1/ε calls to c-U used in standard QPE.Source: B. Example: randomized Fourier… · p. 16
  • Under the scalability model, RFE extends reach from 90 to over 200 logical qubits by reducing c-U operations per circuit or increasing tolerable circuit error.Reducing K by a factor of 100,000 is one analyzed route to this larger problem instance.Source: B. Example: randomized Fourier… · p. 16, Figure 6 · p. 17

c. Robustness

  • For λ ≥ 1/2 with K at its minimum value of 2, runtime grows exponentially in λ, potentially limiting practical robustness.The paper notes that runtime costs of reducing fault-tolerance burden need careful consideration.Source: B. Example: randomized Fourier… · p. 18
  • Deviations from the exact exponential-decay noise model can shift the Fourier peak, setting a lower limit on achievable accuracy ε.The section notes a similar feature for bounded adversarial and Gaussian noise models.Source: B. Example: randomized Fourier… · p. 18

IV. DISCUSSION AND OUTLOOK

The discussion finds a finite-scalability limit for standard QPE and reports that randomized Fourier estimation extends the problem-size reach with the same physical-qubit resources. It frames EFTQC’s prospects around hardware, algorithmic, and fault-tolerance advances, while noting that the analysis covers a specific algorithm and QEC model.

IV. DISCUSSION AND OUTLOOK

  • Finite scalability limits the problem size accommodated by QPE compiled to the surface code, as scale-dependent errors meet diminishing returns from fault-tolerant protocols near threshold.The paper attributes this limit to the combination of scale-dependent error rates and diminishing returns as device errors approach the numerically estimated threshold.Source: §IV · p. 18
  • The problem-size limit extends from around 90 qubits for QPE to around 130 qubits using randomized Fourier estimation with the same number of physical qubits.The extension comes at the cost of roughly a 100 times increase in runtime.Source: §IV · pp. 18–19
  • EFTQC’s largest solvable instances are bottlenecked by available physical qubits, whereas FTQC’s are bottlenecked by runtime; the discussion places these transitions in estimated physical-qubit ranges.The proposed ranges are 100 to 10,000 physical qubits for the NISQ-to-EFTQC transition and 10^6 to 10^8 for EFTQC-to-FTQC.Source: §IV · p. 19
  • The framework treats hardware, algorithmic, and fault-tolerance advances as jointly important to characterizing EFTQC, while the pace of vendor scalability growth remains unknown.The authors describe their work as a first attempt to incorporate these factors.Source: §IV · pp. 19–20
  • The reported reach extension may matter for lithium-ion electrolyte chemistry, for which recent resource estimates indicate that more than 100 logical qubits are needed.The authors suggest this could allow relevant problems to be studied before the FTQC regime.Source: §IV · p. 19
  • The study evaluates RFE with the surface code, and the scalability model is not expected to fit vendor profiles perfectly across many orders of magnitude.The authors anticipate it could capture qualitative behavior over at least a few orders of magnitude; they also report that the upper-size-limit finding persists under a more optimistic logarithmic model.Source: §IV · p. 19

Appendix A: Scalability of today’s devices

The authors estimate today’s device scalability by fitting daily worst-case CNOT error-rate measurements from two IBM cloud devices. Their power-law fit gives p0 = 0.005 and s = 1.75, placing the measured point in the NISQ regime despite p0 being below threshold.

Appendix A: Scalability of today’s devices

  • The power-law fit estimates today’s scalability as p0 = 0.005 and s = 1.75, and places the measured point in the NISQ regime despite p0 being below threshold.The data are from IBM’s lagos and brisbane devices.Source: Appendix A · p. 21
  • The estimate uses daily CNOT error-rate measurements collected at 10:00 am over 30 days from two IBM cloud devices.The analysis fits the data to estimate p0 and s.Source: Appendix A · p. 21
  • The plotted quantities are the mean and standard deviation of the devices’ worst-case CNOT error rates, fitted with a power law.The figure plots the worst two-qubit gate error as a function of qubit count.Source: Appendix A · p. 21

Appendix B: Logarithmic scalability model

Appendix B considers a logarithmic alternative to the power-law scalability model, parameterized to match its value and slope at one physical qubit. It retains a finite maximum problem size for finite scalability, while predicting a more optimistic resource overhead profile.

Appendix B: Logarithmic scalability model

  • The alternative model is parameterized so its value and slope at Q_phys = 1 match those of the power-law model.σ is the scalability parameter analogous to s in Equation 3.Source: Appendix B · p. 21
  • Under the logarithmic model, the physical-qubit count at which the physical error rate exceeds threshold grows exponentially in the gap between p0 and p_th, compared with the power-law model.Source: Appendix B · p. 21
  • For each finite scalability parameter σ, the logarithmic model predicts a maximum QPE instance size, while being more optimistic than the power-law model under the stated matching conditions.The caption specifies matching base error rate and logarithmic slope; its comparison sentence is incomplete in the supplied passage.Source: Figure 8 · p. 22
  • The plotted limited-instance-size range uses p0 = 0.001, rather than p0 = 0.0001 in Figure 4, because the logarithmic model predicts a larger maximum instance size under the stated matching conditions.Source: Appendix B · p. 22

Related papers

Loading 2311.14814v1…