OctoInformBeta

OpenAI preprint, September 2026 · Section 6. From localization to parity

Section 6: Born rule and complementary Hadamard entries: The Born rule and a finite character identity connect output probabilities to localization estimates

Localization bounds parity through complementary Hadamard entries.

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

A parity circuit receives nn input qubits among N≥nN\ge n total qubits and measures one output wire oo. The remaining input wires start at zero, and the unmeasured output wires may contain arbitrary garbage. A classical bit belongs to {0,1}\{0,1\}; a word of length NN assigns a bit to each wire. A quantum operator on NN qubits is a complex matrix indexed by these words, and a single-qubit operator is a complex matrix indexed by bits.

For a bit b∈{0,1}b\in\{0,1\}, the computational basis vector |b⟩|b\rangle is the single-qubit vector with amplitude one at bb and zero at the other bit.✦ For a one-qubit vector vv, the rank-one operator |v⟩⟨v||v\rangle\langle v| has entries vavb¯v_a\overline{v_b} for bits a,b∈{0,1}a,b\in\{0,1\}.✦ Tensor products of single-qubit operators AiA_i are defined by (1). (⨂i=1NAi)z,w=∏i=1N(Ai)zi,wi.\left(\bigotimes_{i=1}^N A_i\right)_{z,w} =\prod_{i=1}^N(A_i)_{z_i,w_i}.(1)✦

The input wire set InI_n, the zero-padded input zxz_x of a word x∈{0,1}nx\in\{0,1\}^n, and its complementary input word z‾x\bar z_x are specified in (2). For any wire set FF, flip⁡F\operatorname{flip}_F complements the bits in FF and fixes all other bits.✦ In={1,…,n},zx=(x,0N−n),z‾x=flip⁡In(zx).I_n=\{1,\ldots,n\},\qquad z_x=(x,0^{N-n}),\qquad \bar z_x=\operatorname{flip}_{I_n}(z_x).(2)

The parity π(x)\pi(x) is the sum of the input bits modulo two.✦ The bit character χ\chi is the real-valued function on {0,1}\{0,1\} defined in (3). π(x)=⨁i=1nxi,χ(b)={1,b=0,−1,b=1.\pi(x)=\bigoplus_{i=1}^n x_i,\qquad \chi(b)=\begin{cases}1,&b=0,\\-1,&b=1.\end{cases}(3)

For an operator WW on NN qubits and a full input word z∈{0,1}Nz\in\{0,1\}^N, the output Born probability pW,o(b∣z)p_{W,o}(b\mid z) and parity success probability sW,o(x)s_{W,o}(x) are the sums over full output words in (4). pW,o(b∣z)=∑y∈{0,1}Nyo=b|Wy,z|2,sW,o(x)=∑y∈{0,1}Nyo=π(x)|Wy,zx|2.p_{W,o}(b\mid z)=\sum_{\substack{y\in\{0,1\}^N\\y_o=b}}|W_{y,z}|^2, \qquad s_{W,o}(x)=\sum_{\substack{y\in\{0,1\}^N\\y_o=\pi(x)}}|W_{y,z_x}|^2.(4)

A local unitary layer L=(Li)i=1NL=(L_i)_{i=1}^N on NN qubits is a family of one-qubit unitaries, one for every wire; its matrix is ⨂iLi\bigotimes_iL_i. The Hadamard gate HH, with normalization 1/21/\sqrt2, and the input Hadamard layer matrix Hn,NH_{n,N} are given in (5), where II is the single-qubit identity matrix. H=12(111−1),Hn,N=H⊗n⊗I⊗(N−n).H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad H_{n,N}=H^{\otimes n}\otimes I^{\otimes(N-n)}.(5)

Product Projections and Circuit Classes

Product projection data MM on NN qubits consist of a support SS of wires and one-qubit vectors viv_i, normalized for every i∈Si\in S.✦ For a wire set FF, the mismatch pattern projection PFP_F, the product projection [M=0][M=0], and the high spectral projection [M≥r][M\ge r] are defined in (6); the real cutoff rr includes equality. PF=⨂i=1N{I−|vi⟩⟨vi|,i∈S∩F,|vi⟩⟨vi|,i∈S\F,I,i∉S,[M=0]=P⌀,[M≥r]=∑F⊆S|F|≥rPF.\begin{aligned} P_F&=\bigotimes_{i=1}^N \begin{cases} I-|v_i\rangle\langle v_i|,&i\in S\cap F,\\ |v_i\rangle\langle v_i|,&i\in S\setminus F,\\ I,&i\notin S, \end{cases}\\ [M=0]&=P_{\varnothing},\qquad [M\ge r]=\sum_{\substack{F\subseteq S\\|F|\ge r}}P_F. \end{aligned}(6)

For a full word z∈{0,1}Nz\in\{0,1\}^N, the computational basis count MzM_z is the product projection data on NN qubits with every wire in its support and local vectors |zi⟩|z_i\rangle.✦ The zero-outcome count DoD_o for an output wire oo among NN qubits is the product projection data with support {o}\{o\} and local vector |0⟩|0\rangle at every wire; write Po=[Do=0]P_o=[D_o=0].✦ For an operator WW, let CW,oC_{W,o} denote the input Hadamard conjugate of its zero-outcome operator, as in (7). CW,o=Hn,N(W*PoW)Hn,N.C_{W,o}=H_{n,N}(W^\ast P_oW)H_{n,N}.(7)

A local gate on NN qubits is an operator that applies a one-qubit unitary on a wire qq and the identity elsewhere; its support is {q}\{q\}. A Toffoli gate has a control set SS and a target t∉St\notin S, with support S∪{t}S\cup\{t\}. The basis action of a Toffoli gate with control set SS and target t∉St\notin S is the permutation of full basis words that complements the target bit exactly when every control bit is one and otherwise fixes the word; its gate matrix is the permutation matrix of this action.

A disjoint gate layer ℓ\ell is a chronological list of local or Toffoli gates with pairwise disjoint supports.✦ Its layer matrix GℓG_\ell is the product of its gate matrices.✦ For a chronological circuit list ℒ=(ℓ1,…,ℓm)\mathcal L=(\ell_1,\ldots,\ell_m), the circuit matrix is (8); the rightmost matrix acts first. Wℒ=Gℓm⋯Gℓ1.W_{\mathcal L}=G_{\ell_m}\cdots G_{\ell_1}.(8)✦

For a natural depth dd, the enlarged reflection-circuit class Ud(N)U_d(N) consists at depth zero of local layer matrices, and at depth d+1d+1 of products VRLVRL, where V∈Ud(N)V\in U_d(N), RR is a product of reflections associated with product projections on pairwise disjoint sets of wires, and LL is a local-layer matrix.✦ Identity layers are allowed.

For a natural depth dd and real exponents 0≤s<t0\le s<t, the uniform localization assertion Bd(s,t)B_d(s,t) is the existence of a threshold N0N_0 such that (9) holds for every N≥N0N\ge N_0, every U∈Ud(N)U\in U_d(N), and all product projection data M,DM,D on NN qubits. The full localization assertion is the statement that Bd(s,t)B_d(s,t) holds for every natural depth dd and every pair of real exponents 0≤s<t0\le s<t.✦ Every operator norm here is the Euclidean operator norm. ∥[M≥Nt]U[D=0]U*[M=0]∥2→2≤exp⁡(−Ns).\bigl\|[M\ge N^t]U[D=0]U^\ast[M=0]\bigr\|_{2\to2} \le \exp(-N^s).(9)

The Claim

Theorem 1. Let n≤Nn\le N and let oo be an output wire. For every operator WW on NN qubits and every full input word zz, the Born diagonal identity is (10). (W*PoW)z,z=pW,o(0∣z).(W^\ast P_oW)_{z,z}=p_{W,o}(0\mid z).(10)✦

For every operator BB on NN qubits, the parity character trace identity is (11). ∑x∈{0,1}n(Hn,NBHn,N)z‾x,zx=∑x∈{0,1}nχ(π(x))Bzx,zx.\sum_{x\in\{0,1\}^n}(H_{n,N}BH_{n,N})_{\bar z_x,z_x} =\sum_{x\in\{0,1\}^n}\chi(\pi(x))B_{z_x,z_x}.(11)✦

Suppose n>0n>0 and WW is unitary. Let ε,δ\varepsilon,\delta be real numbers such that every input xx satisfies sW,o(x)≥12+εs_{W,o}(x)\ge\tfrac12+\varepsilon and |(CW,o)z‾x,zx|≤δ|(C_{W,o})_{\bar z_x,z_x}|\le\delta. Then the parity advantage satisfies (12). ε≤δ.\varepsilon\le\delta.(12)✦

For every operator WW, input xx, and real cutoff r≤nr\le n, the complementary Hadamard entry obeys (13). |(CW,o)z‾x,zx|≤∥[Mzx≥r](Hn,NW*)Po(Hn,NW*)*[Mzx=0]∥2→2.\bigl|(C_{W,o})_{\bar z_x,z_x}\bigr| \le \bigl\|[M_{z_x}\ge r](H_{n,N}W^\ast)P_o (H_{n,N}W^\ast)^\ast[M_{z_x}=0]\bigr\|_{2\to2}.(13)✦

Assume the full localization assertion. Fix a natural depth bound dd, a real c≥1c\ge1, and a bias 0<ε≤120<\varepsilon\le\tfrac12; the following polynomial-qubit parity lower bound then holds for all input sizes from some natural threshold n0n_0 onward. When n≥n0n\ge n_0 and n≤N≤ncn\le N\le n^c, a chronological list ℒ\mathcal L of at most dd disjoint gate layers has, for each measured output wire oo, an input x∈{0,1}nx\in\{0,1\}^n satisfying (14). sWℒ,o(x)<12+ε.s_{W_{\mathcal L},o}(x)<\frac12+\varepsilon.(14)✦

What Is Checked

The identities and entry localization estimate are stated over arbitrary complex operators, the advantage estimate over unitary operators, and the asymptotic statement over disjoint gate layers with zero-initialized ancillas. The single-qubit Hadamard matrix in (5) is unitary.✦