标题： 补采样：在样本复杂度中的可证明、可验证和NISQ可行的量子优势 显示英文标题

标题： Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity

摘要： 考虑一个包含$N=2^n$个元素的固定宇宙，以及某个大小为$K$的子集上的均匀分布。 给定来自该分布的样本，补集采样的任务是提供来自补集的样本。 我们给出一个简单的量子算法，仅使用一个量子样本——即该子集元素上的均匀叠加的一个副本。 当$K=N/2$时，我们证明该量子算法以概率$1$成功，而经典情况下需要$\Theta(N)$个样本才能以有界误差概率成功。 这表明在样本到样本的设置中，量子计算可以在与经典计算的比较中实现最大的分离。 此外，我们证明可以将同一界限提升以证明平均情况下的难度。 由此可知，在存在单向函数的假设下，补集采样在样本复杂性设置中提供了可证明、可验证且适用于NISQ设备的量子优势。 显示英文摘要

摘要： Consider a fixed universe of $N=2^n$ elements and the uniform distribution over elements of some subset of size $K$. Given samples from this distribution, the task of complement sampling is to provide a sample from the complementary subset. We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset. When $K=N/2$, we show that the quantum algorithm succeeds with probability $1$, whereas classically $\Theta(N)$ samples are required to succeed with bounded probability of error. This shows that in a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation. Moreover, we show that the same bound can be lifted to prove average-case hardness. It follows that under the assumption of the existence of one-way functions, complement sampling gives provable, verifiable and NISQable quantum advantage in a sample complexity setting.