Provable and verifiable quantum advantage in sample complexity

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 any classical algorithm that succeeds with bounded probability of error requires a number of samples of the order of $N$. This shows that in a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation. We show that the same bound can be lifted to prove average-case hardness, paving the way for demonstrations on noisy intermediate-scale quantum (NISQ) computers. 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.

• View at Publisher

Free Full Text ( Final Version , 295kb )