Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation

Abstract

We consider performing phase estimation under the following conditions: we are given only one copy of the input state, the input state does not have to be an eigenstate of the unitary, and the state must not be measured. Most quantum estimation algorithms make assumptions that make them unsuitable for this 'coherent' setting, leaving only the textbook approach. We present novel algorithms for phase, energy, and amplitude estimation that are both conceptually and computationally simpler than the textbook method, featuring both a smaller query complexity and ancilla footprint. They do not require a quantum Fourier transform, and they do not require a quantum sorting network to compute the median of several estimates. Instead, they use block-encoding techniques to compute the estimate one bit at a time, performing all amplification via singular value transformation. These improved subroutines accelerate the performance of quantum Metropolis sampling and quantum Bayesian inference.

Added Jupyter notebook for reproducibility and fixed a benchmarking error

References in corpus (16)

• Quantum algorithm for solving linear systems of equations
• Entanglement-free Heisenberg-limited phase estimation
• A Grand Unification of Quantum Algorithms
• Efficient Distributed Quantum Computing
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Early fault-tolerant simulations of the Hubbard model
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Nearly tight Trotterization of interacting electrons
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• An improved quantum-inspired algorithm for linear regression
• Hamiltonian Simulation by Uniform Spectral Amplification
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Automatic Post-selection by Ancillae Thermalisation
• Quantum Arthur-Merlin Games
• Bounded Independence Fools Halfspaces

Cited by in corpus (2)

• Quantum algorithm for persistent Betti numbers and topological data analysis
• Quantum search-to-decision reductions and the state synthesis problem