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.