LIPIcs.TQC.2021.9.pdf
- Filesize: 0.65 MB
- 11 pages
Document
Quantum Probability Oracles & Multidimensional Amplitude Estimation
Author
-
Part of:
Volume:
16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-22
File
Document Identifiers
Acknowledgements
I would like to thank Ronald de Wolf, András Gilyén, Ashley Montanaro, and Srinivasan Arunachalam for insightful discussions and comments. I would also like to thank the TQC2021 reviewers for their useful comments.
Cite As Get BibTex
Joran van Apeldoorn. Quantum Probability Oracles & Multidimensional Amplitude Estimation. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.TQC.2021.9
Abstract
We give a multidimensional version of amplitude estimation. Let p be an n-dimensional probability distribution which can be sampled from using a quantum circuit U_p. We show that all coordinates of p can be estimated up to error ε per coordinate using Õ(1/(ε)) applications of U_p and its inverse. This generalizes the normal amplitude estimation algorithm, which solves the problem for n = 2. Our results also imply a Õ(n/ε) query algorithm for 𝓁₁-norm (the total variation distance) estimation and a Õ(√n/ε) query algorithm for 𝓁₂-norm. We also show that these results are optimal up to logarithmic factors.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
- Theory of computation → Quantum computation theory
Keywords
- quantum algorithms
- amplitude estimation
- monte carlo
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. Earlier version in FOCS'98. URL: https://doi.org/10.1145/502090.502097.
- Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 2002. URL: http://arxiv.org/abs/arXiv:quant-ph/0005055.
- Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross. An optimal algorithm for monte carlo estimation. SIAM Journal on Computing, 29(5):1484-1496, 2000. URL: https://doi.org/10.1137/s0097539797315306.
- András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation, pages 1425-1444. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.87.
- Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng. Low depth algorithms for quantum amplitude estimation, 2020. URL: http://arxiv.org/abs/2012.03348.
- Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Phys. Rev. Lett., 95:050501, July 2005. URL: https://doi.org/10.1103/PhysRevLett.95.050501.
- Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. On learning distributions from their samples. In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1066-1100, Paris, France, 2015. PMLR. URL: http://proceedings.mlr.press/v40/Kamath15.html.
- Shelby Kimmel. Quantum adversary (upper) bound. Chicago Journal of Theoretical Computer Science, 19(1):1-14, 2013. URL: https://doi.org/10.4086/cjtcs.2013.004.
- Ashley Montanaro. Quantum speedup of monte carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. URL: https://doi.org/10.1098/rspa.2015.0301.