2026-08-05T23:35:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10843 2024-03-06T10:46:51Z ddc:004 open_access

Average-Case Quantum Advantage with Shallow Circuits Le Gall, François Quantum computing circuit complexity constant-depth circuits Recently Bravyi, Gosset and König (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this paper we show a similar separation in the average-case setting that gives stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. Our results are obtained by introducing a technique to create quantum states exhibiting global quantum correlations from any graph, via a construction that we call the extended graph. Similar results have been very recently (and independently) obtained by Coudron, Stark and Vidick (arXiv:1810.04233}), and Bene Watts, Kothari, Schaeffer and Tal (STOC 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik François Le Gall 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.21 urn:nbn:de:0030-drops-108432 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.21 eng https://creativecommons.org/licenses/by/3.0/legalcode