OctoInformBeta

OpenAI preprint, September 2026 · Section 2. Product projections and localization

Section 2: Reflection normal form and inverse closure: Physical circuits retain their layer count, and taking adjoints preserves the enlarged depth

A reflection normal form for quantum circuits.

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

For localization, circuit depth counts layers of disjoint product-projection reflections. The comparison with circuits built from one-qubit and Toffoli gates concerns the same NN wires, including any ancillas.

A classical bit belongs to {0,1}\{0,1\}✦, and bit strings xx and yy of length NN assign bits xix_i and yiy_i to each wire i∈{1,…,N}i\in\{1,\ldots,N\}. A quantum operator on NN qubits is a complex matrix indexed by these strings✦; a single-qubit operator is a complex matrix indexed by bits.✦ For single-qubit operators AiA_i, the tensor product has the matrix entries in (1). (⨂i=1NAi)x,y=∏i=1N(Ai)xi,yi.\left(\bigotimes_{i=1}^{N} A_i\right)_{x,y} =\prod_{i=1}^{N}(A_i)_{x_i,y_i}.(1)✦

A physical gate gg on NN qubits is either a one-qubit unitary uu on a wire qq, or a Toffoli gate with a finite control set CC and a target t∉Ct\notin C.✦ The Toffoli basis action τC,t\tau_{C,t} is the map on bit strings in (2). (τC,t(x))i={1−xt,i=tand xj=1 for every j∈C,xi,otherwise.\bigl(\tau_{C,t}(x)\bigr)_i= \begin{cases} 1-x_t,&i=t\ \text{and }x_j=1\text{ for every }j\in C,\\ x_i,&\text{otherwise}. \end{cases}(2)✦ The gate matrix G(g)G(g) acts as uu on wire qq and as the identity elsewhere for a local gate; the Toffoli matrix is denoted by TC,tT_{C,t}. Their entries and supports are specified in (3), where II is the single-qubit identity. G(q,u)=⨂i=1NAi,Ai={u,i=q,I,i≠q,supp⁡(q,u)={q},(TC,t)x,y={1,x=τC,t(y),0,otherwise,supp⁡(TC,t)=C∪{t}.\begin{aligned} G(q,u)&=\bigotimes_{i=1}^{N} A_i, &A_i&=\begin{cases}u,&i=q,\\I,&i\ne q,\end{cases} &\operatorname{supp}(q,u)&=\{q\},\\ (T_{C,t})_{x,y}&=\begin{cases}1,&x=\tau_{C,t}(y),\\0,&\text{otherwise},\end{cases} &&&\operatorname{supp}(T_{C,t})&=C\cup\{t\}. \end{aligned}(3)

A physical layer H=(g1,…,gm)H=(g_1,\ldots,g_m) is a chronological list of physical gates with pairwise disjoint supports.✦ Its layer unitary G(H)G(H) and the circuit matrix U(𝒞)U(\mathcal C) of a chronological list 𝒞=(H1,…,Hd)\mathcal C=(H_1,\ldots,H_d) of physical layers are the products in (4); the rightmost matrix acts first. An empty product is the identity. G(H)=G(g1)⋯G(gm),U(𝒞)=G(Hd)⋯G(H1).G(H)=G(g_1)\cdots G(g_m),\qquad U(\mathcal C)=G(H_d)\cdots G(H_1).(4)

Product Projections

Product projection data M=(S,v)M=(S,v) on NN qubits consist of a finite support SS of wires and local vectors vi∈ℂ2v_i\in\mathbb C^2 for all wires, normalized on SS as in (5). ∑b∈{0,1}|vi(b)|2=1(i∈S).\sum_{b\in\{0,1\}}|v_i(b)|^2=1\qquad(i\in S).(5)✦ For a one-qubit vector vv, the outer product |v⟩⟨v||v\rangle\langle v| has entry v(a)v(b)¯v(a)\overline{v(b)} in row aa and column bb.✦ The product projection [M=0][M=0] and its reflection F(M)F(M) are the operators defined in (6). [M=0]=⨂i=1NPi,Pi={|vi⟩⟨vi|,i∈S,I,i∉S,F(M)=I−2[M=0].[M=0]=\bigotimes_{i=1}^{N}P_i,\qquad P_i=\begin{cases}|v_i\rangle\langle v_i|,&i\in S,\\I,&i\notin S,\end{cases} \qquad F(M)=I-2[M=0].(6)

For a bit b∈{0,1}b\in\{0,1\}, the computational basis vector |b⟩∈ℂ2|b\rangle\in\mathbb C^2 is the vector with amplitude 11 at bb and 00 at the other bit.✦ The minus state |−⟩|-\rangle and the Toffoli product projection data MC,tM_{C,t} are defined in (7), with normalization 1/21/\sqrt{2} and target t∉Ct\notin C. |−⟩=|0⟩−|1⟩2,MC,t=(C∪{t},v),vi={|−⟩,i=t,|1⟩,i≠t.|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}},\qquad M_{C,t}=(C\cup\{t\},v),\qquad v_i=\begin{cases}|-\rangle,&i=t,\\|1\rangle,&i\ne t.\end{cases}(7)

The Claim

Definition 1. A local unitary layer L=(u1,…,uN)L=(u_1,\ldots,u_N) is a choice of a one-qubit unitary ui∈U(2)u_i\in\mathrm U(2) on each wire, where U(2)\mathrm U(2) is the group of two-dimensional unitary matrices. Its matrix ℓ(L)\ell(L) is given in (8). L∈U(2)N,ℓ(L)=⨂i=1Nui.L\in\mathrm U(2)^N,\qquad \ell(L)=\bigotimes_{i=1}^{N}u_i.(8)✦ A disjoint reflection layer R=(M1,…,Mm)R=(M_1,\ldots,M_m) is a list of product projection data whose supports are pairwise disjoint, with matrix ρ(R)\rho(R) specified in (9). supp⁡(Mj)∩supp⁡(Mk)=⌀(j≠k),ρ(R)=F(M1)⋯F(Mm).\operatorname{supp}(M_j)\cap\operatorname{supp}(M_k)=\varnothing \quad(j\ne k),\qquad \rho(R)=F(M_1)\cdots F(M_m).(9)✦ The enlarged reflection-circuit class Ud(N)U_d(N) is the class of operators defined recursively by (10); LL ranges over local unitary layers and RR over disjoint reflection layers. U0(N)={ℓ(L):L is a local unitary layer},Ud+1(N)={Vρ(R)ℓ(L):V∈Ud(N),R,L as above}.\begin{aligned} U_0(N)&=\{\ell(L):L\text{ is a local unitary layer}\},\\ U_{d+1}(N)&=\{V\rho(R)\ell(L):V\in U_d(N),\ R,L\text{ as above}\}. \end{aligned}(10)✦

Theorem 1. Let CC be a finite set of control wires and let t∉Ct\notin C be a target. Then TC,t=F(MC,t).T_{C,t}=F(M_{C,t}).(11)✦ Let 𝒞\mathcal C be a chronological list of dd physical layers on NN qubits. Then U(𝒞)∈Ud(N).U(\mathcal C)\in U_d(N).(12)✦ Let U∈Ud(N)U\in U_d(N). Then U†∈Ud(N).U^\dagger\in U_d(N).(13)✦

What Is Checked

The statements (11), (12) and (13) concern complex matrices indexed by all NN-bit strings, product projection data normalized on their supports, and physical and reflection layers with pairwise disjoint supports.