We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must be constant outside it. While GC^0 can compute functions requiring exponential-size circuits, Kumar (CCC 2023) showed that switching-lemma lower bounds for AC^0 extend to GC^0 with no loss in parameters. We prove a parallel result for the polynomial method: any lower bound for AC^0[p] obtained via the polynomial method extends to GC^0[p] without loss in parameters. As a consequence, we show that the majority function MAJ requires depth-$d$ GC^0[p] circuits of size $2^{Ω(n^{1/2(d-1)})}$, matching the best-known lower bounds for AC^0[p]. This yields the most expressive class of non-monotone circuits for which exponential-size lower bounds are known for an explicit function. We also prove a similar result for the algorithmic method, showing that E^NP requires exponential-size GCC^0 circuits, extending a result of Williams (JACM 2014). Finally, leveraging our improved classical lower bounds, we establish the strongest known unconditional separations between quantum and classical circuit classes. We separate QNC^0 from GC^0 and GC^0[p] in various settings and show that BQLOGTIME is not contained in GC^0. As a consequence, we construct an oracle relative to which BQP lies outside uniform GC^0, extending the Raz-Tal oracle separation between BQP and PH (STOC 2019).
We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must be constant outside it. While GC^0 can compute functions requiring exponential-size circuits, Kumar (CCC 2023) showed that switching-lemma lower bounds for AC^0 extend to GC^0 with no loss in parameters. We prove a parallel result for the polynomial method: any lower bound for AC^0[p] obtained via the polynomial method extends to GC^0[p] without loss in parameters. As a consequence, we show that the majority function MAJ requires depth-d GC^0[p] circuits of size 2Ω(n1/2(d−1)), matching the best-known lower bounds for AC^0[p]. This yields the most expressive class of non-monotone circuits for which exponential-size lower bounds are known for an explicit function. We also prove a similar result for the algorithmic method, showing that E^NP requires exponential-size GCC^0 circuits, extending a result of Williams (JACM 2014). Finally, leveraging our improved classical lower bounds, we establish the strongest known unconditional separations between quantum and classical circuit classes. We separate QNC^0 from GC^0 and GC^0[p] in various settings and show that BQLOGTIME is not contained in GC^0. As a consequence, we construct an oracle relative to which BQP lies outside uniform GC^0, extending the Raz-Tal oracle separation between BQP and PH (STOC 2019).
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
QAC0 Contains TC0 (with Many Copies of the Input)
QAC0 is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical AC0 lower bounds to QAC0 have failed.
We give one possible explanation of this: QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0 could be more powerful than QAC0. Moreover, we prove that QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, Cotler, Huang, and Li (2022). We establish that with a constant error rate, separation can be achieved in terms of NP. When the error rate is Ω(logn/n), we can extend this result to the separation of PH. Notably, our oracles, in all separations, do not necessitate error correction schemes or fault tolerance, as all quantum circuits are of constant depth. This indicates that even quantum computers with minor errors, without error correction, may surpass classical complexity classes under various scenarios and assumptions. We also explore various common noise settings and present new classical hardness results, generalizing those found in studies by Raz and Tal (2022) and Bassirian, Bouland, Fefferman, Gunn, and Tal (2021), which are of independent interest.
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.
Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation. Indeed, Jozsa conjectured that “ Any quantum polynomial-time algorithm can be implemented with only O (log n ) quantum depth interspersed with polynomial-time classical computations. ” This can be formalized as asserting the equivalence of BQP and “ BQNC BPP .” However, Aaronson conjectured that “ there exists an oracle separation between BQP and BPP BQNC . ” BQNC BPP and BPP BQNC are two natural and seemingly incomparable ways of hybrid classical-quantum computation. In this work, we manage to prove Aaronson’s conjecture and in the meantime prove that Jozsa’s conjecture, relative to an oracle, is false. In fact, we prove a stronger statement that for any depth parameter d , there exists an oracle that separates quantum depth d and 2 d +1 in the presence of classical computation. Thus, our results show that relative to oracles, doubling the quantum circuit depth does make the hybrid model more powerful, and this cannot be traded by classical computation.
Quantum computers were initially proposed to surpass the limitations of classical computers in simulating physical systems. Soon after, the field of quantum computing advanced through landmark discoveries of quantum algorithms, with some conjectured to provide exponential advantages over classical counterparts. These include Shor’s factoring algorithm, which has profound implications in cryptography. Additionally, moderate yet significant polynomial separations have further increased interest in the field. However, despite this progress, unconditional proofs confirming quantum superiority on the theoretical side remain elusive. At the same time, large, noise-resilient quantum computations on the experimental side, which could challenge the extended Church-Turing thesis by potentially breaking classical computational barriers, have yet to be achieved. Meanwhile, our understanding of the differences between classical and quantum mechanics has deepened. We now possess rigorous theoretical tools, such as Bell inequalities and nonlocal games, to describe behaviors unique to these theories. Moreover, the main loopholes for observing non-classical correlations have been closed experimentally, showing that correlations in the physical world exceed those predicted by classical mechanics. This thesis investigates computational complexity differences between quantum and classical models by studying shallow-depth circuits. The primary focus lies in identifying, elucidating, and proving computational quantum advantages. Additionally, the analysis delves into the bijection between these circuits and foundational non-local game constructions, exploring how quantum-classical deviations in multi-party correlation settings translate to computational advantages. A key question addressed is how to synthesize constant-depth quantum circuits for various problems to leverage quantum advantages. To this end, circuit synthesis techniques tailored to measurement-based quantum computation are developed, enabling simultaneously optimal quantum strategies for certain nonlocal games based on a particular bijection between this model and XOR non-local games. Building on this work, we confront a pivotal challenge: If a candidate quantum circuit potentially provides a computational advantage, how can we prove that no classical circuit surpasses it? This work presents new unconditional quantum-classical separations within shallow-depth settings, distinguishing for the first time constant-depth quantum circuits with one- and two-qubit gates from biased polynomial threshold circuits, which incorporate neural-network-type functionalities. These separations extend to prime-dimensional quantum systems, and we conjecture to have identified Razborov-Smolensky-type problems uniquely solvable by specific prime dimensions. The thesis also differentiates constant-depth quantum circuits with multi-qubit Toffoli gates from their classical counterparts, emphasizing the power of parallel quantum computation. Finally, verifying shallow-depth quantum computations is challenging due to conjectured exponential separations from classical computations, limiting correctness verification through simulation. While specific quantum algorithms within BQP have been addressed, we explore whether a quantum computer can reliably execute any instance from a fixed class of quantum circuits. Moving beyond heuristic-based solutions, we propose a benchmarking protocol that certifies, with exponentially high confidence, the execution of arbitrary circuits of specified dimensions, widths, and depths.