We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC$^0$ circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC$^0$ circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC$^0$ and AC$^0$.
We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC0 circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC0 circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC0 and AC0.
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
The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP and PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 2-Forrelation can be solved by a classical random choice between two one-query IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle O such that IQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP and DQC1. We prove Fourier growth bounds for multi-query IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixj that allows extracting inner-product phases within an IQP circuit.
Parity ∈/ QAC0 ⟺ QAC0 is Fourier-Concentrated
A major open problem in understanding shallow quantum circuits (QAC0) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC0: any QAC0 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0. Thus, proving a quantum analog of the seminal LMN theorem for AC0 is necessary to bound the quantum circuit complexity of PARITY.
In the other direction, LMN does not fully capture the limitations of AC0. For example, despite MAJORITY having 99% of its weight on low-degree Fourier coefficients, no AC0 circuit can non-trivially correlate with it. In contrast, we provide a QAC0 circuit that achieves (1−o(1)) correlation with MAJORITY, establishing the first average-case decision separation between AC0 and QAC0. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC0.
PARITY is also known to be equivalent in QAC0 to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY ∈ QAC0.
BQP⊆IP Does Not Relativize
We construct an oracle relative to which BQP⊆IP, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between IP and MIP, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions f and g, the goal is to determine if f is correlated with the Fourier spectrum of g. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier.
Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions.
Our results imply that any prover-efficient classical interactive protocol for BQP must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.
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).
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0, it ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae, Hadamard and T single-qubit gates, O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(loglog(1/ε)), and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-d QAC circuit can be simulated in depth O(d) using only Hadamard, X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∈/QAC0 to proving a Parity lower bound against circuits consisting only of Hadamard, X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.