论文标题
量子近似计数，具有非适应性栅栏的迭代
Quantum Approximate Counting with Nonadaptive Grover Iterations
论文作者
论文摘要
近似计数是指我们给出了对函数$ f的查询访问$ f的问题：[n] \ to \ {0,1 \} $，我们希望估算$ k =＃\ {x：f（x）= 1 \} $，以在$ 1+ε$（具有很高的可能性）之内，同时最小化Queries的数量。在量子设置中，可以使用$ o \ left（\ min \ left（\ sqrt {n/ε}，\ sqrt {n/k}/ε\ right）\ right）$查询来完成近似计数。最近已经证明，这可以通过仅使用“ Grover Etererations”的简单算法来实现。但是，该算法可以适应这些迭代。出于对计算简单性的关注，我们考虑了使用适应性有限的循环迭代的算法。我们表明，仅使用非适应性栅格迭代的算法可以实现$ o \ left（\ sqrt {n/ε} \ right）$查询复杂性，这很紧。
Approximate Counting refers to the problem where we are given query access to a function $f : [N] \to \{0,1\}$, and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of $1+ε$ (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with $O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $O\left(\sqrt{N/ε}\right)$ query complexity, which is tight.
