pith. sign in

arxiv: 2604.07178 · v1 · submitted 2026-04-08 · 🪐 quant-ph

On the Computational Complexity of Geometrically Local QAC0 circuits

Yangjing Dong , Fengning Ou , Penghui Yao This is my paper

Pith reviewed 2026-05-10 17:39 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QAC0geometrically local quantum circuits2D-QAC01D-QAC0parity functiondepth lower boundslight-cone argumentrestriction argument
0
0 comments X

The pith

Any QAC0 circuit can be exactly simulated by a two-dimensional geometrically local QAC0 circuit with quadratic size blow-up.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that constant-depth polynomial-size quantum circuits built from single-qubit unitaries and generalized Toffoli gates remain equally powerful when restricted to nearest-neighbor interactions on a two-dimensional grid. A direct simulation converts any such circuit into an equivalent 2D local version while increasing size by at most a quadratic factor, establishing the equality QAC0 equals 2D-QAC0. The same techniques yield nearly logarithmic depth lower bounds for one-dimensional local circuits computing parity even with unlimited ancilla qubits, and nearly linear depth lower bounds when input bits must occupy contiguous positions. The proofs rely on adapting light-cone and restriction arguments to the geometrically local setting.

Core claim

We show that any QAC0 circuit can be exactly simulated by a two-dimensional geometrically local QAC0 circuit with a quadratic size blow-up, implying QAC0 equals 2D-QAC0. We further show that a bounded-error QAC0 circuit for parity would yield an exact thin-width 2D-QAC0 circuit for parity. For one-dimensional QAC0 circuits we prove nearly logarithmic depth lower bounds for parity even with ancillas and nearly linear depth lower bounds when inputs are contiguous; both bounds are nearly tight.

What carries the argument

Quadratic-size simulation of general QAC0 by 2D geometrically local nearest-neighbor QAC0, combined with light-cone and restriction arguments that produce depth lower bounds for 1D-QAC0.

If this is right

  • QAC0 equals 2D-QAC0 exactly.
  • Any bounded-error QAC0 circuit for parity yields an exact 2D-QAC0 circuit for parity of width n to the epsilon.
  • 1D-QAC0 requires Omega(log n) depth to compute parity even with unlimited ancilla qubits.
  • When inputs must be placed in contiguous blocks, 1D-QAC0 requires Omega(n) depth for parity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Two spatial dimensions suffice to recover the full power of non-local shallow quantum circuits.
  • The thin-width construction may allow efficient hardware layouts that embed arbitrary Toffoli gates using only local interactions.
  • The 1D lower bounds suggest a dimensional hierarchy inside QAC0 that could separate it from classical AC0.

Load-bearing premise

The light-cone and restriction arguments extend directly to geometrically local gates without hidden overheads that would invalidate the quadratic simulation or the depth lower bounds when ancilla are present or inputs are contiguous.

What would settle it

An explicit QAC0 circuit for parity with constant error whose exact 2D local simulation requires super-quadratic size, or a 1D-QAC0 circuit family computing parity in o(log n) depth with ancillas.

Figures

Figures reproduced from arXiv: 2604.07178 by Fengning Ou, Penghui Yao, Yangjing Dong.

Figure 1
Figure 1. Figure 1: An example of one layer of a 2D-QAC circuit. Each square represents a qubit. A 2D-QAC circuit is composed of several such layers. In the remainder of this section, we investigate the computational power of the aforementioned models, centering our discussion on the function Parityn and the corresponding unitary U⊕n . 4.1 Exactly Simulating General QAC Circuits with 2D-QAC Circuits We demonstrate how to simu… view at source ↗
Figure 2
Figure 2. Figure 2: Simulation for a depth 1 QAC0 circuit Assuming C operates on n inputs, and has k multi-qubit gates. C˜ requires k × n ancilla on k rows. Including the input qubits this is (k + 1) × n. Note that k ≤ n, so the total number of qubits is upper bounded by (n + 1) × n. Ultimately, C˜ stores the computational result of C in the first row, while maintaining all remaining qubits in the state |1⟩. The circuit U may… view at source ↗
Figure 3
Figure 3. Figure 3: A 1D-QAC circuit for generating the 8-qubit cat state 5.1 Local Approximation of 1D-QAC In this subsection, we present a local approximation circuit for a 1D-QAC circuit by erasing all gates in the circuit that are entangled with a large number of input qubits. Then every remaining gate in a local circuit acts on a bounded number of input qubits. By a light-cone argument, we obtain a lower bound for the Pa… view at source ↗
Figure 4
Figure 4. Figure 4: Forward light-cone of the first qubit, and backward light-cone of the last qubit [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustrations of different kinds of input qubits [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: By selecting the first and third inputs in [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The circuit proceeds from bottom to top. Gates depicted with dashed lines represent those [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗
read the original abstract

The computational complexity of $\mathsf{QAC}^0$, which are constant-depth, polynomial-size quantum circuit families consisting of arbitrary single-qubit unitaries and $n$-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local $\mathsf{QAC}^0$ circuits, where all the generalized Toffoli gates act on nearest neighbor qubits. We show that any $\mathsf{QAC}^0$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}^0$ circuit, i.e., a $\mathsf{2D\text{-}QAC}^{0}$ circuit, with a quadratic size blow-up. This implies that $\mathsf{QAC}^0 = \mathsf{2D\text{-}QAC}^{0}$. We further show that if there existed a $\mathsf{QAC}^0$ circuit that computes Parity with a bounded constant error, then for any $\varepsilon > 0$, there would exist a $\mathsf{2D\text{-}QAC}^{0}$ circuit that exactly computes Parity, with a very "thin" width $n^\varepsilon$. We further study the computational power of $\mathsf{1D\text{-}QAC}^{0} $ circuits, i.e., one-dimensional $\mathsf{QAC}^0$ circuits, which are the "thinnest" $\mathsf{2D\text{-}QAC}^{0}$ circuits. We prove a nearly logarithmic depth lower bound on $\mathsf{1D\text{-}QAC}^{0} $ circuits to compute the Parity function, even if allowing an unlimited number of ancilla. Furthermore, if the inputs are encoded in contiguous qubits, we prove that it requires a nearly linear depth $\mathsf{1D\text{-}QAC}^{0} $ circuit to compute the Parity function. This lower bound is almost tight. The results are proved via the combination of the restriction argument and the light-cone argument. These results may provide a new angle for studying the computational power of $\mathsf{QAC}^0$ circuits and for resolving the long-standing open problem of whether Parity is in $\mathsf{QAC}^0$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that any QAC^0 circuit (constant-depth poly-size quantum circuits with single-qubit gates and arbitrary generalized Toffoli gates) can be exactly simulated by a 2D geometrically local QAC^0 circuit with only quadratic size blow-up, implying QAC^0 = 2D-QAC^0. It further claims that if Parity is in QAC^0 with bounded error then it is exactly computable by 2D-QAC^0 circuits of width n^ε for any ε>0. For 1D-QAC^0 it proves nearly logarithmic depth lower bounds for Parity (unlimited ancilla) and nearly linear depth when inputs are contiguous, via restriction and light-cone arguments.

Significance. If the simulation result holds it would establish that 2D geometric locality does not restrict the power of constant-depth QAC^0, with potential implications for quantum circuit complexity and the open question of whether Parity is in QAC^0. The 1D lower bounds are nearly tight and rely on standard combinatorial techniques (restriction + light-cone) that are appropriate for these classes. The paper receives credit for applying these methods to geometrically local variants and for the conditional thin-width result on Parity.

major comments (2)
  1. [Abstract and simulation theorem] Abstract and the simulation theorem (presumably §3): The claimed exact quadratic-size simulation of general QAC^0 by constant-depth 2D-local QAC^0 is inconsistent with light-cone causality. A depth-d 2D geometrically local circuit has causal cones of radius O(d) = O(1), so each output depends on only O(1) input qubits irrespective of ancilla or total size. This cannot reproduce the n-ary dependency of an n-qubit generalized Toffoli for large n. The paper's own light-cone argument for the 1D lower bounds makes the same obstruction applicable here, rendering the simulation claim load-bearing and unsupported.
  2. [1D lower-bound section] 1D lower-bound section (light-cone argument): The light-cone technique is correctly invoked to obtain the Ω(log n / log log n) and Ω(n / polylog n) depth lower bounds for Parity. However, the identical causal-cone limitation directly rules out the 2D simulation result, creating an internal inconsistency that must be resolved for the central equality claim to stand.
minor comments (2)
  1. [Abstract] The abstract's phrasing of the conditional Parity result ('with a very thin width n^ε') would benefit from an explicit statement of the circuit depth and the precise dependence on ε.
  2. [Preliminaries] Notation for geometrically local gates (nearest-neighbor generalized Toffolis) should be defined more formally in the preliminaries, including how ancilla placement is handled in the 2D grid embedding.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for identifying a critical issue with the simulation result. We address each major comment below and outline the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract and simulation theorem] Abstract and the simulation theorem (presumably §3): The claimed exact quadratic-size simulation of general QAC^0 by constant-depth 2D-local QAC^0 is inconsistent with light-cone causality. A depth-d 2D geometrically local circuit has causal cones of radius O(d) = O(1), so each output depends on only O(1) input qubits irrespective of ancilla or total size. This cannot reproduce the n-ary dependency of an n-qubit generalized Toffoli for large n. The paper's own light-cone argument for the 1D lower bounds makes the same obstruction applicable here, rendering the simulation claim load-bearing and unsupported.

    Authors: We thank the referee for this observation. The light-cone causality argument is correct and applies directly to our claimed simulation: a constant-depth 2D geometrically local QAC^0 circuit cannot produce outputs whose value depends on more than a constant number of input qubits, which precludes exact simulation of an n-ary generalized Toffoli. This is indeed an inconsistency with the manuscript's central simulation theorem. We will revise the paper by removing the simulation result, the quadratic blow-up claim, and the implication that QAC^0 = 2D-QAC^0. The remaining results on 1D lower bounds and the conditional thin-width statement for Parity (which does not rely on the flawed simulation) will be retained. revision: yes

  2. Referee: [1D lower-bound section] 1D lower-bound section (light-cone argument): The light-cone technique is correctly invoked to obtain the Ω(log n / log log n) and Ω(n / polylog n) depth lower bounds for Parity. However, the identical causal-cone limitation directly rules out the 2D simulation result, creating an internal inconsistency that must be resolved for the central equality claim to stand.

    Authors: We agree that the light-cone technique is appropriately applied in the 1D section and that the same causal-cone limitation exposes the inconsistency in the 2D simulation claim. As noted in our response to the first comment, we will remove the simulation theorem and the equality QAC^0 = 2D-QAC^0 to resolve this inconsistency. The 1D lower bounds themselves remain valid and are unaffected. revision: yes

Circularity Check

0 steps flagged

No circularity: results follow from explicit combinatorial constructions and independent light-cone/restriction arguments

full rationale

The claimed quadratic simulation of arbitrary QAC0 by 2D-QAC0 is presented as a direct construction on circuit structure (not a fitted parameter or self-definition). The 1D lower bounds for Parity are obtained by applying light-cone and restriction arguments to the geometry of the circuit; these arguments are external to the simulation claim and do not reduce to it. No self-citation is load-bearing for the central equality, no ansatz is smuggled, and no quantity is renamed as a prediction. The derivation chain remains self-contained against the stated combinatorial techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the standard quantum circuit model and the applicability of restriction and light-cone arguments to geometrically constrained gates; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption Quantum circuits composed of single-qubit unitaries and generalized Toffoli gates admit light-cone analysis that bounds information propagation to neighboring qubits.
    Invoked to obtain the 1D depth lower bounds for parity.
  • domain assumption Any non-local generalized Toffoli gate can be replaced by a sequence of geometrically local gates on a 2D grid with only quadratic overhead.
    Central to the simulation result equating QAC0 and 2D-QAC0.

pith-pipeline@v0.9.0 · 5715 in / 1605 out tokens · 104535 ms · 2026-05-10T17:39:05.433780+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    [Ber11] Debajyoti Bera

    Accessed: 2026-01-16. [Ber11] Debajyoti Bera. A lower bound method for quantum circuits.Inf. Process. Lett., 111(15):723–726, aug

    work page 2026

  2. [2]

    Unconditional Quantum Advantage for Sam- pling with Shallow Circuits

    [BWP26] Adam Bene Watts and Natalie Parham. Unconditional Quantum Advantage for Sam- pling with Shallow Circuits. In Shubhangi Saraf, editor,17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:12, Dagstuhl, Germany,

    work page 2026

  3. [3]

    Linear-size QAC0 channels: Learning, testing and hardness.arXiv preprint arXiv:2510.00593,

    [DOY25] Yangjing Dong, Fengning Ou, and Penghui Yao. Linear-size QAC0 channels: Learning, testing and hardness.arXiv preprint arXiv:2510.00593,

    work page arXiv

  4. [4]

    Tight bounds on depth- 2 QAC-circuits computing parity.arXiv preprint arXiv:2504.06433,

    [FGPT25] Stephen Fenner, Daniel Grier, Daniel Pad ´e, and Thomas Thierauf. Tight bounds on depth- 2 QAC-circuits computing parity.arXiv preprint arXiv:2504.06433,

    work page arXiv

  5. [5]

    Random Uni- taries in Constant (Quantum) Time

    [FPVY26] Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random Uni- taries in Constant (Quantum) Time. In Shubhangi Saraf, editor,17th Innovations in The- oretical Computer Science Conference (ITCS 2026), volume 362 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:25, Dagstuhl, Germany,

    work page 2026

  6. [6]

    Brown, and Frederic T

    [GKH+20] Pranav Gokhale, Samantha Koretsky, Shilin Huang, Swarnadeep Majumder, Andrew Drucker, Kenneth R. Brown, and Frederic T. Chong. Quantum fan-out: Circuit opti- mizations and technology modeling.2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 276–290,

    work page 2021

  7. [7]

    Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu

    [GKM+26] Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quan- tum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. In Shubhangi Saraf, editor,17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 73:1–73:14, ...

    work page 2026

  8. [8]

    [GMW26] Daniel Grier, Jackson Morris, and Kewen Wu.QAC 0 containsTC 0 (with many copies of the input).arXiv preprint arXiv:2601.03243,

    Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. [GMW26] Daniel Grier, Jackson Morris, and Kewen Wu.QAC 0 containsTC 0 (with many copies of the input).arXiv preprint arXiv:2601.03243,

    work page arXiv

  9. [9]

    Interactive shallow clifford circuits: Quantum advan- tage against NC 1 and beyond

    [GS20] Daniel Grier and Luke Schaeffer. Interactive shallow clifford circuits: Quantum advan- tage against NC 1 and beyond. InProceedings of the 52nd Annual ACM SIGACT Sym- posium on Theory of Computing, STOC 2020, pages 875–888, New York, NY, USA,

    work page 2020

  10. [10]

    [HLB+24] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R

    Association for Computing Machinery. [HLB+24] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. Learning shallow quantum circuits. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1343–1351, New York, NY, USA,

    work page 2024

  11. [11]

    Improved lower bounds for QAC0.arXiv preprint arXiv:2512.14643,

    [JTVW25] Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright. Improved lower bounds for QAC0.arXiv preprint arXiv:2512.14643,

    work page arXiv

  12. [12]

    Quantum circuits: Fanout, parity, and counting.arXiv preprint quant- ph/9903046,

    [Moo99] Cristopher Moore. Quantum circuits: Fanout, parity, and counting.arXiv preprint quant- ph/9903046,

    work page arXiv

  13. [13]

    On the pauli spectrum of QAC0

    28 [NPVY24] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the pauli spectrum of QAC0. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1498–1506, New York, NY, USA,

    work page 2024

  14. [14]

    Fenner, Daniel Grier, and Thomas Thierauf

    [PFGT20] Daniel Pad ´e, Stephen A. Fenner, Daniel Grier, and Thomas Thierauf. Depth-2 QAC cir- cuits cannot simulate quantum parity.CoRR, abs/2005.12169,

    work page arXiv 2005

  15. [15]

    Bounds on the QAC 0 Complexity of Approximating Parity

    [Ros21] Gregory Rosenthal. Bounds on the QAC 0 Complexity of Approximating Parity. In James R. Lee, editor,12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 32:1– 32:20, Dagstuhl, Germany,

    work page 2021

  16. [16]

    Constant-depth unitary preparation of dicke states.arXiv preprint arXiv:2601.10693,

    [VJ26] Francisca Vasconcelos and Malvika Raj Joshi. Constant-depth unitary preparation of dicke states.arXiv preprint arXiv:2601.10693,

    work page arXiv

  17. [17]

    Exponential separa- tion between shallow quantum circuits and unbounded fan-in shallow classical circuits

    [WKST19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separa- tion between shallow quantum circuits and unbounded fan-in shallow classical circuits. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 515–526, New York, NY, USA,

    work page 2019