The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, one of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice
QNC0/qpoly , and
AC0[p] , which is the class of classical constant-depth circuits with unbounded-fan in and
MODp gates. Additionally, we show a separation between
QAC0 , the circuit class containing Toffoli gates with unbounded control, and
AC0[p] , when
QAC0 is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between
AC0[p] and
[QNC0,AC0]2 , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider
QNC0 circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that
QNC0[p]=QTC0 . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
We consider quantum circuits consisting of
d layers of nearest-neighbor two-qubit gates acting on
n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error
δ, with parallel runtime
2O(d)loglog(n/δ) and
n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime
O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized
AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized
AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth
Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
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$.
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity.
QAC0 circuits are
QAC circuits of constant depth, and are quantum analogues of
AC0 circuits. We prove the following:
∙ For all
d≥7 and
ε>0 there is a depth-
d QAC circuit of size
exp(poly(n1/d)log(n/ε)) that approximates the
n-qubit parity function to within error
ε on worst-case quantum inputs. Previously it was unknown whether
QAC circuits of sublogarithmic depth could approximate parity regardless of size.
∙ We introduce a class of
QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical
QAC circuits that approximate this component.
∙ Arbitrary depth-
d QAC circuits require at least
Ω(n/d) multi-qubit gates to achieve a
1/2+exp(−o(n/d)) approximation of parity. When
d=Θ(logn) this nearly matches an easy
O(n) size upper bound for computing parity exactly.
∙ QAC circuits with at most two layers of multi-qubit gates cannot achieve a
1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large
n.
The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name nekomata after an analogous cat y\=okai.