Quantum Advantage in Sampling

Quantum advantage in sampling refers to the ability of a quantum computer to efficiently draw samples from a probability distribution that no classical computer can sample from in a reasonable time. Unlike decision problems (which have yes/no answers), sampling problems ask for random outputs drawn according to a specific distribution. The leading experimental claims of quantum supremacy are all sampling-based, including Google’s random circuit sampling (2019) and various boson sampling experiments.

The computational argument

The theoretical case for quantum sampling advantage rests on complexity-theoretic arguments:

1. A random quantum circuit on $n$ qubits produces output probabilities proportional to $|\langle x|U|0^n\rangle|^2$, where $U$ is the circuit unitary. For a sufficiently random $U$, these probabilities are distributed according to the Porter-Thomas distribution.

2. Computing individual output probabilities exactly is #P-hard (at least as hard as counting problems). Under plausible complexity-theoretic conjectures (the non-collapse of the polynomial hierarchy), no classical algorithm can sample from this distribution efficiently.

3. A quantum computer produces samples from this distribution naturally, simply by executing the circuit and measuring.

The logical structure is: if a classical computer could efficiently sample from the same distribution, it would imply unlikely collapses in the complexity-theoretic hierarchy.

Google’s random circuit sampling

Google’s 2019 Sycamore experiment claimed quantum supremacy by sampling from random circuits on 53 qubits with depth 20. They estimated that their quantum processor completed the sampling task in 200 seconds, while the best classical simulation would require 10,000 years on a state-of-the-art supercomputer.

This claim was subsequently challenged:

• IBM argued that with sufficient disk storage, a classical supercomputer could complete the task in 2.5 days
• Subsequent classical algorithms using tensor network methods further reduced the classical simulation time
• The cross-entropy benchmark used to verify the samples has been debated as a measure of computational advantage

Despite these challenges, the experiment demonstrated that quantum processors can operate in a regime where classical simulation is extremely costly, even if the exact boundary of “impossibility” is debatable.

Boson sampling

Boson sampling, proposed by Aaronson and Arkhipov in 2011, is a sampling problem based on the output distribution of identical photons passing through a linear optical interferometer. The output probabilities are related to permanents of complex matrices, which are #P-hard to compute. Chinese groups (USTC) demonstrated boson sampling with up to 113 photons using Gaussian boson sampling, claiming quantum advantage.

Limitations of sampling advantages

Sampling advantages face several criticisms:

• No direct utility: The sampled distributions are not known to have practical applications. This is “computational supremacy” rather than practical advantage.
• Verification difficulty: Verifying that the quantum device is correctly sampling from the target distribution requires exponential classical computation for large instances, creating a circular problem.
• Noise sensitivity: Real quantum devices produce noisy samples. The fidelity decreases exponentially with circuit depth and qubit count, and at some noise level the output becomes classically simulable.
• Moving goalposts: As classical simulation algorithms improve, the claimed advantage shrinks or disappears for specific instances.

Why it matters for learners

Sampling-based quantum advantage is currently the only experimentally demonstrated form of quantum computational advantage (with appropriate caveats). Understanding both the theoretical foundations and practical limitations helps you evaluate quantum supremacy claims critically. The distinction between sampling advantage (computational complexity argument) and practical advantage (solving a useful problem faster) is one of the most important nuances in the field.

See also

• Quantum Supremacy
• Boson Sampling
• Quantum Advantage Claims
• Quantum Circuit Complexity
• Noisy Intermediate-Scale Quantum