Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.20299
curl -X POST /api/v1/records/arxiv/2602.20299/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.20299/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'