2025/02/12 by Marcello Benedetti, Harry Buhrman, Benedetti, Marcello +3 · 1 citation
Computer Science · #Computational Drug Discovery Methods #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2502.08721
openalex publication_date 2025/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a fixed universe of N=2n 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.