{"id":"openai-math/Product-projection-localization-and-the-QAC0-parity-lower-bound","pdf":"https://github.com/openai/math/blob/main/preprints/Product-projection-localization-and-the-QAC0-parity-lower-bound-September-24-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Product-projection-localization-and-the-QAC0-parity-lower-bound-September-24-2026","tags":["quantum-computing","circuit-complexity","qac0","parity"],"score":0,"title":"Product-projection localization and the QAC0 parity lower bound","domain":"Mathematical physics","family":"274","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.MP","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":1,"published":"2026-09-24","reactions":{},"discussion":[{"url":"https://scottaaronson.blog/?p=10169#:~:text=one%20of%20the%20great%20questions%20of%20quantum%20complexity%20theory%20since%201999","date":"2026-10-07","kind":"web","site":"Shtetl-Optimized","text":"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…","added":"2026-10-24","title":"The Mathocalypse"}],"formalized":true,"family_title":"Parity is not in QAC 0"}