2026-07-21T20:02:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25304 2026-03-19T13:03:15Z ddc:004 open_access

Unconditional Quantum Advantage for Sampling with Shallow Circuits Bene Watts, Adam Parham, Natalie Circuit Complexity Sampling Separation Shallow Quantum Circuits Unconditional Separations Complexity of Distributions 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 when the number of random input bits given to the classical circuit is bounded. We introduce a distribution D_{n} over {0,1}ⁿ and construct a constant-depth uniform quantum circuit family {C_n}_n such that C_n 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 kn + n^δ i.i.d. Bernouli random variables with entropy 1/k and produces output close to D_{n} in total variation distance has depth Ω(log log n). This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs. The distribution D_n and classical circuit lower bounds are inspired by 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Bene Watts and Natalie Parham 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.17 urn:nbn:de:0030-drops-253048 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode