Average-Case Quantum Advantage with Shallow Circuits
arXiv:1810.12792 · doi:10.4230/LIPIcs.CCC.2019.21
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).
arXiv comment18 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 (7)
- Multi-party entanglement in graph states
- Quantum advantage with shallow circuits
- Average-case complexity versus approximate simulation of commuting quantum computations
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- On the hardness of classically simulating the one clean qubit model
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Modeling Pauli measurements on graph states with nearest-neighbor classical communication
Cited by in corpus (9)
- 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
- Power of Uninitialized Qubits in Shallow Quantum Circuits
- 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
- Quantum advantage in temporally flat measurement-based quantum computation
- Unconditionally separating noisy from bounded polynomial threshold circuits of constant depth