OctoInformBeta

OpenAI preprint, September 2026 · Section 5. The finite scale induction

Lemma 7: Finite polynomial transition estimates and explicit intermediate exponents

A backward step for circuit localization.

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

The finite-scale induction concerns exponentially small transition amplitudes between sectors specified by local qubit states, with cutoffs that are powers of the total number NN of qubits.

A classical bit is an element of {0,1}\{0,1\}✦, and a word x∈{0,1}Nx\in\{0,1\}^N assigns a bit to each wire.✦ A quantum operator on NN qubits is a complex matrix indexed by these words✦; a single-qubit operator is a complex matrix indexed by bits.✦ All operator norms are Euclidean operator norms. The adjoint is denoted by †\dagger, and conjugation of an operator XX by UU means UXU†UXU^\dagger.✦

For a one-qubit vector vv, its outer product |v⟩⟨v||v\rangle\langle v| is the single-qubit operator in (1); for a family aia_i of single-qubit operators, its tensor product ⨂i=1Nai\bigotimes_{i=1}^N a_i is the quantum operator on NN qubits with the entries given there. (|v⟩⟨v|)xy=vxvy¯,x,y∈{0,1},(⨂i=1Nai)xy=∏i=1N(ai)xiyi,x,y∈{0,1}N.\begin{aligned} \bigl(|v\rangle\langle v|\bigr)_{xy} &=v_x\overline{v_y}, &&x,y\in\{0,1\},\\ \left(\bigotimes_{i=1}^N a_i\right)_{xy} &=\prod_{i=1}^N(a_i)_{x_i y_i}, &&x,y\in\{0,1\}^N. \end{aligned}(1)

Product projection data MM on NN qubits consist of a support SM⊆{1,…,N}S_M\subseteq\{1,\ldots,N\} and local vectors viM∈ℂ2v_i^M\in\mathbb C^2, normalized on that support as in (2). ∑z∈{0,1}|(viM)z|2=1(i∈SM).\sum_{z\in\{0,1\}}\left|(v_i^M)_z\right|^2=1 \qquad(i\in S_M).(2)✦ Write QiM=|viM⟩⟨viM|Q_i^M=|v_i^M\rangle\langle v_i^M| and let II denote the identity on the relevant space. The mismatch pattern projection PFMP_F^M, for a set FF of wire indices, is the tensor product in (3). PFM=⨂i=1N{I−QiM,i∈SM∩F,QiM,i∈SM\F,I,i∉SM.P_F^M=\bigotimes_{i=1}^N \begin{cases} I-Q_i^M,&i\in S_M\cap F,\\ Q_i^M,&i\in S_M\setminus F,\\ I,&i\notin S_M. \end{cases}(3)✦

For product projection data MM on NN qubits, the product projection [M=0][M=0] is the projection that selects the prescribed local vectors on the support of MM.✦ For product projection data MM on NN qubits and a real cutoff rr, the high spectral projection [M≥r][M\ge r] is the sum of the mismatch pattern projections of MM with at least rr mismatches, and the low spectral projection [M<r][M<r] is the complementary projection, as defined in (4). [M=0]=⨂i=1N{QiM,i∈SM,I,i∉SM,[M≥r]=∑F⊆SM|F|≥rPFM,[M<r]=I−[M≥r].\begin{aligned} [M=0]&=\bigotimes_{i=1}^N \begin{cases}Q_i^M,&i\in S_M,\\I,&i\notin S_M,\end{cases}\\ [M\ge r]&=\sum_{\substack{F\subseteq S_M\\|F|\ge r}}P_F^M, &[M<r]&=I-[M\ge r]. \end{aligned}(4)

For product projection data MM on NN qubits, the spectral functional calculus is the map that sends a function f:ℕ→ℝf:\mathbb N\to\mathbb R to the operator f(M)f(M) in (5). For a real polynomial p(X)=∑kckXkp(X)=\sum_k c_kX^k, the operator p(M)p(M) and the real number WN(p)W_N(p), its weighted coefficient cost, are given in the same equation; write deg⁡0p\deg_0 p for its degree, with deg⁡00=0\deg_0 0=0. f(M)=∑F⊆SMf(|F|)PFM,p(M)=∑F⊆SMp(|F|)PFM,WN(p)=∑k|ck|Nk.\begin{aligned} f(M)&=\sum_{F\subseteq S_M}f(|F|)P_F^M,\\ p(M)&=\sum_{F\subseteq S_M}p(|F|)P_F^M, &W_N(p)&=\sum_k|c_k|N^k. \end{aligned}(5)

Uniform Localization

A local-layer matrix is a tensor product of single-qubit unitary operators, and a reflection-layer matrix is the matrix of a layer of reflections on pairwise disjoint sets of wires. For a natural depth dd, the enlarged reflection-circuit class Ud(N)U_d(N) is the class of operators of depth at most dd defined recursively by (6). Identity layers are allowed, and the rightmost matrix acts first. U0(N)={L:L is a local-layer matrix},Ud+1(N)={VRL:V∈Ud(N),R is a reflection-layer matrix,L is a local-layer matrix}.\begin{aligned} U_0(N)&=\{L:L\text{ is a local-layer matrix}\},\\ U_{d+1}(N)&=\{VRL:V\in U_d(N),\ R\text{ is a reflection-layer matrix},\ L\text{ is a local-layer matrix}\}. \end{aligned}(6)✦

For a natural depth dd and real exponents s,ts,t, the uniform localization assertion Bd(s,t)B_d(s,t) requires (7) for all sufficiently large NN, simultaneously for every U∈Ud(N)U\in U_d(N) and all product projection data M,DM,D. ∥[M≥Nt]U[D=0]U†[M=0]∥≤exp⁡(−Ns).\bigl\|[M\ge N^t]U[D=0]U^\dagger[M=0]\bigr\| \le \exp(-N^s).(7)✦

The Claim

Theorem 1. Let M,DM,D be product projection data on NN qubits, UU a quantum operator, and pp a real polynomial. Let r,μ,δr,\mu,\delta be real, with δ≥0\delta\ge0 and deg⁡0p≤μ\deg_0p\le\mu. Suppose (8) holds for every choice of product projection data KK with |SK|≤μ|S_K|\le\mu. ∥[M≥r]U[K=0]U†[M=0]∥≤δ.\bigl\|[M\ge r]U[K=0]U^\dagger[M=0]\bigr\|\le\delta.(8) Then the polynomial transition estimate is (9). ∥[M≥r]Up(D)U†[M=0]∥≤WN(p)δ.\bigl\|[M\ge r]Up(D)U^\dagger[M=0]\bigr\|\le W_N(p)\delta.(9)✦

Suppose instead that UU is unitary and that real numbers r,b,A,B,E,Tr,b,A,B,E,T satisfy (10). The finite backward estimate is (11). ∥[M≥r]Up(D)U†[M=0]∥≤A,∥p(D)∥≤B,∥([D=0]−p(D))[D<b]∥≤E,∥[D≥b]U†[M=0]U[D=0]∥≤T.\begin{aligned} \bigl\|[M\ge r]Up(D)U^\dagger[M=0]\bigr\|&\le A,\\ \|p(D)\|&\le B,\\ \bigl\|([D=0]-p(D))[D<b]\bigr\|&\le E,\\ \bigl\|[D\ge b]U^\dagger[M=0]U[D=0]\bigr\|&\le T. \end{aligned}(10) ∥[M≥r]U[D=0]U†[M=0]∥2≤A+E+(1+B)T.\bigl\|[M\ge r]U[D=0]U^\dagger[M=0]\bigr\|^2 \le A+E+(1+B)T.(11)✦

Let dd be a nonnegative integer and assume Bd(σ,τ)B_d(\sigma,\tau) for every pair of real exponents 0≤σ<τ0\le\sigma<\tau. Let real exponents s,a,u,w,t,bs,a,u,w,t,b satisfy (12), and assume Bd+1(t,b)B_{d+1}(t,b). 0≤s<a<u<w<t<b,a+b2<u.0\le s<a<u<w<t<b, \qquad \frac{a+b}{2}<u.(12) The uniform backward conclusion is (13). Bd+1(s,t).B_{d+1}(s,t).(13)✦

In the paper, the result reads: for d≥1d\ge1, assume Bd−1(σ,τ)B_{d-1}(\sigma,\tau) for every fixed 0≤σ<τ0\le\sigma<\tau; for fixed real 0≤s<t<b<2t−s0\le s<t<b<2t-s, Bd(t,b)B_d(t,b) implies Bd(s,t)B_d(s,t).

What Is Checked

The uniform statement (13) is over the recursively defined circuit classes and normalized product projection data, while the finite statements (11) and (9) concern real polynomials and arbitrary qubit counts, with unitarity required for the finite backward estimate.