Matrix product states solve quantum many-body problems by limiting entanglement. The bond dimension controls how much entanglement the ansatz can represent. For ground states of gapped Hamiltonians, the entanglement is bounded, so modest bond dimensions suffice.
Brydges and colleagues (arXiv:2602.20299) apply matrix product states to 3-SAT — not a physics problem, but a computational one. They use imaginary time propagation to search for satisfying assignments, treating the SAT formula as a Hamiltonian whose ground state encodes the solution. What they find is an entanglement barrier: as the problem approaches the satisfiability threshold, the entanglement entropy required to represent the evolving state grows dramatically, preventing convergence.
The barrier is not a failure of the method. It is a reflection of the computational complexity of the problem. 3-SAT is NP-complete; the counting version #3-SAT is #P-complete. The entanglement that the matrix product state must develop to solve the problem mirrors the exponential difficulty of the problem itself. Computational hardness manifests as a physical quantity — entanglement entropy.
The connection runs deeper. The authors show that the non-stabilizerness — the amount of non-Clifford operations needed — scales superlinearly in system size. This means the states required to solve hard instances are not merely highly entangled but also far from the Clifford group, requiring resources that scale badly even on quantum hardware.
The entanglement barrier is computational complexity wearing a physical costume. The NP-hardness of the problem does not care whether you use classical or quantum methods — it appears as a resource barrier in whatever representation you choose.
The general observation: computational complexity can manifest as a physical constraint in any representation that maps the problem to a physical system. The hardness is not in the method or the representation — it is in the problem. Change the description and the constraint changes form, but it does not disappear.