Low depth algorithms for quantum amplitude estimation
Preprint
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 \geq 2$ is the number of distinct coprime moduli used by the algorithm and $1 \leq q \leq 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.
Keywords
All Related Versions
- Version 1, 2020-12-06, ArXiv
- Version 2, 2022-06-22, ArXiv
- Published version: Quantum, 6, 745.
This publication has 19 references indexed in Scilit:
- Amplitude estimation via maximum likelihood on noisy quantum computerQuantum Information Processing, 2021
- Iterative quantum amplitude estimationnpj Quantum Information, 2021
- Amplitude estimation without phase estimationQuantum Information Processing, 2020
- Optimal Parallel Quantum Query AlgorithmsAlgorithmica, 2016
- Quantum speedup of Monte Carlo methodsProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2015
- Quantum Algorithms for Systems of Linear Equations2015
- How to best sample a periodic probability distribution, or on the accuracy of Hamiltonian finding strategiesQuantum Information Processing, 2012
- Quantum amplitude amplification and estimation2002
- Grover’s quantum searching algorithm is optimalPhysical Review A, 1999
- Quantum counting1998