{"id":"arxiv/2602.20299","url":"https://arxiv.org/abs/2602.20299","tags":["quant-ph","cond-mat.stat-mech","cond-mat.str-el","physics.comp-ph"],"score":0,"title":"Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability","domain":"quant-ph","source":"arxiv","authors":["Tim Pokart","Frank Pollmann","Jan Carl Budich"],"reviews":0,"subject":"quant-ph","summary":"We approach the 3-SAT satisfiability problem with the quantum-inspired method of imaginary time propagation (ITP) applied to matrix product states (MPS) on a classical computer. This ansatz is fundamentally limited by a quantum entanglement barrier that emerges in imaginary time, reflecting the exponential hardness expected for this NP-complete problem. Strikingly, we argue based on careful analysis of the structure imprinted onto the MPS by the 3-SAT instances that this barrier arises from classical computational complexity. To reveal this connection, we elucidate with stochastic models the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-23","reactions":{}}