OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Theorem 1: With polynomial total qubits, single-qubit unitaries and Toffoli gates cannot maintain a fixed positive advantage on all sufficiently long inputs

Shallow circuits lose uniform advantage on parity.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Parity computation asks for the parity of an nn-bit input at one measured output wire of a circuit on NN qubits. The total NN counts both input qubits and ancillas.

A bit bb is an element of {0,1}\{0,1\}, with addition modulo two.✦ An NN-bit word zz is a function from the wire set {0,…,N−1}\{0,\ldots,N-1\} to the bits.✦ An NN-qubit operator AA is a complex matrix indexed by NN-bit words✦, and a single-qubit operator aa is a complex 2×22\times2 matrix.✦ The tensor product ⨂i=0N−1ai\bigotimes_{i=0}^{N-1}a_i of single-qubit operators a0,…,aN−1a_0,\ldots,a_{N-1} is the NN-qubit operator with entries given by (1). (⨂i=0N−1ai)y,z=∏i=0N−1(ai)yi,zi,y,z∈{0,1}N.\left(\bigotimes_{i=0}^{N-1}a_i\right)_{y,z} =\prod_{i=0}^{N-1}(a_i)_{y_i,z_i}, \qquad y,z\in\{0,1\}^N.(1)✦

A gate gg on NN qubits is either a single-qubit unitary uu on a wire qq, or a Toffoli gate with a control set c⊆{0,…,N−1}c\subseteq\{0,\ldots,N-1\} and a target wire t∉ct\notin c.✦ The Toffoli basis map Tc,tT_{c,t} is the map on NN-bit words defined by (2). Tc,t(z)={z with bit t replaced by 1−zt,zi=1 for every i∈c,z,otherwise.T_{c,t}(z)= \begin{cases} z\text{ with bit }t\text{ replaced by }1-z_t, & z_i=1\text{ for every }i\in c,\\ z,&\text{otherwise}. \end{cases}(2)✦

The gate matrix GgG_g of a gate gg is the operator specified in (3), where I2I_2 is the single-qubit identity. Glocal(q,u)=⨂i=0N−1ai,ai={u,i=q,I2,i≠q,(GToffoli(c,t))y,z=𝟏{y=Tc,t(z)}.\begin{aligned} G_{\mathrm{local}(q,u)} &=\bigotimes_{i=0}^{N-1}a_i, & a_i&=\begin{cases}u,&i=q,\\I_2,&i\ne q,\end{cases}\\ \bigl(G_{\mathrm{Toffoli}(c,t)}\bigr)_{y,z} &=\mathbf{1}_{\{y=T_{c,t}(z)\}}. \end{aligned}(3)✦ The support of a local gate on qq is {q}\{q\}, and the support of a Toffoli gate with controls cc and target tt is c∪{t}c\cup\{t\}.✦

A physical layer L=(g1,…,gr)L=(g_1,\ldots,g_r) is a list of gates with pairwise disjoint supports.✦ For a physical layer L=(g1,…,gr)L=(g_1,\ldots,g_r) and a circuit with chronological layer list (L1,…,Lm)(L_1,\ldots,L_m), the layer matrix VLV_L and circuit matrix WW are the operators given by the products in (4); the rightmost matrix acts first. The depth of a circuit with chronological layer list (L1,…,Lm)(L_1,\ldots,L_m) is mm. VL=Gg1⋯Ggr,W=VLm⋯VL1,V_L=G_{g_1}\cdots G_{g_r}, \qquad W=V_{L_m}\cdots V_{L_1},(4) with an empty product equal to the identity.

For n≤Nn\le N and an nn-bit word xx, the zero-padded input ι(x)\iota(x) is the NN-bit word and the parity π(x)\pi(x) is the bit defined by (5). ι(x)i={xi,i<n,0,n≤i<N,π(x)=⨁i=0n−1xi.\iota(x)_i=\begin{cases}x_i,&i<n,\\0,&n\le i<N,\end{cases} \qquad \pi(x)=\bigoplus_{i=0}^{n-1}x_i.(5)

The parity success probability s(W,o,x)s(W,o,x) of an NN-qubit operator WW, an output wire o∈{0,…,N−1}o\in\{0,\ldots,N-1\} and an input x∈{0,1}nx\in\{0,1\}^n is the sum in (6) over full output words with the correct measured bit. s(W,o,x)=∑y∈{0,1}Nyo=π(x)|Wy,ι(x)|2.s(W,o,x)= \sum_{\substack{y\in\{0,1\}^N\\y_o=\pi(x)}} \left|W_{y,\iota(x)}\right|^2.(6)✦

The Claim

Theorem 1. Fix a depth d∈ℕd\in\mathbb N, a real exponent c≥1c\ge1, and a real number 0<ε≤120<\varepsilon\le\tfrac12. For all sufficiently large nn, let WW be a circuit of depth at most dd on NN qubits, where n≤N≤ncn\le N\le n^c, and let oo be any output wire. There is an input x∈{0,1}nx\in\{0,1\}^n such that s(W,o,x)<12+ε.s(W,o,x)<\frac12+\varepsilon.(7)✦

Theorem 2. Fix positive integers d,k,Cd,k,C. For all sufficiently large nn, let WW be a circuit of depth at most dd on NN qubits, where n≤N≤C(n+1)kn\le N\le C(n+1)^k, and let oo be any output wire. There is an input x∈{0,1}nx\in\{0,1\}^n such that s(W,o,x)<23.s(W,o,x)<\frac23.(8)✦

What Is Checked

The parity hardness statements (7) and (8) are stated over disjoint gate layers with the circuit matrices (4) and the parity success probability (6).