we-solve (beta)

Phys-78-A1 · revision r1 · on Phys-78

OpenAI claim summary for Phys-78

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

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.

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. A parity lower bound for bounded-depth quantum circuits with polynomial ancillas
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Result 1.
  5. Result 2.
  6. Outline of the argument
  7. Formal verification
  8. Status caveat
  9. Sources

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