论文标题
紧密的量子下限以与量子状态进行近似计数
Tight Quantum Lower Bound for Approximate Counting with Quantum States
论文作者
论文摘要
我们证明了Aaronson，Kothari，Kretschmer和Thaler（2020）考虑的计数问题的以下变体的紧密下限。任务是区分输入集$ x \ subseteq [n] $的大小$ k $还是$ k'=（1+ \ varepsilon）k $。我们假设该算法可以访问 *会员资格的Oracle（对于[N] $中的每个$ i \）都可以回答$ i \ in x $中的每个$ i \;和\项目统一叠加$ |ψ_x\ rangle = \ sum_ {i \ in x} | i \ rangle/\ sqrt {| x |} $ a $ x $的元素。此外，我们考虑了算法如何访问此状态的三种不同方式： - 算法可以具有状态$ |ψ_x\ rangle $的副本; - 该算法可以执行反射甲骨文，该反射甲骨文反映了状态$ |ψ_x\ rangle $; - 算法可以执行状态生成的Oracle（或其逆），该Oracle执行转换$ | 0 \ rangle \ mapsto |ψ_x\ rangle $。 没有第二种类型的资源（与$ |ψ_x\ rangle $相关的资源），问题就被牢牢地理解了。 Aaronson等人最近启动了第二种资源对问题的研究。我们完全解决了所有值$ 1/k \ le \ varepsilon \ le 1 $的问题，从而在算法可用的所有类型的资源之间进行了严格的权衡。我们还证明了我们的下限很紧。因此，我们解决了Aaronson等人的主要开放问题。 使用Belovs（2015）的对手的变体证明了下限，并采用对称组的表示理论适用于$ S_N $ -MODULES $ \ MATHBB {C}^{\ binom {\ binom {[n]} \ Mathbb {C} $。
We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler (2020). The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k'=(1+\varepsilon)k$. We assume the algorithm has access to * the membership oracle, which, for each $i\in [n]$, can answer whether $i\in x$, or not; and \item the uniform superposition $|ψ_x\rangle = \sum_{i\in x} |i\rangle/\sqrt{|x|}$ over the elements of $x$. Moreover, we consider three different ways how the algorithm can access this state: - the algorithm can have copies of the state $|ψ_x\rangle$; - the algorithm can execute the reflecting oracle which reflects about the state $|ψ_x\rangle$; - the algorithm can execute the state-generating oracle (or its inverse) which performs the transformation $|0\rangle\mapsto|ψ_x\rangle$. Without the second type of resources (the ones related to $|ψ_x\rangle$), the problem is well-understood. The study of the problem with the second type of resources was recently initiated by Aaronson et al. We completely resolve the problem for all values of $1/k \le \varepsilon\le 1$, giving tight trade-offs between all types of resources available to the algorithm. We also demonstrate that our lower bounds are tight. Thus, we close the main open problems from Aaronson et al. The lower bounds are proven using variants of the adversary bound from Belovs (2015) and employing representation theory of the symmetric group applied to the $S_n$-modules $\mathbb{C}^{\binom{[n]}k}$ and $\mathbb{C}^{\binom{[n]}k}\otimes \mathbb{C}$.
