Low depth algorithms for quantum amplitude estimation
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.
| Published: | 2022-06-27, volume 6, page 745 |
| Eprint: | arXiv:2012.03348v2 |
| Doi: | https://doi.org/10.22331/q-2022-06-27-745 |
| Citation: | Quantum 6, 745 (2022). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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 [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.
Popular summary
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.
https://doi.org/10.1137/1.9781611976014.5
[2] D. S. Abrams and C. P. Williams, ``Fast quantum algorithms for numerical integrals and stochastic processes,'' arXiv:quant-ph/9908083, 1999.
arXiv:quant-ph/9908083
[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.
https://doi.org/10.4230/LIPIcs.STACS.2012.636
[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.
arXiv:2011.06492
[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.
arXiv:1106.4267
[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.
https://doi.org/10.1090/conm/305/05215
[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.
https://doi.org/10.1007/BFb0055105
[8] P. Burchard, ``Lower bounds for parallel quantum counting,'' arXiv preprint arXiv:1910.04555, 2019.
arXiv:1910.04555
[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.
https://doi.org/10.1007/s11128-012-0407-6
[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.
https://doi.org/10.1038/s41534-021-00379-1
arXiv:1912.05559
[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.
https://doi.org/10.1145/276698.276712
[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.
https://doi.org/10.1007/978-3-642-27848-8_771-1
[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.
https://doi.org/10.2307/2282952
[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.
https://doi.org/10.1007/s00453-016-0206-z
[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.
arXiv:quant-ph/9511026
[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.
arXiv:2006.09349
[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.
https://doi.org/10.1109/TIT.2018.2883306
[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.
https://doi.org/10.1098/rspa.2015.0301
[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.
https://doi.org/10.22331/q-2018-08-06-79
[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.
https://doi.org/10.1007/s11128-019-2565-2
[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.
https://doi.org/10.1007/s11128-021-03215-9
arXiv:2006.16223
[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.
https://doi.org/10.1103/PhysRevLett.122.140504
[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.
https://doi.org/10.26421/QIC15.3-4-7
[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.
https://doi.org/10.1103/PhysRevA.60.2746
Cited by
[1] Marco Maronese, Massimiliano Incudini, Luca Asproni, and Enrico Prati, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 554 (2023) ISBN:979-8-3503-4323-6.
[2] Duarte Magano and Miguel Murça, "Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations", Physical Review A 106 6, 062419 (2022).
[3] Qiyao Liang, Yiqing Zhou, Archismita Dalal, and Peter Johnson, "Modeling the performance of early fault-tolerant quantum algorithms", Physical Review Research 6 2, 023118 (2024).
[4] Thais L. Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", Scientific Reports 13 1, 18258 (2023).
[5] Sohum Thakkar, Skander Kazdaghli, Natansh Mathur, Iordanis Kerenidis, André J. Ferreira–Martins, and Samurai Brito, "Improved financial forecasting via quantum machine learning", Quantum Machine Intelligence 6 1, 27 (2024).
[6] 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).
[7] Marco Maronese, Massimiliano Incudini, Luca Asproni, and Enrico Prati, "The Quantum Amplitude Estimation Algorithms on Near-Term Devices: A Practical Guide", Quantum Reports 6 1, 1 (2023).
[8] Yihui Quek, Eneet Kaur, and Mark M. Wilde, "Multivariate trace estimation in constant quantum depth", Quantum 8, 1220 (2024).
[9] Zoltán Udvarnoki, Gábor Fáth, and Norbert Fogarasi, "Quantum advantage of Monte Carlo option pricing", Journal of Physics Communications 7 5, 055001 (2023).
[10] Koichi Miyamoto, "Quantum algorithm for calculating risk contributions in a credit portfolio", EPJ Quantum Technology 9 1, 32 (2022).
[11] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).
[12] 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).
[13] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).
[14] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).
[15] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).
[16] 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).
[17] Sascha Wilkens and Joe Moorhouse, "Quantum computing for financial risk measurement", Quantum Information Processing 22 1, 51 (2023).
[18] Salvatore Certo, Anh Pham, Nicolas Robles, and Andrew Vlasic, "Conditional generative models for learning stochastic processes", Quantum Machine Intelligence 5 2, 42 (2023).
[19] Miguel Murça, Duarte Magano, and Yasser Omar, "Two methods for breaking down a quantum algorithm", Physical Review A 109 2, 022412 (2024).
[20] 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).
[21] Steven Herbert, "Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth", Quantum 6, 823 (2022).
[22] Archismita Dalal and Amara Katabarwa, "Noise tailoring for robust amplitude estimation", New Journal of Physics 25 2, 023015 (2023).
[23] 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, (2022).
[24] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner, and William J. Zeng, "A Threshold for Quantum Advantage in Derivative Pricing", Quantum 5, 463 (2021).
[25] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini, and Michael Lubasch, "Variational quantum amplitude estimation", Quantum 6, 670 (2022).
[26] Amara Katabarwa, Alex Kunitsa, Borja Peropadre, and Peter Johnson, "Reducing runtime and error in VQE using deeper and noisier quantum circuits", arXiv:2110.10664, (2021).
[27] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini, "Quantum tomography using state-preparation unitaries", arXiv:2207.08800, (2022).
[28] Prasanth Shyamsundar, "Non-Boolean quantum amplitude amplification and quantum mean estimation", Quantum Information Processing 22 12, 423 (2023).
[29] Rhea Parekh, Andrea Ricciardi, Ahmed Darwish, and Stephen DiAdamo, "Quantum Algorithms and Simulation for Parallel and Distributed Quantum Computing", arXiv:2106.06841, (2021).
[30] 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).
[31] 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).
[32] Jonas Landman, "Quantum Algorithms for Unsupervised Machine Learning and Neural Networks", arXiv:2111.03598, (2021).
[33] M. C. Braun, T. Decker, N. Hegemann, S. F. Kerstan, C. Maier, and J. Ulmanis, "Quantum amplitude estimation with error mitigation for time-evolving probabilistic networks", arXiv:2303.16588, (2023).
[34] Koichi Miyamoto, "Quantum algorithm for calculating risk contributions in a credit portfolio", arXiv:2201.11394, (2022).
[35] Koichi Miyamoto, "Bermudan option pricing by quantum amplitude estimation and Chebyshev interpolation", arXiv:2108.09014, (2021).
[36] 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, (2021).
[37] M. C. Braun, T. Decker, N. Hegemann, and S. F. Kerstan, "Error Resilient Quantum Amplitude Estimation from Parallel Quantum Phase Estimation", arXiv:2204.01337, (2022).
[38] 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, (2022).
[39] Joran van Apeldoorn and Tijn de Vos, "A Framework for Distributed Quantum Queries in the CONGEST Model", arXiv:2202.10969, (2022).
[40] Koichi Miyamoto, "Quantum algorithms for numerical differentiation of expected values with respect to parameters", Quantum Information Processing 21 3, 109 (2022).
The above citations are from Crossref's cited-by service (last updated successfully 2024-05-12 07:56:03) and SAO/NASA ADS (last updated successfully 2024-05-12 07:56:05). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.