Product-projection localization and the QAC0 parity lower bound
We prove that constant-depth quantum circuits with arbitrary one-qubit and unbounded-arity Toffoli gates cannot compute parity with any fixed positive worst-case advantage using polynomially many qubits. Ancillas start in zero, only one output qubit is measured, and all final garbage is unrestricted. This resolves Moore's parity conjecture in the measured-output model.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Product-projection-localization-and-the-QAC0-parity-lower-bound
curl -X POST /api/v1/records/openai-math/Product-projection-localization-and-the-QAC0-parity-lower-bound/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Product-projection-localization-and-the-QAC0-parity-lower-bound/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
The MathocalypseShtetl-OptimizedOct 7, 2026
one of the great questions of quantum complexity theory since 1999 that many of my colleagues had been closing in on. Nearly 4 th -power separation between randomized and quantum query complexity for total Boolean functions . A favorite problem of mine since 1998 (!), when we knew only that the…