OctoInformBeta

OpenAI preprint, September 2026 ยท Section 1. Introduction

Section 1: Physical circuits and measured-output parity: Parity success includes every final value of the unmeasured wires

Physical circuits with one measured output.

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

Let nn be the number of input qubits and NN the total number of qubits, including ancillas.

The Definition

Definition 1. A classical bit bb is an element of {0,1}\{0,1\}, with arithmetic modulo two.โœฆ An NN-bit computational basis string xx is an element of the set ๐’ฒN\mathcal W_N in (1): ๐’ฒN={0,1}{0,โ€ฆ,Nโˆ’1}.\mathcal W_N=\{0,1\}^{\{0,\ldots,N-1\}}.(1)โœฆ An operator WโˆˆOp⁡(N)W\in\operatorname{Op}(N) on NN qubits is a complex matrix indexed by ๐’ฒNร—๐’ฒN\mathcal W_N\times\mathcal W_N, as in (2), with the row index denoting the output string: Op⁡(N)=โ„‚๐’ฒNร—๐’ฒN.\operatorname{Op}(N) =\mathbb C^{\mathcal W_N\times\mathcal W_N}.(2)โœฆ A single-qubit operator aa is a complex 2ร—22\times2 matrix indexed by classical bits.โœฆ For single-qubit operators a0,โ€ฆ,aNโˆ’1a_0,\ldots,a_{N-1}, their tensor product is the operator whose entries, for basis strings x,yโˆˆ๐’ฒNx,y\in\mathcal W_N, are defined by (3): (โจ‚i=0Nโˆ’1ai)y,x=โˆi=0Nโˆ’1(ai)yi,xi.\left(\bigotimes_{i=0}^{N-1}a_i\right)_{y,x} =\prod_{i=0}^{N-1}(a_i)_{y_i,x_i}.(3)โœฆ

An elementary gate gโˆˆ๐’ขNg\in\mathcal G_N on NN qubits is a local single-qubit unitary or a Toffoli gate, as specified in (4), where U(2)\mathrm U(2) is the group of single-qubit unitaries: ๐’ขN={local⁡(q,u):0โ‰คq<N,uโˆˆU(2)}โˆช{Toffoli⁡(C,t):CโІ{0,โ€ฆ,Nโˆ’1},0โ‰คt<N,tโˆ‰C}.\begin{split} \mathcal G_N={}& \{\operatorname{local}(q,u):0\le q<N,\ u\in\mathrm U(2)\}\\ &{}\cup \{\operatorname{Toffoli}(C,t): C\subseteq\{0,\ldots,N-1\},\ 0\le t<N,\ t\notin C\}. \end{split}(4)โœฆ The support supp⁡(g)\operatorname{supp}(g) of an elementary gate gโˆˆ๐’ขNg\in\mathcal G_N is its set of participating wires, given by (5): supp⁡(local⁡(q,u))={q},supp⁡(Toffoli⁡(C,t))=Cโˆช{t}.\operatorname{supp}(\operatorname{local}(q,u))=\{q\}, \qquad \operatorname{supp}(\operatorname{Toffoli}(C,t))=C\cup\{t\}.(5)โœฆ For a control set CโІ{0,โ€ฆ,Nโˆ’1}C\subseteq\{0,\ldots,N-1\} and a target wire tโˆˆ{0,โ€ฆ,Nโˆ’1}\Ct\in\{0,\ldots,N-1\}\setminus C, the Toffoli basis action TC,tT_{C,t} is the map from ๐’ฒN\mathcal W_N to ๐’ฒN\mathcal W_N defined by (6): (TC,tx)j={1โˆ’xt,j=tand xi=1 for every iโˆˆC,xj,otherwise.(T_{C,t}x)_j= \begin{cases} 1-x_t,&j=t\ \text{and }x_i=1\text{ for every }i\in C,\\ x_j,&\text{otherwise}. \end{cases}(6)โœฆ The matrix G(local⁡(q,u))G(\operatorname{local}(q,u)) is the tensor product (3) with aq=ua_q=u and ai=I2a_i=I_2 for iโ‰ qi\ne q, where I2I_2 is the single-qubit identity matrix. The matrix of a Toffoli gate has entries G(Toffoli⁡(C,t))y,x=๐Ÿ{y=TC,tx}G(\operatorname{Toffoli}(C,t))_{y,x}=\mathbf1_{\{y=T_{C,t}x\}}, using (6), where the indicator is one when its condition holds and zero otherwise.

A physical layer LL on NN qubits is a finite list of elementary gates whose supports are pairwise disjoint, as specified in (7): L=(g1,โ€ฆ,gm),gaโˆˆ๐’ขN,supp⁡(ga)โˆฉsupp⁡(gb)=โŒ€(aโ‰ b).L=(g_1,\ldots,g_m),\qquad g_a\in\mathcal G_N,\qquad \operatorname{supp}(g_a)\cap\operatorname{supp}(g_b)=\varnothing \quad(a\ne b).(7)โœฆ The matrix A(L)A(L) of a physical layer is the product in (8), with the empty product equal to the identity: A(L)=G(g1)โ‹ฏG(gm).A(L)=G(g_1)\cdots G(g_m).(8)โœฆ A physical circuit ๐’ž=(L1,โ€ฆ,Lโ„“)\mathcal C=(L_1,\ldots,L_\ell) on NN qubits is a chronological list of physical layers on NN qubits. The operator W๐’žโˆˆOp⁡(N)W_{\mathcal C}\in\operatorname{Op}(N) of a physical circuit ๐’ž=(L1,โ€ฆ,Lโ„“)\mathcal C=(L_1,\ldots,L_\ell) on NN qubits is the product of layer matrices in (9), with the rightmost matrix acting first and the empty circuit having the identity operator II: W๐’ž=A(Lโ„“)โ‹ฏA(L1).W_{\mathcal C}=A(L_\ell)\cdots A(L_1).(9)โœฆ

For nโ‰คNn\le N, the initialization xห†โˆˆ๐’ฒN\widehat x\in\mathcal W_N of an input string xโˆˆ๐’ฒnx\in\mathcal W_n is the NN-bit string defined by (10).โœฆ In a physical input register with nโ‰คNn\le N, the first nn wires carry the input and the remaining wires start at zero.โœฆ xห†j={xj,j<n,0,jโ‰ฅn,0โ‰คj<N.\widehat x_j= \begin{cases} x_j,&j<n,\\ 0,&j\ge n, \end{cases} \qquad 0\le j<N.(10)โœฆ The parity ฯ€(x)โˆˆ{0,1}\pi(x)\in\{0,1\} of an input string xโˆˆ๐’ฒnx\in\mathcal W_n is the bit defined in (11): ฯ€(x)=โˆ‘i=0nโˆ’1xi(mod⁡2).\pi(x)=\sum_{i=0}^{n-1}x_i\pmod 2.(11)โœฆ For WโˆˆOp⁡(N)W\in\operatorname{Op}(N), an input string xโˆˆ๐’ฒnx\in\mathcal W_n with nโ‰คNn\le N, and a designated output wire oo with 0โ‰คo<N0\le o<N, the parity success probability psucc(W,o;x)p_{\mathrm{succ}}(W,o;x) is the quantity in (12): psucc(W,o;x)=โˆ‘yโˆˆ๐’ฒNyo=ฯ€(x)|Wy,xห†|2.p_{\mathrm{succ}}(W,o;x) =\sum_{\substack{y\in\mathcal W_N\\y_o=\pi(x)}} \left|W_{y,\widehat x}\right|^2.(12)โœฆ

What Is Checked

The circuit constructions are stated over finite registers and finite gate lists, while the success expression (12) is defined for every complex operator WโˆˆOp⁡(N)W\in\operatorname{Op}(N).