{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T18:20:51Z","timestamp":1781634051222,"version":"3.54.5"},"reference-count":28,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 &#x03B2;<\/mml:mi>&#x2208;<\/mml:mo>(<\/mml:mo>0<\/mml:mn>,<\/mml:mo>1<\/mml:mn>]<\/mml:mo><\/mml:math>, our algorithms require N<\/mml:mi>=<\/mml:mo>O<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>(<\/mml:mo>1<\/mml:mn>&#x03F5;<\/mml:mi>1<\/mml:mn>+<\/mml:mo>&#x03B2;<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mfrac>)<\/mml:mo><\/mml:math> oracle calls and require the oracle to be called sequentially D<\/mml:mi>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>&#x03F5;<\/mml:mi>1<\/mml:mn>&#x2212;<\/mml:mo>&#x03B2;<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mfrac>)<\/mml:mo><\/mml:math> times to perform amplitude estimation within additive error &#x03F5;<\/mml:mi><\/mml:math>. These algorithms interpolate between the classical algorithm (<\/mml:mo>&#x03B2;<\/mml:mi>=<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math> and the standard quantum algorithm (&#x03B2;<\/mml:mi>=<\/mml:mo>0<\/mml:mn><\/mml:math>) and achieve a tradeoff N<\/mml:mi>D<\/mml:mi>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>2<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>. 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 &#x03B2;<\/mml:mi>&#x2208;<\/mml:mo>(<\/mml:mo>0<\/mml:mn>,<\/mml:mo>1<\/mml:mn>]<\/mml:mo><\/mml:math> 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 &#x03B2;<\/mml:mi>=<\/mml:mo>q<\/mml:mi>\/<\/mml:mo><\/mml:mrow>k<\/mml:mi><\/mml:math> where k<\/mml:mi>&#x2265;<\/mml:mo>2<\/mml:mn><\/mml:math> is the number of distinct coprime moduli used by the algorithm and 1<\/mml:mn>&#x2264;<\/mml:mo>q<\/mml:mi>&#x2264;<\/mml:mo>k<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:math>, 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.<\/jats:p>","DOI":"10.22331\/q-2022-06-27-745","type":"journal-article","created":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T14:25:46Z","timestamp":1656339946000},"page":"745","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":52,"title":["Low depth algorithms for quantum amplitude estimation"],"prefix":"10.22331","volume":"6","author":[{"given":"Tudor","family":"Giurgica-Tiron","sequence":"first","affiliation":[{"name":"Goldman, Sachs & Co., New York, USA."},{"name":"Stanford University, Palo Alto, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Iordanis","family":"Kerenidis","sequence":"additional","affiliation":[{"name":"QC Ware Corp., Palo Alto, USA and Paris, France."},{"name":"CNRS, Universit\u00e9 Paris, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Farrokh","family":"Labib","sequence":"additional","affiliation":[{"name":"Goldman, Sachs & Co., New York, USA."},{"name":"CWI Amsterdam, Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Prakash","sequence":"additional","affiliation":[{"name":"QC Ware Corp., Palo Alto, USA and Paris, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Zeng","sequence":"additional","affiliation":[{"name":"Goldman, Sachs & Co., New York, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"4 S. Aaronson and P. Rall, ``Quantum approximate counting, simplified,'' in Symposium on Simplicity in Algorithms. SIAM, 2020, pp. 24\u201332. [Online]. Available: https:\/\/dx.doi.org\/10.1137\/1.9781611976014.5 0pt.","DOI":"10.1137\/1.9781611976014.5"},{"key":"1","unstructured":"D. S. Abrams and C. P. Williams, ``Fast quantum algorithms for numerical integrals and stochastic processes,'' arXiv:quant-ph\/9908083, 1999."},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u2013647. [Online]. Available: https:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2012.636 0pt.","DOI":"10.4230\/LIPIcs.STACS.2012.636"},{"key":"3","unstructured":"A. Bouland, W. van Dam, H. Joorati, I. Kerenidis, and A. Prakash, ``Prospects and challenges of quantum finance,'' arXiv preprint arXiv:2011.06492, 2020."},{"key":"4","unstructured":"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."},{"key":"5","doi-asserted-by":"publisher","unstructured":"4 G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, ``Quantum amplitude amplification and estimation,'' Contemporary Mathematics, vol. 305, pp. 53\u201374, 2002. [Online]. Available: https:\/\/dx.doi.org\/10.1090\/conm\/305\/05215 0pt.","DOI":"10.1090\/conm\/305\/05215"},{"key":"6","doi-asserted-by":"publisher","unstructured":"4 G. Brassard, P. H\u00f8yer, and A. Tapp, ``Quantum counting,'' in International Colloquium on Automata, Languages, and Programming. Springer, 1998, pp. 820\u2013831. [Online]. Available: https:\/\/dx.doi.org\/10.1007\/BFb0055105 0pt.","DOI":"10.1007\/BFb0055105"},{"key":"7","unstructured":"P. Burchard, ``Lower bounds for parallel quantum counting,'' arXiv preprint arXiv:1910.04555, 2019."},{"key":"8","unstructured":"P. Erd\u00f6s and J. L. Selfridge, ``Complete prime subsets of consecutive integers,'' Proceedings of the Manitoba Conference on Numerical Mathematics, Winnipeg, p. 13, 1971."},{"key":"9","doi-asserted-by":"publisher","unstructured":"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\u2013623, 2013. [Online]. Available: https:\/\/dx.doi.org\/10.1007\/s11128-012-0407-6 0pt.","DOI":"10.1007\/s11128-012-0407-6"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41534-021-00379-1"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u201362. [Online]. Available: https:\/\/dx.doi.org\/10.1145\/276698.276712 0pt.","DOI":"10.1145\/276698.276712"},{"key":"12","unstructured":"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."},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-3-642-27848-8_771-1"},{"key":"14","doi-asserted-by":"crossref","unstructured":"C. Hipp and R. Michel, ``On the Bernstein-v. Mises approximation of posterior distributions,'' The Annals of Statistics, pp. 972\u2013980, 1976.","DOI":"10.1214\/aos\/1176343595"},{"key":"15","doi-asserted-by":"publisher","unstructured":"4 W. Hoeffding, ``Probability inequalities for sums of bounded random variables,'' in The collected works of Wassily Hoeffding. Springer, 1994, pp. 409\u2013426. [Online]. Available: https:\/\/doi.org\/10.2307\/2282952 0pt.","DOI":"10.2307\/2282952"},{"key":"16","doi-asserted-by":"publisher","unstructured":"4 S. Jeffery, F. Magniez, and R. De Wolf, ``Optimal parallel quantum query algorithms,'' Algorithmica, vol. 79, no. 2, pp. 509\u2013529, 2017. [Online]. Available: https:\/\/dx.doi.org\/10.1007\/s00453-016-0206-z 0pt.","DOI":"10.1007\/s00453-016-0206-z"},{"key":"17","unstructured":"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."},{"key":"18","unstructured":"A. Y. Kitaev, ``Quantum measurements and the abelian stabilizer problem,'' arXiv preprint quant-ph\/9511026, 1995."},{"key":"19","unstructured":"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."},{"key":"20","doi-asserted-by":"publisher","unstructured":"4 T. Li and X. Wu, ``Quantum query complexity of entropy estimation,'' IEEE Transactions on Information Theory, vol. 65, no. 5, pp. 2899\u20132921, 2018. [Online]. Available: https:\/\/dx.doi.org\/10.1109\/TIT.2018.2883306 0pt.","DOI":"10.1109\/TIT.2018.2883306"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1098\/rspa.2015.0301"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/s11128-019-2565-2"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/s11128-021-03215-9"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.122.140504"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u2013356, 2015. [Online]. Available: https:\/\/dx.doi.org\/10.26421\/QIC15.3-4-7 0pt.","DOI":"10.26421\/QIC15.3-4-7"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.60.2746"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-27-745\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T14:25:51Z","timestamp":1656339951000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-27-745\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,27]]},"references-count":28,"URL":"https:\/\/doi.org\/10.22331\/q-2022-06-27-745","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,27]]},"article-number":"745"}}