On proving the robustness of algorithms for early fault-tolerant quantum computers
arXiv:2209.11322 · doi:10.22331/q-2024-11-20-1531
Abstract
The hope of the quantum computing field is that quantum architectures are able to scale up and realize fault-tolerant quantum computing. Due to engineering challenges, such ''cheap'' error correction may be decades away. In the meantime, we anticipate an era of ''costly'' error correction, or early fault-tolerant quantum computing. Costly error correction might warrant settling for error-prone quantum computations. This motivates the development of quantum algorithms which are robust to some degree of error as well as methods to analyze their performance in the presence of error. Several such algorithms have recently been developed; what is missing is a methodology to analyze their robustness. To this end, we introduce a randomized algorithm for the task of phase estimation and give an analysis of its performance under two simple noise models. In both cases the analysis leads to a noise threshold, below which arbitrarily high accuracy can be achieved by increasing the number of samples used in the algorithm. As an application of this general analysis, we compute the maximum ratio of the largest circuit depth and the dephasing scale such that performance guarantees hold. We calculate that the randomized algorithm can succeed with arbitrarily high probability as long as the required circuit depth is less than 0.916 times the dephasing scale.
arXiv comment27 pages, 3 figures, 1 table, 1 algorithm. Submitted to QIP 2023, APS March Meetings 2023, Quantum
References in corpus (46)
- A variational eigenvalue solver on a quantum processor
- Quantum algorithm for solving linear systems of equations
- Surface codes: Towards practical large-scale quantum computation
- Quantum-enhanced measurements: beating the standard quantum limit
- A Quantum Approximate Optimization Algorithm
- Simulated Quantum Computation of Molecular Energies
- Quantum Amplitude Amplification and Estimation
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Elucidating Reaction Mechanisms on Quantum Computers
- Quantum Error Correction for Beginners
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum measurements and the Abelian Stabilizer Problem
- A Quantum Algorithm for Finding the Minimum
- Building a fault-tolerant quantum computer using concatenated cat codes
- Demonstration of quantum error correction and universal gate set on a binomial bosonic logical qubit
- Quantum Counting
- Is there evidence for exponential quantum advantage in quantum chemistry?
- Robust Online Hamiltonian Learning
- Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
- Layered architecture for quantum computing
- Efficient Bayesian Phase Estimation
- Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
- Experimental Bayesian Quantum Phase Estimation on a Silicon Photonic Chip
- Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
- Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
- Robust Calibration of a Universal Single-Qubit Gate-Set via Robust Phase Estimation
- Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis
- Parameter estimation of quantum channels
- A Threshold for Quantum Advantage in Derivative Pricing
- Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- A randomized quantum algorithm for statistical phase estimation
- Experimental Phase Estimation Enhanced By Machine Learning
- Minimizing estimation runtime on noisy quantum computers
- Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
- Limitations in quantum computing from resource constraints
- Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
- On low-depth algorithms for quantum phase estimation
- Amplitude estimation via maximum likelihood on noisy quantum computer
- State Preparation Boosters for Early Fault-Tolerant Quantum Computation
- Adaptive Hamiltonian Estimation Using Bayesian Experimental Design
- Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
- Variational Quantum Factoring
- Faster Phase Estimation
- Robustness of Shor's algorithm
Cited by in corpus (6)
- Error mitigation and circuit division for early fault-tolerant quantum phase estimation
- Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation
- Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
- Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era
- Thermodynamic Constraints on Information Transmission in Quantum Ensembles
- Weakly Fault-Tolerant Computation in a Quantum Error-Detecting Code