Low depth algorithms for quantum amplitude estimation

Abstract

We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For $\beta \in (0,1]$, our algorithms require $N=\tilde{O}(\frac{1}{{\epsilon }^{1+\beta }})$ oracle calls and require the oracle to be called sequentially $D=O(\frac{1}{{\epsilon }^{1-\beta }})$ times to perform amplitude estimation within additive error $\epsilon$. These algorithms interpolate between the classical algorithm $(\beta =1)$ and the standard quantum algorithm ($\beta =0$) and achieve a tradeoff $ND=O(1/{\epsilon }^2)$. These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits. The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for $\beta \in (0,1]$ and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete $\beta =q/k$ where $k\ge 2$ is the number of distinct coprime moduli used by the algorithm and $1\le q\le k-1$, and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Quantum Sub-Gaussian Mean Estimator
• Prospects and challenges of quantum finance
• An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
• Lower Bounds for Parallel Quantum Counting

Cited by in corpus (36)

• Quantum computing for finance
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Early Fault-Tolerant Quantum Computing
• Variational quantum amplitude estimation
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
• Efficient quantum readout-error mitigation for sparse measurement outcomes of near-term quantum devices
• Multivariate trace estimation in constant quantum depth
• Amplitude Estimation from Quantum Signal Processing
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Quantum algorithm for credit valuation adjustments
• Quantum Monte Carlo for Economics: Stress Testing and Macroeconomic Deep Learning
• Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
• Noisy quantum amplitude estimation without noise estimation
• Option pricing under stochastic volatility on a quantum computer
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach
• Noise-Aware Quantum Amplitude Estimation
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Quantum Computing for Data Centric Engineering and Science
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications
• Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits
• Bayesian Quantum Amplitude Estimation
• Noise tailoring for Robust Amplitude Estimation
• Quantum-enhanced mean value estimation via adaptive measurement
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Conditional Generative Models for Learning Stochastic Processes
• Reducing runtime and error in VQE using deeper and noisier quantum circuits
• Efficient quantum algorithm for weighted partial sums and numerical integration
• Classical post-processing approach for quantum amplitude estimation
• Making the cut: two methods for breaking down a quantum algorithm
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• On the bias in iterative quantum amplitude estimation
• Quantum algorithm for anisotropic diffusion and convection equations with vector norm scaling