By bilinearity, it suffices to consider \(A=\bigotimes _i A_i\) and \(B=\bigotimes _i B_i\), with \(A_i=\mathbb 1\) off \(S\) and \(B_i=\mathbb 1\) off \(T\). Pairing the local coordinates identifies their tensor product with \(\bigotimes _i(A_i\otimes B_i)\). Every factor outside \(S\cup T\) is the identity.

On the ring, the bonds meeting \(X\) are \(\{ i-1,i\} \) and \(\{ i,i+1\} \) for \(i\in X\), so the one-step neighbourhood is the set of sites within ring distance \(1\), and a displacement of modulus at most \(r+1\) is one of modulus at most \(r\) followed by one of modulus at most \(1\). In the other two cases, two sites on a common bond are at distance at most \(1\), and the inclusion follows by induction on \(r\) and the triangle inequality. A site in both light cones would give, by the triangle inequality, two points of the two sets at distance at most \(2r\). The composition law holds because the light cone of radius \(r\) is the \(r\)-fold iterate of the one-step neighbourhood.

By induction on the layers it suffices to treat one layer \(W\). Split its gates into those whose bond meets \(X\), with product \(G\), and the others, with product \(H\). The gates commute, so \(W=HG\). The operator \(H\) is unitary and acts on the complement of \(X\), so it commutes with \(Z\) and \(W^\dagger ZW=G^\dagger ZG\). The bonds of \(G\) lie in the one-step neighbourhood of \(X\), and products and adjoints of operators acting on a set act on it. On the ring, Lemma 33.1.5 identifies the light cone.

Write \(|\psi \rangle =U|\pi \rangle \) with \(|\pi \rangle =\bigotimes _i|v_i\rangle \). Since \(UU^\dagger =\mathbb 1\), \(\langle \psi |ZZ'|\psi \rangle =\langle \pi |(U^\dagger ZU)(U^\dagger Z'U)|\pi \rangle \), and by Lemma 33.1.6 the two factors act on disjoint sets of sites. For products \(\bigotimes _i m_i\) and \(\bigotimes _i m'_i\) with disjoint supports the expectation in \(|\pi \rangle \) is \(\prod _i\langle v_i|m_im'_i|v_i\rangle \), and at each site one of \(m_i\), \(m'_i\) is the identity; bilinearity then gives \(\langle \pi |AB|\pi \rangle \langle \pi | \pi \rangle =\langle \pi |A|\pi \rangle \langle \pi |B|\pi \rangle \) for \(A\), \(B\) acting on disjoint sets.

If \(U=W_T\cdots W_1\) with layers \(W_k\), then \(U^\dagger =W_1^\dagger \cdots W_T^\dagger \), and \(W_k^\dagger \) is the layer whose gates are the adjoints of the gates of \(W_k\), on the same bonds. The layers of \(U'U\) are those of \(U\) followed by those of \(U'\).

The first layer applies \(u_k\otimes u_{k+1}\) on the pairs \(\{ k,k+1\} \) with \(k\) odd and \(k{\lt}N\), and the second applies \(u_N\) when \(N\) is odd. A nonzero product vector \(\bigotimes _i|v_i\rangle \) has \(v_i\neq 0\) for every \(i\), and \(|v_i\rangle =c_iu_i|0\rangle \) for a unitary \(u_i\) whose first column is \(|v_i\rangle /\lVert v_i\rVert \) and \(c_i=\lVert v_i\rVert \). Hence \(\bigotimes _i|v_i\rangle =(\prod _ic_i)(\bigotimes _iu_i)|0\cdots 0\rangle \), and Lemma 33.1.8 composes the two circuits.

A configuration \(x\) agrees with \(y\) outside the range of \(f\circ e\) exactly when it agrees with \(y\) outside the range of \(f\) and \(x\circ f\) agrees with \(y\circ f\) outside the range of \(e\). Placed operators with disjoint ranges act on disjoint sets of sites, hence commute. The product formula follows by induction on \(K\): the sum over intermediate configurations in the matrix product has a single nonzero term, the configuration agreeing with the output on the range of the new map and with the input elsewhere.

The statements on configurations are evaluations of the definition. For the first item, the placed matrices act on disjoint windows, so by Lemma 33.1.10 the matrix element of their product is the product over the windows of the matrix elements of the \(Y_p\), and it vanishes unless the output configuration is \(0\) outside the windows. The second item is the matrix product written out.

In series the layers of \(U\) are followed by those of \(U'\) (Lemma 33.1.8). In parallel, by induction on \(I\), the layers of two circuits of depth \(T\) inside disjoint sets are merged one by one: the union of two layers acting inside disjoint sets is a layer, whose operator is the product of the two because the nonempty bonds of the two layers are distinct, and the circuit inside one set commutes with every layer inside the other. A product of \(K\) gates on neighbouring sites of the open chain, placed by \(e\), is the circuit whose \(j\)-th layer is the \(j\)-th gate placed by \(e\), padded with empty layers; the products on disjoint ranges then run in parallel.

Dividing by a root of the determinant of order \(d^n\), a global phase and hence a single-site gate, reduces to determinant one. Column-by-column Givens elimination writes such a unitary as a product of two-level operators, each a real rotation or a diagonal phase on the span of two basis vectors. Write \(G_{ab}(g)\) for the operator acting as the \(2\times 2\) matrix \(g\) on the span of the basis vectors \(|a\rangle ,|b\rangle \) and as the identity on their complement, and \(Q=\bigl(\begin{smallmatrix} 0 & 1 \\ -1 & 0 \end{smallmatrix}\bigr)\) for the quarter turn. For pairwise distinct \(a,b,c\),

and choosing \(c\) to differ from \(a\) at one site fewer than \(b\) does reduces a two-level operator between configurations differing at several sites to one between configurations differing at one site fewer. Between configurations differing at one site \(t\) it is a single-site operation at \(t\) controlled by the other sites. Every rotation and every phase of determinant one is a group commutator \(g_1g_2g_1^\dagger g_2^\dagger \). Write \(C_S(u)\) for the single-site operation \(u\) at \(t\) controlled by the sites of \(S\), with \(t\notin S\); for unitaries \(v,w\) and a site \(s\neq t\),

so a controlled commutator is a product of two operations with one control fewer and two operations on two sites; induction removes the controls. An operation on two distant sites is conjugated to neighbouring sites by SWAP gates.

The first two items are the support statements of Lemma 33.1.10: a placed operator acts on the range of the placement, and placing composes. For the third item, the sites of the window lie in a pair \(\{ a',a'+1\} \) with \(a'=\min (a,n-2)\). For the fourth, enlarge the window of each gate to \(\min (m,n)\ge 2\) consecutive sites inside the chain. The gate is then a unitary on these sites placed on the chain, hence by Theorem 33.2.1 a product of at most \(K_{\min (m,n)}\) gates on neighbouring sites; take \(C=\sum _{l\le m}K_l\).

For each configuration \(x\) exactly one string \(m\), the restriction of \(x\) to \(S\), has \(P_m|x\rangle \neq 0\). So \(\sum _mP_mU|\pi \rangle =U|\pi \rangle \), which is nonzero because \(U\) is unitary; the unitary \(V_m=\bigotimes _iv_{m,i}\), with \(V_m^\dagger V_m=\bigotimes _iv_{m,i}^\dagger v_{m,i}=\mathbb 1\), keeps a nonzero vector nonzero, and \(V_mP_mU|\pi \rangle =c|\psi \rangle \neq 0\) forces \(|\psi \rangle \neq 0\).

For the first statement take \(S=\emptyset \) and \(v_{m,i}=\mathbb 1\). For the second, \(P_m=\mathbb 1\) for the only string \(m\), so \(V_mU|\pi \rangle =c|\psi \rangle \) with \(c\neq 0\) by Lemma 33.3.2. Take \(u_i=v_{m,i}^\dagger \). Then \(\bigotimes _iu_i|\psi \rangle =U(c^{-1}|\pi \rangle )\), where \(c^{-1}|\pi \rangle \) is the product vector with the vector of one site multiplied by \(c^{-1}\), and the circuit \(U\) of depth at most \(T\) is padded with empty layers to depth \(T\).

Enumerating \(X\) writes \(P_\sigma \) as \(Y\otimes \mathbb 1\) with \(Y_{u,w}=1\) if \(w=\sigma (x)|_X\) for some \(x\) with \(x|_X=u\), and \(0\) otherwise; permutation matrices are unitary. For the layer, induct over the pairs: \(P_{\sigma _a}P_\rho =P_{\rho \sigma _a}\), and \(\rho \sigma _a\) agrees with \(\sigma _a\) on the pair \(\{ a,a+1\} \), which the earlier pairs do not meet, and with \(\sigma _k\) on an earlier pair \(\{ k,k+1\} \), because \(\sigma _a(x)\) agrees with \(x\) there. The entry of \(\bigotimes _iP_{\tau _i}\) at \((x,y)\) is \(\prod _i[y_i=\tau _i(x_i)]\), which is \(1\) if \(y=\tau (x)\) and \(0\) otherwise.

Since \(\sum _{m}P_{m}=\mathbb 1\) and \(U\) is unitary, some \(P_{m}U|v\rangle \) is nonzero, and the unitary \(V_m\) keeps it nonzero. The other statements follow by induction over the sequence of rounds and from the linearity of the operators.

An output of the concatenation is an output \(|w\rangle \) of \(\mathcal R'\) from an output \(c\, W|v\rangle \) of \(\mathcal R\), hence \(|w\rangle =c|w'\rangle \) with \(|w'\rangle \) an output of \(\mathcal R'\) from \(W|v\rangle \in E'\), and \(|w'\rangle =c'\, W'W|v\rangle \). The last statement is the definition of preparation with measurement rounds.

Let \(U\) be a unitary with \(\lVert X\rVert _1=\operatorname {tr}(X^\dagger U)\) for \(X=|u\rangle \langle v|\). Then \(\lVert X\rVert _1=\lvert \langle u|Uv | \rvert \rangle \leq \lVert u\rVert \, \lVert v\rVert \). For the second statement choose a phase \(c\) with \(\langle \psi |c\varphi | = \rangle \lvert \langle \psi |\varphi | \rvert \rangle \) and put \(|\varphi '\rangle =c|\varphi \rangle \), so that \(|\varphi '\rangle \langle \varphi '|=|\varphi \rangle \langle \varphi |\) and

By the triangle inequality the trace norm is at most \(2\lVert \psi -\varphi '\rVert \), and \(\lVert \psi -\varphi '\rVert ^2=2-2\lvert \langle \psi |\varphi | \rvert \rangle \).

Choose such a vector \(|\psi _N\rangle \) for every large \(N\). By Lemma 33.3.10 the trace norm of \(|\psi _N\rangle \langle \psi _N|-|\varphi _N\rangle \langle \varphi _N|\) is at most \(2\sqrt{2\varepsilon _N}\), which tends to zero.

Applying \(X_k\) to the basis vector \(|u\rangle \) gives the entries. The entry of the product at \((x,y)\) is \(\prod _k[y|_{S_k}=f_k(x|_{S_k})]\) when \(x\) and \(y\) agree outside the \(S_k\), and \(0\) otherwise; this is \(1\) exactly when \(y=\rho (x)\). For the product vector, only the configuration \(y'\) agreeing with \(y\) outside \(S\) and equal to \((z,\dots ,z)\) on \(S\) contributes.

The amplitude of \(|\chi _M\rangle \) at \(s\) is \(\alpha _{s_0}\) if all \(s_n\) are equal and \(0\) otherwise. Values are taken in \(\mathbb Z_b\). Start from the product vector with \(\sum _i\alpha _i|i\rangle \) on the system qudit \(0\), \(\sum _i|i\rangle \) on the other system qudits, and \(|0\rangle \) on the ancillas. A first layer of gates \(|k\rangle |a\rangle \mapsto |k\rangle |a+k\rangle \) on the system qudit \(n\) and its ancilla, and a second layer of gates \(|a\rangle |k\rangle \mapsto |a-k\rangle |k\rangle \) on the ancilla \(n\) and the system qudit \(n+1\), for \(n{\lt}M-1\), give

the last factor being the last ancilla. Measure the ancillas \(n{\lt}M-1\). The outcome \(m\) forces \(k_{n+1}=k_n-m_n\), so the system qudits are left in \(\sum _i\alpha _i\bigotimes _n|i-p_n\rangle \) with the prefix sums \(p_n=m_0+\cdots +m_{n-1}\). The single-site corrections, \(X^{p_n}\) on the system qudit \(n\) and \(X^{-m_n}\) on the ancilla \(n\), give \(|\chi _M\rangle \) with every ancilla in \(|0\rangle \). The two layers are layers of permutation gates and the corrections are single-site permutations, and Lemma 33.3.4 computes their action configuration by configuration. The product vector is nonzero because \(\alpha \neq 0\).

Let \(B_{J,a}\) be Kraus operators for \(\Psi _J\). Then \(B_{J,a}K_J\) are Kraus operators for \(\mathcal F\), and

The two composition identities follow by linearity of the finite sum.

Induct on the protocol tree. The onsite and layer cases use their channel properties, and the instrument case uses Theorem 33.4.2. To compose protocols, put the second protocol after each branch of the first. An instrument keeps the same branch depth, a nearest-neighbor layer adds one, and enlarging a depth bound commutes with adding the second depth. An onsite operation followed by a fixed continuation is an instrument whose continuation ignores its outcomes. This also embeds deterministic protocols. The remaining conversion properties follow from the identity channel, the depth bounds, composition, and preservation of positivity and trace.

Unitarity of \(U,V_m\), orthogonality of each \(P_m\), and \(\sum _mP_m=I\) give \(\sum _m(V_mP_mU)^{\dagger }(V_mP_mU)=I\). Conjugating a rank-one operator gives the stated pure-input formula. For deterministic preparation, every output is \(c_m\psi \), including \(c_m=0\) for an outcome of probability zero. Thus the average output is \((\sum _m|c_m|^2)|\psi \rangle \langle \psi |\). Trace preservation and normalization give \(\sum _m|c_m|^2=1\).

Use the round’s circuit as a deterministic local channel protocol. The following onsite instrument has the computational-basis projectors at measured sites and one identity Kraus operator at each unmeasured site. Its outcome tuples correspond bijectively to the measured configurations \(m\), and its product Kraus operators are \(P_m\). For outcome \(m\), choose the onsite channel of the product correction unitary \(V_m\). The resulting Kraus operators are exactly \(V_mP_mU\). The instrument and corrections have depth zero, so composition leaves the circuit’s depth bound unchanged.

The rows of \(F\) are orthonormal because \(\sum _b\zeta ^{(a-c)b}=d\, [a=c]\), the geometric sum of a \(d\)-th root of unity \(\zeta ^{a-c}\) that differs from \(1\) unless \(a=c\). The matrix \(X^xZ^z\) is a permutation matrix times a diagonal matrix of unimodular numbers.

These are entrywise computations. For the third item, \(|v\rangle \) has \(|0\rangle \) on \(Z\) exactly when the diagonal projection onto the configurations vanishing on \(Z\) fixes \(|v\rangle \), and that projection commutes with an operator acting outside \(Z\).

On a vector with \(|0\rangle \) at \(e\) and \(f\), the Fourier matrix at \(e\) gives the amplitude \(d^{-1/2}\) to every value \(x_e\), and the shift copies it to \(f\): this prepares \(d^{-1/2}\sum _j|j\rangle _e|j\rangle _f\). The second gate and the projections compute, configuration by configuration, the amplitude \(d^{-1/2}F_{z_c,\, x_f-z_e}\) for the content \(x_f-z_e\) moved from \(c\) to \(f\), which is \(d^{-1}\zeta ^{z_c(x_f-z_e)}\), the amplitude of the right-hand side. Configurations with \(x_c\neq z_c\) or \(x_e\neq z_e\) vanish on both sides.

The first gates act on pairwise disjoint pairs \(\{ e,f\} \), and the second gates on pairwise disjoint pairs \(\{ c,e\} \), so they form two layers. By induction over the list, the projections and the two layers factor into the hops one after the other: the first gate of the head \(h\) of the list commutes with the second gates of the other hops because its sites \(e,f\) are not theirs, and the projections at the sites of the other hops commute with the operator of \(h\). Lemma 33.5.4 for \(h\) applies because the other hops leave \(|0\rangle \) at \(e\) and \(f\). A single-site unitary at the site \(c\) of \(h\), left by another hop whose site \(f\) is \(c\), reappears at the site \(f\) of \(h\) after the transposition; so the hops leave a product of single-site unitaries, depending on the outcomes, after \(d^{-H}P_{h_1}\cdots P_{h_H}\). The correction is its inverse.

The first item composes two applications of Theorem 33.5.5. For the second, the sites \(a+j\) with \(0\le j{\lt}N\) are distinct, the transposition of the hop \(j\) exchanges \(a+2j\) and \(a+2j+2\), and the hops of the forward chain, applied in the order \(j=0,1,\dots \), move the content of \(a\) step by step to \(a+2L\); each hop moves the \(|0\rangle \) from \(a+2j+2\) to \(a+2j\), while \(a+2j+1\) keeps its \(|0\rangle \).

Two hops with disjoint sites satisfy the condition of validity in either order. The product of the transpositions of \(\mathcal L_g\) fixes the sites outside \(S_g\), hence maps \(S_g\) into itself, and the products of the other lists fix \(S_g\) pointwise.

By Lemma 33.5.7 the forward chains of all the gates form a valid list, and so do the backward chains, with products of transpositions \(P\) and \(P^{-1}\): on the stretch of \(g\) both agree with the chains of \(g\), which are inverse to each other. The forward chains need \(|0\rangle \) at the interiors; afterwards the sites \(a,\dots ,a+2L-1\) of every gate carry \(|0\rangle \), by Lemma 33.5.6 for its own chain and since the other chains act on disjoint sites. The gates on the pairs \(\{ a+2L,a+2L+1\} \) keep these \(|0\rangle \), which the backward chains need. By Lemma 33.5.6 every output is a multiple of \(P^{-1}GP|v\rangle \), with \(G\) the product of the gates on the neighbouring pairs, and \(P^{-1}GP\) is the product of the conjugated gates. The conjugate of \(u\) at \(a+2L,a+2L+1\) is \(u\) at \(P^{-1}(a+2L)=a\) and \(P^{-1}(a+2L+1)=a+2L+1\) by Lemma 33.5.3.

The chain of the site \(a+t\) meets the sites \(a+t,\dots ,a+t+2L\), and before it the sites \(a+t+1,\dots ,a+t+2L\) form the zone \(t+1\). Starting from \(|0\rangle \) at the zone \(s\), the interior, the round \(t\) moves the content of \(a+t\) to \(a+t+2L\) and leaves \(|0\rangle \) at the zone \(t\), since the permutation of the chain maps the zone \(t+1\) together with \(a+t\) onto the zone \(t\) together with \(a+t+2L\). The chains of different gates act on disjoint stretches, so the lists of all the gates are valid (Lemma 33.5.7), and by Theorem 33.5.5 every round implements the permutation of its chains. Composition (Lemma 33.3.8) gives the claim; the backward rounds run the forward ones in reverse.

The unitaries on the consecutive sites act inside the stretches, so they keep \(|0\rangle \) at the zones \(0\), and their product \(G\) is a local circuit of depth \(K\), applied in one round without hops of depth \(K+2\). By Lemma 33.5.10 every output is a multiple of \(P^{-1}GP|v\rangle \). Conjugation by \(P\) maps the consecutive sites of every gate back to its two registers, so \(P^{-1}GP\) is the product of the gates.

For one channel on a bond, \(\operatorname{Tr}\bigl(\sum _jK_j\rho K_j^\dagger A\bigr) =\operatorname{Tr}\bigl(\rho \sum _jK_j^\dagger AK_j\bigr)\) by cyclicity of the trace, and \(\sum _jK_j^\dagger K_j=\mathbb 1\) makes it trace preserving and completely positive. Both properties pass to compositions, hence to layers and circuits. A gate \(G\) on a bond is the channel with the single operator \(G\).

By induction on the layers it suffices to treat one layer. The dual of a channel on a bond disjoint from \(X\) fixes \(Z\): its operators commute with \(Z\), so \(\sum _jK_j^\dagger ZK_j=\sum _jK_j^\dagger K_jZ=Z\). The dual of a channel on a bond meeting \(X\) maps operators acting on the one-step neighbourhood of \(X\) to such operators, since that set contains the bond. The channels of a layer commute, so the dual of the layer is the dual of the channels meeting \(X\) applied after the dual of the others.

The dual of a channel is not multiplicative, but the dual of one layer is multiplicative on operators \(Z\), \(Z'\) acting on sets \(X\), \(Y\) whose one-step neighbourhoods are disjoint. Indeed, no bond of the layer meets both \(X\) and \(Y\). If a channel acts off a set on which an operator \(B\) acts, then its dual \(\Psi \) satisfies \(\Psi (AB)=\Psi (A)B\) and \(\Psi (BA)=B\Psi (A)\). Writing the dual of the layer as the dual of the channels meeting \(X\) after the dual of the others, and using Lemma 33.6.3 for the latter applied to \(Z'\), one obtains the dual of \(ZZ'\) as the product of the duals. By induction on the layers, \(\Phi ^\dagger (ZZ')=\Phi ^\dagger (Z)\Phi ^\dagger (Z')\), and the two factors act on disjoint sets. For a product density \(\sigma =\bigotimes _i\sigma _i\) of trace one and products \(\bigotimes _im_i\), \(\bigotimes _im'_i\) with disjoint supports, \(\operatorname{Tr}(\sigma \bigotimes _im_im'_i) =\prod _i\operatorname{Tr}(\sigma _im_im'_i)\), and at each site one of \(m_i\), \(m'_i\) is the identity; bilinearity and the duality \(\operatorname{Tr}(\Phi (\sigma )A)=\operatorname{Tr}(\sigma \Phi ^\dagger (A))\) conclude.

The operators \(K_J\) satisfy \(\sum _JK_J^\dagger K_J=\bigotimes _i\sum _jK_{ij}^\dagger K_{ij}=\mathbb 1\), so the Kraus form gives complete positivity and trace preservation. Since \(K_J\) is a tensor product, \(K_J(\bigotimes _i\sigma _i)K_J^\dagger =\bigotimes _iK_{iJ(i)}\sigma _iK_{iJ(i)}^\dagger \), and summing over \(J\) factorizes site by site. The duality is cyclicity of the trace. Finally, the partial trace of \(X\otimes \tau \) is \(\operatorname{Tr}(\tau )X=X\).

The dual maps \(\bigotimes _im_i\) to \(\bigotimes _i\Phi _i^\dagger (m_i)\), and \(\Phi _i^\dagger (\mathbb 1)=\sum _jK_{ij}^\dagger K_{ij}=\mathbb 1\). Hence the identity factors off \(X\) are kept. For products with disjoint supports, one of \(m_i\), \(m'_i\) is the identity at each site, so \(\Phi _i^\dagger (m_im'_i)=\Phi _i^\dagger (m_i)\Phi _i^\dagger (m'_i)\). Linearity concludes.

By induction on the protocol: onsite channels are trace preserving and completely positive by Lemma 33.6.6, channel layers are by construction, and both properties are stable under composition. Appending the layers of a circuit of depth \(T\) one at a time, each onsite channel keeps the depth and each layer raises it by one; the attaching and discarding channels are onsite. The identity onsite channel gives depth \(0\), depth bounds are monotone, and a conversion is realized by a channel, which maps a positive semidefinite matrix of trace one to a positive semidefinite matrix of trace one. A preparation in depth \(T\) by local channels starts from a product density and is itself such a protocol.

The composition \(\Psi _2\circ \Psi _1\) of local channel protocols of depths \(T_1\) and \(T_2\) is a local channel protocol of depth \(T_1+T_2\). Write \(\Psi _2\) as the sequence of its onsite channels and channel layers, and apply them after \(\Psi _1\) one at a time: the first onsite channel of \(\Psi _2\) becomes a further onsite channel in the last group \(\Phi _{T_1}\) of \(\Psi _1\), each onsite channel keeps the depth, and each of the \(T_2\) channel layers raises it by one.

By induction on the protocol. For an onsite channel this is Lemma 33.6.7 with radius \(0\); a channel layer adds one to the radius, by Lemma 33.6.3 for the support and as in the proof of Lemma 33.6.4 for (5), and an onsite channel keeps it.

Write \(\rho =\bigotimes _i\sigma _i\) and \(\sigma =\Psi (\rho )\) for a local channel protocol \(\Psi \) of depth \(T'\le T\), and let \(\Psi ^\dagger \) be its dual from Lemma 33.6.11, of radius \(T'\). If \(Z\) and \(Z'\) act on sets at distance larger than \(2T\ge 2T'\), then \(\Psi ^\dagger (Z)\) and \(\Psi ^\dagger (Z')\) act on disjoint sets, and (5) together with the factorization of the product density \(\rho \) gives

A relabelling of the basis is conjugation by a permutation matrix. On product operators, the factors of \(\beta _k(\bigotimes _im_i)\) outside \(Y\) are products of identities, and linearity concludes. For unblocking, an operator on the original ring acts on a set of sites exactly when it commutes with every operator acting on the complement; \(\beta _k\) maps the operators acting on the sites outside the blocks in \(X\) to operators acting outside \(X\), which commute with \(W\). Finally, the site \(t+kj'\) with \(j'=j+m\) equals \((t+kj)+km\) modulo \(Mk\).

The first statements are those of Lemmas 33.6.9 and 33.6.10 on the blocked ring, composed with the blocking channel of Lemma 33.6.14. For the dual, compose the blocking channel with the protocol on the blocked ring and apply Lemma 33.6.11 there; unblocking the dual and Lemma 33.6.14 give the supports on the original ring. Blocking maps the product \(\bigotimes _i\sigma _i\) to the product over the blocks of \(\sigma _{jk}\otimes \dots \otimes \sigma _{jk+k-1}\), each of trace \(\prod _t\operatorname{Tr}\sigma _{jk+t}=1\), so the correlation statement is Lemma 33.6.12 on the blocked ring.

Enumerate the configurations and apply the corresponding properties of the matrix trace norm. Reindexing is a linear equivalence and preserves zero and addition.

Use the identity channel, enlarge the bounds, and use \(\lVert A\rVert _1=0\) if and only if \(A=0\), respectively.

The composition \(\Psi _2\circ \Psi _1\) has the sum of the two depths. The error \(\Psi _1(\rho )-\sigma \) is Hermitian. Trace-norm contractivity of trace-preserving positive maps and the triangle inequality give

Identity channels give reflexivity; the definition gives symmetry. For transitivity, compose the approximate conversions in each direction. The sum of the errors tends to zero. For \(b_N=1+\log (N+1)\ge 1\), the depth satisfies

Thus the depth remains polylogarithmic.

The inclusion has orthonormal columns. Complete the compression outside its range using the existing support-completion channel; the complementary term vanishes on \(EXE^\dagger \). Matrix multiplication gives the exact left inverse, and tensoring preserves composition. The paired basis inclusion factors entrywise into two local inclusions. The ceiling-logarithm bound is \(B\le d^k\).

Swaps on disjoint bonds commute and fix each other’s endpoints. Their finite product therefore has the stated action. Applying the permutation matrix homomorphism identifies that product with the layer operator.

The selection permutation preserves each spatial site, hence is free. Conjugating the port layer by it changes only the wire placement. Extend each digit’s site permutation by identity outside that digit’s selected wires. Disjoint ranges ensure the finite product has the desired action on each digit; every factor has a one-layer implementation.

A right endpoint of a nontrivial matching bond cannot be another left endpoint. Data and scratch slots are disjoint, and different digit selections have disjoint ranges. The action formulas of Theorem 33.8.4 give the claimed placement.

Wire reindexing is a linear equivalence on matrices. Its conjugation on linear maps is multiplicative, so it preserves the commuting family product. Placing Kraus operators preserves their completeness relation. Each routed map is a zero-depth onsite channel; only the one forward and one backward routing contribute to the depth.

Encode the two endpoints independently, then complete each pair channel outside its joint code. The resulting map is CPTP, so choose its normalized finite Kraus representation. The common data-to-scratch routing has depth \(k\) and puts every pair channel onsite. Apply Theorem 33.8.6 once to the complete matching. Protocol composition gives the final linear-in-\(L\) bound. The off-code joint decoder need not factor onsite; it is only executed after colocation. This theorem is not an assertion about protocols with an unrestricted intermediate dimension depending on \(N\).

Choose normalized local Kraus families. On product operators, all formulas follow site by site; these products span the entire chain matrix algebra. Use the exact local decoding identity before tensoring with a reference.

Use the explicit configuration equivalence and the matrix reindexing algebra equivalence. Check tensoring on matrix units, then use linear extensionality. Applying the split to each placed Kraus operator proves the full channel identity.

The rectangular global encoding matrix splits as the tensor product of its selected and complementary encoding matrices. Check the resulting tensor intertwining on matrix units, then use linear extensionality and the representation-independent placement identity.

Use local CPTP completions, then the placed-channel intertwining theorem. Induction over the commuting gate product proves the whole-layer identity.

Induct on the bounded protocol. Encode each onsite operation site by site, and use the encoded-layer theorem for a pair layer. Compose the exact intertwiners in the actual execution order.

Restrict the site maps to a finite set and compose one new site at a time. Check the selected/complementary factorization on product matrices, which span the complete chain matrix algebra.

Use the explicit finite-product basis equivalence independently at each spatial site. The selected/complementary configuration formulas identify the placed operator entry by entry. Channel conjugation and register placement preserve composition by their linear-equivalence and tensor identities.

Factor an onsite channel into its one-site lifts and place each local Kraus family on the corresponding data digits. For a native layer, extract its two-site Kraus matrices and use the data/scratch colocation identities. Apply the shared-routing theorem once to the full commuting family, with forward and backward depth \(k\).

Reindexing and tensoring with an identity preserve CPTP. The split and its inverse cancel, as do the native encoding and completed decoding. Tensor the native intertwining equation with the identity on the complementary configuration space and conjugate by the same split.

Compile to the fixed alphabet \(d^k\), apply the zero-cost onsite and \(2k\)-cost layer implementations along the explicit word, then transport the native intertwiner through the physical encoding. No physical simulation equation is assumed. This encoded statement does not itself supply the source’s original physical-port input/output initialization convention or a complete QCcc dilation and protocol-block witness.

Cancel the injective all-data placement in the native selected-register identity to obtain placement on whole spatial-site blocks. Decompose the onsite channel into its single-site factors. Each factor has normalized Kraus operators supported within one site, so composition retains depth zero.

Write the port and data words as explicit injective basis maps. Their product isometries agree with the onsite product encoders under sitewise digit coordinates. Complete each local decoder outside its code, and compose it with the other encoder. The onsite intertwining identity gives exact code conversion, while whole-site locality gives the zero-depth certificates.

Split each data codeword into its data configuration and zero complementary configuration. Check the initialization equality on matrix units and use linear extensionality. The tensor-map action on Kronecker products proves commutation with preparation of the fixed reference.

Preprocess locally into the data code, use the bounded encoded compiler, and postprocess locally back into the port code. The explicit initialization identity identifies the compiler’s reference with the product-zero memory state. Both extra channel maps have physical depth zero. This theorem does not assert reset of discarded dilation environments or construct a full source QCcc protocol-block witness. The following unitary construction supplies the explicit local environments and final discard.

Induct on the unitary circuit. An onsite operator remains supported at the same spatial site. An onsite wire permutation extends by the identity outside the old wires. Each counted layer still acts on the designated ports. Placement preserves multiplication of operators.

Apply the register split with the complementary wires enumerated in their original order. Matrix reindexing preserves multiplication and adjoints. The environment factor \(Z_A\) has trace one.

The two wire-sum bijections enumerate the selected wires and exactly their complements. Reindex the register-placement identity by these bijections. The zero configuration separates as \((0^A,0^B)\), and the two finite partial-trace sums combine into the trace over \(A+B\) wires.

In the three-block coordinates, the first operation sends \((X\otimes \sigma )\otimes \tau \) to \([U(X\otimes \sigma )U^\dagger ]\otimes \tau \). The second operation acts identically on the first environment, so tracing that environment commutes with this operation, even when it is correlated with the system. Taking both partial traces gives (9). Both layout embeddings preserve ports and spatial owners; multiplication adds the depth bounds.

The selected/environment configuration is the restriction to the selected original wires together with the complete environment word. Each column block is therefore the corresponding local matrix tensored with the identity on unselected wires. Sum the resulting Kraus maps and use representation-independent register placement.

The system dimension is \(d^m\) and the environment dimension \(d^{2m}=(d^m)^2\). The Choi-rank bound and unitary extension of the pure-input isometry give the retained-system dilation, following [ 244 , Theorems 2.2 and 2.5 ] . Place that unitary on the selected wires and their fresh environment. Its support lies in one spatial site. For a supported Kraus family, extract its matrices on the site register; injectivity of operator placement transfers their normalization to that register.

Induct on the channel protocol. A unitary primitive needs no fresh wires. Dilate an onsite Kraus primitive using fresh wires at its site. At composition, combine the two disjoint environment blocks and apply (9). Increasing a depth upper bound preserves the same witness. Tensoring the resulting map equality with the reference identity preserves composition.

Apply the same-depth unitary dilation to the original-port channel protocol and compose its map equality with the port initializer. The designated-memory reset follows from the original-port identity; the additional environments are discarded without a reset claim. The source’s QCcc block/control and pure-output system–ancilla conditions remain separate, as recorded in [ 88 ] .

Apply the defining operator-norm bound to \(A\).

Both Heisenberg evolutions are \(A\mapsto e^{-itH}Ae^{itH}\).

Matrix exponentiation and multiplication are continuous; the norm of the resulting linear map on \(\mathcal A_X\) is continuous.

Use \(\| AB-BA\| \leq 2\| A\| \| B\| \).

Operators on disjoint tensor factors commute.

Separate the terms disjoint from \(X\). Their sum commutes with every operator in \(\mathcal A_X\). Differentiate in the corresponding interaction picture, apply the fundamental theorem of calculus and invariance of operator norm under unitary conjugation, and then take the restricted operator norm.

The quantity \(\max _if_i(t)/w_i\) satisfies the scalar inequality \(g(t)\leq c+v\int _0^tg\), and Grönwall’s inequality gives \(g(t)\leq ce^{vt}\). For the refinement, insert this bound into the integral once more.

Write \(H=H_C+H'\), with \(H_C\) the sum of the terms inside \(C\). The two parts commute, and \(H'\) commutes with \(\mathcal A_C\), so \(\tau _t(A)=e^{itH_C}Ae^{-itH_C}\). Every factor commutes with \(B\).

Let \(F_k(t)=C_B(X_k,t)\) for \(t\geq 0\). The local commutator recursion gives \(F_k(t)\leq F_k(0)+\sum _ja_{kj}\int _0^tF_j\), with \(a_{kj}=2\| h_j\| \) when \(X_j\) meets \(X_k\) and \(a_{kj}=0\) otherwise. Put \(D(x)=\min \{ n,d_G(x,y)\} \) and \(w_k=e^{-\mu D(a_k)}\). If \(X_j\) meets \(X_k\), then \(d_G(a_k,a_j)\leq 2R\), so \(w_j\leq e^{2\mu R}w_k\); the norms of the terms meeting \(X_k\) sum to at most \(|X_k|b_0\leq v_Rb_0\). Hence \(\sum _ja_{kj}w_j\leq 2v_Rb_0e^{2\mu R}w_k\). The initial value \(F_k(0)\) vanishes unless \(y\in X_k\), and then \(D(a_k)\leq R\) and \(F_k(0)\leq 2\| B\| \leq 2\| B\| e^{\mu R}w_k\). The weighted integral comparison gives \(F_i(t)\leq 2\| B\| e^{\mu R}w_ie^{2v_Rb_0e^{2\mu R}t}\) with \(w_i=e^{-\mu n}\). Replace \(H\) by \(-H\) for negative times and multiply by \(\| A\| \). For the constants take \(\mu =1\); the infinite-distance case is Lemma 33.9.11.

Let \(C\) be the connected component of \(a_i\). A support of finite diameter lies in one component, so it is contained in \(C\) or disjoint from it; also \(X_i\subseteq C\) and \(y\notin C\). Apply Lemma 33.9.9.

The Weyl operators satisfy \(\sum _pW(p)_{ii'}\overline{W(p)_{jj'}}=q\, \delta _{ij}\delta _{i'j'}\). The corresponding sum over the products factorizes over the sites, and the resulting Kronecker deltas reproduce the partial-trace formula.

The values act on \(K\) by the partial-trace formula. The averaging formula is a Kraus decomposition by rescaled unitaries. Operators acting on \(K\) commute with every \(W_p\). A uniform average of unitary conjugations is a contraction.

By the averaging formula, \(B-E_K(B)\) is the average of \((BW_p-W_pB)W_p^\dagger \). Write \(W_p\) as a product of on-site unitaries and use \(\| [B,UV]\| \leq \| [B,U]\| +\| [B,V]\| \) for unitaries \(U,V\).

The bound \(2\| A\| \) follows from contractivity. For the other bound, apply the commutator lemma with \(\varepsilon _y=0\) when \(d_G(a_i,y)=\infty \) and \(\varepsilon _y=2e^R\| A\| e^{v|t|-d_G(a_i,y)}\) otherwise, using graph-distance propagation with \(\mu =1\). Group the sites outside the ball by their distance \(d{\gt}l\), and use \((d+1)^k\leq 2^kk!\, e^{(d+1)/2}\) and a geometric series.

The expectation is complex linear, preserves Hermiticity, and contracts the operator norm. The theorem “Projected evolution approximates the explicit product” in [ 216 ] therefore constructs a single unitary path with the stated derivative, uniqueness, and comparison estimate. The derivative of \(e^{itH'}e^{-itH}\) has generator \(e^{itH'}(H'-H)e^{-itH'}\) multiplying on the left, so both evolutions have the same initial value.

Each \(G_K(s)\) acts on \(K\). Hence every operator \(B\) acting on \(K^c\) commutes with every \(G_K(s)\). The theorem “Commutation with the evolution” in [ 216 ] gives that \(U(t)\) commutes with \(B\), by the conservation identity \(U(t)^*BU(t)=B\) and unitarity. The commutant characterization of the supported-operator algebra shows that \(U(t)\) acts on \(K\). This argument concerns the same path for every real time, including negative times.

The identity is an admissible unitary and its commutator is zero. For each admissible \(U\), the operator \(\widehat U\) is unitary, so

The assertions follow from the upper- and lower-bound properties of the supremum. Reversing a commutator changes only its sign.

The identities \([\widehat U,B+C]=[\widehat U,B]+[\widehat U,C]\) and \([\widehat U,cB]=c[\widehat U,B]\), followed by the norm inequalities and the supremum bound, give (14) and \(d_y(cB)\le |c|d_y(B)\). If \(c\ne 0\), apply the latter inequality to \(c^{-1}\) and \(cB\) to obtain the reverse bound in (15). If \(c=0\), use \(d_y(0)=0\). Take \(c=-1\) for negation and write \(B-C=B+(-C)\) for subtraction. For the finite sum, distribute the commutator and use

Taking the supremum over \(U\) proves the claim.

The commutation hypothesis bounds every norm in the supremum by zero, whereas \(d_y(B)\ge 0\). For a spectator operator, \((U\otimes \mathbb 1)(\mathbb 1\otimes S)=U\otimes S =(\mathbb 1\otimes S)(U\otimes \mathbb 1)\).

The \((a,b)\) block of \(A\otimes S\) is \(S_{ab}A\). Linearity gives \(E_K(S_{ab}A)=S_{ab}E_K(A)\), proving (19). The expectation fixes the identity, which yields (20). Every physical matrix is supported on \(I\), so \(E_I(B_{ab})=B_{ab}\) for every block.

Each block \(E_K(B_{ab})\) is supported on \(K\) by its partial-trace formula. Operators on disjoint sets of physical sites commute, so \(E_K(B_{ab})U=UE_K(B_{ab})\). Matrix multiplication by \(\widehat U\) acts separately on each spectator block, giving the claimed equality.

Each tensor factor \(M_x\) is unitary. Taking adjoints and multiplying factor by factor gives \(P_S(p)^\dagger P_S(p)=\mathbb 1\) and \(P_S(p)P_S(p)^\dagger =\mathbb 1\). The complementary-set identity follows because both products have factor \(\mathbb 1\) on \(K\) and \(W(p_x)\) off \(K\). The singleton product has identity factors off \(\{ y\} \), so it is supported there. For (22), the factor at \(y\) on the right is \(W(p_y)\mathbb 1\). At every other site it is \(\mathbb 1\, M_x\). These are the factors on the left.

Expand \([B,UV]=[B,U]V+U[B,V]\). The triangle inequality and invariance of the norm under left or right multiplication by a unitary give \(\| [B,UV]\| \le \| [B,U]V\| +\| U[B,V]\| =\| [B,U]\| +\| [B,V]\| \).

For every physical \(U\), the \((a,b)\) block of \(\widehat UB\widehat U^\dagger \) is \(UB_{ab}U^\dagger \). Apply the physical Weyl averaging formula to each \(B_{ab}\) in (17).

By Theorem 33.11.2.5, every \(\widehat{W_K(p)}\) is unitary, so each summand in (24) has norm \(\| B\| \). There are \(q^{2|I|}\) labels. The triangle inequality and the normalization \(q^{-2|I|}q^{2|I|}=1\) give the result.

For unitaries \(V,W\) on \(\mathcal H\otimes \mathcal K\), \([B,VW]=[B,V]W+V[B,W]\) and hence \(\| [B,VW]\| \le \| [B,V]\| +\| [B,W]\| \) by Theorem 33.11.2.6. Starting from \(P_{\varnothing }(p)=\mathbb 1\), use the insertion identity (22) and the unitary, single-site support properties of Theorem 33.11.2.5. Induction over the sites outside \(K\), with the identity on the spectator throughout, bounds the commutator with \(\widehat{W_K(p)}\) by \(\sum _{y\notin K}\varepsilon _y\). With \(V=\widehat{W_K(p)}\), unitarity gives

Average (27) over all Weyl labels using (24) and \(q^{-2|I|}\sum _p B=B\) to obtain (25).