Focus beyond quadratic speedups for error-corrected quantum advantage

Abstract

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.

11 pages, 2 tables, 1 figure

References in corpus (66)

• Fault-tolerant quantum computation by anyons
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Quantum Amplitude Amplification and Estimation
• Trapped-Ion Quantum Computing: Progress and Challenges
• Multi-particle entanglement of hot trapped ions
• Fault-tolerant quantum computation with high threshold in two dimensions
• Entanglement and quantum computation with ions in thermal motion
• High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
• High-fidelity quantum logic gates using trapped-ion hyperfine qubits
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• Toward the first quantum simulation with quantum speedup
• High-Fidelity Universal Gate Set for ${}^9$Be${}^{+}$ Ion Qubits
• Restrictions on Transversal Encoded Quantum Gate Sets
• Quantum speedup of Monte Carlo methods
• Modular Entanglement of Atomic Qubits using both Photons and Phonons
• High-rate, high-fidelity entanglement of qubits across an elementary quantum network
• Single-qubit quantum memory exceeding $10$-minute coherence time
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Blueprint for a microwave trapped-ion quantum computer
• Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
• Fast and robust two-qubit gates for scalable ion trap quantum computing
• Fast quantum logic gates with trapped-ion qubits
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Quantum computing enhanced computational catalysis
• High-order quantum algorithm for solving linear differential equations
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Degenerate Quantum LDPC Codes With Good Finite Length Performance
• Novel constructions for the fault-tolerant Toffoli gate
• Tradeoffs for reliable quantum information storage in 2D systems
• Quantum Simulations of Classical Annealing Processes
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Multi-Element Logic Gates for Trapped-Ion Qubits
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Optimized simulated annealing for Ising spin glasses
• Classification of topologically protected gates for local stabilizer codes
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Repeated multi-qubit readout and feedback with a mixed-species trapped-ion register
• Efficient Arbitrary Simultaneously Entangling Gates on a trapped-ion quantum computer
• Hybrid quantum logic and a test of Bell's inequality using two different atomic isotopes
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Using concatenated quantum codes for universal fault-tolerant quantum gates
• Two-qubit entangling gates within arbitrarily long chains of trapped ions
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Demonstration of two-atom entanglement with ultrafast optical pulses
• Three-dimensional surface codes: Transversal gates and fault-tolerant architectures
• Simulating the performance of a distance-3 surface code in a linear ion trap
• A fault-tolerant non-Clifford gate for the surface code in two dimensions
• Universal fault-tolerant gates on concatenated stabilizer codes
• Applying quantum algorithms to constraint satisfaction problems
• Low overhead quantum computation using lattice surgery
• Subsystem codes with spatially local generators
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Overhead analysis of universal concatenated quantum codes
• Distilling one-qubit magic states into Toffoli states
• Fault-tolerant gates on hypergraph product codes
• Time-optimal quantum computation
• Optimal complexity correction of correlated errors in the surface code
• Beyond single-shot fault-tolerant quantum error correction
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• 2D quantum computation with 3D topological codes
• Universal fault-tolerant quantum computation with Bacon-Shor codes
• Classical and Quantum Algorithms for Tensor Principal Component Analysis
• Ultra-fast two-qubit ion gate using sequences of resonant pulses
• Quantum state preparation by phase randomization
• Flexible layout of surface code computations using AutoCCZ states

Cited by in corpus (73)

• Challenges and Opportunities in Quantum Machine Learning
• Realizing Repeated Quantum Error Correction in a Distance-Three Surface Code
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum computing for finance
• Is quantum advantage the right goal for quantum machine learning?
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• A Threshold for Quantum Advantage in Derivative Pricing
• Quantum Computing for Molecular Biology
• Biology and medicine in the landscape of quantum advantages
• Quantum-enhanced Markov chain Monte Carlo
• Benchmarking quantum computers
• Exponential quantum speedup in simulating coupled classical oscillators
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Integrating Quantum Computing Resources into Scientific HPC Ecosystems
• Towards quantum advantage via topological data analysis
• Low depth mechanisms for quantum optimization
• A hardware-efficient leakage-reduction scheme for quantum error correction with superconducting transmon qubits
• Towards large-scale quantum optimization solvers with few qubits
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Quantum Computing for Fusion Energy Science Applications
• Simulating Chemistry on Bosonic Quantum Devices
• Quantum Differentially Private Sparse Regression Learning
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
• A "thoughtful" Local Friendliness no-go theorem: a prospective experiment with new assumptions to suit
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• Quantum speedup for track reconstruction in particle accelerators
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Quantum algorithm for credit valuation adjustments
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Opening the Black Box Inside Grover's Algorithm
• Quantum Equation of Motion with Orbital Optimization for Computing Molecular Properties in Near-Term Quantum Computing
• What the foundations of quantum computer science teach us about chemistry
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• QRAM: A Survey and Critique
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Accelerating Quantum Algorithms with Precomputation
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Coupled cluster method tailored with quantum computing
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• From quantum-enhanced to quantum-inspired Monte Carlo
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Quantum Computing for Data Centric Engineering and Science
• Quartic quantum speedups for planted inference
• Solving Free Fermion Problems on a Quantum Computer
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• Quantifying Grover speed-ups beyond asymptotic analysis
• Impact of dynamics, entanglement, and Markovian noise on the fidelity of few-qubit digital quantum simulation
• Achieving computational gains with quantum error-correction primitives: Generation of long-range entanglement enhanced by error detection
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Quantum Motif Clustering
• Unified Architecture for Quantum Lookup Tables
• Nuwa: A Quantum Circuit Transpiler Based on a Finite-Horizon Heuristic for Placement and Routing
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Performance analysis of a filtering variational quantum algorithm
• Expanding the reach of quantum optimization with fermionic embeddings
• Quantum generative classification with mixed states
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device