Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work \cite{TerhalDiVincenzo04}, Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation \cite{wang2021possibilistic}, a particularly weak form of this task where the goal is to output any string appearing with non-zero probability in the output distribution of the circuit. We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates. Our results are unconditional and are obtained by a reduction to the problem of computing the parity, a well-studied problem in classical circuit complexity.
Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work \cite{TerhalDiVincenzo04}, Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation \cite{wang2021possibilistic}, a particularly weak form of this task where the goal is to output any string appearing with non-zero probability in the output distribution of the circuit. We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates. Our results are unconditional and are obtained by a reduction to the problem of computing the parity, a well-studied problem in classical circuit complexity.
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.
In a breakthrough work, Bravyi, Gosset, and K\"onig (BGK) [Science 362, 308 (2018)] unconditionally proved that constant-depth quantum circuits are more powerful than their classical counterparts. Their result is equivalent to saying that a particular family of constant-depth quantum circuits takes classical circuits at least $\mathrm{\ensuremath{\Omega}}(logn)$ depth to ``simulate,'' in a certain sense. In our paper, we formalize their sense of simulation, which we call ``possibilistic simulation'' or ``p-simulation,'' and construct explicit classical circuits that can p-simulate any depth-d quantum circuit with Clifford and tT-gates in depth O(d+t). Our classical circuits use NOT,AND,OR gates of fan-in $\ensuremath{\le}2$.
Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC0) can solve with near certainty (probability 1−o(1)), but that any bounded fan-in constant-depth classical circuit (NC0) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC0 circuits and AC0[p] circuits for all primes p≥2, and a conditional separation between noisy QNC0 circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks -- that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err with constant probability over a uniformly random input. We show that is true even for quantum tasks which are ⊕L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography.
We study the classical simulatability of constant-depth polynomial-size quantum circuits followed by only one single-qubit measurement, where the circuits consist of universal gates on at most two qubits and additional gates on an unbounded number of qubits. First, we consider unbounded Toffoli gates as additional gates and deal with the weak simulation, i.e., sampling the output probability distribution. We show that there exists a constant-depth quantum circuit with only one unbounded Toffoli gate that is not weakly simulatable, unless $\bqp \subseteq \postbpp \cap \am$. Then, we consider unbounded fan-out gates as additional gates and deal with the strong simulation, i.e., computing the output probability. We show that there exists a constant-depth quantum circuit with only two unbounded fan-out gates that is not strongly simulatable, unless $\p = \pp$. These results are in contrast to the fact that any constant-depth quantum circuit without additional gates on an unbounded number of qubits is strongly and weakly simulatable.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.
In a recent breakthrough, Bravyi, Gosset and Konig (BGK) [Science, 2018] proved that simulating constant depth quantum circuits takes classical circuits Ω(logn) depth. In our paper, we first formalise their notion of simulation, which we call possibilistic simulation. Then, from well-known results, we deduce that their circuits can be simulated in depth O(log2n). Separately, we construct explicit classical circuits that can simulate any depth-d quantum circuit with Clifford and tT-gates in depth O(d+t). Our classical circuits use {NOT, AND, OR} gates of fan-in ≤2.