2026-08-02T16:14:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14004 2024-03-06T10:53:23Z ddc:004 open_access

Quantum Probability Oracles & Multidimensional Amplitude Estimation van Apeldoorn, Joran quantum algorithms amplitude estimation monte carlo 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joran van Apeldoorn 2021 Is Part Of LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2021.9 urn:nbn:de:0030-drops-140046 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.9 eng https://creativecommons.org/licenses/by/4.0/legalcode