Simple Algorithm
Quantum Computing · Rydberg State · 32 min

Tensor Networks & Matrix Product States

When entanglement is low, the exponential wall disappears.

A generic 100-qubit state needs 21002^{100} amplitudes, yet DMRG routinely finds ground states of long spin chains to many digits on an ordinary workstation. The reason is entanglement: when every cut through a state is only weakly entangled, the exponential wall collapses into a chain of small matrices.

What you’ll learn

  • Define matrix product states and bond dimension, and count their parameters.
  • Prove that every state is an MPS with bond dimension equal to the Schmidt rank across each cut, via successive SVDs.
  • State and prove the truncation bound ∥ψ−ψD∥2≤2∑kεk(D)\norm{\psi-\psi_D}^2\le2\sum_k\varepsilon_k(D).
  • Explain area laws and why they make gapped 1D ground states efficiently representable, while volume-law states are not.

Matrix product states

Label the sites 1,…,n1,\dots,n from left to right, each with local dimension dd, and write every amplitude as a product of matrices, one per site:

ψs1s2⋯sn=A1s1A2s2⋯Ansn.\psi_{s_1s_2\cdots s_n} = A_1^{s_1}A_2^{s_2}\cdots A_n^{s_n}.

Here AksA_k^{s} is a χk−1×χk\chi_{k-1}\times\chi_k matrix for each value ss of site kk, and χ0=χn=1\chi_0 = \chi_n = 1, so the product is a number. The χk\chi_k are the bond dimensions and χ=max⁡kχk\chi = \max_k\chi_k. Storage drops from dnd^n to O(ndχ2)\order{nd\chi^2} numbers.

StateBond dimensionMatrices
Product ∣a1⟩⋯∣an⟩\ket{a_1}\cdots\ket{a_n}11Aks=⟨s∣ak⟩A_k^{s} = \braket{s|a_k}, just numbers
GHZ, 12(∣0⋯0⟩+∣1⋯1⟩)\tfrac{1}{\sqrt2}(\ket{0\cdots0}+\ket{1\cdots1})22bulk A0=diag⁡(1,0)A^0 = \diag(1,0), A1=diag⁡(0,1)A^1 = \diag(0,1); ends A1s=12esTA_1^{s} = \tfrac{1}{\sqrt2}e_s^{T}, Ans=esA_n^{s} = e_s
W, 1n∑k∣0⋯1k⋯0⟩\tfrac{1}{\sqrt n}\sum_k\ket{0\cdots1_k\cdots0}22bulk A0=IA^0 = I, A1=(0100)A^1 = \begin{pmatrix}0&1\\0&0\end{pmatrix}; ends A1s=1ne0TAsA_1^{s} = \tfrac{1}{\sqrt n}e_0^{T}A^{s}, Ans=Ase1A_n^{s} = A^{s}e_1
AKLT spin-1 chain ground state22each spin 1 is a projected pair of virtual spins ½ in singlets with its neighbors
Generic stateup to d⌊n/2⌋d^{\lfloor n/2\rfloor}no structure to exploit
In the W matrices, A1A^1 is nilpotent ((A1)2=0(A^1)^2 = 0), which forbids two excitations; the boundary vectors forbid zero.

Two facts make MPS practical. The norm and the expectation value of any local operator can be computed by contracting the chain from one end in O(ndχ3)\order{nd\chi^3} time. And there is a gauge freedom, Aks↦Xk−1−1AksXkA_k^{s}\mapsto X_{k-1}^{-1}A_k^{s}X_k, that leaves every amplitude unchanged; fixing it, for example to the left-canonical form ∑sAks†Aks=I\sum_sA_k^{s\dagger}A_k^{s} = I, turns the bond indices into orthonormal bases of the left blocks.

Predict before you look

A generic 20-qubit state is written exactly as an MPS. What is log⁡2\log_2 of the bond dimension needed at the middle cut?

Show the answer

10

The middle cut separates 10 qubits from 10 qubits, so the Schmidt rank can be as large as min⁡(210,210)=1024\min(2^{10},2^{10}) = 1024, and for a generic state it is. Exact MPS buy nothing for generic states: the savings come only from low entanglement.

Every state is an MPS

DerivationProof by successive SVDs
  1. ψs1,(s2⋯sn)=∑α1=1r1Us1α1(ΣV†)α1,(s2⋯sn)\psi_{s_1,(s_2\cdots s_n)} = \sum_{\alpha_1=1}^{r_1}U_{s_1\alpha_1}\big(\Sigma V^\dagger\big)_{\alpha_1,(s_2\cdots s_n)}

    Reshape the amplitudes into a d×dn−1d\times d^{n-1} matrix (site 1 against the rest) and take its singular value decomposition:

  2. (ΣV†)(α1s2),(s3⋯sn)=∑α2U(α1s2),α2′(Σ′V′†)α2,(s3⋯sn)\big(\Sigma V^\dagger\big)_{(\alpha_1s_2),(s_3\cdots s_n)} = \sum_{\alpha_2}U'_{(\alpha_1s_2),\alpha_2}\big(\Sigma'V'^\dagger\big)_{\alpha_2,(s_3\cdots s_n)}

    Set A1s1=Us1,:A_1^{s_1} = U_{s_1,:}, a 1×r11\times r_1 row. Regroup the remainder ΣV†\Sigma V^\dagger as an (r1d)×dn−2(r_1d)\times d^{n-2} matrix and decompose again:

  3. ψs1⋯sn=A1s1A2s2⋯Ansn,∑sAks†Aks=I\psi_{s_1\cdots s_n} = A_1^{s_1}A_2^{s_2}\cdots A_n^{s_n},\qquad \sum_sA_k^{s\dagger}A_k^{s} = I

    Set (A2s2)α1α2=U(α1s2),α2′(A_2^{s_2})_{\alpha_1\alpha_2} = U'_{(\alpha_1s_2),\alpha_2} and continue to the right end. Each UU has orthonormal columns, so the result is in left-canonical form:

  4. ∣ψ⟩=∑α=1rk∣Lα⟩⊗∣R~α⟩\ket\psi = \sum_{\alpha=1}^{r_k}\ket{L_\alpha}\otimes\ket{\tilde R_\alpha}

    Bond kk has the right size: left-canonical form makes the left-block vectors ∣Lα⟩=∑(A1s1⋯Aksk)α∣s1⋯sk⟩\ket{L_\alpha} = \sum(A_1^{s_1}\cdots A_k^{s_k})_{\alpha}\ket{s_1\cdots s_k} orthonormal. So the matrix decomposed at step kk is the coefficient matrix of ∣ψ⟩\ket\psi across cut kk in an orthonormal basis, its singular values are the Schmidt coefficients, and its rank is rkr_k.

  5. Minimality: an MPS with bond dimension χk\chi_k writes ∣ψ⟩=∑α=1χk∣Lα⟩∣Rα⟩\ket\psi = \sum_{\alpha=1}^{\chi_k}\ket{L_\alpha}\ket{R_\alpha} across cut kk (contract everything to the left and to the right of the bond), so the Schmidt rank is at most χk\chi_k. A state of Schmidt rank rr has entanglement entropy at most log⁡2r\log_2r, which gives the entropy bound.

Truncation: what a small bond costs

Let λ1[k]≥λ2[k]≥⋯\lambda^{[k]}_1\ge\lambda^{[k]}_2\ge\cdots be the eigenvalues of the reduced state of sites 1..k1..k, that is, the squared Schmidt coefficients at cut kk, and define the discarded weight εk(D)=∑α>Dλα[k]\varepsilon_k(D) = \sum_{\alpha>D}\lambda^{[k]}_\alpha. For a single cut, the Eckart–Young theorem says truncating the SVD is optimal: the closest vector of Schmidt rank at most DD is at squared distance exactly εk(D)\varepsilon_k(D). For all cuts at once:

DerivationProof: nested truncations
  1. ψ(k)=Πk ψ(k−1)\psi^{(k)} = \Pi_k\,\psi^{(k-1)}

    Sweep left to right. At cut kk, let PkP_k project sites 1..k1..k onto the top-DD left Schmidt vectors of the current state, and set Πk=Pk⊗I\Pi_k = P_k\otimes I, with ψ(0)=ψ\psi^{(0)} = \psi:

  2. ∥ψ−Πn−1ψ∥2=∑k=1n−1∥(Πk−1−Πk)ψ∥2=∑k∥(I−Πk) ψ(k−1)∥2\norm{\psi-\Pi_{n-1}\psi}^2 = \sum_{k=1}^{n-1}\norm{(\Pi_{k-1}-\Pi_k)\psi}^2 = \sum_k\norm{(I-\Pi_k)\,\psi^{(k-1)}}^2

    Nesting: ψ(k)\psi^{(k)} lies in range(Pk)⊗Hk+1..n\mathrm{range}(P_k)\otimes\Hil_{k+1..n}, so its left Schmidt vectors at cut k+1k+1 lie in range(Pk)⊗Cd\mathrm{range}(P_k)\otimes\C^d, and Πk+1≤Πk\Pi_{k+1}\le\Pi_k. The projectors therefore commute, ψ(k)=Πkψ\psi^{(k)} = \Pi_k\psi, and the errors (Πk−1−Πk)ψ(\Pi_{k-1}-\Pi_k)\psi are mutually orthogonal:

  3. ∥ψ−Πn−1ψ∥2≤∑kεk(D)\norm{\psi-\Pi_{n-1}\psi}^2\le\sum_k\varepsilon_k(D)

    Each term is the weight that cut kk of ψ(k−1)\psi^{(k-1)} discards. Since ψ(k−1)=Πk−1ψ\psi^{(k-1)} = \Pi_{k-1}\psi and Πk−1\Pi_{k-1} is a contraction acting only on sites left of cut kk, the reduced state of sites k+1..nk+1..n can only decrease in operator order; by Weyl's monotonicity theorem each of its eigenvalues decreases, so its tail beyond DD is at most εk(D)\varepsilon_k(D):

  4. Every bond has dimension at most DD: cut kk is truncated at step kk, and each later truncation can equally be applied as a projection on the sites to the right of its own cut (a truncated Schmidt sum can be produced from either side), which cannot raise the Schmidt rank at cut kk.

  5. ∥ψ−ψ^D∥2=2(1−1−δ)≤2δ≤2∑kεk(D)\norm{\psi-\hat\psi_D}^2 = 2\big(1-\sqrt{1-\delta}\big)\le2\delta\le2\sum_k\varepsilon_k(D)

    Normalize. ψD=Πn−1ψ\psi_D = \Pi_{n-1}\psi is a projection of ψ\psi, so ⟨ψ∣ψD⟩=∥ψD∥2=1−δ\braket{\psi|\psi_D} = \norm{\psi_D}^2 = 1-\delta with δ≤∑kεk\delta\le\sum_k\varepsilon_k, and for ψ^D=ψD/∥ψD∥\hat\psi_D = \psi_D/\norm{\psi_D}:

The bound turns entanglement spectra into cost: if the Schmidt spectrum at every cut decays fast, a modest DD suffices for all n−1n-1 cuts at once. How fast is fast enough? Schuch, Wolf, Verstraete and Cirac (2008) showed that even a logarithmically growing von Neumann entropy does not by itself guarantee an efficient MPS approximation, whereas a similar bound on a Rényi entropy SαS_\alpha with α<1\alpha<1 does.

Check your understanding

A circuit on a chain starts from a product state and applies gg CNOTs across the cut between sites kk and k+1k+1, plus any gates that act entirely on one side of that cut. Ignoring the cap min⁡(2k,2n−k)\min(2^k,2^{n-k}), what is the largest possible Schmidt rank across the cut?

  1. g+1g+1
  2. 2g2^g
  3. 4g4^g
  4. 22
Show the answer

B. 2g2^g

CNOT=∣0⟩ ⁣⟨0∣⊗I+∣1⟩ ⁣⟨1∣⊗X\mathrm{CNOT} = \dyad0\otimes I+\dyad1\otimes X is a sum of two products across the cut (operator Schmidt rank 2), so each application at most doubles the Schmidt rank, and gates on one side do not change it. Hence r≤2gr\le2^g, attained by building gg Bell pairs across the cut. A general two-qubit gate has operator Schmidt rank up to 4, giving 4g4^g. This is why shallow 1D circuits are cheap to simulate with MPS.

Area laws: why low entanglement is common

For which states are the εk(D)\varepsilon_k(D) small? Ground states of local Hamiltonians typically obey an area law: the entanglement entropy of a region scales with the size of its boundary, not its volume.

SettingBlock entropy S(ℓ)S(\ell)Consequence
Gapped 1D local HamiltonianO(1)\order{1}, independent of ℓ\ell and nn (Hastings 2007)MPS with poly⁡(n)\poly(n) bond dimension suffice; a provably polynomial-time algorithm exists (Landau, Vazirani & Vidick 2015)
Critical 1D chain (CFT with central charge cc)c3log⁡ℓ+O(1)\tfrac{c}{3}\log\ell+\order{1} for a block in an infinite chain (Calabrese & Cardy 2004)bond dimension must grow polynomially with ℓ\ell; DMRG still works well
Gapped 2D, L×LL\times L regionO(L)\order{L} (expected; proved only in special cases)MPS need χ=eO(L)\chi = e^{\order{L}}; PEPS are natural, but exact contraction is #P-hard in general
Random states, long-time quench dynamics≈ℓlog⁡2d\approx\ell\log_2d (volume law; Page 1993)no efficient MPS: bond dimension exponential in ℓ\ell, or in time tt

Area laws explain why DMRG (White 1992), which variationally optimizes over MPS, is so accurate in 1D. Circuits fit the same picture: a depth-tt circuit of nearest-neighbor gates on a chain crosses each cut with at most tt gates, so it outputs an MPS with χ≤4t\chi\le4^{t}, efficiently simulable at shallow depth (Vidal 2003). Deep generic circuits produce volume-law states and defeat MPS.

Key takeaways

  • An MPS writes amplitudes as products of χk−1×χk\chi_{k-1}\times\chi_k matrices: O(ndχ2)\order{nd\chi^2} parameters instead of dnd^n.
  • Successive SVDs give an exact MPS whose bond dimensions equal the Schmidt ranks, which is optimal; the entanglement entropy across a bond is at most log⁡2χ\log_2\chi.
  • Truncation error is controlled by discarded Schmidt weight: ∥ψ−ψD∥2≤2∑kεk(D)\norm{\psi-\psi_D}^2\le2\sum_k\varepsilon_k(D).
  • Area laws (S=O(1)S = \order1 for gapped 1D ground states) explain the success of MPS and DMRG in 1D; volume-law states from random states, long-time dynamics or deep circuits remain hard.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

An MPS on nn qubits with bond dimension χ\chi stores how many numbers, up to constant factors?

  1. O(χn)\order{\chi^n}
  2. O(nχ)\order{n\chi}
  3. O(nχ2)\order{n\chi^2}
  4. O(2nχ)\order{2^n\chi}
Show the answer

C. O(nχ2)\order{n\chi^2}

nn sites, each with d=2d = 2 matrices of χ2\chi^2 entries: O(nχ2)\order{n\chi^2}, linear in nn.

Question 2

Across one cut, a state has Schmidt rank rr. What is the minimal MPS bond dimension on that bond?

  1. ⌈log⁡2r⌉\lceil\log_2r\rceil
  2. rr
  3. r2r^2
  4. 2r2^r
Show the answer

B. rr

An MPS bond of dimension χ\chi writes the state as a sum of χ\chi products across the cut, so χ≥r\chi\ge r; successive SVDs achieve χ=r\chi = r.

Question 3

For the ground state of a gapped local Hamiltonian on a long chain, the entanglement entropy of a block of ℓ\ell consecutive sites (with 1≪ℓ≪n1\ll\ell\ll n):

  1. is bounded by a constant independent of ℓ\ell
  2. grows like ℓ\ell
  3. grows like log⁡ℓ\log\ell
  4. grows like ℓ\sqrt\ell
Show the answer

A. is bounded by a constant independent of ℓ\ell

This is Hastings' 1D area law: the boundary of a 1D block is two points, so the entropy is O(1)\order{1}. Logarithmic growth is the signature of a gapless (critical) chain.

Question 4

Truncating every bond to DD discards Schmidt weight εk(D)\varepsilon_k(D) at each of the n−1n-1 cuts. Which bound holds for the best normalized MPS approximation of bond dimension DD?

  1. ∥ψ−ψD∥2≤max⁡kεk(D)\norm{\psi-\psi_D}^2\le\max_k\varepsilon_k(D)
  2. ∥ψ−ψD∥≤∏kεk(D)\norm{\psi-\psi_D}\le\prod_k\varepsilon_k(D)
  3. No bound is possible without knowing the Hamiltonian
  4. ∥ψ−ψD∥2≤2∑kεk(D)\norm{\psi-\psi_D}^2\le2\sum_k\varepsilon_k(D)
Show the answer

D. ∥ψ−ψD∥2≤2∑kεk(D)\norm{\psi-\psi_D}^2\le2\sum_k\varepsilon_k(D)

The Verstraete–Cirac bound: errors from different cuts add (nested truncations make them orthogonal), and normalizing costs at most a factor 2.

Further reading

  • G. Vidal, "Efficient classical simulation of slightly entangled quantum computations", Phys. Rev. Lett. 91, 147902 (2003).
  • F. Verstraete & J. I. Cirac, "Matrix product states represent ground states faithfully", Phys. Rev. B 73, 094423 (2006).
  • M. B. Hastings, "An area law for one-dimensional quantum systems", J. Stat. Mech. P08024 (2007).
  • U. Schollwöck, "The density-matrix renormalization group in the age of matrix product states", Ann. Phys. 326, 96 (2011).
  • J. Eisert, M. Cramer & M. B. Plenio, "Colloquium: Area laws for the entanglement entropy", Rev. Mod. Phys. 82, 277 (2010).