论文标题
稳健的量子最小发现，并应用假设选择
Robust quantum minimum finding with an application to hypothesis selection
论文作者
论文摘要
我们考虑使用嘈杂的比较器在长度$ n $列表中找到最小元素的问题。噪声的建模如下：给定两个元素进行比较，如果元素的值通过元素上定义的某些公制的元素差异至少$α$不同，则将正确进行比较；如果元素的值比$α$接近，则比较结果不受任何保证。我们证明了一种噪声量子最小发现的量子算法，可保留无噪声情况的二次加速：我们的算法在时间上运行$ \ tilde o（\ sqrt {\ sqrt {n（n（1+δ）}）$，其中$δ$在$上是$ neult of the Interm y Internal $ n Intertim $ n Intertim $ nifter $ nifter $ nifter $ nift y Intufim $ nift y Intudal $ nift y Intufim $ actim youttim youttim youttim $ coutim youttim $ cout。概率。我们的嘈杂比较器模型是由假设选择问题的动机，在给定一组已知的候选概率分布和来自未知目标分布的样本中，人们试图输出某些候选分布分布$ O（\ varepsilon）$ - 接近未知目标。经典阵线上的许多工作都致力于加快经典假设选择的运行时间，从$ O（n^2）$到$ O（n）$，部分是通过使用统计基础（例如Scheffé测试）的。假设经典数据访问的量子甲骨文概括并应用了我们的噪声量子最小找到算法，我们将此运行时间用于sublinear ecmime。最终的预期运行时间为$ \ tilde o（\ sqrt {n（1+δ）}）$，其$ O（\ log n）$来自未知分布的样本复杂性与经典算法。我们预计，在比较器（可能是另一种量子或经典算法）的情况下，稳健的量子最小找到是对算法的有用构建块，或者是限制或遭受一些不确定性的分辨率。
We consider the problem of finding the minimum element in a list of length $N$ using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least $α$ by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than $α$, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time $\tilde O(\sqrt{N (1+Δ)})$, where $Δ$ is an upper-bound on the number of elements within the interval $α$, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of $N$ known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution $O(\varepsilon)$-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from $O(N^2)$ to $O(N)$, in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is $\tilde O( \sqrt{N(1+Δ)})$, with the same $O(\log N)$ sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.
