论文标题
测试和学习量子队几乎是最佳的
Testing and Learning Quantum Juntas Nearly Optimally
论文作者
论文摘要
我们考虑了测试和学习量子$ k $ -juntas的问题：$ n $ qubit的统一矩阵，这些矩阵仅在$ n $ Qubits的$ k $上进行非凡起作用，其余的身份。作为我们的主要算法结果，我们给出了（a）$ \ widetilde {o}（\ sqrt {k}）$ - 查询可以将量子$ k $ -juntas与每个量子级矩阵区分开的量子量算法，这些算法与每个量子级别的单位矩阵远。 （b）a $ o（4^k）$ - 查询算法学习量子$ k $ -juntas。我们为测试量子$ k $ -juntas和学习量子$ k $ -juntas的上限补充，分别为$ω（\ sqrt {k}）$和$ω（\ frac {4^k} {k} {k}）$的接近匹配下限。我们的技术是傅立叶分析，并利用了量子对单位的影响的概念。
We consider the problem of testing and learning quantum $k$-juntas: $n$-qubit unitary matrices which act non-trivially on just $k$ of the $n$ qubits and as the identity on the rest. As our main algorithmic results, we give (a) a $\widetilde{O}(\sqrt{k})$-query quantum algorithm that can distinguish quantum $k$-juntas from unitary matrices that are "far" from every quantum $k$-junta; and (b) a $O(4^k)$-query algorithm to learn quantum $k$-juntas. We complement our upper bounds for testing quantum $k$-juntas and learning quantum $k$-juntas with near-matching lower bounds of $Ω(\sqrt{k})$ and $Ω(\frac{4^k}{k})$, respectively. Our techniques are Fourier-analytic and make use of a notion of influence of qubits on unitaries.
