Tight bounds on depth-2 QAC-circuits computing parity

2025/04/08 by Stephen Fenner, Fenner, Stephen, Daniel Grier +5 · 1 voice · 7 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture #cs.CC #math-ph #quant-ph

paper · pdf · doi:10.48550/arxiv.2504.06433

Abstract

We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This result is incomparable with other recent lower bounds on constant-depth QAC-circuits by Rosenthal [ICTS~2021,arXiv:2008.07470] and uses different techniques which may be of independent interest: 1. We show that all members of a certain class of multivariate polynomials are irreducible. The proof applies a technique of Shpilka & Volkovich [STOC 2008]. 2. We give a tight-in-some-sense characterization of when a multiqubit CZ gate creates or removes entanglement from the state it is applied to. The current paper strengthens an earlier version of the paper [arXiv:2005.12169].

Citations

• Bounds on the QAC⁰ Complexity of Approximating Parity
• Depth-2 QAC circuits cannot simulate quantum parity
• On the Computational Power of QAC0 with Barely Superlinear Ancillae
• Quantum advantage with shallow circuits
• Quantum Computation and Quantum Information
• Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits
• Quantum Circuits with Unbounded Fan-out
• Quantum Lower Bounds for Fanout
• Bounds on the Power of Constant-Depth Quantum Circuits
• Counting, Fanout, and the Complexity of Quantum ACC
• Quantum Circuits: Fanout, Parity, and Counting
• Parity, circuits, and the polynomial-time hierarchy

Cited by

• On the Computational Complexity of Geometrically Local QAC0 circuits

Discussions

• It was known depth-2 QAC0 circuits cannot do parity exactly: arxiv.org/abs/2504.06433. AC0 can implement any truth table in depth 2 with exp size. But comparing them is nuanced, QAC is constrained by [bsky, 2 points, 1 comments]

Related

• Depth-2 QAC circuits cannot simulate quantum parity
• Improved Lower Bounds for QAC0
• Bounds on the QAC⁰ Complexity of Approximating Parity
• Low-degree approximation of QAC⁰ circuits
• On the Computational Complexity of Geometrically Local QAC0 circuits