Modeling the Performance of Early Fault-Tolerant Quantum Algorithms

Abstract

Progress in fault-tolerant quantum computation (FTQC) has driven the pursuit of practical applications with early fault-tolerant quantum computers (EFTQC). These devices, limited in their qubit counts and fault-tolerance capabilities, require algorithms that can accommodate some degrees of error, which are known as EFTQC algorithms. To predict the onset of early quantum advantage, a comprehensive methodology is needed to develop and analyze EFTQC algorithms, drawing insights from both the methodologies of noisy intermediate-scale quantum (NISQ) and traditional FTQC. To address this need, we propose such a methodology for modeling algorithm performance on EFTQC devices under varying degrees of error. As a case study, we apply our methodology to analyze the performance of Randomized Fourier Estimation (RFE), an EFTQC algorithm for phase estimation. We investigate the runtime performance and the fault-tolerant overhead of RFE in comparison to the traditional quantum phase estimation algorithm. Our analysis reveals that RFE achieves significant savings in physical qubit counts while having a much higher runtime upper bound. We anticipate even greater physical qubit savings when considering more realistic assumptions about the performance of EFTQC devices. By providing insights into the performance trade-offs and resource requirements of EFTQC algorithms, our work contributes to the development of practical and efficient quantum computing solutions on the path to quantum advantage.

arXiv comment9 pages, 8 figures, plus appendix

References in corpus (27)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Surface codes: Towards practical large-scale quantum computation
• Quantum Algorithms Revisited
• Characterizing Quantum Supremacy in Near-Term Devices
• Predicting Many Properties of a Quantum System from Very Few Measurements
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Roads towards fault-tolerant universal quantum computation
• Surface code quantum computing by lattice surgery
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Evenly distributed unitaries: on the structure of unitary designs
• Random Quantum Circuits are Approximate 2-designs
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• A randomized quantum algorithm for statistical phase estimation
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Minimizing estimation runtime on noisy quantum computers
• Low depth algorithms for quantum amplitude estimation
• 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
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Noise tailoring for Robust Amplitude Estimation

Cited by in corpus (6)

• Sampling Error Analysis in Quantum Krylov Subspace Diagonalization
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• Quantum computing quantum Monte Carlo algorithm
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Weakly Fault-Tolerant Computation in a Quantum Error-Detecting Code