2021-06-22
Quantum probability oracles & multidimensional amplitude estimation
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.4230/LIPIcs.TQC.2021.9 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| 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. (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 |
|
