Know What's Happening in Technology

Quantum Algorithm Beats Classical Tools on Complement Sampling Tasks

Researchers at Quantinuum and QuSoft have introduced a quantum algorithm that solves the complement sampling problem using a single quantum sample, a task that classically requires on the order of N samples when the subset size is half the universe. The work, published in Physical Review Letters, provides a provable and verifiable quantum advantage in sample complexity rather than computational speed. Experiments on Quantinuum’s H2 trapped‑ion hardware confirmed the theoretical predictions, showing reliable transformation of the quantum state into the complement superposition. The authors suggest the technique could underpin new cryptographic constructions due to its classical hardness.