Abstract
Quantum random sampling schemes are used to demonstrate the computational advantage of quantum computers over classical systems in current-day experimental hardware. However, their outputs are extremely difficult to verify and it has been called into question whether they can yield a scalable quantum advantage. In this talk, I will present a new model of computation, Bell sampling, wherein two copies of a state prepared by a quantum circuit are measured in the transversal Bell basis. We give complexity-theoretic evidence that it is classically intractable to perform Bell sampling from random quantum circuits. Importantly, the Bell samples allow for some efficient tests of the sampled distribution. I will raise the question whether it might be more challenging to spoof Bell sampling and whether Bell sampling might be more noise-robust than standard-basis sampling. Above all, this talk will be an invitation to further study Bell sampling as a model of quantum computation.