Bounds on the QAC0 Complexity of Approximating Parity
summary
Constant-depth QAC0 circuits can approximate parity arbitrarily well but at steep cost: depth seven requires exponential size, and the paper gives a depth-11 construction later optimized to seven. Proofs reduce parity/fan-out to building Nekomata (generalized cat states) and use controlled-Z, generalized Toffoli and an OR gadget; a matching lower bound holds for a mostly-classical subclass. More generally, depth d circuits of size ≤ (1/5)·n/(d+1) cannot beat a one-half approximation.
AI-written summary · about
chapters (6)
- 0:00Start
- 0:51Fanout & Motivation
- 3:10Bounds for Parity/Fanout
- 10:40Bounds for Nekomata in Mostly Classical Circuits
- 14:02Remaining Proof Summaries & Result Clarifications
- 15:11A Normal Form for QAC Circuits
related talks
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
21mHow the Parity Architecture helps predict Financial Crashes
33mLightning Talks
01h 10mQuantum Advantage with Shallow Clifford Circuits
01h 37mFault-Tolerance Against Adversarial Errors & PCPs
15mScalable Equivalence Checking and Verification of Shallow Quantum Circuits
58mLimitations for Quantum PCPs
32mOptimal Quantum Programs