Provable and Verifiable Quantum Advantage in Sample Complexity

Abstract

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.

Main text: 7 pages, 3 figures. Supplemental material: 18 pages, 3 figures. Published version

References in corpus (12)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Quantum computational advantage using photons
• Quantum fingerprinting
• Solving the sampling problem of the Sycamore quantum circuits
• Learning with Errors is easy with quantum samples
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• A quantum circuit design of AES
• Protecting Expressive Circuits with a Quantum Error Detection Code
• On the Sample Complexity of Quantum Boltzmann Machine Learning
• Spoofing cross entropy measure in boson sampling
• Verifiable Quantum Advantage without Structure