Matrix product state

File:Matrix product state obc tikz.svg

For periodic boundary conditions,Penrose graphical notation (tensor diagram notation) of a matrix product state of five particles.

A matrix product state (MPS) is a representation of a quantum many-body state. It is at the core of the one of the most effective algorithms for solving one dimensional strongly correlated quantum systems – the density matrix renormalization group (DMRG) algorithm.

For a system of $N$ spins of dimension $d$, the general form of the MPS for periodic boundary conditions (PBS) can be written in the following form:

For open boundary conditions, Penrose graphical notation (tensor diagram notation) of a matrix product state of five particles.

$$|\mathrm{\Psi }⟩=\sum _{\{s\}}\mathrm{Tr}[A_1^{(s_1)}{A}_2^{(s_2)}\cdots A_N^{(s_N)}]|s_1{s}_2\dots s_N⟩.$$For open boundary conditions (OBC), $|\mathrm{\Psi }⟩$ takes the form

$|\mathrm{\Psi }⟩=\sum _{\{s\}}{A}_1^{(s_1)}{A}_2^{(s_2)}\cdots A_N^{(s_N)}|s_1{s}_2\dots s_N⟩.$

Here $A_i^{(s_i)}$ are the $D_i\times D_{i+1}$ matrices ($D$ is the dimension of the virtual subsystems) and $|s_i⟩$ are the single-site basis states. For periodic boundary conditions, we consider $D_{N+1}=D_1$, and for open boundary conditions $D_1=1$. The parameter $D$  is related to the entanglement between particles. In particular, if the state is a product state (i.e. not entangled at all), it can be described as a matrix product state with $D=1$. $\{s_i\}$ represents a $d$-dimensional local space on site $i=1,2,...,N$. For qubits, $s_i\in \{0,1\}$. For qudits (Template:Mvar-level systems), $s_i\in \{0,1,\dots ,d-1\}$.

For states that are translationally symmetric, we can choose: $$A_1^{(s)}=A_2^{(s)}=\cdots =A_N^{(s)}\equiv A^{(s)}.$$In general, every state can be written in the MPS form (with $D$ growing exponentially with the particle number Template:Mvar). Note that the MPS decomposition is not unique. MPS are practical when $D$ is small – for example, does not depend on the particle number. Except for a small number of specific cases (some mentioned in the section Examples), such a thing is not possible, though in many cases it serves as a good approximation.

For introductions see, and. In the context of finite automata see. For emphasis placed on the graphical reasoning of tensor networks, see the introduction.

Wave function as a Matrix Product State

For a system of $N$ lattice sites each of which has a $d$-dimensional Hilbert space, the completely general state can be written as

$|\mathrm{\Psi }⟩=\sum _{\{s\}}{\psi }_{s_1...s_N}|s_1\dots s_N⟩,$

where ${\psi }_{s_1...s_N}$ is a $d^N$-dimensional tensor. For example, the wave function of the system described by the Heisenberg model is defined by the $2^N$ dimensional tensor, whereas for the Hubbard model the rank is $4^N$.

The main idea of the MPS approach is to separate physical degrees of freedom of each site, so that the wave function can be rewritten as the product of $N$ matrices, where each matrix corresponds to one particular site. The whole procedure includes the series of reshaping and singular value decompositions (SVD).

There are three ways to represent wave function as an MPS: left-canonical decomposition, right-canonical decomposition, and mixed-canonical decomposition.

Left-Canonical Decomposition

The decomposition of the $d^N$-dimensional tensor starts with the separation of the very left index, i.e., the first index $s_1$, which describes physical degrees of freedom of the first site. It is performed by reshaping $|\mathrm{\Psi }⟩$ as follows

$|\mathrm{\Psi }⟩=\sum _{\{s\}}{\psi }_{s_1,(s_2...s_N)}|s_1\dots s_N⟩.$

In this notation, $s_1$ is treated as a row index, $(s_2\dots s_N)$ as a column index, and the coefficient ${\psi }_{s_1,(s_2...s_N)}$ is of dimension $(d\times d^{N-1})$. The SVD procedure yields

${\psi }_{s_1,(s_2...s_N)}=\sum _{{\alpha }_1}^{r_1}{U}_{s_1,{\alpha }_1}{D}_{{\alpha }_1,{\alpha }_1}(V^{†}{)}_{{\alpha }_1,(s_2...s_N)}=\sum _{{\alpha }_1}^{r_1}{U}_{s_1,{\alpha }_1}{\psi }_{{\alpha }_1,(s_2...s_N)}=\sum _{{\alpha }_1}^{r_1}{A}_{{\alpha }_1}^{s_1}{\psi }_{{\alpha }_1,(s_2...s_N)}.$

The separation of physical degrees of freedom of the first site.

In the relation above, matrices $D$ and $V^{†}$ are multiplied and form the matrix ${\psi }_{{\alpha }_1,(s_2...s_N)}$ and $r_1\le d$. $A_{{\alpha }_1}^{s_1}$ stores the information about the first lattice site. It was obtained by decomposing matrix $U$ into $d$ row vectors $A^{s_1}$ with entries $A_{{\alpha }_1}^{s_1}=U_{s_1,{\alpha }_1}$. So, the state vector takes the form

$|\mathrm{\Psi }⟩=\sum _{\{s\}}\sum _{{\alpha }_1}{A}_{{\alpha }_1}^{s_1}{\psi }_{{\alpha }_1,(s_2...s_N)}|s_1\dots s_N⟩.$

The separation of the second site is performed by grouping $s_2$ and ${\alpha }_1$, and representing ${\psi }_{{\alpha }_1,(s_2...s_N)}$ as a matrix ${\psi }_{({\alpha }_1{s}_2),(s_3...s_N)}$ of dimension $(r_{1}d\times d^{N-2})$. The subsequent SVD of ${\psi }_{({\alpha }_1{s}_2),(s_3...s_N)}$ can be performed as follows:

${\psi }_{({\alpha }_1{s}_2),(s_3...s_N)}=\sum _{{\alpha }_2}^{r_2}{U}_{({\alpha }_1{s}_2),{\alpha }_2}{D}_{{\alpha }_2,{\alpha }_2}(V^{†}{)}_{{\alpha }_2,(s_3...s_N)}=\sum _{{\alpha }_2}^{r_2}{A}_{{\alpha }_1,{\alpha }_2}^{s_2}{\psi }_{{\alpha }_2,(s_3...s_N)}$.

The separation of physical degrees of freedom for the first two sites.

Above we replace $U$ by a set of $d$ matrices of dimension $(r_1\times r_2)$ with entries $A_{{\alpha }_1,{\alpha }_2}^{s_2}=U_{({\alpha }_1{s}_2),{\alpha }_2}$. The dimension of ${\psi }_{{\alpha }_2,(s_3...s_N)}$ is $(r_2\times d^{N-2})$ with $r_2\le r_{1}d\le d^2$. Hence,

$|\mathrm{\Psi }⟩=\sum _{\{s\}}\sum _{{\alpha }_1}{A}_{{\alpha }_1}^{s_1}{\psi }_{({\alpha }_1{s}_2),(s_3...s_N)}|s_1\dots s_N⟩=\sum _{\{s\}}\sum _{{\alpha }_1,{\alpha }_2}{A}_{{\alpha }_1}^{s_1}{A}_{{\alpha }_1,{\alpha }_2}^{s_2}{\psi }_{{\alpha }_2,(s_3...s_N)}|s_1\dots s_N⟩.$

Following the steps described above, the state $|\mathrm{\Psi }⟩$ can be represented as a product of matrices

$|\mathrm{\Psi }⟩=\sum _{\{s\}}\sum _{{\alpha }_1,\dots ,{\alpha }_{N-1}}{A}_{{\alpha }_1}^{s_1}{A}_{{\alpha }_1,{\alpha }_2}^{s_2}\dots A_{{\alpha }_{N-2},{\alpha }_{N-1}}^{s_{N-1}}{A}_{{\alpha }_{N-1}}^{s_N}|s_1\dots s_N⟩.$

The maximal dimensions of the $A$-matrices take place in the case of the exact decomposition, i.e., assuming for simplicity that $N$ is even, $(1\times d),(d\times d^2),\dots ,(d^{N/2-1}\times d^{N/2}),(d^{N/2}\times d^{N/2-1}),\dots ,(d^2\times d),(d\times 1)$ going from the first to the last site. However, due to the exponential growth of the matrix dimensions in most of the cases it is impossible to perform the exact decomposition.

The dual MPS is defined by replacing each matrix $A$ with $A^{*}$:

$⟨\mathrm{\Psi }|=\sum _{\{s\}}\sum _{\alpha {\text{'}}_1,...,\alpha {\text{'}}_{N-1}}{A}_{\alpha {\text{'}}_1}^{*s{\text{'}}_1}{A}_{\alpha {\text{'}}_1,\alpha {\text{'}}_2}^{*s{\text{'}}_2}...A_{\alpha {\text{'}}_{N-2},\alpha {\text{'}}_{N-1}}^{*s{\text{'}}_{N-1}}{A}_{\alpha {\text{'}}_{N-1}}^{*s{\text{'}}_N}⟨s{\text{'}}_1...s{\text{'}}_N|.$

Note that each matrix $U$ in the SVD is a semi-unitary matrix with property $U^{†}U=I$. This leads to

${\delta }_{{\alpha }_i,{\alpha }_j}=\sum _{{\alpha }_{i-1}{s}_i}(U^{†}{)}_{{\alpha }_i,({\alpha }_{i-1}{s}_i)}{U}_{({\alpha }_{i-1}{s}_i),{\alpha }_j}=\sum _{{\alpha }_{i-1}{s}_i}(A^{s_i†}{)}_{{\alpha }_i,{\alpha }_{i-1}}{A}_{{\alpha }_{i-1},{\alpha }_j}^{s_i}=\sum _{s_i}(A^{s_i†}{A}^{s_i}{)}_{{\alpha }_i,{\alpha }_j}$.

To be more precise, $\sum _{s_i}{A}^{s_i†}{A}^{s_i}=I$. Since matrices are left-normalized, we call the composition left-canonical.

Right-Canonical Decomposition

Similarly, the decomposition can be started from the very right site. After the separation of the first index, the tensor ${\psi }_{s_1...s_N}$ transforms as follows:

${\psi }_{s_1...s_N}={\psi }_{(s_1...s_{N-1}),s_N}=\sum _{{\alpha }_{N-1}}{U}_{(s_1...s_{N-1}),{\alpha }_{N-1}}{D}_{{\alpha }_{N-1},{\alpha }_{N-1}}(V^{†}{)}_{{\alpha }_{N-1},s_N}=\sum _{{\alpha }_{N-1}}{\psi }_{(s_1...s_{N-1}),{\alpha }_{N-1}}{B}_{{\alpha }_{N-1}}^{s_N}$.

The matrix ${\psi }_{(s_1...s_{N-1}),{\alpha }_{N-1}}$ was obtained by multiplying matrices $U$ and $D$, and the reshaping of $(V^{†}{)}_{{\alpha }_{N-1},s_N}$ into $d$ column vectors forms $B_{{\alpha }_{N-1}}^{s_N}$. Performing the series of reshaping and SVD, the state vector takes the form

$|\mathrm{\Psi }⟩=\sum _{\{s\}}\sum _{{\alpha }_1,\dots ,{\alpha }_{N-1}}{B}_{{\alpha }_1}^{s_1}{B}_{{\alpha }_1,{\alpha }_2}^{s_2}\dots B_{{\alpha }_{N-2},{\alpha }_{N-1}}^{s_{N-1}}{B}_{{\alpha }_{N-1}}^{s_N}|s_1\dots s_N⟩.$

Since each matrix $V$ in the SVD is a semi-unitary matrix with property $V^{†}V=I$, the $B$-matrices are right-normalized and obey $\sum _{s_i}{B}^{s_i}{B}^{s_i†}=I$. Hence, the decomposition is called right-canonical.

Mixed-Canonical Decomposition

The decomposition performs from both the right and from the left. Assuming that the left-canonical decomposition was performed for the first n sites, ${\psi }_{s_1...s_N}$ can be rewritten as

${\psi }_{s_1...s_N}=\sum _{{\alpha }_1,\dots ,{\alpha }_n}{A}_{{\alpha }_1}^{s_1}{A}_{{\alpha }_1,{\alpha }_2}^{s_2}\dots A_{{\alpha }_{n-1},{\alpha }_n}^{s_n}{D}_{{\alpha }_n,{\alpha }_n}(V^{†}{)}_{{\alpha }_n,(s_{n+1}...s_N)}$.

MPS representation obtained by the mixed-canonical decomposition.

In the next step, we reshape $(V^{†}{)}_{{\alpha }_n,(s_{n+1}...s_N)}$ as ${\psi }_{({\alpha }_n{s}_{n+1}...s_{n-1}),s_N}$ and proceed with the series of reshaping and SVD from the right up to site $s_{n+1}$:

$\begin{array}{ccc}{\psi }_{({\alpha }_n{s}_{n+1}...s_{n-1}),s_N}& =& \sum _{{\alpha }_{n+1}...{\alpha }_N}{U}_{({\alpha }_n{s}_{n+1}),{\alpha }_{n+1}}{D}_{{\alpha }_{n+1},{\alpha }_{n+1}}{B}_{{\alpha }_{n+1},{\alpha }_{n+2}}^{s_{n+2}}\dots B_{{\alpha }_{N-2},{\alpha }_{N-1}}^{s_{N-1}}{B}_{{\alpha }_{N-1}}^{s_N}\\ & =& \sum _{{\alpha }_{n+1}...{\alpha }_N}{B}_{{\alpha }_n,{\alpha }_{n+1}}^{s_{n+1}}{B}_{{\alpha }_{n+1},{\alpha }_{n+2}}^{s_{n+2}}\dots B_{{\alpha }_{N-2},{\alpha }_{N-1}}^{s_{N-1}}{B}_{{\alpha }_{N-1}}^{s_N}\end{array}$.

As the result,

${\psi }_{s_1...s_N}=\sum _{{\alpha }_1,\dots ,{\alpha }_N}{A}_{{\alpha }_1}^{s_1}{A}_{{\alpha }_1,{\alpha }_2}^{s_2}\dots A_{{\alpha }_{n-1},{\alpha }_n}^{s_n}{D}_{{\alpha }_n,{\alpha }_n}{B}_{{\alpha }_n,{\alpha }_{n+1}}^{s_{n+1}}{B}_{{\alpha }_{n+1},{\alpha }_{n+2}}^{s_{n+2}}\dots B_{{\alpha }_{N-2},{\alpha }_{N-1}}^{s_{N-1}}{B}_{{\alpha }_{N-1}}^{s_N}$.

Examples

Greenberger–Horne–Zeilinger state

Greenberger–Horne–Zeilinger state, which for Template:Math particles can be written as superposition of Template:Math zeros and Template:Math ones

$|\mathrm{G}\mathrm{H}\mathrm{Z}⟩=\frac{|0{⟩}^{\otimes N}+|1{⟩}^{\otimes N}}{\sqrt{2}}$

can be expressed as a Matrix Product State, up to normalization, with

$A^{(0)}=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]A^{(1)}=\left[\begin{array}{cc}0& 0\\ 0& 1\end{array}\right],$

or equivalently, using notation from:

$A=\left[\begin{array}{cc}|0⟩& 0\\ 0& |1⟩\end{array}\right].$

This notation uses matrices with entries being state vectors (instead of complex numbers), and when multiplying matrices using tensor product for its entries (instead of product of two complex numbers). Such matrix is constructed as

$A\equiv |0⟩A^{(0)}+|1⟩A^{(1)}+\dots +|d-1⟩A^{(d-1)}.$

Note that tensor product is not commutative.

In this particular example, a product of two A matrices is:

$AA=\left[\begin{array}{cc}|00⟩& 0\\ 0& |11⟩\end{array}\right].$

W state

W state, i.e., the superposition of all the computational basis states of Hamming weight one.

$|\mathrm{W}⟩=\frac{1}{\sqrt{3}}(|001⟩+|010⟩+|100⟩)$

Even though the state is permutation-symmetric, its simplest MPS representation is not. For example:

$A_1=\left[\begin{array}{cc}|0⟩& 0\\ |0⟩& |1⟩\end{array}\right]A_2=\left[\begin{array}{cc}|0⟩& |1⟩\\ 0& |0⟩\end{array}\right]A_3=\left[\begin{array}{cc}|1⟩& 0\\ 0& |0⟩\end{array}\right].$

AKLT model

The AKLT ground state wavefunction, which is the historical example of MPS approach, corresponds to the choice

$A^{+}=\sqrt{\frac{2}{3}}{\sigma }^{+}=\left[\begin{array}{cc}0& \sqrt{2/3}\\ 0& 0\end{array}\right]$

$A^0=\frac{-1}{\sqrt{3}}{\sigma }^z=\left[\begin{array}{cc}-1/\sqrt{3}& 0\\ 0& 1/\sqrt{3}\end{array}\right]$

$A^{-}=-\sqrt{\frac{2}{3}}{\sigma }^{-}=\left[\begin{array}{cc}0& 0\\ -\sqrt{2/3}& 0\end{array}\right]$

where the $\sigma \text{'s}$ are Pauli matrices, or

$A=\frac{1}{\sqrt{3}}\left[\begin{array}{cc}-|0⟩& \sqrt{2}|+⟩\\ -\sqrt{2}|-⟩& |0⟩\end{array}\right].$

Majumdar–Ghosh model

Majumdar–Ghosh ground state can be written as MPS with

$A=\left[\begin{array}{ccc}0& |\uparrow ⟩& |\downarrow ⟩\\ \frac{-1}{\sqrt{2}}|\downarrow ⟩& 0& 0\\ \frac{1}{\sqrt{2}}|\uparrow ⟩& 0& 0\end{array}\right].$

See also

• Density matrix renormalization group
• Variational method (quantum mechanics)
• Renormalization
• Markov chain
• Tensor network

External links

• Open-source review article focused on tensor network algorithms, applications, and software
• State of Matrix Product States – Physics Stack Exchange
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Tensor Networks in a Nutshell: An Introduction to Tensor Networks