2026-07-23T19:58:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25360 2026-03-19T13:04:01Z ddc:004 open_access

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals Grier, Daniel Kane, Daniel M. Morris, Jackson Ostuni, Anthony Wu, Kewen Shallow circuits sampling quantum circuits We construct a family of distributions {𝒟_n}_n with 𝒟_n over {0, 1}ⁿ and a family of depth-7 quantum circuits {C_n}_n such that 𝒟_n is produced exactly by C_n with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance 1 - e^{-Ω(n)} from 𝒟_n. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and König (Science, 2018) to separate shallow quantum and classical circuits for relational problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Grier and Daniel M. Kane and Jackson Morris and Anthony Ostuni and Kewen Wu 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.73 urn:nbn:de:0030-drops-253607 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.73 eng https://creativecommons.org/licenses/by/4.0/legalcode