A randomized quantum algorithm for statistical phase estimation

Abstract

Phase estimation is a quantum algorithm for measuring the eigenvalues of a Hamiltonian. We propose and rigorously analyse a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, such as those based on qDRIFT, all sources of error in our algorithm can be suppressed by collecting more data samples, without increasing the circuit depth.

5+20 pages, 4 figures

References in corpus (15)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• A Grand Unification of Quantum Algorithms
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Quantum computing enhanced computational catalysis
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Efficient synthesis of universal Repeat-Until-Success circuits
• Early fault-tolerant simulations of the Hubbard model
• Efficient synthesis of probabilistic quantum circuits with fallback
• Compilation by stochastic Hamiltonian sparsification
• Hamiltonian Simulation by Uniform Spectral Amplification
• Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications
• Improving the accuracy of quantum computational chemistry using the transcorrelated method
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• Phase estimation with randomized Hamiltonians

Cited by in corpus (65)

• Early Fault-Tolerant Quantum Computing
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• On low-depth algorithms for quantum phase estimation
• Demonstrating Bayesian Quantum Phase Estimation with Quantum Error Detection
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum Computation for Periodic Solids in Second Quantization
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• On the complexity of implementing Trotter steps
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Statistical phase estimation and error mitigation on a superconducting quantum processor
• Error-resilient Monte Carlo quantum simulation of imaginary time
• Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Quantum simulation of battery materials using ionic pseudopotentials
• Importance sampling for stochastic quantum simulations
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• A stochastic quantum Krylov protocol with double factorized Hamiltonians
• Rapid quantum ground state preparation via dissipative dynamics
• Optimal scheduling in probabilistic imaginary-time evolution on a quantum computer
• Dissipative Preparation of Many-Body Quantum States: Towards Practical Quantum Advantage
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Quantum error mitigation for Fourier moment computation
• Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Compilation of a simple chemistry application to quantum error correction primitives
• Calculating the many-body density of states on a digital quantum computer
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Spectral estimation for Hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution
• Reversing Unknown Quantum Processes via Virtual Combs for Channels with Limited Information
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Probing spectral features of quantum many-body systems with quantum simulators
• Virtual quantum error detection
• In the shadow of the Hadamard test: Using the garbage state for good and further modifications
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Halving the Cost of Quantum Algorithms with Randomization
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Complementary polynomials in quantum signal processing
• Accelerating two-dimensional electronic spectroscopy simulations with a probe qubit protocol
• Quantum computing quantum Monte Carlo algorithm
• Randomized semi-quantum matrix processing
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Experimental demonstration of optimal measurement for unambiguously discriminating asymmetric qudit states
• Hardware-efficient quantum phase estimation via local control
• Quantum eigenvalue processing
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Fault-tolerant quantum simulation of generalized Hubbard models
• Phase estimation with partially randomized time evolution
• Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
• Toward scalable quantum computations of atomic nuclei
• Optimal Coherent Quantum Phase Estimation via Tapering
• Towards Practical Quantum Phase Estimation: A Modular, Scalable, and Adaptive Approach
• Recurrence in discrete-time quantum stochastic walks
• Dissipative ground state preparation in ab initio electronic structure theory
• Short-time simulation of quantum dynamics by Pauli measurements
• Simulating sparse SYK model with a randomized algorithm on a trapped-ion quantum computer
• Quantum linear system algorithm with optimal queries to initial state preparation
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation
• Quantum Simulation via Stochastic Combination of Unitaries