Method

Tensor networks: matrix product states, tensor trains and what they compute

A tensor network writes one huge array, such as the 2n2^{n} amplitudes of an nn-qubit state, as a chain or grid of small tensors joined by shared indices. When the data carries little entanglement or correlation, the small tensors stay small and the storage grows with nn instead of 2n2^{n}. That is why tensor networks reproduced IBM's 127-qubit kicked Ising experiment on classical hardware, and why the same idea appears as tensor trains in numerical finance and as compressed layers in neural networks.

Updated

At a glance

What it is
A large tensor written as a contraction of many small ones, drawn as a graph: tensors are nodes, shared indices are edges
The workhorse
The matrix product state (MPS), a chain of three-index tensors. Numerical mathematics calls the same object a tensor train
The one number that matters
The bond dimension χ\chi, the size of the shared indices. Storage for nn qubits is about 2nχ22n\chi^2 numbers instead of 2n2^{n}
When it works
When correlations are local or tree-like, so a small χ\chi captures the state: shallow circuits, 1D chains, smooth functions
When it fails
When entanglement grows across every cut, as in deep random circuits: χ\chi then has to grow exponentially and the advantage is gone
Is it quantum computing?
No. It runs on CPUs and GPUs. It is maths from quantum physics, which is why it is often called quantum-inspired

From one big tensor to a chain of small ones

A tensor is an array with several indices: a vector has one, a matrix two. The state of nn qubits is a tensor with nn indices of size 2, and so has 2n2^{n} entries. A function sampled on 2202^{20} grid points can be read the same way, as a tensor with 20 binary indices, one per bit of the grid position.

A matrix product state factors such a tensor into a chain. Each site gets a small tensor with one physical index (the qubit, or the bit) and two bond indices that connect it to its neighbours. Any tensor can be written this way exactly: split off the first index with a singular value decomposition (SVD), keep the remainder, repeat. The ranks that appear between neighbours are the bond dimensions. If the singular values drop off quickly, most of them can be discarded, and the chain becomes a compressed and controlled approximation[1].

Physicists named it MPS and built the density matrix renormalisation group (DMRG) on it. Oseledets introduced the same format to numerical analysis as the tensor train (TT), with the algorithm above as TT-SVD[2]. The two literatures use different words for one object: bond dimension and TT rank, site tensor and TT core. Beyond the chain there are trees, two-dimensional grids called projected entangled pair states (PEPS), and matrix product operators (MPO), which compress a matrix the way an MPS compresses a vector.

The bond dimension measures correlation. Across any cut of the chain, χ\chi bounds how much entanglement (for a quantum state) or how much mutual structure (for data) the two halves can share. Low χ\chi means little shared information and cheap storage. This is the whole bargain: tensor networks are exponentially cheaper exactly when the object has limited correlation, and no cheaper otherwise.

A tensor train in twenty lines of NumPy

Python
import numpy as np

# 2**20 samples of a smooth function, read as a tensor with 20 indices of size 2.
d = 20
x = np.linspace(0, 1, 2**d)
f = np.exp(-3 * x) * np.cos(8 * x)

# TT-SVD: split off one index at a time with a truncated SVD.
cores, rest, rank = [], f.reshape(1, -1), 1
for k in range(d - 1):
    u, s, vt = np.linalg.svd(rest.reshape(rank * 2, -1), full_matrices=False)
    keep = max(1, int(np.sum(s > 1e-10 * s[0])))
    cores.append(u[:, :keep].reshape(rank, 2, keep))
    rest, rank = s[:keep, None] * vt[:keep], keep
cores.append(rest.reshape(rank, 2, 1))

# Contract the train back into one vector and compare it with the original.
g = cores[0]
for core in cores[1:]:
    g = np.tensordot(g, core, axes=([-1], [0]))
g = g.reshape(-1)

print("largest bond dimension:", max(c.shape[2] for c in cores))  # 2
print("numbers stored:", sum(c.size for c in cores), "instead of", f.size)  # 152 instead of 1048576
print(f"largest error: {np.max(np.abs(g - f)):.0e}")  # 6e-15: rounding only

The function is a sum of two complex exponentials, and an exponential of a binary grid position factors into one 2-number tensor per bit, so every bond needs dimension 2. A noisy or non-smooth function would need larger bonds. The sample needs NumPy only.

Simulating quantum circuits with tensor networks

A quantum circuit is itself a tensor network: every gate is a small tensor, and computing an amplitude or an expectation value means contracting the whole graph. Markov and Shi showed that the cost of an exact contraction grows exponentially in the treewidth of the circuit's graph, not in the number of qubits, so shallow circuits with local gates are cheap[4]. Vidal's time-evolving block decimation (TEBD) keeps the state as an MPS while gates are applied, with a cost linear in the number of qubits and exponential in the entanglement[3]. A quantum computer can only outrun these methods on circuits whose entanglement grows with their size.

That is what made IBM's 2023 kicked Ising experiment a test case. It measured expectation values on a 127-qubit[5] Eagle processor with error mitigation, at circuit volumes the authors described as beyond brute-force classical computation, and reported that MPS and isometric 2D tensor network methods broke down in the strongly entangled regime[5]. Within four months, several groups reproduced it on classical hardware, three of them with tensor networks. Tindall, Fishman, Stoudenmire and Sels built a network with the heavy-hexagon geometry of the chip, contracted it approximately with belief propagation, and obtained results significantly more accurate and precise than the quantum processor[6]. Begušić, Gray and Chan ran several approximate methods orders of magnitude faster than the experiment[7], the most accurate with an effective bond dimension above 16,000,000[7] and an absolute error below 0.01[7]. Patra, Jahromi, Singh and Orús used graph-based PEPS and extended the simulation to the 433- and 1,121-qubit[8] layouts of IBM's Osprey and Condor processors, for evolution times about 8 times longer[8].

Read these results for what they are. They show that one celebrated experiment had correlations a well-chosen tensor network could follow, which Tindall et al. quantify as tree-like. They do not show that every circuit is classically easy: random circuits that build up entanglement across the chip still defeat every known tensor network, and the line between the two keeps moving as both sides improve. The quantum advantage page puts this case next to every other claim of a quantum computer beating classical ones, and how each has fared, and the quantum simulation guide follows the later simulation claims that tensor networks matched or narrowed.

Which tensor network for which job

StructureFitsWhere it shows up
MPS / tensor train1D chains, shallow circuits, smooth functions on a gridDMRG and TEBD in physics[3]; TT interpolation in finance; Aer's MPS simulator
PEPS (2D grid), graph PEPSTwo-dimensional lattices, chip layoutsThe Osprey and Condor simulations[8]
Lattice-shaped network, belief propagationCorrelations that look locally like a treeThe Eagle kicked Ising simulation[6]
Exact contraction with a good orderAny circuit; cost set by the treewidthCircuit simulators that contract the gate network[4]
MPO / TT layerA large weight matrixCompressed neural network layers[11][12]
MPS Born machineA probability distribution over bit stringsGenerative models and optimisers[13][14]

The same circuit on a state vector and on an MPS, with eigenkit

from eigenkit import Circuit, CircuitBuilder, Z

def chain(n):
    qc = CircuitBuilder(n_qubits=n)
    for q in range(n):
        qc.ry(0.3, q)
    for q in range(n - 1):
        qc.cnot(q, q + 1)
    for q in range(n):
        qc.ry(0.2, q)
    return qc

# 12 qubits: the dense state vector and the MPS core give the same value.
small, zz = chain(12), Z(0) * Z(11)
print(round(float(Circuit(small, observables=zz)([])), 6))                                # 0.527122
print(round(float(Circuit(small, observables=zz, provider="qiskit-aer-mps")([])), 6))  # 0.527122

# 60 qubits: 2**60 amplitudes do not fit in any memory; the MPS stays small.
big = chain(60)
print(round(float(Circuit(big, observables=Z(0) * Z(59), provider="qiskit-aer-mps")([])), 6))  # 0.010872

One layer of CNOTs builds little entanglement, so the MPS stays small at 60 qubits. Add layers and its bond dimension, and with it the run time, grows quickly. The MPS provider comes with pip install eigenkit[qiskit].

Tensor networks in machine learning and optimisation

The same factorisation works on models. Stoudenmire and Schwab used an MPS as the weight tensor of a classifier and reached less than 1%[10] test error on MNIST. Novikov and co-authors replaced the dense weight matrices of fully connected layers with tensor trains and reported compression of one layer by a factor of up to 200,000[11], and of a whole VGG network up to 7 times[11]. The survey by Sengupta, Adhikary, Oseledets and Biamonte covers the theory on both sides[9].

In finance, a tensor neural network puts an MPO layer in place of a dense layer. Patel et al., a team from Multiverse Computing and Crédit Agricole, trained it on the PDE of the Heston model and found it converged up to twelve times[12] faster than dense networks with the same parameter count. The option pricing page puts that result next to tensor-train interpolation and amplitude estimation.

An MPS can also be a generative model: squared amplitudes give a probability for every bit string, and sampling from an MPS is exact and cheap. Han et al. trained such a Born machine with a DMRG-like sweep[13], and it is the classical twin of the quantum circuit Born machine. Alcazar, Ghazi Vakili, Kalayci and Perdomo-Ortiz turned it into an optimiser, TN-GEO: fit an MPS Born machine to the best candidates found so far, sample new candidates from it, keep the good ones, repeat. On portfolio optimisation instances built from the S&P 500 and other indices they report TN-GEO among the best of the state-of-the-art solvers they compared[14]. That is the authors' assessment on their benchmark, with solvers they chose.

Questions

What is a tensor network in simple terms?

It is a way to store a very large array as many small arrays that are multiplied together along shared indices. Drawn as a graph, each small array is a node and each shared index is an edge. When the data has limited correlation, the small arrays stay small, and the storage grows with the number of indices instead of exponentially.

What is the difference between a matrix product state and a tensor train?

There is none in substance. Physicists call the chain of three-index tensors a matrix product state and its link sizes bond dimensions. Numerical mathematicians call the same object a tensor train and the link sizes TT ranks. The algorithms differ in emphasis: DMRG and TEBD in physics, TT-SVD, TT-cross and tensor completion in numerical analysis.

What is bond dimension?

It is the size of an index shared by two neighbouring tensors in the network. It caps how much correlation, or for a quantum state how much entanglement, can pass across that link. Storage and run time grow polynomially with it, so a small bond dimension is what makes a tensor network cheap.

Can tensor networks simulate any quantum computer?

No. They simulate circuits whose entanglement stays limited or whose correlations are tree-like, which covered IBM's 127-qubit kicked Ising experiment. Deep circuits that entangle every part of the chip need a bond dimension that grows exponentially, and then a tensor network is no cheaper than a full state vector.

Are tensor networks quantum computing?

No. They run on ordinary CPUs and GPUs. They come from quantum many-body physics, which is why methods built on them are called quantum-inspired, and they are the main classical benchmark that quantum hardware has to beat.

Are tensor networks used in machine learning?

Yes, in three ways: as the weights of a model (MPS classifiers), as compressed layers inside neural networks (tensor train and MPO layers), and as generative models (MPS Born machines). Each works when the data or the weights have the low-correlation structure that keeps bond dimensions small.

Sources

  1. R. Orús. A practical introduction to tensor networks: matrix product states and projected entangled pair states. Annals of Physics 349, 2014. arXiv:1306.2164.
  2. I. V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing 33(5), 2011.
  3. G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters 91, 2003. arXiv:quant-ph/0301063.
  4. I. L. Markov, Y. Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing 38(3), 2008. arXiv:quant-ph/0511069.
  5. Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt et al. Evidence for the utility of quantum computing before fault tolerance. Nature 618, 2023.
  6. J. Tindall, M. Fishman, E. M. Stoudenmire, D. Sels. Efficient tensor network simulation of IBM's Eagle kicked Ising experiment. PRX Quantum 5, 010308, 2024. arXiv:2306.14887.
  7. T. Begušić, J. Gray, G. K.-L. Chan. Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance. Science Advances 10, eadk4321, 2024. arXiv:2308.05077.
  8. S. Patra, S. S. Jahromi, S. Singh, R. Orús. Efficient tensor network simulation of IBM's largest quantum processors. Physical Review Research 6, 013326, 2024. arXiv:2309.15642.
  9. R. Sengupta, S. Adhikary, I. Oseledets, J. Biamonte. Tensor networks in machine learning. European Mathematical Society Magazine 126, 2022. arXiv:2207.02851.
  10. E. M. Stoudenmire, D. J. Schwab. Supervised learning with quantum-inspired tensor networks. Advances in Neural Information Processing Systems 29, 2016. arXiv:1605.05775.
  11. A. Novikov, D. Podoprikhin, A. Osokin, D. Vetrov. Tensorizing neural networks. Advances in Neural Information Processing Systems 28, 2015. arXiv:1509.06569.
  12. R. G. Patel, C.-W. Hsing, S. Sahin, S. Palmer, S. S. Jahromi et al. Quantum-inspired tensor neural networks for option pricing. arXiv preprint, 2022. arXiv:2212.14076.
  13. Z.-Y. Han, J. Wang, H. Fan, L. Wang, P. Zhang. Unsupervised generative modeling using matrix product states. Physical Review X 8, 031012, 2018. arXiv:1709.01662.
  14. J. Alcazar, M. Ghazi Vakili, C. B. Kalayci, A. Perdomo-Ortiz. Enhancing combinatorial optimization with classical and quantum generative models. Nature Communications 15, 2761, 2024. arXiv:2101.06250.

Run it yourself with eigenkit

eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.

$ pip install eigenkit