Mean estimation when you have the source code; or, quantum Monte Carlo methods

DOI10.1137/1.9781611977554.CH44arXiv2208.07544MaRDI QIDQ6407965FDOQ6407965

Robin Kothari, Ryan O'Donnell

Publication date: 16 August 2022

Abstract: Suppose $$ is a real random variable, and one is given access to ``the code that generates it (for example, a randomized or quantum circuit whose output is $$). We give a quantum procedure that runs the code $O(n)$ times and returns an estimate $$ for $$ that with high probability satisfies $$, where $$. This dependence on $n$ is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse $$. Our method improves upon previous works, which either made additional assumptions about $$, and/or assumed the algorithm knew an a priori bound on $sigma$, and/or used additional logarithmic factors beyond $O(n)$. The central subroutine for our result is essentially Grover's algorithm but with complex phases.ally Grover's algorithm but with complex phases.

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Mean estimation when you have the source code; or, quantum Monte Carlo methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407965)