论文标题
当您拥有源代码时的平均估计；或，量子蒙特卡洛方法
Mean estimation when you have the source code; or, quantum Monte Carlo methods
论文作者
论文摘要
假设$ \ boldsymbol {y} $是一个真正的随机变量，并且可以访问生成它的``代码''（例如，其输出为$ \ boldsymbol {y} $的随机或量子电路）。我们提供一个量子程序，该过程运行代码$ o（n）$ times，并返回估计$ \ wideHat {\boldsymbolμ} $，for $μ= \ mthrm {e} [\ boldsymbol {y}] $，具有很高的可能性满足了$ | | | | widehat {\boldsymbolμ} -Inglysimentionalsional。 \leqσ/n $，其中$σ= \ mathrm {stddev} [\ boldsymbol {y}] $。对$ n $的这种依赖是量子算法最佳的。可以与经典算法进行比较，后者只能实现二次更差的$ | \ wideHat {\boldsymbolμ} - μ| \leqσ/\ sqrt {n} $。我们的方法改进了以前的作品，该作品要么对$ \ boldsymbol {y} $做出了其他假设，而且/或假定该算法知道$σ$的先验限制，或者/或使用$ O（n）$以上的其他对数因素。我们结果的中心子例程本质上是格罗弗的算法，但具有复杂的阶段。
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μ}$ for $μ= \mathrm{E}[\boldsymbol{y}]$ that with high probability satisfies $|\widehat{\boldsymbolμ} - μ| \leq σ/n$, where $σ= \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μ} - μ| \leq σ/\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 $σ$, 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.
