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).
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).
Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, König and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.
Recent works by Bravyi, Gosset and Konig (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, Konig and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise.
We prove that this quantum advantage persists even if the quantum circuits can be subject to arbitrary corruption: in this paper we assume that any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We show that even in this model, quantum circuits can still solve in constant depth computational problems that require logarithmic depth to solve with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits.
In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the robustness of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.
We construct a family of distributions {Dn}n with Dn over {0,1}n and a family of depth-7 quantum circuits {Cn}n such that Dn is produced exactly by Cn 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 Dn. 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.
Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which constant-depth classical (i.e., 0) circuits cannot. Their results have the advantage that the quantum circuit is fairly practical, and their proofs are free of hardness assumptions (e.g., factoring is classically hard, etc.). Unfortunately, constant-depth classical circuits are too weak to yield a convincing real-world demonstration of quantum advantage. We attempt to hold on to the advantages of the above results, while increasing the power of the classical model. Our main result is a two-round interactive task which is solved by a constant-depth quantum circuit (using only Clifford gates, between neighboring qubits of a 2D grid, with Pauli measurements), but such that any classical solution would necessarily solve -hard problems. This implies a more powerful class of constant-depth classical circuits (e.g., 0[p] for any prime p) unconditionally cannot perform the task. Furthermore, under standard complexity-theoretic conjectures, log-depth circuits and log-space Turing machines cannot perform the task either. Using the same techniques, we prove hardness results for weaker complexity classes under more restrictive circuit topologies. Specifically, we give 0 interactive tasks on 2 × n and 1 × n grids which require classical simulations of power 1 and 0[6], respectively. Moreover, these hardness results are robust to a small constant fraction of error in the classical simulation.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.
We prove an explicit depth hierarchy theorem for QNC0. For each d≥12, we construct a family of two-round interactive problems on which no depth-(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than d by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every d, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0 over NC0.
A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.
These results show that increasing depth strictly increases computational power within QNC0, establishing a genuinely quantum hierarchy.
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 } n 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 k n + 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.