On proving the robustness of algorithms for early fault-tolerant quantum computers

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.

27 pages, 3 figures, 1 table, 1 algorithm. Submitted to QIP 2023, APS March Meetings 2023, Quantum

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• A Quantum Approximate Optimization Algorithm
• Simulated Quantum Computation of Molecular Energies
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Robust Online Hamiltonian Learning
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• On low-depth algorithms for quantum phase estimation
• Modeling the Performance of Early Fault-Tolerant Quantum Algorithms

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