we-solve (beta)

Phys-78 · physics · mathematics · Physics

A parity lower bound for bounded-depth quantum circuits with polynomial ancillas

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
Fix depth d, total-qubit exponent $c\geq 1$ and $\epsilon >0$. For all sufficiently large input lengths n, is parity impossible with success at least 1/2+epsilon on every input using depth-d circuits of arbitrary one-qubit gates and unbounded-arity Toffoli gates on at most $n^c$ qubits, layers of disjoint supports, zero-state ancillas and one measured output qubit?

Short English statement

Fix depth d, total-qubit exponent $c\geq 1$ and $\epsilon >0$. For all sufficiently large input lengths n, is parity impossible with success at least 1/2+epsilon on every input using depth-d circuits of arbitrary one-qubit gates and unbounded-arity Toffoli gates on at most $n^c$ qubits, layers of disjoint supports, zero-state ancillas and one measured output qubit?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Phys-78-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Phys-78

Polynomial-qubit constant-depth circuits of one-qubit and unbounded Toffoli gates are claimed unable to compute parity with fixed worst-case advantage. The question retains these same parameters and conventions. A separate regular-trajectory proof claims the same measured-output parity lower bound for $\mathrm{QAC}^0$ circuits with zero-initialized ancillas. The question retains these same parameters and conventions. Within these assumptions, this is a claimed affirmative answer to the stated question.

A parity lower bound for bounded-depth quantum circuits with polynomial ancillas

OpenAI's claim

The linked manuscripts present the following claims by OpenAI: Polynomial-qubit constant-depth circuits of one-qubit and unbounded Toffoli gates are claimed unable to compute parity with fixed worst-case advantage; A separate regular-trajectory proof claims the same measured-output parity lower bound for $\mathrm{QAC}^0$ circuits with zero-initialized ancillas. Together they give a claimed affirmative answer in the matching scope.

Mathematical statement of the claimed result

Result 1.
Fix depth bound $d\ge0$, ancilla exponent $c\ge1$, and advantage $0<\varepsilon\le1/2$. Use $n$ input qubits, with a total register size bounded by $n^c$. Permit arbitrary unitaries acting on single qubits, together with Toffoli gates of any arity, with disjoint supports in each layer, zero-initialized ancillas, and one measured output. The claim is that for all sufficiently large $n$, every circuit of depth at most $d$ has an input $x$ with \[ \mathbb P(\text{output}=x_1\oplus\cdots\oplus x_n)<1/2+\varepsilon. \] Unused output registers may be discarded.
Result 2.
Fix positive integers $d,k,C$ and $0<\varepsilon\le1/2$. The allowed circuits use arbitrary one-qubit unitaries, unbounded Toffoli gates, disjoint supports within layers, zero ancillas, and a measured output bit. The source claims a finite $n_0$ such that for every $n\ge n_0$, any circuit with a total register size bounded by $C(n+1)^k$, and with depth bounded by $d$, has some input $x$ satisfying \[ \mathbb P(\text{answer}=\operatorname{Parity}_n(x))<1/2+\varepsilon. \]

Outline of the argument

Product projections localize the output test onto small supports. A controlled-coefficient polynomial approximation permits depth reduction, and the resulting low-degree description has insufficient parity correlation even when final garbage registers are unrestricted.

Two polynomial filters regularize circuit trajectories. Low-degree perturbations and excitation tails are transported through the gates, then projection insertion and pruning restrict the histories that can affect the output; this restriction forces the parity advantage to vanish.

Formal verification

For family 274, the documented entries include the measured-output parity lower bound for polynomial-qubit constant-depth circuits and the supporting product-projection estimate, with zero ancillas and unrestricted discarded registers. The listed Comparator files are QACParity.lean, RegularParity.lean. Named declarations include OAI.QAC.parity_lower_bound, OAI.QAC.parity_lower_bound_polynomial_size. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

Go to contribution →