QuantumCore

Lesson 46 · 110 min · advanced

Matrix Product States & Sequential Circuits

Loading progress…

Derives the matrix product state (MPS) form ψs1…sn=A[1]s1⋯A[n]sn\psi_{s_1\ldots s_n}=A^{[1]s_1}\cdots A^{[n]s_n} by successive SVDs, proves that the bond dimension χk\chi_k is the Schmidt rank across cut kk and that S≤log⁡2χkS\le\log_2\chi_k, and proves that LL staircase layers of nearest-neighbour gates give χ≤2L\chi\le2^L. The W state is the worked example; MPS and tree classifiers close the lesson.

Prerequisites: Strongly Entangling Layers, Von Neumann & Entanglement Entropy

Objectives and key results

  • Reshape an nn-qubit amplitude vector across a cut kk and read off the Schmidt decomposition from the singular value decomposition of the matrix M(k)∈C2k×2n−kM^{(k)}\in\mathbb C^{2^k\times2^{n-k}}.

  • Construct the MPS of any state by successive SVDs, writing every reshape explicitly, and prove the left-canonical condition ∑sAs†As=I\sum_sA^{s\dagger}A^s=I.

  • Prove that the bond dimension χk\chi_k equals the Schmidt rank across cut kk and that S(ρ1..k)≤log⁡2χkS(\rho_{1..k})\le\log_2\chi_k.

  • Define the operator-Schmidt rank of a two-qubit gate and prove that a sequential circuit of nearest-neighbour gates prepares states with χk≤2\chi_k\le2, and χk≤min⁡(2L,2min⁡(k,n−k))\chi_k\le\min(2^L,2^{\min(k,n-k)}) after LL staircase layers or LL layers of single-CNOT blocks.

  • Compute the Schmidt spectra, the explicit MPS tensors and the entanglement entropy h(13)=log⁡23−23h(\tfrac13)=\log_23-\tfrac23 of ∣W3⟩\lvert W_3\rangle, and prepare it with a sequential circuit.

  • Explain the structure of MPS and tree classifiers, their qubit-efficient execution and the known results on their trainability.

definition · Matrix product state
∣ψ⟩=∑s1,…,sn∈{0,1}A[1]s1A[2]s2⋯A[n]sn ∣s1s2⋯sn⟩,A[k]sk∈Cχk−1×χk,χ0=χn=1\lvert\psi\rangle=\sum_{s_1,\ldots,s_n\in\{0,1\}}A^{[1]s_1}A^{[2]s_2}\cdots A^{[n]s_n}\,\lvert s_1s_2\cdots s_n\rangle,\qquad A^{[k]s_k}\in\mathbb C^{\chi_{k-1}\times\chi_k},\quad\chi_0=\chi_n=1
algorithm · Successive SVD step
Ψ(αk−1sk),(sk+1⋯sn)(k)=Cαk−1,(sksk+1⋯sn)(k−1),Ψ(k)=U(k)Σ(k)V(k)†,Aαk−1αk[k]sk=U(αk−1sk),αk(k),C(k)=Σ(k)V(k)†\Psi^{(k)}_{(\alpha_{k-1}s_k),(s_{k+1}\cdots s_n)}=C^{(k-1)}_{\alpha_{k-1},(s_ks_{k+1}\cdots s_n)},\qquad\Psi^{(k)}=U^{(k)}\Sigma^{(k)}V^{(k)\dagger},\qquad A^{[k]s_k}_{\alpha_{k-1}\alpha_k}=U^{(k)}_{(\alpha_{k-1}s_k),\alpha_k},\qquad C^{(k)}=\Sigma^{(k)}V^{(k)\dagger}
theorem · Bond dimension and entanglement
χk=rank⁡M(k)=Schmidt rank across cut k,∑sA[k]s†A[k]s=Iχk,S(ρ1..k)=−∑α=1χkλα2log⁡2λα2≤log⁡2χk\chi_k=\operatorname{rank}M^{(k)}=\text{Schmidt rank across cut }k,\qquad\sum_{s}A^{[k]s\dagger}A^{[k]s}=I_{\chi_k},\qquad S(\rho_{1..k})=-\sum_{\alpha=1}^{\chi_k}\lambda_\alpha^2\log_2\lambda_\alpha^2\le\log_2\chi_k
theorem · Staircase bound
χk(Gn−1(L)⋯G1(L)⋯Gn−1(1)⋯G1(1)∣0n⟩)≤2min⁡(L, k, n−k),χk≤min⁡(∏i=1mkr(G(i)), 2min⁡(k,n−k)) in any order\chi_k\big(G^{(L)}_{n-1}\cdots G^{(L)}_1\cdots G^{(1)}_{n-1}\cdots G^{(1)}_1\lvert0^n\rangle\big)\le2^{\min(L,\,k,\,n-k)},\qquad\chi_k\le\min\Big(\prod_{i=1}^{m_k}r\big(G^{(i)}\big),\ 2^{\min(k,n-k)}\Big)\ \text{in any order}
identity · Entanglement of the W state
∣W3⟩=23 ∣0⟩∣01⟩+∣10⟩2+13 ∣1⟩∣00⟩,S(ρ0)=h(13)=log⁡23−23≈0.9182958,χ1=χ2=2\lvert W_3\rangle=\sqrt{\tfrac23}\,\lvert0\rangle\tfrac{\lvert01\rangle+\lvert10\rangle}{\sqrt2}+\sqrt{\tfrac13}\,\lvert1\rangle\lvert00\rangle,\qquad S(\rho_0)=h\big(\tfrac13\big)=\log_23-\tfrac23\approx0.9182958,\qquad\chi_1=\chi_2=2

Cuts, Schmidt rank and entanglement entropy#

A general nn-qubit state has 2n2^n complex amplitudes. Ground states of local Hamiltonians and outputs of shallow circuits on a line carry little entanglement across every cut of the chain and admit a compressed description as a product of small matrices, a matrix product state. Vidal (2003) showed that circuits whose states keep a bounded Schmidt rank are efficiently simulable classically in this form; the density-matrix renormalisation group is a variational method over the same family (Schollwöck 2011). For quantum machine learning the MPS form measures how much entanglement an ansatz can produce and suggests architectures with useful resource and trainability properties. Everything rests on one operation: cutting the chain into a left and a right block and viewing the state as a matrix.

Definition

Matricisation across a cut

For a state ∣ψ⟩\lvert\psi\rangle of nn qubits and a cut kk, the matrix M(k)∈C2k×2n−kM^{(k)}\in\mathbb C^{2^k\times2^{n-k}} is Mr,c(k)=ψs1…sn,r=∑j=1ksj2k−j,c=∑j=k+1nsj2n−j.M^{(k)}_{r,c}=\psi_{s_1\ldots s_n},\qquad r=\sum_{j=1}^ks_j2^{k-j},\qquad c=\sum_{j=k+1}^ns_j2^{n-j}. Since x=r 2n−k+cx=r\,2^{n-k}+c, M(k)M^{(k)} is the amplitude vector read row-major into 2k2^k rows of length 2n−k2^{n-k}: row rr collects the amplitudes whose first kk bits spell rr. In array terms M(k)M^{(k)} is ψ\psi reshaped to the shape (2k,2n−k)(2^k,2^{n-k}). The Schmidt rank across cut kk is χk:=rank⁡M(k)\chi_k:=\operatorname{rank}M^{(k)}.

Lemma

The Schmidt decomposition is the SVD of the reshaped state

Let M(k)=∑α=1χkλαuαvα†M^{(k)}=\sum_{\alpha=1}^{\chi_k}\lambda_\alpha u_\alpha v_\alpha^\dagger be a singular value decomposition with λ1≥⋯≥λχk>0\lambda_1\ge\cdots\ge\lambda_{\chi_k}>0 and orthonormal vectors uα∈C2ku_\alpha\in\mathbb C^{2^k}, vα∈C2n−kv_\alpha\in\mathbb C^{2^{n-k}}. Put ∣aα⟩=∑r(uα)r∣r⟩\lvert a_\alpha\rangle=\sum_r(u_\alpha)_r\lvert r\rangle and ∣bα⟩=∑c(vα)c‾∣c⟩\lvert b_\alpha\rangle=\sum_c\overline{(v_\alpha)_c}\lvert c\rangle. Then ∣ψ⟩=∑α=1χkλα∣aα⟩⊗∣bα⟩,∑αλα2=1,ρ1..k=Trk+1..n∣ψ⟩⟨ψ∣=∑α=1χkλα2∣aα⟩⟨aα∣,\lvert\psi\rangle=\sum_{\alpha=1}^{\chi_k}\lambda_\alpha\lvert a_\alpha\rangle\otimes\lvert b_\alpha\rangle,\qquad\sum_\alpha\lambda_\alpha^2=1,\qquad\rho_{1..k}=\mathrm{Tr}_{k+1..n}\lvert\psi\rangle\langle\psi\rvert=\sum_{\alpha=1}^{\chi_k}\lambda_\alpha^2\lvert a_\alpha\rangle\langle a_\alpha\rvert , with {∣aα⟩}\{\lvert a_\alpha\rangle\} and {∣bα⟩}\{\lvert b_\alpha\rangle\} orthonormal. The Schmidt coefficients λα\lambda_\alpha are the singular values of M(k)M^{(k)}, and the number of nonzero eigenvalues of ρ1..k\rho_{1..k} is χk\chi_k.

Proof (7 steps)
  1. Step 1:
    ∣ψ⟩=∑xψx∣x⟩=∑r=02k−1∑c=02n−k−1Mr,c(k) ∣r⟩⊗∣c⟩\lvert\psi\rangle=\sum_{x}\psi_x\lvert x\rangle=\sum_{r=0}^{2^k-1}\sum_{c=0}^{2^{n-k}-1}M^{(k)}_{r,c}\,\lvert r\rangle\otimes\lvert c\rangle
    Because sites 1,…,k1,\ldots,k are the most significant bits, ∣x⟩=∣r⟩⊗∣c⟩\lvert x\rangle=\lvert r\rangle\otimes\lvert c\rangle for x=r2n−k+cx=r2^{n-k}+c; this is the definition of M(k)M^{(k)}.
  2. Step 2:
    Mr,c(k)=∑α=1χkλα (uα)r (vα)c‾M^{(k)}_{r,c}=\sum_{\alpha=1}^{\chi_k}\lambda_\alpha\,(u_\alpha)_r\,\overline{(v_\alpha)_c}
    Entry (r,c)(r,c) of the rank-one matrix uαvα†u_\alpha v_\alpha^\dagger is (uα)r(vα)c‾(u_\alpha)_r\overline{(v_\alpha)_c}.
  3. Step 3:
    ∣ψ⟩=∑αλα(∑r(uα)r∣r⟩)⊗(∑c(vα)c‾∣c⟩)=∑αλα∣aα⟩⊗∣bα⟩\lvert\psi\rangle=\sum_\alpha\lambda_\alpha\Big(\sum_r(u_\alpha)_r\lvert r\rangle\Big)\otimes\Big(\sum_c\overline{(v_\alpha)_c}\lvert c\rangle\Big)=\sum_\alpha\lambda_\alpha\lvert a_\alpha\rangle\otimes\lvert b_\alpha\rangle
    Substitute and factor the double sum, which is possible because the summand is a product of an rr-term and a cc-term.
  4. Step 4:
    ⟨aα∣aβ⟩=uα†uβ=δαβ,⟨bα∣bβ⟩=∑c(vα)c(vβ)c‾=vβ†vα‾=δαβ\langle a_\alpha\vert a_\beta\rangle=u_\alpha^\dagger u_\beta=\delta_{\alpha\beta},\qquad\langle b_\alpha\vert b_\beta\rangle=\sum_c(v_\alpha)_c\overline{(v_\beta)_c}=\overline{v_\beta^\dagger v_\alpha}=\delta_{\alpha\beta}
    The singular vectors are orthonormal, and complex conjugation preserves orthonormality.
  5. Step 5:
    ∑αλα2=∥M(k)∥F2=∑x∣ψx∣2=1\sum_\alpha\lambda_\alpha^2=\big\lVert M^{(k)}\big\rVert_F^2=\sum_x\lvert\psi_x\rvert^2=1
    The Frobenius norm is the sum of squared singular values, and M(k)M^{(k)} contains every amplitude once.
  6. Step 6:
    ρ1..k=∑r,r′(∑cMr,c(k)Mr′,c(k)‾)∣r⟩⟨r′∣=∑r,r′(M(k)M(k)†)r,r′∣r⟩⟨r′∣\rho_{1..k}=\sum_{r,r'}\Big(\sum_cM^{(k)}_{r,c}\overline{M^{(k)}_{r',c}}\Big)\lvert r\rangle\langle r'\rvert=\sum_{r,r'}\big(M^{(k)}M^{(k)\dagger}\big)_{r,r'}\lvert r\rangle\langle r'\rvert
    Partial trace over the right block: TrB∣r⟩⟨r′∣⊗∣c⟩⟨c′∣=δcc′∣r⟩⟨r′∣\mathrm{Tr}_B\lvert r\rangle\langle r'\rvert\otimes\lvert c\rangle\langle c'\rvert=\delta_{cc'}\lvert r\rangle\langle r'\rvert.
  7. Step 7:
    M(k)M(k)†=∑α,βλαλβuα(vα†vβ)uβ†=∑αλα2uαuα† ⇒ ρ1..k=∑αλα2∣aα⟩⟨aα∣M^{(k)}M^{(k)\dagger}=\sum_{\alpha,\beta}\lambda_\alpha\lambda_\beta u_\alpha(v_\alpha^\dagger v_\beta)u_\beta^\dagger=\sum_\alpha\lambda_\alpha^2u_\alpha u_\alpha^\dagger\ \Rightarrow\ \rho_{1..k}=\sum_\alpha\lambda_\alpha^2\lvert a_\alpha\rangle\langle a_\alpha\rvert
    Orthonormality of the vαv_\alpha. This is a spectral decomposition, so the nonzero eigenvalues of ρ1..k\rho_{1..k} are the χk\chi_k numbers λα2\lambda_\alpha^2; the same argument with M(k)†M(k)M^{(k)\dagger}M^{(k)} gives the right block.

∎

Theorem

Entanglement entropy is bounded by the logarithm of the Schmidt rank

For every cut kk, S(ρ1..k)=−∑α=1χkλα2log⁡2λα2 ≤ log⁡2χk ≤ min⁡(k, n−k),S(\rho_{1..k})=-\sum_{\alpha=1}^{\chi_k}\lambda_\alpha^2\log_2\lambda_\alpha^2\ \le\ \log_2\chi_k\ \le\ \min(k,\,n-k), with equality in the first inequality if and only if all nonzero Schmidt coefficients are equal, λα2=1/χk\lambda_\alpha^2=1/\chi_k.

Proof (7 steps)
  1. Step 1:
    S(ρ1..k)=−Tr ρ1..klog⁡2ρ1..k=−∑α=1χkpαlog⁡2pα,pα:=λα2>0S(\rho_{1..k})=-\mathrm{Tr}\,\rho_{1..k}\log_2\rho_{1..k}=-\sum_{\alpha=1}^{\chi_k}p_\alpha\log_2p_\alpha,\qquad p_\alpha:=\lambda_\alpha^2>0
    The eigenvalues of ρ1..k\rho_{1..k} are the pαp_\alpha and 00 (previous lemma), and the zero eigenvalues contribute nothing by the convention 0log⁡0=00\log0=0.
  2. Step 2:
    S=∑α=1χkpα f(tα),f(t)=log⁡2t,tα=1pαS=\sum_{\alpha=1}^{\chi_k}p_\alpha\,f(t_\alpha),\qquad f(t)=\log_2t,\qquad t_\alpha=\frac1{p_\alpha}
    Rewrite −log⁡2pα=log⁡2(1/pα)-\log_2p_\alpha=\log_2(1/p_\alpha). The weights pαp_\alpha are positive and sum to 11.
  3. Step 3:
    f′′(t)=−1t2ln⁡2<0(t>0)f''(t)=-\frac{1}{t^2\ln2}<0\quad(t>0)
    ff is strictly concave on (0,∞)(0,\infty).
  4. Step 4:
    ∑αpαf(tα)≤f(∑αpαtα)\sum_\alpha p_\alpha f(t_\alpha)\le f\Big(\sum_\alpha p_\alpha t_\alpha\Big)
    Jensen's inequality for the concave function ff and the probability weights pαp_\alpha.
  5. Step 5:
    ∑αpαtα=∑α=1χkpα⋅1pα=χk ⇒ S(ρ1..k)≤log⁡2χk\sum_\alpha p_\alpha t_\alpha=\sum_{\alpha=1}^{\chi_k}p_\alpha\cdot\frac1{p_\alpha}=\chi_k\ \Rightarrow\ S(\rho_{1..k})\le\log_2\chi_k
    The weighted mean of the reciprocals is the number of terms.
  6. Step 6:
    S=log⁡2χk  ⟺  t1=⋯=tχk  ⟺  pα=1χk ∀αS=\log_2\chi_k\iff t_1=\cdots=t_{\chi_k}\iff p_\alpha=\frac1{\chi_k}\ \forall\alpha
    For a strictly concave function, equality in Jensen's inequality holds only when all points with positive weight coincide.
  7. Step 7:
    χk=rank⁡M(k)≤min⁡(2k,2n−k) ⇒ log⁡2χk≤min⁡(k,n−k)\chi_k=\operatorname{rank}M^{(k)}\le\min\big(2^k,2^{n-k}\big)\ \Rightarrow\ \log_2\chi_k\le\min(k,n-k)
    The rank of a matrix is at most its number of rows and at most its number of columns.

∎

Quick check

What is the largest Schmidt rank that any state of n=10n=10 qubits can have across the middle cut k=5k=5?

tolerance ±0.5

Matrix product states from successive SVDs#

Definition

Matrix product state (MPS)

An MPS of nn qubits with bond dimensions χ0=1,χ1,…,χn−1,χn=1\chi_0=1,\chi_1,\ldots,\chi_{n-1},\chi_n=1 is a family of matrices A[k]s∈Cχk−1×χkA^{[k]s}\in\mathbb C^{\chi_{k-1}\times\chi_k}, one for each site kk and each s∈{0,1}s\in\{0,1\}, such that ψs1s2…sn=A[1]s1A[2]s2⋯A[n]sn=∑α1,…,αn−1Aα1[1]s1Aα1α2[2]s2⋯Aαn−1[n]sn.\psi_{s_1s_2\ldots s_n}=A^{[1]s_1}A^{[2]s_2}\cdots A^{[n]s_n}=\sum_{\alpha_1,\ldots,\alpha_{n-1}}A^{[1]s_1}_{\alpha_1}A^{[2]s_2}_{\alpha_1\alpha_2}\cdots A^{[n]s_n}_{\alpha_{n-1}} . The first matrix is a row and the last a column, so the product is a number. The indices αk\alpha_k are bond indices. Site k<nk<n is left-canonical when ∑s∈{0,1}A[k]s†A[k]s=Iχk\sum_{s\in\{0,1\}}A^{[k]s\dagger}A^{[k]s}=I_{\chi_k}.

Theorem

Every state is an MPS: the successive-SVD construction

Every state ∣ψ⟩\lvert\psi\rangle of nn qubits has an MPS representation with χk≤min⁡(2k,2n−k)\chi_k\le\min(2^k,2^{n-k}), obtained by n−1n-1 singular value decompositions. Starting from C(0):=ψC^{(0)}:=\psi viewed as a 1×2n1\times2^n row and χ0=1\chi_0=1, step k=1,…,n−1k=1,\ldots,n-1 reshapes C(k−1)C^{(k-1)} to Ψ(k)∈C2χk−1×2n−k\Psi^{(k)}\in\mathbb C^{2\chi_{k-1}\times2^{n-k}}, computes a thin SVD Ψ(k)=U(k)Σ(k)V(k)†\Psi^{(k)}=U^{(k)}\Sigma^{(k)}V^{(k)\dagger} keeping the χk=rank⁡Ψ(k)\chi_k=\operatorname{rank}\Psi^{(k)} positive singular values, and sets Aαk−1αk[k]sk=U(αk−1sk),αk(k)A^{[k]s_k}_{\alpha_{k-1}\alpha_k}=U^{(k)}_{(\alpha_{k-1}s_k),\alpha_k} and C(k)=Σ(k)V(k)†C^{(k)}=\Sigma^{(k)}V^{(k)\dagger}. Finally Aαn−1[n]sn=Cαn−1,sn(n−1)A^{[n]s_n}_{\alpha_{n-1}}=C^{(n-1)}_{\alpha_{n-1},s_n}.

Proof (8 steps)
  1. Step 1:
    Ψs1,(s2⋯sn)(1)=ψs1s2…sn,Ψ(1)=M(1)∈C2×2n−1\Psi^{(1)}_{s_1,(s_2\cdots s_n)}=\psi_{s_1s_2\ldots s_n},\qquad\Psi^{(1)}=M^{(1)}\in\mathbb C^{2\times2^{n-1}}
    Step 11 is the matricisation across cut 11: the vector ψ\psi reshaped row-major to (2,2n−1)(2,2^{n-1}), possible because s1s_1 is the most significant bit.
  2. Step 2:
    Ψ(1)=U(1)Σ(1)V(1)† ⇒ ψs1…sn=∑α1=1χ1Us1,α1(1)(Σ(1)V(1)†)α1,(s2⋯sn)=∑α1Aα1[1]s1Cα1,(s2⋯sn)(1)\Psi^{(1)}=U^{(1)}\Sigma^{(1)}V^{(1)\dagger}\ \Rightarrow\ \psi_{s_1\ldots s_n}=\sum_{\alpha_1=1}^{\chi_1}U^{(1)}_{s_1,\alpha_1}\big(\Sigma^{(1)}V^{(1)\dagger}\big)_{\alpha_1,(s_2\cdots s_n)}=\sum_{\alpha_1}A^{[1]s_1}_{\alpha_1}C^{(1)}_{\alpha_1,(s_2\cdots s_n)}
    Thin SVD with U(1)∈C2×χ1U^{(1)}\in\mathbb C^{2\times\chi_1}; the definitions Aα1[1]s1=Us1,α1(1)A^{[1]s_1}_{\alpha_1}=U^{(1)}_{s_1,\alpha_1} and C(1)=Σ(1)V(1)†∈Cχ1×2n−1C^{(1)}=\Sigma^{(1)}V^{(1)\dagger}\in\mathbb C^{\chi_1\times2^{n-1}}.
  3. Step 3:
    Ψ(αk−1sk),(sk+1⋯sn)(k):=Cαk−1,(sksk+1⋯sn)(k−1),row index 2(αk−1−1)+sk\Psi^{(k)}_{(\alpha_{k-1}s_k),(s_{k+1}\cdots s_n)}:=C^{(k-1)}_{\alpha_{k-1},(s_ks_{k+1}\cdots s_n)},\qquad\text{row index }2(\alpha_{k-1}-1)+s_k
    Reshape for k≥2k\ge2: each row of C(k−1)C^{(k-1)} has length 2n−k+12^{n-k+1} and is split row-major into 22 rows of length 2n−k2^{n-k}, because sks_k is the most significant of the remaining bits. No entry is changed.
  4. Step 4:
    Ψ(k)=U(k)Σ(k)V(k)†,Aαk−1αk[k]sk:=U(αk−1sk),αk(k),C(k):=Σ(k)V(k)†∈Cχk×2n−k\Psi^{(k)}=U^{(k)}\Sigma^{(k)}V^{(k)\dagger},\qquad A^{[k]s_k}_{\alpha_{k-1}\alpha_k}:=U^{(k)}_{(\alpha_{k-1}s_k),\alpha_k},\qquad C^{(k)}:=\Sigma^{(k)}V^{(k)\dagger}\in\mathbb C^{\chi_k\times2^{n-k}}
    Thin SVD of Ψ(k)\Psi^{(k)} with χk=rank⁡Ψ(k)\chi_k=\operatorname{rank}\Psi^{(k)}. Cutting the column U⋅,αk(k)U^{(k)}_{\cdot,\alpha_k} of length 2χk−12\chi_{k-1} into the pairs (αk−1,sk)(\alpha_{k-1},s_k) yields the two matrices A[k]0,A[k]1∈Cχk−1×χkA^{[k]0},A^{[k]1}\in\mathbb C^{\chi_{k-1}\times\chi_k}.
  5. Step 5:
    Cαk−1,(sk⋯sn)(k−1)=∑αkU(αk−1sk),αk(k) Cαk,(sk+1⋯sn)(k)=∑αkAαk−1αk[k]skCαk,(sk+1⋯sn)(k)C^{(k-1)}_{\alpha_{k-1},(s_k\cdots s_n)}=\sum_{\alpha_k}U^{(k)}_{(\alpha_{k-1}s_k),\alpha_k}\,C^{(k)}_{\alpha_k,(s_{k+1}\cdots s_n)}=\sum_{\alpha_k}A^{[k]s_k}_{\alpha_{k-1}\alpha_k}C^{(k)}_{\alpha_k,(s_{k+1}\cdots s_n)}
    Read the SVD entrywise and undo the reshape of the previous step.
  6. Step 6:
    ψs1…sn=∑α1,…,αkAα1[1]s1Aα1α2[2]s2⋯Aαk−1αk[k]sk Cαk,(sk+1⋯sn)(k)\psi_{s_1\ldots s_n}=\sum_{\alpha_1,\ldots,\alpha_k}A^{[1]s_1}_{\alpha_1}A^{[2]s_2}_{\alpha_1\alpha_2}\cdots A^{[k]s_k}_{\alpha_{k-1}\alpha_k}\,C^{(k)}_{\alpha_k,(s_{k+1}\cdots s_n)}
    Induction on kk: the case k=1k=1 is the second step, and the previous identity replaces C(k−1)C^{(k-1)} by A[k]C(k)A^{[k]}C^{(k)}.
  7. Step 7:
    k=n−1:C(n−1)∈Cχn−1×2,Aαn−1[n]sn:=Cαn−1,sn(n−1) ⇒ ψs1…sn=A[1]s1⋯A[n]snk=n-1:\quad C^{(n-1)}\in\mathbb C^{\chi_{n-1}\times2},\qquad A^{[n]s_n}_{\alpha_{n-1}}:=C^{(n-1)}_{\alpha_{n-1},s_n}\ \Rightarrow\ \psi_{s_1\ldots s_n}=A^{[1]s_1}\cdots A^{[n]s_n}
    The remaining factor has one physical index; its columns are the last site's matrices, of shape χn−1×1\chi_{n-1}\times1.
  8. Step 8:
    χk≤min⁡(2χk−1, 2n−k) ⇒ χk≤min⁡(2k, 2n−k)\chi_k\le\min\big(2\chi_{k-1},\,2^{n-k}\big)\ \Rightarrow\ \chi_k\le\min\big(2^k,\,2^{n-k}\big)
    Ψ(k)\Psi^{(k)} has 2χk−12\chi_{k-1} rows and 2n−k2^{n-k} columns; induction from χ0=1\chi_0=1 gives χk≤2k\chi_k\le2^k.

∎

Lemma

The SVD construction is left-canonical

The matrices of the successive-SVD construction satisfy ∑sA[k]s†A[k]s=Iχk\sum_{s}A^{[k]s\dagger}A^{[k]s}=I_{\chi_k} for k=1,…,n−1k=1,\ldots,n-1. Consequently the 2k×χk2^k\times\chi_k matrix LkL_k with entries (Lk)(s1⋯sk),αk=(A[1]s1⋯A[k]sk)αk(L_k)_{(s_1\cdots s_k),\alpha_k}=\big(A^{[1]s_1}\cdots A^{[k]s_k}\big)_{\alpha_k} has orthonormal columns, Lk†Lk=IχkL_k^\dagger L_k=I_{\chi_k}.

Proof (5 steps)
  1. Step 1:
    (∑sA[k]s†A[k]s)α′α=∑s∑βAβα′[k]s‾ Aβα[k]s\Big(\sum_sA^{[k]s\dagger}A^{[k]s}\Big)_{\alpha'\alpha}=\sum_{s}\sum_{\beta}\overline{A^{[k]s}_{\beta\alpha'}}\,A^{[k]s}_{\beta\alpha}
    Matrix product with (A†)α′β=Aβα′‾(A^\dagger)_{\alpha'\beta}=\overline{A_{\beta\alpha'}}, summed over the physical index.
  2. Step 2:
    =∑(β,s)U(βs),α′(k)‾ U(βs),α(k)=(U(k)†U(k))α′α=\sum_{(\beta,s)}\overline{U^{(k)}_{(\beta s),\alpha'}}\,U^{(k)}_{(\beta s),\alpha}=\big(U^{(k)\dagger}U^{(k)}\big)_{\alpha'\alpha}
    The pair (β,s)(\beta,s) runs over all 2χk−12\chi_{k-1} rows of U(k)U^{(k)}, by the definition of A[k]sA^{[k]s}.
  3. Step 3:
    U(k)†U(k)=Iχk ⇒ ∑sA[k]s†A[k]s=IχkU^{(k)\dagger}U^{(k)}=I_{\chi_k}\ \Rightarrow\ \sum_sA^{[k]s\dagger}A^{[k]s}=I_{\chi_k}
    The left singular vectors kept in a thin SVD are orthonormal.
  4. Step 4:
    (Lk)(r,sk),αk=∑αk−1(Lk−1)r,αk−1Aαk−1αk[k]sk,L1=U(1)(L_k)_{(r,s_k),\alpha_k}=\sum_{\alpha_{k-1}}(L_{k-1})_{r,\alpha_{k-1}}A^{[k]s_k}_{\alpha_{k-1}\alpha_k},\qquad L_1=U^{(1)}
    Recursive form of LkL_k, with rr the row index of the first k−1k-1 bits.
  5. Step 5:
    Lk†Lk=∑skA[k]sk†(Lk−1†Lk−1)A[k]sk=∑skA[k]sk†A[k]sk=IχkL_k^\dagger L_k=\sum_{s_k}A^{[k]s_k\dagger}\big(L_{k-1}^\dagger L_{k-1}\big)A^{[k]s_k}=\sum_{s_k}A^{[k]s_k\dagger}A^{[k]s_k}=I_{\chi_k}
    Group the rows of LkL_k by sks_k; induction hypothesis Lk−1†Lk−1=IL_{k-1}^\dagger L_{k-1}=I, then the canonical condition.

∎

Theorem

Bond dimension equals Schmidt rank

In the successive-SVD construction, M(k)=LkΣ(k)V(k)†M^{(k)}=L_k\Sigma^{(k)}V^{(k)\dagger} is a singular value decomposition of the matricisation across cut kk. Hence the singular values of step kk are the Schmidt coefficients across cut kk, χk\chi_k is the Schmidt rank, and S(ρ1..k)=−∑α(σα(k))2log⁡2(σα(k))2≤log⁡2χkS(\rho_{1..k})=-\sum_\alpha\big(\sigma^{(k)}_\alpha\big)^2\log_2\big(\sigma^{(k)}_\alpha\big)^2\le\log_2\chi_k.

Proof (5 steps)
  1. Step 1:
    M(s1⋯sk),(sk+1⋯sn)(k)=ψs1…sn=∑αk(Lk)(s1⋯sk),αk Cαk,(sk+1⋯sn)(k)M^{(k)}_{(s_1\cdots s_k),(s_{k+1}\cdots s_n)}=\psi_{s_1\ldots s_n}=\sum_{\alpha_k}(L_k)_{(s_1\cdots s_k),\alpha_k}\,C^{(k)}_{\alpha_k,(s_{k+1}\cdots s_n)}
    The induction identity of the construction, with the first kk factors collected into LkL_k.
  2. Step 2:
    M(k)=LkC(k)=Lk Σ(k) V(k)†M^{(k)}=L_kC^{(k)}=L_k\,\Sigma^{(k)}\,V^{(k)\dagger}
    Matrix form of the previous line and the definition of C(k)C^{(k)}.
  3. Step 3:
    Lk†Lk=Iχk,V(k)†V(k)=Iχk,Σ(k)=diag(σ1(k),…,σχk(k)), σα(k)>0L_k^\dagger L_k=I_{\chi_k},\qquad V^{(k)\dagger}V^{(k)}=I_{\chi_k},\qquad\Sigma^{(k)}=\mathrm{diag}\big(\sigma^{(k)}_1,\ldots,\sigma^{(k)}_{\chi_k}\big),\ \sigma^{(k)}_\alpha>0
    The left-canonical lemma, the orthonormal right singular vectors of Ψ(k)\Psi^{(k)}, and the positive singular values kept.
  4. Step 4:
    ⇒ M(k)=∑α=1χkσα(k) (Lk)⋅,α (V⋅,α(k))† is a thin SVD of M(k)\Rightarrow\ M^{(k)}=\sum_{\alpha=1}^{\chi_k}\sigma^{(k)}_\alpha\,(L_k)_{\cdot,\alpha}\,\big(V^{(k)}_{\cdot,\alpha}\big)^\dagger\ \text{is a thin SVD of }M^{(k)}
    A factorisation into orthonormal columns, a positive diagonal and orthonormal rows is a singular value decomposition.
  5. Step 5:
    λα(k)=σα(k),rank⁡M(k)=χk\lambda^{(k)}_\alpha=\sigma^{(k)}_\alpha,\qquad\operatorname{rank}M^{(k)}=\chi_k
    Singular values are unique (they are the square roots of the eigenvalues of M(k)M(k)†M^{(k)}M^{(k)\dagger}), so they coincide with the Schmidt coefficients of the lemma; the entropy statement is the previous theorem.

∎

The MPS stores ∑k=1n2χk−1χk\sum_{k=1}^n2\chi_{k-1}\chi_k complex numbers. When every bond dimension is bounded by χ\chi, this is at most 2nχ22n\chi^2 instead of 2n2^n. For a Haar-random state the Schmidt ranks are generically maximal, χk=2min⁡(k,n−k)\chi_k=2^{\min(k,n-k)}, and nothing is gained; the inspector below shows the bond dimensions (2,4,8,4,2)(2,4,8,4,2) of a random 66-qubit state. Compression discards small Schmidt coefficients, at the cost given by the following identity.

Proposition

Truncation error at one cut

Let ∣ψ⟩=∑α=1χkλα∣aα⟩∣bα⟩\lvert\psi\rangle=\sum_{\alpha=1}^{\chi_k}\lambda_\alpha\lvert a_\alpha\rangle\lvert b_\alpha\rangle be the Schmidt decomposition across cut kk, keep the χ′<χk\chi'<\chi_k largest terms in ∣ψ′⟩\lvert\psi'\rangle, and let ε=∑α>χ′λα2\varepsilon=\sum_{\alpha>\chi'}\lambda_\alpha^2 be the discarded weight. Then ∥ψ−ψ′∥2=ε\lVert\psi-\psi'\rVert^2=\varepsilon and the normalised state ∣ψ~⟩=∣ψ′⟩/1−ε\lvert\tilde\psi\rangle=\lvert\psi'\rangle/\sqrt{1-\varepsilon} has fidelity ∣⟨ψ∣ψ~⟩∣2=1−ε\lvert\langle\psi\vert\tilde\psi\rangle\rvert^2=1-\varepsilon. By the Eckart–Young theorem no state of Schmidt rank χ′\chi' is closer to ∣ψ⟩\lvert\psi\rangle in norm.

Proof (4 steps)
  1. Step 1:
    ∣ψ⟩−∣ψ′⟩=∑α=χ′+1χkλα∣aα⟩∣bα⟩\lvert\psi\rangle-\lvert\psi'\rangle=\sum_{\alpha=\chi'+1}^{\chi_k}\lambda_\alpha\lvert a_\alpha\rangle\lvert b_\alpha\rangle
    The kept terms cancel.
  2. Step 2:
    ∥ψ−ψ′∥2=∑α,β>χ′λαλβ⟨aα∣aβ⟩⟨bα∣bβ⟩=∑α>χ′λα2=ε\big\lVert\psi-\psi'\big\rVert^2=\sum_{\alpha,\beta>\chi'}\lambda_\alpha\lambda_\beta\langle a_\alpha\vert a_\beta\rangle\langle b_\alpha\vert b_\beta\rangle=\sum_{\alpha>\chi'}\lambda_\alpha^2=\varepsilon
    The product vectors ∣aα⟩∣bα⟩\lvert a_\alpha\rangle\lvert b_\alpha\rangle are orthonormal.
  3. Step 3:
    ⟨ψ∣ψ′⟩=∑α≤χ′λα2=1−ε=∥ψ′∥2\langle\psi\vert\psi'\rangle=\sum_{\alpha\le\chi'}\lambda_\alpha^2=1-\varepsilon=\lVert\psi'\rVert^2
    Same orthonormality, together with ∑αλα2=1\sum_\alpha\lambda_\alpha^2=1.
  4. Step 4:
    ∣⟨ψ∣ψ~⟩∣2=(1−ε)21−ε=1−ε\big\lvert\langle\psi\vert\tilde\psi\rangle\big\rvert^2=\frac{(1-\varepsilon)^2}{1-\varepsilon}=1-\varepsilon
    Divide by the norm 1−ε\sqrt{1-\varepsilon} of ∣ψ′⟩\lvert\psi'\rangle and square.

∎

The second inspector caps every bond at χ′=4\chi'=4 for a random state of 88 qubits. Only the three middle cuts exceed this cap, and the inspector reports the discarded weight. For a random state the Schmidt spectrum is flat, so truncation is costly; for the low-entanglement states of the next sections it is exact.

Quick check

How many complex numbers does an MPS of n=10n=10 qubits with χk=2\chi_k=2 at every cut store, counting all entries of all matrices A[k]sA^{[k]s}?

tolerance ±0.5

Sequential circuits and the bond-dimension bound#

Which circuits produce states of small bond dimension? A two-qubit gate whose qubits lie on the same side of a cut cannot change the Schmidt rank across it, so only gates that straddle the cut matter. How much a straddling gate can increase the Schmidt rank is measured by a property of the gate alone.

Definition

Operator-Schmidt rank

A two-qubit operator GG on qubits (a,b)(a,b) can be written as G=∑m=1rAm⊗BmG=\sum_{m=1}^rA_m\otimes B_m with AmA_m acting on aa and BmB_m on bb. The smallest such rr is the operator-Schmidt rank r(G)r(G). It is computed from the realigned matrix R(G)∈C4×4R(G)\in\mathbb C^{4\times4}, R(G)(i,a),(j,b)=⟨ij∣G∣ab⟩,R(G)_{(i,a),(j,b)}=\langle ij\vert G\vert ab\rangle, whose rows are labelled by the output and input bit (i,a)(i,a) of the first qubit and whose columns by those of the second qubit, (j,b)(j,b): we prove below that r(G)=rank⁡R(G)r(G)=\operatorname{rank}R(G).

Lemma

Operator-Schmidt ranks of common gates

(a) r(G)=rank⁡R(G)≤4r(G)=\operatorname{rank}R(G)\le4 for every two-qubit operator. (b) r((U1⊗U2)G(V1⊗V2))=r(G)r\big((U_1\otimes U_2)G(V_1\otimes V_2)\big)=r(G) for invertible single-qubit Ui,ViU_i,V_i. (c) A controlled gate C(U)=∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗UC(U)=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes U has r=2r=2 if UU is not a multiple of II, and r=1r=1 otherwise. Hence CNOT\mathrm{CNOT}, CZ\mathrm{CZ}, CRY(θ)\mathrm{CRY}(\theta) for θ∉2πZ\theta\notin2\pi\mathbb Z, and every gate (U1⊗U2) CNOT (V1⊗V2)(U_1\otimes U_2)\,\mathrm{CNOT}\,(V_1\otimes V_2) consisting of one CNOT dressed with single-qubit gates have r=2r=2. (d) SWAP\mathrm{SWAP} has r=4r=4. (e) The block B(θ)=CNOT(b,a) CRY(a,b,θ)B(\theta)=\mathrm{CNOT}(b,a)\,\mathrm{CRY}(a,b,\theta), a controlled rotation followed by a CNOT in the opposite direction, has r=4r=4 for θ∉2πZ\theta\notin2\pi\mathbb Z.

Proof (9 steps)
  1. Step 1:
    G=∑i,a,j,b⟨ij∣G∣ab⟩ ∣ij⟩⟨ab∣=∑(i,a),(j,b)R(G)(i,a),(j,b) Eia⊗Ejb,Eia=∣i⟩⟨a∣G=\sum_{i,a,j,b}\langle ij\vert G\vert ab\rangle\,\lvert ij\rangle\langle ab\rvert=\sum_{(i,a),(j,b)}R(G)_{(i,a),(j,b)}\,E_{ia}\otimes E_{jb},\qquad E_{ia}=\lvert i\rangle\langle a\rvert
    Expansion in matrix units, using ∣ij⟩⟨ab∣=∣i⟩⟨a∣⊗∣j⟩⟨b∣\lvert ij\rangle\langle ab\rvert=\lvert i\rangle\langle a\rvert\otimes\lvert j\rangle\langle b\rvert.
  2. Step 2:
    G=∑m=1rAm⊗Bm ⇒ R(G)=∑m=1rvec(Am) vec(Bm)T,vec(A)(i,a)=Aia ⇒ rank⁡R(G)≤rG=\sum_{m=1}^rA_m\otimes B_m\ \Rightarrow\ R(G)=\sum_{m=1}^r\mathrm{vec}(A_m)\,\mathrm{vec}(B_m)^{\mathsf T},\quad\mathrm{vec}(A)_{(i,a)}=A_{ia}\ \Rightarrow\ \operatorname{rank}R(G)\le r
    ⟨ij∣A⊗B∣ab⟩=AiaBjb\langle ij\vert A\otimes B\vert ab\rangle=A_{ia}B_{jb}, so each term contributes a rank-one matrix, and rank is subadditive.
  3. Step 3:
    R(G)=∑m=1rank⁡RxmymT ⇒ G=∑mmat(xm)⊗mat(ym) ⇒ r(G)=rank⁡R(G)≤4R(G)=\sum_{m=1}^{\operatorname{rank}R}x_my_m^{\mathsf T}\ \Rightarrow\ G=\sum_{m}\mathrm{mat}(x_m)\otimes\mathrm{mat}(y_m)\ \Rightarrow\ r(G)=\operatorname{rank}R(G)\le4
    Conversely, a rank factorisation of R(G)R(G) (for example from its SVD) is read back through the first step, with mat\mathrm{mat} the inverse of vec\mathrm{vec}. A 4×44\times4 matrix has rank at most 44. This proves (a).
  4. Step 4:
    (U1⊗U2)(∑mAm⊗Bm)(V1⊗V2)=∑m(U1AmV1)⊗(U2BmV2)(U_1\otimes U_2)\Big(\sum_mA_m\otimes B_m\Big)(V_1\otimes V_2)=\sum_m(U_1A_mV_1)\otimes(U_2B_mV_2)
    Local factors do not increase the number of terms, so rr cannot grow; applying the inverses shows it cannot shrink either, which proves (b).
  5. Step 5:
    R(C(U))(i,a),(j,b)=δia(δi0 δjb+δi1 Ujb):row (0,0)=vec(I), row (1,1)=vec(U), rows (0,1),(1,0)=0R\big(C(U)\big)_{(i,a),(j,b)}=\delta_{ia}\big(\delta_{i0}\,\delta_{jb}+\delta_{i1}\,U_{jb}\big):\quad\text{row }(0,0)=\mathrm{vec}(I),\ \text{row }(1,1)=\mathrm{vec}(U),\ \text{rows }(0,1),(1,0)=0
    C(U)C(U) does not change the control bit, so ⟨ij∣C(U)∣ab⟩=0\langle ij\vert C(U)\vert ab\rangle=0 unless i=ai=a; the control value selects II or UU on the target.
  6. Step 6:
    rank⁡R(C(U))=dim⁡span⁡{vec(I),vec(U)}={2,U∉C I,1,U∈C I,RY(θ)=cos⁡θ2 I−isin⁡θ2 Y\operatorname{rank}R\big(C(U)\big)=\dim\operatorname{span}\{\mathrm{vec}(I),\mathrm{vec}(U)\}=\begin{cases}2,&U\notin\mathbb C\,I,\\1,&U\in\mathbb C\,I,\end{cases}\qquad R_Y(\theta)=\cos\tfrac\theta2\,I-i\sin\tfrac\theta2\,Y
    This proves (c) for CNOT=C(X)\mathrm{CNOT}=C(X) and CZ=C(Z)\mathrm{CZ}=C(Z). RY(θ)R_Y(\theta) is a multiple of II only for sin⁡θ2=0\sin\frac\theta2=0, i.e. θ∈2πZ\theta\in2\pi\mathbb Z (then CRY(2π)=Z⊗I\mathrm{CRY}(2\pi)=Z\otimes I). The dressed CNOT has r=2r=2 by (b).
  7. Step 7:
    R(SWAP)(i,a),(j,b)=⟨ij∣ba⟩=δib δjaR(\mathrm{SWAP})_{(i,a),(j,b)}=\langle ij\vert ba\rangle=\delta_{ib}\,\delta_{ja}
    SWAP∣ab⟩=∣ba⟩\mathrm{SWAP}\lvert ab\rangle=\lvert ba\rangle. Row (i,a)(i,a) has its only nonzero entry in column (a,i)(a,i), and distinct rows use distinct columns, so RR is a permutation matrix of rank 44. This proves (d).
  8. Step 8:
    B∣00⟩=∣00⟩,B∣01⟩=∣11⟩,B∣10⟩=c∣10⟩+s∣01⟩,B∣11⟩=−s∣10⟩+c∣01⟩,c=cos⁡θ2, s=sin⁡θ2B\lvert00\rangle=\lvert00\rangle,\quad B\lvert01\rangle=\lvert11\rangle,\quad B\lvert10\rangle=c\lvert10\rangle+s\lvert01\rangle,\quad B\lvert11\rangle=-s\lvert10\rangle+c\lvert01\rangle,\qquad c=\cos\tfrac\theta2,\ s=\sin\tfrac\theta2
    The CRY acts only when a=1a=1, with RY(θ)∣0⟩=c∣0⟩+s∣1⟩R_Y(\theta)\lvert0\rangle=c\lvert0\rangle+s\lvert1\rangle and RY(θ)∣1⟩=−s∣0⟩+c∣1⟩R_Y(\theta)\lvert1\rangle=-s\lvert0\rangle+c\lvert1\rangle; the CNOT then flips aa whenever b=1b=1.
  9. Step 9:
    R(B)=(100000sc0001c−s00),det⁡R(B)=−s2=−sin⁡2θ2R(B)=\begin{pmatrix}1&0&0&0\\0&0&s&c\\0&0&0&1\\c&-s&0&0\end{pmatrix},\qquad\det R(B)=-s^2=-\sin^2\tfrac\theta2
    Rows (i,a)(i,a) and columns (j,b)(j,b) in the order 00,01,10,1100,01,10,11, entries ⟨ij∣B∣ab⟩\langle ij\vert B\vert ab\rangle read off the previous line; the determinant follows by expansion along the first row. It vanishes only for θ∈2πZ\theta\in2\pi\mathbb Z, which proves (e).

∎

Lemma

A straddling gate multiplies the Schmidt rank by at most its operator-Schmidt rank

Let ∣ψ⟩\lvert\psi\rangle have Schmidt rank χ\chi across cut kk and let GG act on the sites (k,k+1)(k,k+1), which straddle the cut. Then the Schmidt rank of G∣ψ⟩G\lvert\psi\rangle across cut kk is at most r(G) χr(G)\,\chi. An operator acting only on sites 1,…,k1,\ldots,k, or only on sites k+1,…,nk+1,\ldots,n, leaves the Schmidt rank across cut kk unchanged if it is invertible. In particular single-qubit gates and gates on (j,j+1)(j,j+1) with j≠kj\ne k do not change χk\chi_k.

Proof (5 steps)
  1. Step 1:
    ∣∑m=1N∣xm⟩⊗∣ym⟩⟩ ⟷ M=∑m=1NxmymT,rank⁡M≤N\Big\lvert\sum_{m=1}^{N}\lvert x_m\rangle\otimes\lvert y_m\rangle\Big\rangle\ \longleftrightarrow\ M=\sum_{m=1}^Nx_my_m^{\mathsf T},\qquad\operatorname{rank}M\le N
    The matricisation of a sum of NN product vectors is a sum of NN rank-one matrices. By the Schmidt lemma the Schmidt rank equals rank⁡M\operatorname{rank}M.
  2. Step 2:
    ∣ψ⟩=∑α=1χλα∣aα⟩∣bα⟩,G=∑j=1r(I1..k−1⊗Aj)⊗(Bj⊗Ik+2..n)\lvert\psi\rangle=\sum_{\alpha=1}^{\chi}\lambda_\alpha\lvert a_\alpha\rangle\lvert b_\alpha\rangle,\qquad G=\sum_{j=1}^{r}\big(I_{1..k-1}\otimes A_j\big)\otimes\big(B_j\otimes I_{k+2..n}\big)
    Schmidt decomposition of the input, and an optimal operator-Schmidt decomposition of GG: site kk is the last site of the left block and site k+1k+1 the first of the right block.
  3. Step 3:
    G∣ψ⟩=∑j=1r∑α=1χλα (A~j∣aα⟩)⊗(B~j∣bα⟩)G\lvert\psi\rangle=\sum_{j=1}^{r}\sum_{\alpha=1}^{\chi}\lambda_\alpha\,\big(\tilde A_j\lvert a_\alpha\rangle\big)\otimes\big(\tilde B_j\lvert b_\alpha\rangle\big)
    Distribute; A~j\tilde A_j and B~j\tilde B_j denote the factors with identities attached. This is a sum of rχr\chi product vectors, so the Schmidt rank is at most rχr\chi.
  4. Step 4:
    (W⊗I)∣ψ⟩ ⟷ W M(k),(I⊗W′)∣ψ⟩ ⟷ M(k)W′T(W\otimes I)\lvert\psi\rangle\ \longleftrightarrow\ W\,M^{(k)},\qquad(I\otimes W')\lvert\psi\rangle\ \longleftrightarrow\ M^{(k)}W'^{\mathsf T}
    An operator on one block multiplies the matricisation from one side.
  5. Step 5:
    rank⁡(WM(k))=rank⁡M(k)=rank⁡(M(k)W′T)\operatorname{rank}\big(WM^{(k)}\big)=\operatorname{rank}M^{(k)}=\operatorname{rank}\big(M^{(k)}W'^{\mathsf T}\big)
    Multiplication by an invertible matrix preserves rank. A gate on (j,j+1)(j,j+1) with j≤k−1j\le k-1 lies in the left block and one with j≥k+1j\ge k+1 in the right block.

∎

Theorem

Bond dimension of nearest-neighbour and sequential circuits

Let ∣ψ⟩=V∣0n⟩\lvert\psi\rangle=V\lvert0^n\rangle, where VV is a sequence of single-qubit gates and of two-qubit gates on neighbouring sites (j,j+1)(j,j+1). Fix a cut kk and let G(1),…,G(m)G^{(1)},\ldots,G^{(m)} be the gates on sites (k,k+1)(k,k+1), in time order, with operator-Schmidt ranks r1,…,rmr_1,\ldots,r_m (an empty product equals 11).

(a) χk(ψ)≤min⁡(r1r2⋯rm, 2min⁡(k,n−k))\chi_k(\psi)\le\min\big(r_1r_2\cdots r_m,\ 2^{\min(k,n-k)}\big).

(b) If no two-qubit gate has acted on any of the sites k+1,…,nk+1,\ldots,n before G(1)G^{(1)}, then χk(ψ)≤min⁡(min⁡(r1,2) r2⋯rm, 2min⁡(k,n−k))\chi_k(\psi)\le\min\big(\min(r_1,2)\,r_2\cdots r_m,\ 2^{\min(k,n-k)}\big).

(c) A staircase layer applies two-qubit gates G1,…,Gn−1G_1,\ldots,G_{n-1} on the sites (1,2),…,(n−1,n)(1,2),\ldots,(n-1,n) in this order. If VV consists of LL staircase layers of arbitrary two-qubit gates, with single-qubit gates anywhere, then for every cut χk≤2min⁡(L, k, n−k)=min⁡(2L,2min⁡(k,n−k)).\chi_k\le2^{\min(L,\,k,\,n-k)}=\min\big(2^L,2^{\min(k,n-k)}\big).

So one staircase layer gives χk≤2\chi_k\le2. For single-CNOT blocks (r=2r=2: CNOT, CZ or CRY dressed with single-qubit gates) part (a) gives χk≤min⁡(2mk,2min⁡(k,n−k))\chi_k\le\min(2^{m_k},2^{\min(k,n-k)}), with mkm_k the number of gates crossing cut kk, in any gate order; in particular min⁡(2L,2min⁡(k,n−k))\min(2^L,2^{\min(k,n-k)}) for LL layers.

Proof (10 steps)
  1. Step 1:
    χk(∣0n⟩)=1\chi_k\big(\lvert0^n\rangle\big)=1
    The initial state is a product state: M(k)M^{(k)} has a single nonzero entry.
  2. Step 2:
    χk(G(i)∣ϕ⟩)≤ri χk(∣ϕ⟩),χk(g∣ϕ⟩)=χk(∣ϕ⟩) for every other gate g\chi_k\big(G^{(i)}\lvert\phi\rangle\big)\le r_i\,\chi_k\big(\lvert\phi\rangle\big),\qquad\chi_k\big(g\lvert\phi\rangle\big)=\chi_k\big(\lvert\phi\rangle\big)\ \text{for every other gate }g
    The multiplication lemma for the straddling gates; every other gate of VV acts within one block (gates on (j,j+1)(j,j+1) with j≠kj\ne k, single-qubit gates) and is unitary.
  3. Step 3:
    χk(ψ)≤r1r2⋯rm,χk(ψ)≤min⁡(2k,2n−k)\chi_k(\psi)\le r_1r_2\cdots r_m,\qquad\chi_k(\psi)\le\min\big(2^k,2^{n-k}\big)
    Induction over the gates of VV, and the dimension bound on rank⁡M(k)\operatorname{rank}M^{(k)}. This proves (a).
  4. Step 4:
    ∣ϕ⟩=∣ϕL⟩1..k⊗∣ck+1⟩⊗∣ck+2⟩⊗⋯⊗∣cn⟩just before G(1)\lvert\phi\rangle=\lvert\phi_L\rangle_{1..k}\otimes\lvert c_{k+1}\rangle\otimes\lvert c_{k+2}\rangle\otimes\cdots\otimes\lvert c_n\rangle\quad\text{just before }G^{(1)}
    Under the hypothesis of (b), sites k+1,…,nk+1,\ldots,n have only received single-qubit gates, which keep each of them in a single-qubit state ∣cj⟩\lvert c_j\rangle; all two-qubit gates so far act inside sites 1,…,k1,\ldots,k.
  5. Step 5:
    G(1)∣ϕ⟩=∑j(A~j∣ϕL⟩)⊗Bj∣ck+1⟩⊗∣crest⟩=∑t∈{0,1}(∑j⟨t∣Bj∣ck+1⟩ A~j∣ϕL⟩)⊗∣t⟩⊗∣crest⟩G^{(1)}\lvert\phi\rangle=\sum_{j}\big(\tilde A_j\lvert\phi_L\rangle\big)\otimes B_j\lvert c_{k+1}\rangle\otimes\lvert c_{\mathrm{rest}}\rangle=\sum_{t\in\{0,1\}}\Big(\sum_j\langle t\vert B_j\vert c_{k+1}\rangle\,\tilde A_j\lvert\phi_L\rangle\Big)\otimes\lvert t\rangle\otimes\lvert c_{\mathrm{rest}}\rangle
    Insert I=∑t∣t⟩⟨t∣I=\sum_t\lvert t\rangle\langle t\rvert on site k+1k+1: every vector Bj∣ck+1⟩B_j\lvert c_{k+1}\rangle lies in the two-dimensional space of one qubit. The result is a sum of 22 product vectors across cut kk, so χk≤2\chi_k\le2; the lemma also gives χk≤r1\chi_k\le r_1.
  6. Step 6:
    χk(ψ)≤min⁡(r1,2) r2⋯rm\chi_k(\psi)\le\min(r_1,2)\,r_2\cdots r_m
    The later straddling gates multiply by at most r2,…,rmr_2,\ldots,r_m and all other gates preserve χk\chi_k; with the dimension bound this proves (b).
  7. Step 7:
    G on (k,k+1):G∣ϕ⟩=∑β=1χk+1∣Lβ′⟩1..k+1∣Rβ⟩k+2..n=∑β=1χk+1∑t∈{0,1}(⟨t∣k+1∣Lβ′⟩)⊗∣t⟩∣Rβ⟩ ⇒ χk≤2χk+1G\text{ on }(k,k+1):\quad G\lvert\phi\rangle=\sum_{\beta=1}^{\chi_{k+1}}\lvert L'_\beta\rangle_{1..k+1}\lvert R_\beta\rangle_{k+2..n}=\sum_{\beta=1}^{\chi_{k+1}}\sum_{t\in\{0,1\}}\big(\langle t\rvert_{k+1}\lvert L'_\beta\rangle\big)\otimes\lvert t\rangle\lvert R_\beta\rangle\ \Rightarrow\ \chi_k\le2\chi_{k+1}
    For (c): both sites of GG lie left of cut k+1k+1, so GG keeps χk+1\chi_{k+1} (multiplication lemma), and G∣ϕ⟩G\lvert\phi\rangle has a Schmidt decomposition across cut k+1k+1 with χk+1\chi_{k+1} terms. Resolving site k+1k+1 in the basis ∣t⟩\lvert t\rangle writes it as 2χk+12\chi_{k+1} product vectors across cut kk. For k=n−1k=n-1 put χn:=1\chi_n:=1.
  8. Step 8:
    cℓ(k):=χk after layer ℓ:cℓ(k)≤2 cℓ−1(k+1),c0(k)=1,cℓ(n):=1c_\ell(k):=\chi_k\text{ after layer }\ell:\qquad c_\ell(k)\le2\,c_{\ell-1}(k+1),\qquad c_0(k)=1,\quad c_\ell(n):=1
    Between Gk+1(ℓ−1)G^{(\ell-1)}_{k+1} and Gk(ℓ)G^{(\ell)}_k only the gates Gk+2(ℓ−1),…,Gn−1(ℓ−1)G^{(\ell-1)}_{k+2},\ldots,G^{(\ell-1)}_{n-1} (right of cut k+1k+1) and G1(ℓ),…,Gk−1(ℓ)G^{(\ell)}_1,\ldots,G^{(\ell)}_{k-1} (left of it) act, so χk+1=cℓ−1(k+1)\chi_{k+1}=c_{\ell-1}(k+1) when Gk(ℓ)G^{(\ell)}_k is applied. After Gk(ℓ)G^{(\ell)}_k the remaining gates of layer ℓ\ell lie right of cut kk and do not change χk\chi_k.
  9. Step 9:
    cℓ(k)≤2⋅2min⁡(ℓ−1, n−k−1)=2min⁡(ℓ, n−k) ⇒ χk≤min⁡(2min⁡(L,n−k),2k)=2min⁡(L,k,n−k)c_\ell(k)\le2\cdot2^{\min(\ell-1,\,n-k-1)}=2^{\min(\ell,\,n-k)}\ \Rightarrow\ \chi_k\le\min\big(2^{\min(L,n-k)},2^k\big)=2^{\min(L,k,n-k)}
    Induction on ℓ\ell with the base case c0≡1c_0\equiv1 (for k=n−1k=n-1 the bound reads cℓ(n−1)≤2c_\ell(n-1)\le2), then the dimension bound 2k2^k. This proves (c).
  10. Step 10:
    r(G(i))≤2  ∀i ⇒ χk≤min⁡(2mk,2min⁡(k,n−k))r\big(G^{(i)}\big)\le2\ \ \forall i\ \Rightarrow\ \chi_k\le\min\big(2^{m_k},2^{\min(k,n-k)}\big)
    Insert r≤2r\le2 from the lemma on common gates into (a); no assumption on the order of the gates is needed.

∎

Parts (b) and (c) are stronger than the multiplication lemma alone. The W-state staircase of the next section uses blocks CNOT(q+1,q) CRY(q,q+1,θ)\mathrm{CNOT}(q+1,q)\,\mathrm{CRY}(q,q+1,\theta) of operator-Schmidt rank 44, yet the state has χ=2\chi=2, because each block meets a site that is still in a product state. The order of the gates matters: prepare Bell pairs on qubits (0,1)(0,1) and (2,3)(2,3) and then apply SWAP\mathrm{SWAP} on (1,2)(1,2). Cut 22 is crossed by one gate only, but χ2=4=r(SWAP)\chi_2=4=r(\mathrm{SWAP}), since the right block was entangled before the crossing gate. The GHZ state, prepared by H(0)H(0) and the staircase CNOT(0,1),CNOT(1,2),…\mathrm{CNOT}(0,1),\mathrm{CNOT}(1,2),\ldots, has the Schmidt decomposition 12∣0k⟩∣0n−k⟩+12∣1k⟩∣1n−k⟩\tfrac1{\sqrt2}\lvert0^k\rangle\lvert0^{n-k}\rangle+\tfrac1{\sqrt2}\lvert1^k\rangle\lvert1^{n-k}\rangle across every cut: χk=2\chi_k=2 and S=1S=1 bit, the equality case of the entropy bound.

The next inspector draws a random 22-layer staircase on 66 qubits whose blocks are RY⊗RYR_Y\otimes R_Y, CNOT(k,k+1)\mathrm{CNOT}(k,k+1), RY⊗RYR_Y\otimes R_Y (operator-Schmidt rank 22). Both (a) and (c) give χ≤(2,4,4,4,2)\chi\le(2,4,4,4,2), while the dimension bound allows χ3=8\chi_3=8: the bond dimension grows exponentially in the number of layers, not in nn.

Quick check

A circuit on n=8n=8 qubits consists of L=2L=2 staircase layers of CNOT gates dressed with single-qubit rotations. What is the best upper bound from the theorem on the bond dimension χ4\chi_4 at the middle cut?

tolerance ±0.5

The W state as a bond-dimension-2 MPS#

The three-qubit W state ∣W3⟩=13(∣001⟩+∣010⟩+∣100⟩)\lvert W_3\rangle=\tfrac1{\sqrt3}(\lvert001\rangle+\lvert010\rangle+\lvert100\rangle) is inequivalent to GHZ under stochastic local operations and classical communication (Dür, Vidal and Cirac 2000). Its MPS has bond dimension 22, like GHZ, but its Schmidt spectrum is unequal, so it does not saturate the entropy bound.

Derivation

Schmidt decompositions and entropy of the W state

  1. Step 1:
    ∣W3⟩=23 ∣0⟩⊗∣01⟩+∣10⟩2+13 ∣1⟩⊗∣00⟩\lvert W_3\rangle=\sqrt{\tfrac23}\,\lvert0\rangle\otimes\frac{\lvert01\rangle+\lvert10\rangle}{\sqrt2}+\sqrt{\tfrac13}\,\lvert1\rangle\otimes\lvert00\rangle
    Cut 11: group the three terms by the value of qubit 00; two terms have s1=0s_1=0, one has s1=1s_1=1.
  2. Step 2:
    ⟨0∣1⟩=0,⟨00∣∣01⟩+∣10⟩2⟩=0\langle0\vert1\rangle=0,\qquad\Big\langle00\Big\vert\tfrac{\lvert01\rangle+\lvert10\rangle}{\sqrt2}\Big\rangle=0
    Both families are orthonormal, so this is a Schmidt decomposition with λ=(2/3,1/3)\lambda=(\sqrt{2/3},\sqrt{1/3}) and χ1=2\chi_1=2.
  3. Step 3:
    ∣W3⟩=23 ∣01⟩+∣10⟩2⊗∣0⟩+13 ∣00⟩⊗∣1⟩\lvert W_3\rangle=\sqrt{\tfrac23}\,\frac{\lvert01\rangle+\lvert10\rangle}{\sqrt2}\otimes\lvert0\rangle+\sqrt{\tfrac13}\,\lvert00\rangle\otimes\lvert1\rangle
    Cut 22: group by the value of qubit 22. Again orthonormal on both sides, with the same coefficients and χ2=2\chi_2=2.
  4. Step 4:
    ρ0=23∣0⟩⟨0∣+13∣1⟩⟨1∣=diag(23,13)\rho_0=\tfrac23\lvert0\rangle\langle0\rvert+\tfrac13\lvert1\rangle\langle1\rvert=\mathrm{diag}\big(\tfrac23,\tfrac13\big)
    The Schmidt lemma with the decomposition across cut 11. The state is symmetric under permutations of the qubits, so every single-qubit marginal equals diag(23,13)\mathrm{diag}(\tfrac23,\tfrac13).
  5. Step 5:
    ρ01=23∣Ψ+⟩⟨Ψ+∣+13∣00⟩⟨00∣,∣Ψ+⟩=12(∣01⟩+∣10⟩)\rho_{01}=\tfrac23\lvert\Psi^+\rangle\langle\Psi^+\rvert+\tfrac13\lvert00\rangle\langle00\rvert,\qquad\lvert\Psi^+\rangle=\tfrac{1}{\sqrt2}(\lvert01\rangle+\lvert10\rangle)
    The Schmidt lemma across cut 22: the two-qubit marginal has rank 22 and the same nonzero spectrum as ρ2\rho_2.
  6. Step 6:
    S(ρ0)=−23log⁡223−13log⁡213=h(13)S(\rho_0)=-\tfrac23\log_2\tfrac23-\tfrac13\log_2\tfrac13=h\big(\tfrac13\big)
    Entropy of the spectrum (23,13)(\tfrac23,\tfrac13), the binary entropy h(p)=−plog⁡2p−(1−p)log⁡2(1−p)h(p)=-p\log_2p-(1-p)\log_2(1-p) at p=13p=\tfrac13.
  7. Step 7:
    h(13)=13log⁡23+23(log⁡23−1)=log⁡23−23≈1.5849625−0.6666667=0.9182958h\big(\tfrac13\big)=\tfrac13\log_23+\tfrac23\big(\log_23-1\big)=\log_23-\tfrac23\approx1.5849625-0.6666667=0.9182958
    −log⁡213=log⁡23-\log_2\tfrac13=\log_23 and −log⁡223=log⁡23−1-\log_2\tfrac23=\log_23-1.
  8. Step 8:
    S(ρ0)=S(ρ01)=0.9182958<1=log⁡2χ1S(\rho_0)=S(\rho_{01})=0.9182958<1=\log_2\chi_1
    The bound S≤log⁡2χS\le\log_2\chi is strict because 23≠13\tfrac23\ne\tfrac13. In nats the value is ln⁡3−23ln⁡2≈0.6365142\ln3-\tfrac23\ln2\approx0.6365142, smaller by the factor ln⁡2\ln2.

Result

λ(1)=λ(2)=(23,13),χ=(2,2),S(ρ0)=h(13)=log⁡23−23=0.9182958340544896\boxed{\lambda^{(1)}=\lambda^{(2)}=\Big(\sqrt{\tfrac23},\sqrt{\tfrac13}\Big),\qquad\chi=(2,2),\qquad S(\rho_0)=h\big(\tfrac13\big)=\log_23-\tfrac23=0.9182958340544896}
Derivation

The MPS tensors of the W state by successive SVDs

  1. Step 1:
    Ψ(1)=(01313013000)(rows s1=0,1; columns s2s3=00,01,10,11)\Psi^{(1)}=\begin{pmatrix}0&\frac1{\sqrt3}&\frac1{\sqrt3}&0\\\frac1{\sqrt3}&0&0&0\end{pmatrix}\qquad(\text{rows }s_1=0,1;\ \text{columns }s_2s_3=00,01,10,11)
    Reshape the 88 amplitudes (0,a,a,0,a,0,0,0)(0,a,a,0,a,0,0,0), a=13a=\tfrac1{\sqrt3}, row-major to (2,4)(2,4).
  2. Step 2:
    Ψ(1)Ψ(1)†=diag(23,13) ⇒ U(1)=I2,Σ(1)=diag(23,13),A[1]0=(1, 0), A[1]1=(0, 1)\Psi^{(1)}\Psi^{(1)\dagger}=\mathrm{diag}\big(\tfrac23,\tfrac13\big)\ \Rightarrow\ U^{(1)}=I_2,\quad\Sigma^{(1)}=\mathrm{diag}\Big(\sqrt{\tfrac23},\sqrt{\tfrac13}\Big),\quad A^{[1]0}=(1,\ 0),\ A^{[1]1}=(0,\ 1)
    The rows are orthogonal with squared norms 23\tfrac23 and 13\tfrac13, already in decreasing order, so the left singular vectors are the unit vectors and C(1)=Σ(1)V(1)†=Ψ(1)C^{(1)}=\Sigma^{(1)}V^{(1)\dagger}=\Psi^{(1)}.
  3. Step 3:
    Ψ(2)=(01313013000)(rows (α1,s2)=(1,0),(1,1),(2,0),(2,1); columns s3)\Psi^{(2)}=\begin{pmatrix}0&\frac1{\sqrt3}\\\frac1{\sqrt3}&0\\\frac1{\sqrt3}&0\\0&0\end{pmatrix}\qquad(\text{rows }(\alpha_1,s_2)=(1,0),(1,1),(2,0),(2,1);\ \text{columns }s_3)
    Split each row of C(1)C^{(1)}, of length 44, into two rows of length 22.
  4. Step 4:
    Ψ(2)=(0112012000)⏟U(2)(230013)⏟Σ(2)(1001)⏟V(2)†\Psi^{(2)}=\underbrace{\begin{pmatrix}0&1\\\frac1{\sqrt2}&0\\\frac1{\sqrt2}&0\\0&0\end{pmatrix}}_{U^{(2)}}\underbrace{\begin{pmatrix}\sqrt{\frac23}&0\\0&\sqrt{\frac13}\end{pmatrix}}_{\Sigma^{(2)}}\underbrace{\begin{pmatrix}1&0\\0&1\end{pmatrix}}_{V^{(2)\dagger}}
    The two columns of Ψ(2)\Psi^{(2)} are orthogonal with norms 2/3\sqrt{2/3} and 1/3\sqrt{1/3}; normalising them gives U(2)U^{(2)}.
  5. Step 5:
    A[2]0=(01120),A[2]1=(12000),A[3]0=(230),A[3]1=(013)A^{[2]0}=\begin{pmatrix}0&1\\\frac1{\sqrt2}&0\end{pmatrix},\qquad A^{[2]1}=\begin{pmatrix}\frac1{\sqrt2}&0\\0&0\end{pmatrix},\qquad A^{[3]0}=\begin{pmatrix}\sqrt{\frac23}\\0\end{pmatrix},\qquad A^{[3]1}=\begin{pmatrix}0\\\sqrt{\frac13}\end{pmatrix}
    A[2]s2A^{[2]s_2} collects the rows of U(2)U^{(2)} with that s2s_2; A[3]s3A^{[3]s_3} is column s3s_3 of C(2)=Σ(2)V(2)†C^{(2)}=\Sigma^{(2)}V^{(2)\dagger}.
  6. Step 6:
    ψ001=(1,0)A[2]0A[3]1=(0,1)(013)=13,ψ100=(0,1)A[2]0A[3]0=1223=13\psi_{001}=(1,0)A^{[2]0}A^{[3]1}=(0,1)\begin{pmatrix}0\\\sqrt{\frac13}\end{pmatrix}=\tfrac1{\sqrt3},\qquad\psi_{100}=(0,1)A^{[2]0}A^{[3]0}=\tfrac1{\sqrt2}\sqrt{\tfrac23}=\tfrac1{\sqrt3}
    Contract the product for two of the strings. Likewise ψ010=1223=13\psi_{010}=\tfrac1{\sqrt2}\sqrt{\tfrac23}=\tfrac1{\sqrt3}, and the five other strings give 00.
  7. Step 7:
    A[2]0†A[2]0+A[2]1†A[2]1=(12001)+(12000)=I2A^{[2]0\dagger}A^{[2]0}+A^{[2]1\dagger}A^{[2]1}=\begin{pmatrix}\frac12&0\\0&1\end{pmatrix}+\begin{pmatrix}\frac12&0\\0&0\end{pmatrix}=I_2
    The left-canonical condition at site 22, as guaranteed by the lemma; at site 11 it reads (1,0)T(1,0)+(0,1)T(0,1)=I2(1,0)^{\mathsf T}(1,0)+(0,1)^{\mathsf T}(0,1)=I_2.

Result

∣W3⟩=∑s1s2s3A[1]s1A[2]s2A[3]s3∣s1s2s3⟩,χ1=χ2=2\boxed{\lvert W_3\rangle=\sum_{s_1s_2s_3}A^{[1]s_1}A^{[2]s_2}A^{[3]s_3}\lvert s_1s_2s_3\rangle,\qquad\chi_1=\chi_2=2}
Derivation

A sequential circuit for the W state

  1. Step 1:
    ∣ej⟩:=Xj∣0n⟩,∣Wn⟩=1n∑j=0n−1∣ej⟩\lvert e_j\rangle:=X_j\lvert0^n\rangle,\qquad\lvert W_n\rangle=\frac1{\sqrt n}\sum_{j=0}^{n-1}\lvert e_j\rangle
    Notation: ∣ej⟩\lvert e_j\rangle is the basis state with a single 11 on qubit jj.
  2. Step 2:
    X(0)∣0n⟩=∣e0⟩,invariant before block q:  ∣ϕq⟩=1n∑j<q∣ej⟩+n−qn ∣eq⟩X(0)\lvert0^n\rangle=\lvert e_0\rangle,\qquad\text{invariant before block }q:\ \ \lvert\phi_q\rangle=\frac1{\sqrt n}\sum_{j<q}\lvert e_j\rangle+\sqrt{\frac{n-q}n}\,\lvert e_q\rangle
    For q=0q=0 the sum is empty and the invariant is ∣e0⟩\lvert e_0\rangle. Block qq consists of CRY(q,q+1,θq)\mathrm{CRY}(q,q+1,\theta_q) followed by CNOT(q+1,q)\mathrm{CNOT}(q+1,q).
  3. Step 3:
    CRY(q,q+1,θq)∣eq⟩=cos⁡θq2∣eq⟩+sin⁡θq2 Xq+1∣eq⟩\mathrm{CRY}(q,q+1,\theta_q)\lvert e_q\rangle=\cos\tfrac{\theta_q}2\lvert e_q\rangle+\sin\tfrac{\theta_q}2\,X_{q+1}\lvert e_q\rangle
    In ∣eq⟩\lvert e_q\rangle the control qubit qq is 11 and the target q+1q+1 is 00, and RY(θ)∣0⟩=cos⁡θ2∣0⟩+sin⁡θ2∣1⟩R_Y(\theta)\lvert0\rangle=\cos\tfrac\theta2\lvert0\rangle+\sin\tfrac\theta2\lvert1\rangle. The terms ∣ej⟩\lvert e_j\rangle with j<qj<q have control 00 and are unchanged.
  4. Step 4:
    CNOT(q+1,q) Xq+1∣eq⟩=∣eq+1⟩,CNOT(q+1,q)∣ej⟩=∣ej⟩ (j≤q)\mathrm{CNOT}(q+1,q)\,X_{q+1}\lvert e_q\rangle=\lvert e_{q+1}\rangle,\qquad\mathrm{CNOT}(q+1,q)\lvert e_j\rangle=\lvert e_j\rangle\ (j\le q)
    Qubits q,q+1q,q+1 read 1111 in the first state and the CNOT clears qubit qq; in all other terms qubit q+1q+1 is 00.
  5. Step 5:
    cos⁡θq2=1n−q ⇒ n−qncos⁡θq2=1n,n−qnsin⁡θq2=n−q−1n\cos\tfrac{\theta_q}2=\frac1{\sqrt{n-q}}\ \Rightarrow\ \sqrt{\tfrac{n-q}n}\cos\tfrac{\theta_q}2=\tfrac1{\sqrt n},\qquad\sqrt{\tfrac{n-q}n}\sin\tfrac{\theta_q}2=\sqrt{\tfrac{n-q-1}n}
    The choice of angle that leaves amplitude 1n\tfrac1{\sqrt n} on ∣eq⟩\lvert e_q\rangle; then sin⁡θq2=(n−q−1)/(n−q)\sin\tfrac{\theta_q}2=\sqrt{(n-q-1)/(n-q)}. The invariant holds for q+1q+1.
  6. Step 6:
    ∣ϕn−1⟩=1n∑j<n−1∣ej⟩+1n ∣en−1⟩=∣Wn⟩\lvert\phi_{n-1}\rangle=\frac1{\sqrt n}\sum_{j<n-1}\lvert e_j\rangle+\sqrt{\tfrac1n}\,\lvert e_{n-1}\rangle=\lvert W_n\rangle
    After the last block q=n−2q=n-2. The circuit has 2n−12n-1 gates.
  7. Step 7:
    n=3:X(0); CRY(0,1,2arccos⁡13); CNOT(1,0); CRY(1,2,π2); CNOT(2,1)n=3:\quad X(0);\ \mathrm{CRY}\big(0,1,2\arccos\tfrac1{\sqrt3}\big);\ \mathrm{CNOT}(1,0);\ \mathrm{CRY}\big(1,2,\tfrac\pi2\big);\ \mathrm{CNOT}(2,1)
    2arccos⁡13≈1.9106332\arccos\tfrac1{\sqrt3}\approx1.910633 and 2arccos⁡12=π22\arccos\tfrac1{\sqrt2}=\tfrac\pi2. The blocks act on (0,1)(0,1) and then (1,2)(1,2): one staircase layer, so the theorem (b) guarantees χ≤2\chi\le2 even though each block has operator-Schmidt rank 44.

Result

∏q=n−20[CNOT(q+1,q) CRY(q,q+1,2arccos⁡1n−q)] X(0) ∣0n⟩=∣Wn⟩\boxed{\prod_{q=n-2}^{0}\Big[\mathrm{CNOT}(q+1,q)\,\mathrm{CRY}\big(q,q+1,2\arccos\tfrac1{\sqrt{n-q}}\big)\Big]\,X(0)\,\lvert0^n\rangle=\lvert W_n\rangle}

Circuit · 3 qubits

Quantum circuit on 3 qubitsX on q0; RY(1.91) on q1 controlled by q0; X on q0 controlled by q1; RY(π/2) on q2 controlled by q1; X on q1 controlled by q2q0q1q2XRY(1.91)RY(π/2)

The five-gate staircase for ∣W3⟩\lvert W_3\rangle. The statevector shows the three amplitudes 13≈0.5774\tfrac1{\sqrt3}\approx0.5774 on ∣001⟩\lvert001\rangle, ∣010⟩\lvert010\rangle and ∣100⟩\lvert100\rangle. The lab accepts this circuit too; its hints follow a different route.

∣ψ⟩=13∣001⟩+13∣010⟩+13∣100⟩\lvert\psi\rangle = \tfrac{1}{\sqrt{3}}\lvert 001\rangle + \tfrac{1}{\sqrt{3}}\lvert 010\rangle + \tfrac{1}{\sqrt{3}}\lvert 100\rangle

The entanglement meter reports h(13)≈0.918h(\tfrac13)\approx0.918 bits for every single-qubit cut. The default inspector below analyses ∣W3⟩\lvert W_3\rangle: Schmidt values (0.8165,0.5774)(0.8165,0.5774) at both cuts, χ=(2,2)\chi=(2,2) and S=(0.9183,0.9183)S=(0.9183,0.9183), each strictly below log⁡2χ=1\log_2\chi=1.

Quick check

What is the entanglement entropy, in bits, of one qubit of the four-qubit W state ∣W4⟩=12(∣0001⟩+∣0010⟩+∣0100⟩+∣1000⟩)\lvert W_4\rangle=\tfrac12(\lvert0001\rangle+\lvert0010\rangle+\lvert0100\rangle+\lvert1000\rangle)?

tolerance ±0.001

The TypeScript cell runs two preparations of ∣W3⟩\lvert W_3\rangle and one of GHZ, and computes the Schmidt values per cut from the eigenvalues of the reduced state.

TypeScriptrunnable
import { eigh, reducedStateFromPure, runStatevector } from '@/lib/quantum-simulator';

type Op = { kind: 'gate'; gate: string; targets: number[]; params?: number[] };
const g = (gate: string, targets: number[], ...params: number[]): Op =>
  params.length > 0 ? { kind: 'gate', gate, targets, params } : { kind: 'gate', gate, targets };

// Two preparations of |W3> = (|001> + |010> + |100>)/sqrt(3) and one of GHZ3, qubit 0 = most significant bit.
const circuits: [string, Op[]][] = [
  ['W3 staircase', [g('X', [0]), g('CRY', [0, 1], 2 * Math.acos(1 / Math.sqrt(3))), g('CNOT', [1, 0]),
    g('CRY', [1, 2], Math.PI / 2), g('CNOT', [2, 1])]],
  ['W3 lab circuit', [g('RY', [0], 2 * Math.asin(1 / Math.sqrt(3))), g('X', [0]), g('CRY', [0, 1], Math.PI / 2),
    g('X', [0]), g('CNOT', [0, 2]), g('CNOT', [1, 2]), g('X', [2])]],
  ['GHZ3', [g('H', [0]), g('CNOT', [0, 1]), g('CNOT', [1, 2])]],
];

// Schmidt values across cut k (qubits 0..k-1 | k..n-1): square roots of the nonzero eigenvalues of the
// reduced state of the smaller side, in decreasing order.
function schmidtValues(state: ReturnType<typeof runStatevector>, n: number, k: number): number[] {
  const keep = k <= n - k ? Array.from({ length: k }, (_, j) => j) : Array.from({ length: n - k }, (_, j) => k + j);
  const { values } = eigh(reducedStateFromPure(state, keep).toMatrix());
  return Array.from(values).filter((p) => p > 1e-12).map((p) => Math.sqrt(p)).sort((a, b) => b - a);
}

for (const [name, ops] of circuits) {
  const state = runStatevector({ version: 1, numQubits: 3, numClbits: 0, ops });
  for (const k of [1, 2]) {
    const lam = schmidtValues(state, 3, k);
    const S = -lam.reduce((acc, l) => acc + l * l * Math.log2(l * l), 0);
    console.log(name + ', cut ' + k + ': lambda = [' + lam.map((l) => l.toFixed(10)).join(', ') + ']  chi = ' + lam.length +
      '  S = ' + S.toFixed(10) + '  log2(chi) = ' + Math.log2(lam.length).toFixed(10));
  }
}
console.log('sqrt(2/3) = ' + Math.sqrt(2 / 3).toFixed(10) + ', sqrt(1/3) = ' + Math.sqrt(1 / 3).toFixed(10) +
  ', h(1/3) = log2(3) - 2/3 = ' + (Math.log2(3) - 2 / 3).toFixed(10));

Expected output

W3 staircase, cut 1: lambda = [0.8164965809, 0.5773502692]  chi = 2  S = 0.9182958341  log2(chi) = 1.0000000000
W3 staircase, cut 2: lambda = [0.8164965809, 0.5773502692]  chi = 2  S = 0.9182958341  log2(chi) = 1.0000000000
W3 lab circuit, cut 1: lambda = [0.8164965809, 0.5773502692]  chi = 2  S = 0.9182958341  log2(chi) = 1.0000000000
W3 lab circuit, cut 2: lambda = [0.8164965809, 0.5773502692]  chi = 2  S = 0.9182958341  log2(chi) = 1.0000000000
GHZ3, cut 1: lambda = [0.7071067812, 0.7071067812]  chi = 2  S = 1.0000000000  log2(chi) = 1.0000000000
GHZ3, cut 2: lambda = [0.7071067812, 0.7071067812]  chi = 2  S = 1.0000000000  log2(chi) = 1.0000000000
sqrt(2/3) = 0.8164965809, sqrt(1/3) = 0.5773502692, h(1/3) = log2(3) - 2/3 = 0.9182958341

MPS and tree classifiers#

Huggins, Patil, Mitchell, Whaley and Stoudenmire (2019) proposed classifiers whose circuits are tensor networks. In the MPS classifier the data is encoded into a product state ⨂j∣ϕ(xj)⟩\bigotimes_j\lvert\phi(x_j)\rangle, a staircase of trainable two-qubit unitaries moves along the chain, and one output qubit is measured. In the tree classifier unitaries act on pairs, one qubit of each pair is discarded, and the rest are paired again, a binary tree of depth log⁡2n\log_2n. They trained both on handwritten-digit discrimination and observed robustness to noise.

Proposition

A staircase circuit runs on two physical qubits

Consider a product input ∣c1⟩⊗⋯⊗∣cn⟩\lvert c_1\rangle\otimes\cdots\otimes\lvert c_n\rangle, one staircase layer G1,…,Gn−1G_1,\ldots,G_{n-1} (GkG_k on sites (k,k+1)(k,k+1), in this order), and a computational-basis measurement of every site, or of site nn only. With mid-circuit measurement and reset, the distribution of the outcomes can be produced on two physical qubits: the qubit carrying site kk is measured (or discarded) right after GkG_k and re-prepared in ∣ck+2⟩\lvert c_{k+2}\rangle before Gk+1G_{k+1}. With a bond of bb qubits (dimension 2b2^b) the same argument needs b+1b+1 physical qubits, independently of nn; Huggins et al. call such circuits qubit-efficient.

Proof (6 steps)
  1. Step 1:
    Gk′ acts on (k′,k′+1), k′>k ⇒ no gate after Gk touches site kG_{k'}\ \text{acts on }(k',k'+1),\ k'>k\ \Rightarrow\ \text{no gate after }G_k\text{ touches site }k
    The staircase order: all later gates act on sites ≥k+1\ge k+1.
  2. Step 2:
    (Pt⊗I)(I⊗W)=(I⊗W)(Pt⊗I),Pt=∣t⟩⟨t∣k(P_t\otimes I)(I\otimes W)=(I\otimes W)(P_t\otimes I),\qquad P_t=\lvert t\rangle\langle t\rvert_k
    A projector on site kk commutes with every operator WW acting on the other sites.
  3. Step 3:
    Pr⁡(t1,…,tn)=∥(⨂kPtk)Gn−1⋯G1∣c⟩∥2=∥PtnPtn−1Gn−1⋯Pt2G2Pt1G1∣c⟩∥2\Pr(t_1,\ldots,t_n)=\Big\lVert\Big(\bigotimes_kP_{t_k}\Big)G_{n-1}\cdots G_1\lvert c\rangle\Big\rVert^2=\Big\lVert P_{t_n}P_{t_{n-1}}G_{n-1}\cdots P_{t_2}G_2P_{t_1}G_1\lvert c\rangle\Big\rVert^2
    Born rule for the final measurement, then commute each PtkP_{t_k} backwards to just after GkG_k using the previous two steps. The second expression is the probability of the mid-circuit measurement record.
  4. Step 4:
    ∣c⟩=∣c1⟩⊗⋯⊗∣cn⟩,site k+2 is first touched by Gk+1\lvert c\rangle=\lvert c_1\rangle\otimes\cdots\otimes\lvert c_n\rangle,\qquad\text{site }k+2\text{ is first touched by }G_{k+1}
    Before Gk+1G_{k+1} site k+2k+2 is idle in ∣ck+2⟩\lvert c_{k+2}\rangle, so it may be prepared at that moment, on the qubit freed by measuring and resetting site kk.
  5. Step 5:
    live sites during Gk: {k, k+1} ⇒ 2 physical qubits\text{live sites during }G_k:\ \{k,\,k+1\}\ \Rightarrow\ 2\ \text{physical qubits}
    At any time exactly the two sites of the current gate are active.
  6. Step 6:
    Trk[(I⊗W)ρ(I⊗W)†]=W Trk[ρ] W†\mathrm{Tr}_k\big[(I\otimes W)\rho(I\otimes W)^\dagger\big]=W\,\mathrm{Tr}_k[\rho]\,W^\dagger
    If only site nn is measured, the other sites are discarded instead, and the partial trace over site kk commutes with operators on the remaining sites in the same way.

∎

Trainability. A circuit as expressive as a Haar-random unitary has exponentially small gradients (McClean et al. 2018). Tensor-network circuits restrict the expressivity in a structured way. Pesah et al. (2021) proved for quantum convolutional neural networks, tree-shaped circuits of depth O(log⁡n)O(\log n) with a cost on the final qubits, that the variance of every partial derivative decays at most polynomially in nn: no barren plateau. Their proof uses the logarithmic depth and the locality of the cost, as for the shallow local-cost circuits of Cerezo et al. (2021). A staircase has depth n−1n-1 and is not covered by these depth-based results. For MPS-type models, Liu, Yu, Duan and Deng (2022) proved that the cost decides: with a global loss on all nn output qubits the gradient variance vanishes exponentially in nn, with a local loss it decays at most polynomially. The structured ansatz is therefore necessary but not sufficient; the cost must be local too.

The NumPy cell implements the successive-SVD theorem: reshape C(k−1)C^{(k-1)} to (2χk−1,2n−k)(2\chi_{k-1},2^{n-k}), keep singular values above 10−1210^{-12}, store U(k)U^{(k)} as A[k]A^{[k]} with axes (αk−1,sk,αk)(\alpha_{k-1},s_k,\alpha_k), pass Σ(k)V(k)†\Sigma^{(k)}V^{(k)\dagger} on. It then checks reconstruction, the left-canonical condition and the entropy bound.

Pythonrunnable
import numpy as np

def mps(psi, n, tol=1e-12):
    # Successive SVDs. Qubit 0 (most significant bit) is site 1, so psi reshapes row-major.
    tensors, spectra = [], []
    C, chi = psi.reshape(1, -1), 1
    for k in range(1, n):
        M = C.reshape(chi * 2, -1)              # rows (alpha_{k-1}, s_k), columns (s_{k+1} ... s_n)
        U, S, Vh = np.linalg.svd(M, full_matrices=False)
        keep = S > tol
        U, S, Vh = U[:, keep], S[keep], Vh[keep]
        tensors.append(U.reshape(chi, 2, -1))   # A[k][alpha_{k-1}, s_k, alpha_k]
        spectra.append(S)
        chi = len(S)
        C = np.diag(S) @ Vh
    tensors.append(C.reshape(chi, 2, 1))
    return tensors, spectra

def contract(tensors):
    out = np.ones((1, 1))
    for A in tensors:
        out = np.einsum("ra,asb->rsb", out, A).reshape(-1, A.shape[2])
    return out.reshape(-1)

def entropy(S):
    p = S ** 2
    return float(-np.sum(p * np.log2(p)))

def report(name, psi, n):
    tensors, spectra = mps(psi, n)
    err = np.max(np.abs(contract(tensors) - psi))
    canon = all(np.allclose(np.einsum("asb,asc->bc", A.conj(), A), np.eye(A.shape[2])) for A in tensors[:-1])
    ent = [entropy(S) for S in spectra]
    bound = all(e <= np.log2(len(S)) + 1e-12 for e, S in zip(ent, spectra))
    print(f"{name}: bond dims {[len(S) for S in spectra]}, reconstruction error < 1e-12: {bool(err < 1e-12)}, "
          f"left-canonical: {canon}, S <= log2(chi): {bound}")
    return spectra, ent

w = np.zeros(8)
w[[1, 2, 4]] = 1 / np.sqrt(3)
spectra, ent = report("W3", w, 3)
for k, (S, e) in enumerate(zip(spectra, ent), start=1):
    print(f"  cut {k}: Schmidt values {' '.join(f'{v:.10f}' for v in S)}, S = {e:.10f}")

ghz = np.zeros(16)
ghz[[0, 15]] = 1 / np.sqrt(2)
_, ent = report("GHZ4", ghz, 4)
print(f"  entropies {' '.join(f'{e:.10f}' for e in ent)}")

plus = np.ones(16) / 4
report("|+>^4", plus, 4)

rng = np.random.default_rng(46)
haar = rng.normal(size=64) + 1j * rng.normal(size=64)
report("Haar n=6", haar / np.linalg.norm(haar), 6)

Expected output

W3: bond dims [2, 2], reconstruction error < 1e-12: True, left-canonical: True, S <= log2(chi): True
  cut 1: Schmidt values 0.8164965809 0.5773502692, S = 0.9182958341
  cut 2: Schmidt values 0.8164965809 0.5773502692, S = 0.9182958341
GHZ4: bond dims [2, 2, 2], reconstruction error < 1e-12: True, left-canonical: True, S <= log2(chi): True
  entropies 1.0000000000 1.0000000000 1.0000000000
|+>^4: bond dims [1, 1, 1], reconstruction error < 1e-12: True, left-canonical: True, S <= log2(chi): True
Haar n=6: bond dims [2, 4, 8, 4, 2], reconstruction error < 1e-12: True, left-canonical: True, S <= log2(chi): True

References

  1. U. Schollwöck, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326, 96–192 (2011).doi:10.1016/j.aop.2010.09.012
  2. G. Vidal, Efficient classical simulation of slightly entangled quantum computations, Physical Review Letters 91, 147902 (2003).doi:10.1103/PhysRevLett.91.147902
  3. W. Huggins, P. Patil, B. Mitchell, K. B. Whaley and E. M. Stoudenmire, Towards quantum machine learning with tensor networks, Quantum Science and Technology 4, 024001 (2019).doi:10.1088/2058-9565/aaea94
  4. C. Schön, E. Solano, F. Verstraete, J. I. Cirac and M. M. Wolf, Sequential generation of entangled multiqubit states, Physical Review Letters 95, 110503 (2005).doi:10.1103/PhysRevLett.95.110503
  5. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press (2010), §2.5 (Schmidt decomposition) and §11.3 (entropy).doi:10.1017/CBO9780511976667
  6. W. Dür, G. Vidal and J. I. Cirac, Three qubits can be entangled in two inequivalent ways, Physical Review A 62, 062314 (2000).doi:10.1103/PhysRevA.62.062314
  7. M. A. Nielsen, C. M. Dawson, J. L. Dodd, A. Gilchrist, D. Mortimer, T. J. Osborne, M. J. Bremner, A. W. Harrow and A. Hines, Quantum dynamics as a physical resource, Physical Review A 67, 052301 (2003).doi:10.1103/PhysRevA.67.052301
  8. A. Pesah, M. Cerezo, S. Wang, T. Volkoff, A. T. Sornborger and P. J. Coles, Absence of barren plateaus in quantum convolutional neural networks, Physical Review X 11, 041011 (2021).doi:10.1103/PhysRevX.11.041011
  9. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications 9, 4812 (2018).doi:10.1038/s41467-018-07090-4
  10. M. Cerezo, A. Sone, T. Volkoff, L. Cincio and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nature Communications 12, 1791 (2021).doi:10.1038/s41467-021-21728-w
  11. Z. Liu, L.-W. Yu, L.-M. Duan and D.-L. Deng, Presence and absence of barren plateaus in tensor-network based machine learning, Physical Review Letters 129, 270501 (2022).doi:10.1103/PhysRevLett.129.270501
  12. C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika 1, 211–218 (1936).doi:10.1007/BF02288367

Hands-on labs

  • Prepare the W state and measure its entanglement

    2 steps · auto-graded

    The three-qubit W state ∣W3⟩=13(∣001⟩+∣010⟩+∣100⟩)\lvert W_3\rangle=\tfrac1{\sqrt3}(\lvert001\rangle+\lvert010\rangle+\lvert100\rangle) has bond dimension χ=2\chi=2 at both cuts, so a short sequential circuit prepares it. In the first step you build such a circuit from RYR_Y, XX, controlled-RYR_Y and CNOT gates. In the second step you compute the entanglement entropy of one qubit from its Schmidt spectrum.

    Open lab