New proof shows quantum advantage with shallow circuits

Researchers Adam Bene Watts at the Institute for Quantum Computing, University of Waterloo, and Natalie Parham of Columbia University and Perimeter Institute for Theoretical Physics have demonstrated a clear advantage for quantum circuits when sampling from specific probability distributions. This establishes a logarithmic difference in computational depth, even when classical circuits utilize a limited number of input bits; specifically, k times n plus n to the power of delta i.i.d. Bernoulli random variables with entropy 1/k. This work directly addresses a challenge posed by Bravyi, Gosset, and Koenig, confirming quantum advantage extends to input-independent sampling tasks. The researchers published their findings in Quantum, volume 10, page 2188, with DOI 10.22331/q-2026-.…