The coefficient is a sum over virtual paths of products over the sites, and exactly one factor of each product is multiplied by \(c\). For \(c\, \psi \) scale the first site. For the zero vector take all bond dimensions equal to one and all site matrices zero: every product has a zero factor, since \(N\ge 1\).

The rows \(\alpha \ge a\) of \(MN\) and of \(Mv\) are sums of multiples of vanishing entries. The chain statement follows by induction on \(n\), applying the vector statement to the first factor.

Direct computation of coordinates.

Associativity of the ordered product.

Stack the matrices \(Y^i\) into one matrix with rows indexed by \((\alpha ,i)\), choose an orthonormal basis \(q_0,\dots ,q_{b-1}\) of its column space, and let \(Q^i\) have columns \(q_\beta \) for \(\beta {\lt}b\) and zero columns otherwise. The coefficients of the columns of the stacked matrix in this basis form \(R\). The column space is spanned by the at most \(c\) nonzero columns, so \(b\le c\).

By induction on \(n\). For \(n=0\) take \(R=R_{-1}\). Otherwise apply Theorem 34.2.7 to \(Y^i=R_{-1}P_0^i\), which gives \(Y^i=Q_0^iR_0\) with \(R_0\) row-supported below \(b_1\), and apply the induction hypothesis to \(R_0\) and \(P_1,\dots ,P_{n-1}\):

For one site, expand

by the isometry condition. For the chain, write \(Q^{\sigma }=Q_0^{\sigma _0}Q'^{\sigma '}\), where \(Q'\) is the chain \(Q_1,\dots ,Q_{n-1}\) and \(\sigma '=(\sigma _1,\dots ,\sigma _{n-1})\). The vectors \(Q'^{\sigma '}v\) and \(Q'^{\sigma '}w\) are supported below \(b_1\) by Theorem 34.2.3, so the one-site identity for \(Q_0\) and the induction hypothesis for \(Q'\) give

Theorem 34.2.8 gives the bonds \(b_p\), the families \(Q_p\) and a matrix \(R\) row-supported below \(b_n\) with \(R_{-1}P^\sigma =Q^\sigma R\) for every \(\sigma \). Setting \(r'=Rr\), which is supported below \(b_n\) by Theorem 34.2.3, yields \(R_{-1}P^\sigma r=Q^\sigma Rr=Q^\sigma r'\).

Take \(w=v\) in the inner-product identities of Theorem 34.2.8: \(\sum _i\langle Q^iv,Q^iv\rangle =\langle v,v\rangle \) for one site, and (3) with \(w=v\) for the chain.

The first claim holds entrywise. The second follows by induction on the chain from the right, since each partial product applied to \(v\) is supported below the next bond level.

The vectors \(\sum _{\alpha ,i}Q^i_{\alpha \beta }|\alpha ,i\rangle \), \(\beta {\lt}b\), are orthonormal, so they are the columns of an isometry \(W\) from \(\mathbb {C}^b\) into \(\mathbb {C}^D\otimes \mathbb {C}^d\). The map \(\beta \mapsto (\beta ,0)\) places the basis of \(\mathbb {C}^b\) injectively among the basis vectors \(|\alpha ,i\rangle \). An isometry extends to a unitary agreeing with it on any such placement: put its orthonormal columns at the placed positions and extend them to an orthonormal basis of the larger space. Applied to \(W\) and this placement, this gives \(U\) with \(U|\beta ,0\rangle =W|\beta \rangle \) for \(\beta {\lt}b\).

\(1=D_0\le D\).

For \(N=0\) both sides are one. Otherwise \(c_A(\sigma )\) is the trace of \(\widetilde A^\sigma \), and all diagonal entries except the first vanish because the first padded site matrix is row-supported below \(D_0=1\).

Entrywise comparison; for the second claim the sum over rows \(\alpha \) may be restricted to \(\alpha {\lt}b_k\).

Replace the last family by \(Q_n^i\, r'\langle 0|\), set the last bond dimension to one, and cut down. By Theorems 34.2.14 and 34.2.6, the coefficient at \(\sigma \) is the first coordinate of \(Q^\sigma r'\). If \(r'\) is a unit vector supported below \(b_{n+1}\), the isometry of \(Q_n\) on its first \(b_{n+1}\) columns gives \(\sum _i\| Q_n^ir'\| ^2=\| r'\| ^2=1\).

Apply Theorem 34.2.9 with \(a=1\), \(R_{-1}=c|0\rangle \! \langle 0|\), the square padding of \(A\), and \(r=|0\rangle \). The padded site matrix \(\widetilde A_p\) vanishes on the columns \(\gamma \ge D_{p+1}\), so \(b_{p+1}\le D_{p+1}\). The vector \(Q^\sigma r'\) is supported below \(b_0=1\), so it is its first coordinate times \(|0\rangle \), and that coordinate is \(c\, c_A(\sigma )\) by Theorem 34.2.14. The norm identity is Theorem 34.2.10.

Apply Theorem 34.2.18 with \(c=1\) and assemble the result by Theorem 34.2.17. The last bond has dimension one on both sides, and the others are bounded by Theorem 34.2.18.

In the construction of Theorem 34.2.19, the final vector \(r'\) has norm one by Theorem 34.2.18, so Theorem 34.2.17 makes the last site isometric as well.

The \((ad)\times b\) matrix \(S\) obtained by stacking the \(A^i\) satisfies \(S^\dagger S=\mathbb {1}_b\), so \(b=\operatorname {rank}(S^\dagger S) =\operatorname {rank}S\le ad\).

Induction on \(k\): \(D_0=1\), \(D_{p+1}\le d\, D_p\) for \(p{\lt}n\) by Theorem 34.3.1, and \(D_{n+1}=1\le d^{n+1}\).

Theorem 34.3.2 applies to the chain of Theorem 34.2.19.

Relabel the virtual paths \(k\mapsto N-k\) and the factors of the product \(p\mapsto N-1-p\).

Apply Theorem 34.3.3 to the reverse of \(A\) and reverse the result: by Theorem 34.3.5 this represents \(c_A\) with dimensions at most \(\min (D_k,d^{N-k})\). Apply Theorem 34.3.3 once more. The bound \(d^{N-k}\) is not stated in the source, which bounds only the side at which the decompositions start.

Split the ordered product after its first \(k\) factors; the second claim holds site by site.

The rank is at most the number of rows, \(d^k\), and of columns, \(d^{N-k}\). If \(k\le \lfloor N/2\rfloor \) use \(d^k\), and otherwise \(N-k\le \lfloor N/2\rfloor \). If \(\psi (c)\ne 0\), the entry of the cut matrix at the restrictions of \(c\) is nonzero by Theorem 34.4.2, so the rank is positive. The cut matrices at \(0\) and \(N\) have one row and one column, respectively.

By Theorem 34.2.14 and Theorem 34.4.2, \(c_A(\sigma \tau )=\sum _{\gamma }(L^\sigma )_{0\gamma }(R^\tau )_{\gamma 0}\), where \(L^\sigma \) and \(R^\tau \) are the products of the square paddings of the sites before and after the cut. The first factor of \(R^\tau \) vanishes on the rows \(\gamma \ge D_k\), and for \(k=N\) the empty product \(R^\tau =\mathbb {1}\) vanishes off the diagonal while \(D_N=1\). So the cut matrix is the product of a matrix with \(D_k\) columns and a matrix with \(D_k\) rows.

This is the construction by successive Schmidt decompositions [ 228 , Section 3.1 ] . Let \(W_k\) be the column space of the cut matrix at \(k\), a subspace of \((\mathbb {C}^d)^{\otimes k}\) of dimension \(\operatorname {rank}_k\psi \), and let \(e^{(k)}_\beta \) be an orthonormal basis of \(W_k\). A column of the cut matrix at \(k+1\), with the last of its \(k+1\) sites fixed to \(i\), is the column of the cut matrix at \(k\) at the configuration \(i\tau \); hence \(w\in W_{k+1}\) implies \(w(\, \cdot \, i)\in W_k\). Put \((A_k^i)_{\beta \beta '}=\langle e^{(k)}_\beta ,e^{(k+1)}_{\beta '}(\, \cdot \, i)\rangle \), so that

Parseval’s identity in \(W_k\) and the orthonormality of \(e^{(k+1)}\) give \(\sum _i(A_k^i)^\dagger A_k^i=\mathbb {1}\). By induction on \(k\), the first row of the product of the padded sites before the cut \(k\) is \(\overline{u}\, e^{(k)}_\beta (\sigma )\), where \(u\) is the value of the unit vector \(e^{(0)}_0\) of the one-dimensional space \(W_0\), so \(|u|=1\). Since \(W_N\) is spanned by \(\psi \), \(\psi =c_0\, e^{(N)}_0\) with \(c_0=\langle e^{(N)}_0,\psi \rangle \); scaling the last site by \(u\, c_0\) gives \(\psi \) by Theorem 34.1.7. If \(\psi \) is normalized, \(|u\, c_0|=\| \psi \| =1\), and the last site remains isometric.

Since \(\psi \ne 0\), \(D{\gt}0\). For \(N=0\) take \(c=\psi ()^{-1}\) and the empty chain. For \(N\ge 1\) apply Theorem 34.2.9 with \(R_{-1}=|0\rangle \langle \varphi _F|\), the matrices \(A_k\), and \(r=|\varphi _I\rangle \), assemble the result by Theorem 34.2.17, and take \(c=1\).

Take the square padding \(\widetilde A\) of the representation, \(|\varphi _F\rangle =|0\rangle \) and \(|\varphi _I\rangle =c^{-1}|0\rangle \); then \(\langle 0|\widetilde A^\sigma c^{-1}|0\rangle =c^{-1}c\, \psi (\sigma )\) by Theorem 34.2.14.

The zero vector has a representation by Theorem 34.1.7. If \(\psi \ne 0\), Theorem 34.5.1 gives a representation of \(c\, \psi \) for some \(c\ne 0\), and Theorem 34.1.7 one of \(\psi =c^{-1}(c\, \psi )\). The converse is Theorem 34.5.2 with \(c=1\).

This is the \((|\beta ,0\rangle ,|\beta ',0\rangle )\) entry of \(U^\dagger U=\mathbb {1}\).

By Theorems 34.5.5 and 34.2.10, \(\sum _\sigma \| A^\sigma \varphi _I\| ^2=\| \varphi _I\| ^2=1\), and \(\| A^\sigma \varphi _I\| ^2=|\psi (\sigma )|^2\| \varphi _F\| ^2=|\psi (\sigma )|^2\).

Use the induced matrices and project onto \(|\varphi _F\rangle \): \(\langle \varphi _F|A^\sigma |\varphi _I\rangle =\psi (\sigma )\langle \varphi _F | \varphi _F \rangle =\psi (\sigma )\).

For \(N=0\) take \(|\varphi _I\rangle =\psi ()|0\rangle \) and \(|\varphi _F\rangle =|0\rangle \). Otherwise apply Theorem 34.2.18 with the scalar \(c^{-1}\): this gives isometric families \(Q_p\) and a vector \(r'\) with \(Q^\sigma r'=\psi (\sigma )|0\rangle \) and \(\| r'\| ^2=\sum _\sigma |\psi (\sigma )|^2=1\). Extend each \(Q_p\) to a unitary \(U_p\) by Theorem 34.2.12, and take \(|\varphi _I\rangle =r'\) and \(|\varphi _F\rangle =|0\rangle \). The induced matrices agree with \(Q_p\) on the used columns, so by Theorem 34.2.11 the ancilla component at \(\sigma \) is \(Q^\sigma r'=\psi (\sigma )|0\rangle \). The ancilla decouples because the first bond is one-dimensional.

For the forward direction, \(\psi \) is normalized by Theorem 34.5.6, hence nonzero, and probabilistically generated by Theorem 34.5.7; Theorem 34.5.1 gives a representation of \(c\, \psi \) for some \(c\ne 0\), and Theorem 34.1.7 one of \(\psi \). The converse is Theorem 34.5.8 with \(c=1\).

One direction is Theorem 34.5.7. Conversely, \(\psi \) is normalized, hence nonzero, so Theorem 34.5.1 gives a representation of \(c\, \psi \) for some \(c\ne 0\), and Theorem 34.5.8 applies.

The two relations are the cases \(t=1\) and \(t=0\).

For \(z=(z_1,z_2)\), the relations (4) applied to \(|\varphi \rangle =|z_1\rangle \) and \(t=z_2\) give \(T|z_1,z_2,0\rangle =|z_1,0,z_2\rangle \), so

Since \((W\otimes \mathbb {1})_{(z,j),(y,0)}=\delta _{j,0}\, W_{z,y}\),

A step of the transition scheme factors as \(E R_i\), where \(E|\varphi \rangle =|\varphi \rangle |0\rangle \) and \((R_i)_{\alpha ,y}=W_{(\alpha ,i),y}\), and \(R_iE\) is the operation \(\langle \alpha ,i|W|\beta ,0\rangle \) of the unitary \(W\) on ancilla \(\otimes \) site. Given a deterministic scheme with unitaries \(U^{[k]}\), take \(W^{[k]}=U^{[k]}\) and the initial and final ancilla states \(E|\varphi _I\rangle \) and \(E|\varphi _F\rangle \); the ancilla components are then \(E\) applied to those of the deterministic scheme.

Conversely, after the first step the tag is \(|0\rangle \), so the ancilla component at \(\sigma \) is \(E\) applied to the product of the matrices \(R_iE\) acting on \(v_i=R_i|\varphi _I\rangle \), where \(R_i\) comes from the first ancilla unitary. Since \(\sum _i\| v_i\| ^2=\| \varphi _I\| ^2=1\), the vectors \(v_i\) are the first column of a unitary on \(\mathbb {C}^D\otimes \mathbb {C}^d\) by Theorem 34.2.12, and the scheme becomes a deterministic scheme with ancilla \(\mathbb {C}^D\) started in \(|0\rangle \). The final state is \(\psi (\sigma )\) times the tag-zero part of \(\varphi _F\). The total squared norm is \(1\) by Theorem 34.2.10, so some \(\psi (\sigma )\) is nonzero, the parts of \(\varphi _F\) with a nonzero tag vanish, and the tag-zero part is normalized.

Theorems 34.6.4 and 34.5.9.

The forward direction is Theorem 34.4.4. For the backward direction, the zero vector is covered by Theorem 34.1.7 and every other vector by Theorem 34.4.5.

For \(D\ge 1\) combine Theorems 34.5.3 and 34.7.1. For \(D=0\) both sides say \(\psi =0\): the generated vector is a pairing in \(\mathbb {C}^0\), and a nonzero vector has \(\operatorname {rank}_0\psi =1\) by Theorem 34.4.3. The deterministic case follows by Theorems 34.5.10, 34.5.6 and 34.5.7.

By Theorem 34.7.2 the dimensions that work are exactly those at least every cut rank.

Every cut rank is at most \(d^{\lfloor N/2\rfloor }\) by Theorem 34.4.3; apply Theorems 34.7.1, 34.7.2 and 34.6.4.

Induction on \(k\). For \(k=1\), \(U^{[1]}\) acts on sites \(1\) and \(2\) of \(|0\rangle ^{\otimes N}\) and gives \(U^{[1]}|0,0\rangle \otimes |0\rangle ^{\otimes (N-2)} =|\chi _1\rangle \otimes |0\rangle ^{\otimes (N-2)}\). For \(k\ge 2\), before \(U^{[k]}\) acts, the chain is \(\sum _\alpha \chi _{k-1}(\dots ,\alpha )|\dots ,\alpha \rangle \otimes |0\rangle \otimes |0\rangle ^{\otimes (N-k-1)}\), with \(\alpha \) the value of site \(k\) and site \(k+1\) in \(|0\rangle \). The operation \(U^{[k]}\) acts on sites \(k\) and \(k+1\) only, and

Hence the chain after \(U^{[k]}\) is \(\sum _{i,\beta }\bigl(\sum _\alpha \langle i,\beta |U^{[k]}|\alpha ,0\rangle \chi _{k-1}(\dots ,\alpha )\bigr)|\dots ,i,\beta \rangle \otimes |0\rangle ^{\otimes (N-k-1)}\), and the coefficient is \(\chi _k(\dots ,i,\beta )\) by the recursion of Definition 34.8.1.

Interchanging the outputs twice is the identity and permutes the rows of a unitary. The identity of states follows by induction on \(N\) from the recursion for \(\chi _k\), since \(\langle \beta ,i|\widehat U|\alpha ,0\rangle =\langle i,\beta |U|\alpha ,0\rangle \).

Such a vector is \(\bigl(|0\rangle \langle e_{\sigma _0}|\bigr)A^{\sigma '} |\varphi _I\rangle \) read at the first coordinate, an open-boundary state by Theorems 34.2.9 and 34.2.17; for unitary operations it is normalized by Theorems 34.5.5 and 34.2.10. Conversely, write an open-boundary state as \(\psi (\sigma )=\bigl(R\, P_1^{\sigma _1}\cdots P_{N-1}^{\sigma _{N-1}} |0\rangle \bigr)_{\sigma _0}\) with \(R_{j\gamma }\) the entries of the first site (Theorem 34.2.14), and run the successive decompositions of Theorem 34.2.9 starting from \(R\): this gives \(\psi (\sigma )=\bigl(Q_1^{\sigma _1}\cdots Q_{N-1}^{\sigma _{N-1}} r'\bigr)_{\sigma _0}\) with every \(Q_p\) isometric on its bond block, and \(\| r'\| =1\) when \(\psi \) is normalized. Take \(|\varphi _I\rangle =r'\) and operations inducing \(Q_p\), which in the unitary case are unitary extensions by Theorem 34.2.12; then Theorem 34.2.11 identifies the state.

\(\langle \alpha ,i|U(W\otimes \mathbb {1})|\beta ,0\rangle =\sum _\gamma \langle \alpha ,i|U|\gamma ,0\rangle W_{\gamma \beta }\), and the first operation acts last in the ordered product.

As in the source, the site \(k+1\) serves as the ancilla of the \(k\)-th step. By Theorem 34.8.3, a generated state is a vector of Theorem 34.8.4 with \(|\varphi _I\rangle =|0\rangle \), hence an open-boundary state of bond dimension at most \(d\), normalized in the deterministic case. Conversely, Theorem 34.8.4 writes an open-boundary state as such a vector for some \(|\varphi _I\rangle \). Choose \(W\) with \(W|0\rangle =|\varphi _I\rangle \), the matrix with first column \(|\varphi _I\rangle \) in the probabilistic case and a unitary in the deterministic case, absorb it into the first operation by Theorem 34.8.5, and interchange the outputs of every operation by Theorem 34.8.3.

Induction on \(n\). For \(n=r\) the vectors \(\sum _\sigma (Q^\sigma )_{0x}|\sigma \rangle \), \(x{\lt}b_r\), are orthonormal by the sweep identity (3) and the support of \(Q^\sigma \) in the row \(0\), so a unitary on the \(r\) sites sends \(|e(x)\rangle \) to them. For the step from \(n\) to \(n+1\), the vectors \(\sum _{\alpha ,i}(Q_n^i)_{\alpha x}|e(\alpha ),i\rangle \), \(x{\lt}b_{n+1}\), are orthonormal, so a unitary on the last \(r+1\) sites sends \(|0,e(x)\rangle \) to them. Applying it first and the unitary of the shorter chain on the first \(n\) sites afterwards gives (6) by the product rule \(Q^\sigma =Q^{\sigma _0\cdots \sigma _{n-1}}Q_n^{\sigma _n}\) and the row support of \(Q_n\). A unitary \(Z\) on the last \(r\) sites acts inside the window of the new unitary, so their product is one gate; if \(n=r\), the whole product acts on the \(r+1\) sites of the chain and is one gate. The count of two-site gates follows from Lemma 33.2.3.

If \(N\le k\), one unitary on all the sites with first column \(\psi \) suffices. Otherwise Theorems 34.2.14 and 34.2.9 write \(\psi (\sigma )=(Q^\sigma r')_0\) for an isometric chain with \(b_0=1\) and a vector \(r'\) supported below \(b_N\). The row support gives \(\sum _\sigma |\psi (\sigma )|^2=\sum _\sigma \| Q^\sigma r'\| ^2=\| r'\| ^2\) by Theorem 34.2.10, so \(r'\) is a unit vector. Since \(D\le d^k\), the bond levels are encoded injectively in the configurations of \(k\) sites by some \(e\). A unitary on the last \(k\) sites sends \(|0\cdots 0\rangle \) to \(\sum _x r'_x|e(x)\rangle \), and the staircase of Lemma 34.9.1 with \(r=k\), applied afterwards, gives \(\sum _x r'_x(Q^\sigma )_{0x}=\psi (\sigma )\) by (6), and with \(Z\) this unitary the lemma gives at most \(\max (1,N-k)\) gates. For \(k=1\), gates on windows of two sites are gates on neighbouring sites by Lemma 33.2.3.