Unconditional Quantum Advantage for Sampling with Shallow Circuits

Abstrakt:

Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes.
We introduce a distribution D_n and give a constant-depth, n qubit, quantum circuit that samples from a distribution close to D_n in total variation distance. For any δ<1 we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input n+n^δ uniformly random bits and produces output close to D_n in total variation distance has depth Ω(loglogn). This gives an unconditional proof that constant-depth quantum circuits can sample from distributions which can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error.
The distribution D_n and classical circuit lower bounds are based on work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.