Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
arXiv:2103.09717 · doi:10.22331/q-2021-10-19-566
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.
arXiv commentAdded Jupyter notebook for reproducibility and fixed a benchmarking error
References in corpus (47)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum algorithm for solving linear systems of equations
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Entanglement-free Heisenberg-limited phase estimation
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- A Theory of Trotter Error
- Hamiltonian simulation with nearly optimal dependence on all parameters
- A Grand Unification of Quantum Algorithms
- Quantum speedup of Monte Carlo methods
- Quantum Metropolis Sampling
- Efficient Distributed Quantum Computing
- Iterative Quantum Amplitude Estimation
- Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
- Near-optimal ground state preparation
- Quantum gradient descent for linear systems and least squares
- A Quantum-Quantum Metropolis Algorithm
- Robust Calibration of a Universal Single-Qubit Gate-Set via Robust Phase Estimation
- Quantum Approximate Counting, Simplified
- Quantum Algorithm for Spectral Measurement with Lower Gate Count
- q-means: A quantum algorithm for unsupervised machine learning
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Quantum Recommendation Systems
- Early fault-tolerant simulations of the Hubbard model
- Product Decomposition of Periodic Functions in Quantum Signal Processing
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
- Nearly tight Trotterization of interacting electrons
- Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
- Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
- Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
- An improved quantum-inspired algorithm for linear regression
- Spectral density estimation with the Gaussian Integral Transform
- Hamiltonian Simulation by Uniform Spectral Amplification
- Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
- Finding Angles for Quantum Signal Processing with Machine Precision
- Quantum rejection sampling
- Quantum complexities of ordered searching, sorting, and element distinctness
- Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
- Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
- Quantum Computation of Eigenvalues within Target Intervals
- The quantum query complexity of approximating the median and related statistics
- Automatic Post-selection by Ancillae Thermalisation
- Quantum Arthur-Merlin Games
- Bounded Independence Fools Halfspaces