Writing down a ground state

One spin takes two numbers to describe. Two spins take four, three take eight, and every spin you add doubles the list. Three hundred spins need about 10⁹⁰ numbers, more than there are atoms in the visible universe. People still simulate chains of thousands of spins on a laptop, because the states they care about live in a tiny and very particular corner of all possible states.

Cut it in half

Take a chain of spins and cut it between the fifth and the sixth. Any state of the whole chain can be written as a sum of terms, each one a state of the left half times a state of the right half, with a weight on each term. That is the Schmidt decomposition. If one term carries all the weight, the two halves are independent of each other. If the weight is spread over many terms, the halves are entangled, and the number of terms you have to keep is what costs memory.

Below is a real chain of ten spins. It is the transverse-field Ising model: neighbouring spins want to line up along Z, and a sideways field of strength h tries to turn every spin toward X. The bars are the weights of the Schmidt terms across the middle cut, on a log scale. For comparison, switch to a random state of the same ten spins.

H = −J Σ Z_iZ_i+1 − h Σ X_i

The number of terms you keep at a cut is the bond dimension, written χ. Keeping the χ largest terms is the best any χ-term approximation can do, and the error has a clean form: the squared distance between the true state and the truncated one is exactly the total weight you threw away. The weight-kept readout is the overlap of the truncated, renormalised state with the original.

The area law

For a random state the entanglement across a cut grows with the size of the smaller side, so it scales like the volume of the region. That is why a random state cannot be compressed. Ground states of local Hamiltonians with a spectral gap behave differently. Hastings proved in 2007 that in one dimension their entanglement across any cut is bounded by a constant that depends on the gap and the local dimension, and not on the length of the chain. In higher dimensions the expectation is that entanglement scales with the boundary of the region, which is where the name area law comes from.

At a critical point the gap closes and Hastings's bound no longer applies. For a critical chain the entanglement of a block grows like the logarithm of its length, with a prefactor set by the central charge c of the conformal field theory that describes the critical point. For half of an open chain of length L it goes as (c/6)·log L. The Ising chain at h = J has c = 1/2, so the growth is slow, but it does not stop.

Matrix product states

If every cut in the chain needs only χ terms, the whole state can be written as a product of small matrices, one per site. Each spin gets a tensor with one physical index of size 2 and two bond indices of size at most χ, and multiplying the matrices along the chain gives back any amplitude you ask for. That is a matrix product state. It takes about 2Nχ² numbers, which grows linearly with the length of the chain instead of exponentially.

Hastings's area-law paper already contains the payoff: ground states of gapped chains can be approximated by matrix product states whose bond dimension grows only polynomially with the length of the chain. White's density matrix renormalization group, DMRG, published in 1992, is in hindsight a variational search over exactly this family, and it remains the best general tool for one-dimensional quantum systems. For twenty years its success was an empirical fact. Landau, Vazirani and Vidick made it a theorem with the first provably polynomial-time algorithm for ground states of gapped one-dimensional Hamiltonians.

Where it stops being easy

The gap is doing real work in all of this. Without it, one dimension is already as hard as anything: Aharonov, Gottesman, Irani and Kempe showed that estimating the ground energy of a local Hamiltonian on a line is QMA-complete. And even when a good MPS is known to exist, finding it can be hard in the worst case.

Two dimensions is harder at every step. The natural generalization is a projected entangled pair state, or PEPS, with one tensor on each site of a lattice and bonds along the edges. Writing a PEPS down is still cheap. Reading anything out of it means contracting the network, and exact contraction is #P-complete in the worst case and remains hard on average for random tensors. The area law itself has not been proven for general gapped two-dimensional systems, although it is now known for frustration-free ones.

Low-energy states and quantum PCP

Everything so far is about ground states. The quantum PCP conjecture is about states that are merely close to the ground energy, within a constant fraction of the number of terms in the Hamiltonian. Suppose every such low-energy state had a short classical description from which a verifier could compute its energy. Then estimating the ground energy to that precision would be in NP, and quantum PCP would imply NP = QMA. So any proof of quantum PCP, if one exists and NP ≠ QMA, has to come with Hamiltonians whose low-energy states have no short classical description of that kind.

The first real evidence that such Hamiltonians exist is the NLTS theorem of Anshu, Breuckmann and Nirkhe, which answered a conjecture of Freedman and Hastings. It gives local Hamiltonians for which every state below some constant energy density needs a circuit of more than constant depth to prepare. That rules out the simplest classical descriptions, the shallow circuits. It says nothing about tensor networks or other efficient descriptions, and that gap is where the open problem sits.

That is why tensor networks keep showing up in what I think about. They are the best general answer we have to the question of which quantum states have short classical descriptions, and the quantum PCP conjecture says that for some Hamiltonians, at low energy, no answer of that kind exists. The same objects turn up in quantum gravity too, where a network of perfect tensors becomes a toy model of spacetime. That thread continues in Decoding spacetime.

Sources

1. Hastings. An area law for one-dimensional quantum systems (2007). Also gives the MPS approximation. arXiv:0705.2024
2. Arad, Kitaev, Landau, Vazirani. An area law and sub-exponential algorithm for 1D systems (2013). arXiv:1301.1162
3. Calabrese, Cardy. Entanglement entropy and quantum field theory (2004). The (c/3) log L law. hep-th/0405152
4. Verstraete, Cirac. Matrix product states represent ground states faithfully (2006). cond-mat/0505140
5. White. Density matrix formulation for quantum renormalization groups, PRL 69, 2863 (1992). DMRG. doi
6. Schollwöck. The density-matrix renormalization group in the age of matrix product states (2011). arXiv:1008.3477
7. Landau, Vazirani, Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians (2015). arXiv:1307.5143
8. Aharonov, Gottesman, Irani, Kempe. The power of quantum systems on a line (2009). QMA-complete in 1D. arXiv:0705.4077
9. Schuch, Cirac, Verstraete. Computational difficulty of finding matrix product ground states (2008). arXiv:0802.3351
10. Verstraete, Cirac. Renormalization algorithms for quantum many-body systems in two and higher dimensions (2004). PEPS. cond-mat/0407066
11. Schuch, Wolf, Verstraete, Cirac. Computational complexity of projected entangled pair states (2007). quant-ph/0611050
12. Haferkamp, Hangleiter, Eisert, Gluza. Contracting projected entangled pair states is average-case hard (2020). arXiv:1810.00738
13. Anshu, Arad, Gosset. An area law for 2D frustration-free spin systems (2022). arXiv:2103.02492
14. Freedman, Hastings. Quantum systems on non-k-hyperfinite complexes (2014). The NLTS conjecture. arXiv:1301.1363
15. Anshu, Breuckmann, Nirkhe. NLTS Hamiltonians from good quantum codes (2023). arXiv:2206.13228
16. Cirac, Pérez-García, Schuch, Verstraete. Matrix product states and projected entangled pair states: concepts, symmetries, theorems (2021). Review. arXiv:2011.12127