Mean estimation when you have the source code; or, quantum Monte Carlo methods
Mean estimation when you have the source code; or, quantum Monte Carlo methods
复制标题
DOI：
10.48550/arxiv.2208.07544
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Robin Kothari;R. O'Donnell
中科院分区：
文献类型：
--
作者：
Robin Kothari;R. O'Donnell
假设$\boldSymbol{y}$是一个真实的随机变量，并且允许一个人访问生成它的“代码”(例如，输出为$\boldSymbol{y}$的随机化或量子电路)。我们给出了一个量子过程，它运行代码$O(N)$次，并为$\Mu=\mathm{E}[\boldSymbol{y}]$返回估计$\widehat{\boldSymbol{\Mu}}$，其中$\sigma=\mathm{stddev}[\boldsign{y}]$，其中$\sigma=\mathm{stddev}[\boldSymbol{y}]$。这种对$n$的依赖是量子算法的最佳选择。与经典算法相比，经典算法只能得到二次较差的$|\Widdehat{\boldsign{\Mu}}-\Mu|\leq\sigma/\Sqrt{n}$。我们的方法改进了以前的工作，这些工作要么对$\boldSymbol{y}$做了额外的假设，和/或假设算法知道$\sigma$上的先验界，和/或使用了超过$O(N)$的额外对数因子。我们结果的中心子程序本质上是Grover算法，但具有复杂的阶段。与Grover的算法相同，但具有复杂的阶段。
Suppose $\boldsymbol{y}$ 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 $\boldsymbol{y}$). We give a quantum procedure that runs the code $O(n)$ times and returns an estimate $\widehat{\boldsymbol{\mu}}$ for $\mu = \mathrm{E}[\boldsymbol{y}]$ that with high probability satisfies $|\widehat{\boldsymbol{\mu}} - \mu| \leq \sigma/n$, where $\sigma = \mathrm{stddev}[\boldsymbol{y}]$. This dependence on $n$ is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse $|\widehat{\boldsymbol{\mu}} - \mu| \leq \sigma/\sqrt{n}$. Our method improves upon previous works, which either made additional assumptions about $\boldsymbol{y}$, 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.