Low depth algorithms for quantum amplitude estimation

Tudor Giurgica-Tiron2,3, Iordanis Kerenidis1,5, Farrokh Labib2,4, Anupam Prakash1, and William Zeng2

1QC Ware Corp., Palo Alto, USA and Paris, France.
2Goldman, Sachs & Co., New York, USA.
3Stanford University, Palo Alto, USA.
4CWI Amsterdam, Netherlands.
5CNRS, Université Paris, France.

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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 [24]. 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.

Amplitude estimation (AE) is one of the fundamental quantum algorithms that enables quantum computers to achieve a quadratic speedup over classical algorithms for several statistical estimation tasks. Amplitude estimation also underlies quantum speedups for quantum Monte Carlo methods.

The standard AE algorithm requires $O(1/\epsilon)$ queries to an oracle circuit that is sequentially run $O(1/\epsilon)$ times in order to obtain an $O(\epsilon)$ accuracy. In this work, we address the question of the speedups in the near term setting where the quantum computer is limited in the depth for queries made to the oracle. We a provide provably correct algorithm that achieves a tradeoff of the form $O(ND) = O(1/\epsilon^{2})$ where $N$ is the total number of oracle queries and $D$ the maximum depth of the query.

The results demonstrate the possibility of a $D$-fold speedup over classical algorithms when the quantum computer is able to query the oracle at depth $D$. The new algorithmic idea is to leverage the Chinese remainder theorem to boost the precision of the AE estimates.

► BibTeX data

► References

[1] 4 S. Aaronson and P. Rall, ``Quantum approximate counting, simplified,'' in Symposium on Simplicity in Algorithms. SIAM, 2020, pp. 24–32. [Online]. Available: https:/​/​dx.doi.org/​10.1137/​1.9781611976014.5 0pt.

[2] D. S. Abrams and C. P. Williams, ``Fast quantum algorithms for numerical integrals and stochastic processes,'' arXiv:quant-ph/​9908083, 1999.

[3] 4 A. Ambainis, ``Variable time amplitude amplification and quantum algorithms for linear algebra problems,'' in STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), vol. 14. LIPIcs, 2012, pp. 636–647. [Online]. Available: https:/​/​dx.doi.org/​10.4230/​LIPIcs.STACS.2012.636 0pt.

[4] A. Bouland, W. van Dam, H. Joorati, I. Kerenidis, and A. Prakash, ``Prospects and challenges of quantum finance,'' arXiv preprint arXiv:2011.06492, 2020.

[5] G. Brassard, F. Dupuis, S. Gambs, and A. Tapp, ``An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance,'' arXiv:1106.4267, 2011.

[6] 4 G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, ``Quantum amplitude amplification and estimation,'' Contemporary Mathematics, vol. 305, pp. 53–74, 2002. [Online]. Available: https:/​/​dx.doi.org/​10.1090/​conm/​305/​05215 0pt.

[7] 4 G. Brassard, P. Høyer, and A. Tapp, ``Quantum counting,'' in International Colloquium on Automata, Languages, and Programming. Springer, 1998, pp. 820–831. [Online]. Available: https:/​/​dx.doi.org/​10.1007/​BFb0055105 0pt.

[8] P. Burchard, ``Lower bounds for parallel quantum counting,'' arXiv preprint arXiv:1910.04555, 2019.

[9] P. Erdös and J. L. Selfridge, ``Complete prime subsets of consecutive integers,'' Proceedings of the Manitoba Conference on Numerical Mathematics, Winnipeg, p. 13, 1971.

[10] 4 C. Ferrie, C. E. Granade, and D. G. Cory, ``How to best sample a periodic probability distribution, or on the accuracy of hamiltonian finding strategies,'' Quantum Information Processing, vol. 12, no. 1, pp. 611–623, 2013. [Online]. Available: https:/​/​dx.doi.org/​10.1007/​s11128-012-0407-6 0pt.

[11] 4 D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, ``Iterative quantum amplitude estimation,'' arXiv preprint arXiv:1912.05559, 2019. [Online]. Available: https:/​/​dx.doi.org/​10.1038/​s41534-021-00379-1 0pt.

[12] 4 L. K. Grover, ``A framework for fast quantum mechanical algorithms,'' in Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, pp. 53–62. [Online]. Available: https:/​/​dx.doi.org/​10.1145/​276698.276712 0pt.

[13] Y. Hamoudi and F. Magniez, ``Quantum Chebyshev's inequality and applications,'' in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

[14] 4 A. W. Harrow, A. Hassidim, and S. Lloyd, ``Quantum algorithm for linear systems of equations,'' Physical review letters, vol. 103, no. 15, p. 150502, 2009. [Online]. Available: https:/​/​dx.doi.org/​10.1007/​978-3-642-27848-8_771-1 0pt.

[15] C. Hipp and R. Michel, ``On the Bernstein-v. Mises approximation of posterior distributions,'' The Annals of Statistics, pp. 972–980, 1976.

[16] 4 W. Hoeffding, ``Probability inequalities for sums of bounded random variables,'' in The collected works of Wassily Hoeffding. Springer, 1994, pp. 409–426. [Online]. Available: https:/​/​doi.org/​10.2307/​2282952 0pt.

[17] 4 S. Jeffery, F. Magniez, and R. De Wolf, ``Optimal parallel quantum query algorithms,'' Algorithmica, vol. 79, no. 2, pp. 509–529, 2017. [Online]. Available: https:/​/​dx.doi.org/​10.1007/​s00453-016-0206-z 0pt.

[18] I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, ``q-means: A quantum algorithm for unsupervised machine learning,'' Proceedings of Neural Information Processing Systems (NeurIPS), 2019.

[19] A. Y. Kitaev, ``Quantum measurements and the abelian stabilizer problem,'' arXiv preprint quant-ph/​9511026, 1995.

[20] D. E. Koh, G. Wang, P. D. Johnson, and Y. Cao, ``A framework for engineering quantum likelihood functions for expectation estimation,'' arXiv preprint arXiv:2006.09349, 2020.

[21] 4 T. Li and X. Wu, ``Quantum query complexity of entropy estimation,'' IEEE Transactions on Information Theory, vol. 65, no. 5, pp. 2899–2921, 2018. [Online]. Available: https:/​/​dx.doi.org/​10.1109/​TIT.2018.2883306 0pt.

[22] 4 A. Montanaro, ``Quantum speedup of Monte Carlo methods,'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 471, no. 2181, p. 20150301, 2015. [Online]. Available: https:/​/​dx.doi.org/​10.1098/​rspa.2015.0301 0pt.

[23] 4 J. Preskill, ``Quantum computing in the NISQ era and beyond,'' Quantum, vol. 2, p. 79, 2018. [Online]. Available: https:/​/​dx.doi.org/​10.22331/​q-2018-08-06-79 0pt.

[24] 4 Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, ``Amplitude estimation without phase estimation,'' Quantum Information Processing, vol. 19, no. 2, p. 75, 2020. [Online]. Available: https:/​/​dx.doi.org/​10.1007/​s11128-019-2565-2 0pt.

[25] 4 T. Tanaka, Y. Suzuki, S. Uno, R. Raymond, T. Onodera, and N. Yamamoto, ``Amplitude estimation via maximum likelihood on noisy quantum computer,'' arXiv preprint arXiv:2006.16223, 2020. [Online]. Available: https:/​/​dx.doi.org/​10.1007/​s11128-021-03215-9 0pt.

[26] 4 D. Wang, O. Higgott, and S. Brierley, ``Accelerated variational quantum eigensolver,'' Physical review letters, vol. 122, no. 14, p. 140504, 2019. [Online]. Available: https:/​/​doi.org/​10.1103/​PhysRevLett.122.140504 0pt.

[27] 4 N. Wiebe, A. Kapoor, and K. M. Svore, ``Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning,'' Quantum Information & Computation, vol. 15, no. 3-4, pp. 316–356, 2015. [Online]. Available: https:/​/​dx.doi.org/​10.26421/​QIC15.3-4-7 0pt.

[28] 4 C. Zalka, ``Grover's quantum searching algorithm is optimal,'' Physical Review A, vol. 60, no. 4, p. 2746, 1999. [Online]. Available: https:/​/​dx.doi.org/​10.1103/​PhysRevA.60.2746 0pt.

Cited by

[1] Adam Callison and Nicholas Chancellor, "Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond", Physical Review A 106 1, 010101 (2022).

[2] Tudor Giurgica-Tiron, Sonika Johri, Iordanis Kerenidis, Jason Nguyen, Neal Pisenti, Anupam Prakash, Ksenia Sosnova, Ken Wright, and William Zeng, "Low-depth amplitude estimation on a trapped-ion quantum computer", Physical Review Research 4 3, 033034 (2022).

[3] Bo Yang, Rudy Raymond, and Shumpei Uno, "Efficient quantum readout-error mitigation for sparse measurement outcomes of near-term quantum devices", Physical Review A 106 1, 012423 (2022).

[4] Koichi Miyamoto, Gonzalo Morrás, Takahiro S. Yamamoto, Sachiko Kuroyanagi, and Savvas Nesseris, "Gravitational wave matched filtering by quantum Monte Carlo integration and quantum amplitude amplification", Physical Review Research 4 3, 033150 (2022).

[5] Koichi Miyamoto, "Quantum algorithm for calculating risk contributions in a credit portfolio", arXiv:2201.11394, EPJ Quantum Technology 9 1, 32 (2022).

[6] Steven Herbert, "Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth", Quantum 6, 823 (2022).

[7] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).

[8] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia, and Yuri Alexeev, "A Survey of Quantum Computing for Finance", arXiv:2201.02773.

[9] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", arXiv:2110.13180.

[10] Prasanth Shyamsundar, "Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation", arXiv:2102.04975.

[11] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner, and William J. Zeng, "A Threshold for Quantum Advantage in Derivative Pricing", arXiv:2012.03819.

[12] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini, and Michael Lubasch, "Variational quantum amplitude estimation", arXiv:2109.03687.

[13] Javier Alcazar, Andrea Cadarso, Amara Katabarwa, Marta Mauri, Borja Peropadre, Guoming Wang, and Yudong Cao, "Quantum algorithm for credit valuation adjustments", New Journal of Physics 24 2, 023036 (2022).

[14] Amara Katabarwa, Alex Kunitsa, Borja Peropadre, and Peter Johnson, "Reducing runtime and error in VQE using deeper and noisier quantum circuits", arXiv:2110.10664.

[15] M. C. Braun, T. Decker, N. Hegemann, and S. F. Kerstan, "Error Resilient Quantum Amplitude Estimation from Parallel Quantum Phase Estimation", arXiv:2204.01337.

[16] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", arXiv:2105.11889.

[17] Jonas Landman, "Quantum Algorithms for Unsupervised Machine Learning and Neural Networks", arXiv:2111.03598.

[18] Tomoki Tanaka, Shumpei Uno, Tamiya Onodera, Naoki Yamamoto, and Yohichi Suzuki, "Noisy quantum amplitude estimation without noise estimation", Physical Review A 105 1, 012411 (2022).

[19] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", arXiv:2207.08628.

[20] Rhea Parekh, Andrea Ricciardi, Ahmed Darwish, and Stephen DiAdamo, "Quantum Algorithms and Simulation for Parallel and Distributed Quantum Computing", arXiv:2106.06841.

[21] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini, "Quantum tomography using state-preparation unitaries", arXiv:2207.08800.

[22] Koichi Miyamoto, "Bermudan option pricing by quantum amplitude estimation and Chebyshev interpolation", arXiv:2108.09014.

[23] Alberto Manzano, Daniele Musso, Álvaro Leitao, Andrés Gómez, Carlos Vázquez, Gustavo Ordóñez, and María Rodríguez-Nogueiras, "Quantum Arithmetic for Directly Embedded Arrays", arXiv:2107.13872.

[24] Koichi Miyamoto, "Quantum algorithms for numerical differentiation of expected values with respect to parameters", Quantum Information Processing 21 3, 109 (2022).

[25] Joran van Apeldoorn and Tijn de Vos, "A Framework for Distributed Quantum Queries in the CONGEST Model", arXiv:2202.10969.

[26] Amit Saha, Turbasu Chatterjee, Anupam Chattopadhyay, and Amlan Chakrabarti, "Intermediate Qutrit-based Improved Quantum Arithmetic Operations with Application on Financial Derivative Pricing", arXiv:2205.15822.

The above citations are from Crossref's cited-by service (last updated successfully 2022-12-08 08:30:18) and SAO/NASA ADS (last updated successfully 2022-12-08 08:30:19). The list may be incomplete as not all publishers provide suitable and complete citation data.