Average-Case Quantum Advantage with Shallow Circuits

Abstract

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 \emph{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).

18 pages; accepted to CCC'19; v2: added references, soundness improved (from constant to exponentially small) in the main result; v3: discussion added about the relation with Ref. [BGK18]; v4: corrected typos, footnote 3 removed

References in corpus (3)

• Multi-party entanglement in graph states
• Quantum advantage with shallow circuits
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication

Cited by in corpus (8)

• Quantum advantage with noisy shallow circuits in 3D
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Device-independent and semi-device-independent entanglement certification in broadcast Bell scenarios
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Quantum advantage in temporally flat measurement-based quantum computation