Quantum probability oracles & multidimensional amplitude estimation
Presented at the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021 (July 2021), Virtual, Online
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 ℓ1-norm (the total variation distance) estimation and a Õ(√n/ε) query algorithm for ℓ2-norm. We also show that these results are optimal up to logarithmic factors.
|Leibniz International Proceedings in Informatics|
|Quantum Software Consortium|
|16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
van Apeldoorn, J.T.S. (2021). Quantum probability oracles & multidimensional amplitude estimation. In Conference on the Theory of Quantum Computation, Communication and Cryptography (pp. 9:1–9:11). doi:10.4230/LIPIcs.TQC.2021.9