Matrix Product States

A matrix product state (MPS) rewrites the $2^n$ amplitudes of an $n$ -qubit state as a product of small matrices, one factor per qubit. It is the one-dimensional workhorse of tensor networks, and almost every algorithm in this module operates on it.

From one big tensor to a chain of small ones

Write a general $n$ -qubit state by listing its amplitudes,

|\psi\rangle = \sum_{s_0 s_1 \cdots s_{n-1}} c_{s_0 s_1 \cdots s_{n-1}}\, |s_0 s_1 \cdots s_{n-1}\rangle, \qquad s_k \in \{0,1\}.

The object $c_{s_0 \cdots s_{n-1}}$ is a single tensor with $n$ indices and $2^n$ entries. The MPS idea is to factor this tensor into a contracted product of three-index tensors $A^{[k]}$ , one for each site:

c_{s_0 s_1 \cdots s_{n-1}} = \sum_{\alpha_1,\dots,\alpha_{n-1}} A^{[0]\,s_0}_{\;\alpha_1}\, A^{[1]\,s_1}_{\alpha_1 \alpha_2}\, \cdots\, A^{[n-1]\,s_{n-1}}_{\alpha_{n-1}} .

Each $A^{[k]}$ carries one physical index $s_k$ (the qubit's $0/1$ value) and up to two bond indices $\alpha_k, \alpha_{k+1}$ that link it to its neighbours. Reading the formula, you pick a value for every physical index, multiply the corresponding matrices along the chain, and the result is a single amplitude. The bond indices are summed over — they are internal plumbing, never observed.

Math you'll use here: the singular value decomposition. Any matrix $M$ (rectangular, not necessarily square) factors as

M = U S V^\dagger,

where $U$ and $V$ have orthonormal columns ( $U^\dagger U = I$ , $V^\dagger V = I$ ; they are unitary when square) and $S$ is a non-negative diagonal matrix whose entries $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$ are the singular values. The number of non-zero $\sigma_k$ is the rank of $M$ . This differs from the eigendecomposition $M = P \Lambda P^{-1}$ : the SVD applies to every matrix, uses two orthonormal bases instead of one, and yields non-negative real $\sigma_k$ rather than possibly complex eigenvalues. The link to entanglement is exact: if $M$ is the amplitude matrix of a bipartition, the $\sigma_k$ are the Schmidt coefficients of that cut. Below we apply $M = U S V^\dagger$ repeatedly to peel a state into its MPS, reading the bond dimension off the count of non-zero singular values.

Where the matrices come from: iterated SVD

You construct an MPS by repeatedly applying the singular value decomposition (SVD). Reshape the amplitude tensor into a matrix $M$ that groups the first qubit against the rest, $M_{s_0,\,(s_1\cdots s_{n-1})}$ . The SVD writes

M = U S V^\dagger,

with $U$ holding the first site tensor $A^{[0]}$ , $S$ a diagonal matrix of non-negative singular values, and $S V^\dagger$ the remainder to be split further. Reshape that remainder, group off the next qubit, and SVD again. Repeating $n-1$ times peels the state into the chain of $A^{[k]}$ above. The procedure is exact: no approximation has yet been made.

A worked two-qubit example

Take the Bell state $|\Phi^+\rangle = \tfrac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ . Its amplitude matrix grouping qubit 0 against qubit 1 is

M = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}.

Its SVD is trivial: $U = V = I$ and $S = \mathrm{diag}(\tfrac{1}{\sqrt 2}, \tfrac{1}{\sqrt 2})$ . There are two non-zero singular values, so the bond between the qubits must carry dimension $2$ . By contrast the product state $|00\rangle$ has $M = \mathrm{diag}(1, 0)$ , a single non-zero singular value, so its bond dimension is $1$ . Entanglement is visible directly in the count of non-zero singular values.

Why this is efficient

If every bond index ranges over at most $\chi$ values, each site tensor holds at most $2\chi^2$ numbers, and the whole MPS stores about $n \cdot 2\chi^2$ numbers — linear in $n$ . For weakly entangled states $\chi$ stays small even as $n$ grows, which is precisely why MPS can represent the ground states of many one-dimensional systems on a laptop while the full state vector would need exponential memory. The cost of every operation on an MPS — overlaps, expectation values, applying gates — likewise scales polynomially in $n$ and $\chi$ , never in $2^n$ .

Canonical forms

In practice one keeps the MPS in a canonical form: the tensors to the left of a chosen bond are left-orthonormal and those to the right are right-orthonormal, with the singular values sitting on the bond between them. Canonical form makes the singular values directly meaningful, makes overlaps and expectation values cheap, and is what lets you truncate small singular values to control $\chi$ . We will lean on it when we simulate circuits with MPS later in the module.