We show that noisy shallow 3D-local quantum circuits solve a computational task with higher probability than (ideal) unbounded fan-in classical \({{\mathsf{AC}}}^{0}\)-circuits of a certain subexponential size. This can thus be seen as a fault-tolerant counterpart to the work6. More precisely, we show the following (see Supplementary Note[Theorems 6.7 and 7.10]9):
Theorem 1
(Fault-tolerant quantum advantage against \({{\mathsf{AC}}}^{0}\), informal version) Let (μ, ν) ∈ (0, 1)2 with ν < 1 − μ be arbitrary. There is a computational problem with the following properties:
-
(i)
The problem is beyond the reach of \({{\mathsf{AC}}}^{0}\)-circuits: Any \({{\mathsf{AC}}}^{0}\)-circuit solving the problem with probability at least ν on average over a randomly chosen instance has superpolynomial size.
-
(ii)
The problem can be solved with average probability at least 1 − μ by a 3D-local shallow quantum circuit even in the presence of local stochastic noise. That is, the quantum advantage can be observed using a shallow, noisy quantum circuit which only involves nearest-neighbor gates on qubits arranged on a regular 3D lattice.
Our result thus strengthens the findings of8: While requiring a comparable amount of (imperfect) quantum resources/capabilities, and only local operations in 3D, it establishes a quantum advantage against \({{\mathsf{AC}}}^{0}\) instead of only \({{\mathsf{NC}}}^{0}\). In addition, contrary to earlier work, our result features a classical–quantum gap (1 − μ) − ν (difference of success probabilities) arbitrarily close to 1, a fact we establish by using Raz’s parallel repetition result10,11 for one-round two-player games.
From single-qubit gate teleportation to complexity theory
Our result is obtained by identifying a particularly simple computational problem which is motivated by what we call the single-qubit gate-teleportation circuit (see Fig. 1 and ref. 12). This circuit is a concatenation of multiple applications of the standard gate-teleportation procedure13 for single-qubit Clifford gates, except for the fact that the final “Pauli correction” is not applied – we are only interested in the measurement outcomes produced in the repeated gate-teleportation procedure. In more detail, the single-qubit gate-teleportation circuit is a classically controlled Clifford circuit taking n single-qubit Clifford elements C0, …, Cn−1 as input, and outputting the result of n Bell measurements, i.e., a sequence of n Pauli observables P0, …, Pn−1 (corrections in gate-teleportation).
Fig. 1: The gate-teleportation circuit.
\({U}_{n}^{{\mathsf{Telep}}}\) is a classically controlled Clifford circuit. It takes as input n single-qubit Clifford group elements (C0, …, Cn−1). Each of these is applied to half of a maximally entangled state \(\left\vert \Phi \right\rangle={2}^{-1/2}(\left\vert 00\right\rangle+\left\vert 11\right\rangle )\) (i.e., this constitutes a classically controlled single-qubit Clifford gate.) If Bell measurements are performed on pairs of qubits (shifted by one), the output (P0, …, Pn−1) is an n-tuple of Paulis.
The computational problem we consider is the following: Given an input (C0, …, Cn−1), output a sequence (P0, …, Pn−1) of Paulis that occurs with nonzero probability in the output distribution of the gate-teleportation circuit. This can be formulated succinctly as follows: a correct output is one that satisfies
$${{\rm{tr}}}({P}_{n-1}{C}_{n-1}\cdots {P}_{0}{C}_{0})\,\ne \,0.$$
(1)
For more details see the Supplementary Note[Section 2]9.
On our route to establishing a quantum advantage of noisy shallow 3D-local quantum circuits against \({{\mathsf{AC}}}^{0}\), we show the following result for (ideal) 1D-local quantum circuits (see Supplementary Note[Corollary 5.4]9).
Theorem 2
(Single-qubit gate teleportation yields a quantum advantage against \({{\mathsf{AC}}}^{0}\), informal version) Let \({{\mathcal{C}}}\) be an \({{\mathsf{AC}}}^{0}\)-circuit which, for a uniformly chosen sequence \(C=({C}_{0},\ldots,{C}_{n-1})\in {{\mathsf{Cliff}}}^{n}\) of n single-qubit Clifford gates, produces – with probability at least 0.986 on average – a sequence \(({P}_{0},\ldots,{P}_{n-1})\in {{\mathsf{Pauli}}}^{n}\) which occurs with non-zero probability in the output distribution of the single-qubit gate-teleportation circuit on input C. Then the size of \({{\mathcal{C}}}\) is superpolynomial (in fact subexponential). On the other hand, this problem is solved with certainty by a 1D-local \({{\mathsf{QNC}}}^{0}\) circuit.
This improves our result12 where we showed that the single-qubit gate-teleportation problem cannot be solved by an \({{\mathsf{NC}}}^{0}\) circuit.
Theorem 2 gives a version applicable for the proof of Theorem 6.7 with parameter ν = 0.986. In Section 7 of the Supplementary Note (Theorem 7.10), we show that this can be replaced by an arbitrary constant ν ∈ (0, 1) by considering a relation obtained by parallel repetition. This proof relies on a variant of Raz’s parallel repetition for nonlocal games10,11.
In the terminology of14, Theorem 2 states that the computational problem of “possibilistically” simulating the single-qubit gate-teleportation circuit is infeasible for \({{\mathsf{AC}}}^{0}\)-circuits of polynomial size. The 1D-locality of the single-qubit gate-teleportation is what ultimately yields our fault-tolerant quantum advantage proposal with a 3D-local quantum circuit. In contrast, the so-called relaxed parity-halving problem considered by the authors of6,15 does not have a simple locality structure, and is arguably more complex.
This quantum advantage demonstration based on the single-qubit gate-teleportation circuit shares a few attractive average-case hardness features with prior work such as6,16: The bound on the classical circuits considered here involves the average over a fully random input. In contrast, the results of5,8 (as well as our results for the noise-tolerant setup) require restricting to a subset of inputs corresponding to valid problem instances.