Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.20299

Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability

Tim Pokart, Frank Pollmann, Jan Carl Budich

quant-phcond-mat.stat-mechcond-mat.str-elphysics.comp-phSubmitted Feb 23, 2026• Announced Feb 25, 2026• 0 citations• Revised Mar 6, 2026 (v2)
v1 · Feb 23, 2026v2 · Mar 6, 2026
arXivHTMLPDF

Abstract

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 specific relationship between the classical hardness of the $\sharp$P $\supseteq$ NP-complete counting problem $\sharp$3-SAT and the entanglement properties of the quantum state. Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement. Furthermore, we present estimates of the non-stabilizerness required by the protocol, finding a similar resource barrier. Specifically, the necessary amount of non-Clifford operations scales superlinearly in system size, thus implying extensive resource requirements of ITP on different architectures such as Clifford circuits or gate-based quantum computers.

Comments
17 pages, 12 figures

Related papers

Two slightly-entangled NP-complete problems

Román Orús

We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of $n$ qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant $3$-SAT problem, for which an efficient algorithm is yet to be discovered.

arXiv:quant-ph/0502022•Quantum Information and Computation•Sep 1, 2005•3 citations

Computational Complexity of Quantum Satisfiability

Christian Herrmann, Martin Ziegler

We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices. Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables: in the 1D case it coincides with Boolean propositional logic but, starting with dimension two, violates the distributive law. We introduce the weak and strong satisfiability problem for quantum logic propositional formulae. It turns out that in dimension two, both are also NP --complete. For higher-dimensional spaces ℝ d and ℂ d with d ≥ 3 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale (BSS) model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and extends the (still relatively scarce) list of problems established NP ℝ --complete with one, perhaps, closest in spirit to the classical Cook-Levin Theorem. More precisely, strong satisfiability of ∧ ∨ ∧ --terms is complete, while that of ∧ ∨--terms (i.e., those in conjunctive form) can be decided in polynomial time in dimensions d ≥ 2. The decidability of the infinite-dimensional case being still open, we proceed to investigate the case of indefinite finite dimensions. Here, weak satisfiability still belongs to NP R and strong satisfiability is still hard; the latter, in fact, turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations over matrix rings.

Journal of the ACM•May 4, 2016•14 citations

Classical simulability of Clifford + T circuits with Clifford-augmented matrix product states

Zejun Liu, Bryan K. Clark

Determining the quantum-classical boundary between quantum circuits that can be efficiently simulated classically and those that cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented matrix product state (CAMPS), which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components, and from which Pauli expectation values can be computed in time polynomial in the MPS bond dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with T gates or, equivalently, preceded by multiqubit gates of the form α I + β P . We give a simple and easily computed algebraic criterion that characterizes the individual quantum circuits for which OFD generates an efficient CAMPS—the bond dimension is exponential in the null space of a Galois binary field GF(2) matrix induced by a tableau of the twisted Pauli strings P . This significantly increases the number of circuits with rigorous polynomial-time classical simulations. We also give evidence that the typical N qubit random Clifford circuit doped with N uniformly distributed T gates of polylogarithmic depth or greater has a CAMPS with polynomial bond dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than N T gates. We also propose algorithms for sampling, probability, and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford + T circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.

arXiv:2412.17209•Physical Review Research•Apr 18, 2026•18 citations

On the hardness of cloning and connections to representation theory

Vojtěch Havlíček, Chinmay Nirkhe

The states accepted by a quantum circuit are known as the witnesses for the quantum circuit's satisfiability. The assumption BQP does not equal QMA implies that no efficient algorithm exists for constructing a witness for a quantum circuit from the circuit's classical description. However, a similar complexity-theoretic lower bound on the computational hardness of cloning a witness is not known. In this note, we derive a conjecture about cloning algorithms for maximally entangled states over hidden subspaces which would imply that no efficient algorithm exists for cloning witnesses (assuming BQP does not contain NP). The conjecture and result follow from connections between quantum computation and representation theory; specifically, the relationship between quantum state complexity and the complexity of computing Kronecker coefficients.

arXiv:2411.11805•Nov 18, 2024•1 citation

Linear-Time Algorithm for Quantum 2SAT

Itai Arad, Miklós Sántha, Aarthi Sundaram +1 more

A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors $\Pi_{ij}$ on a system of $n$ qubits, and the task is to decide whether the Hamiltonian $H=\sum \Pi_{ij}$ has a 0-eigenvalue, or all eigenvalues are greater than $1/n^\alpha$ for some $\alpha=O(1)$. The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin $\frac{1}{2}$, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity $O(n^4)$ in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and $n$ is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time $O(n+m)$, where $m$ is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is $O((n+m) M(n))$, where $M(n)$ denotes the complexity of multiplying two $n$-bit integers. A conference version of this paper appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP'16), 2016.

Theory of Computing•Jan 1, 2018•5 citations

The unbearable hardness of deciding about magic

Lorenzo Leone, Jens Eisert, Salvatore F. E. Oliviero

Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits $n$, even approximately. We reduce the problem to solving a $3$-\class{SAT} instance on $n^2$ variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.

quant-pharXiv:2602.22330•Feb 27, 2026•19 citations
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 specific relationship between the classical hardness of the ♯\sharp♯P ⊇\supseteq⊇ NP-complete counting problem ♯\sharp♯3-SAT and the entanglement properties of the quantum state. Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement. Furthermore, we present estimates of the non-stabilizerness required by the protocol, finding a similar resource barrier. Specifically, the necessary amount of non-Clifford operations scales superlinearly in system size, thus implying extensive resource requirements of ITP on different architectures such as Clifford circuits or gate-based quantum computers.
We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of nnn qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant 333-SAT problem, for which an efficient algorithm is yet to be discovered.
We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices. Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables: in the 1D case it coincides with Boolean propositional logic but, starting with dimension two, violates the distributive law. We introduce the weak and strong satisfiability problem for quantum logic propositional formulae. It turns out that in dimension two, both are also NP --complete. For higher-dimensional spaces ℝ d and ℂ d with d ≥ 3 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale (BSS) model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and extends the (still relatively scarce) list of problems established NP ℝ --complete with one, perhaps, closest in spirit to the classical Cook-Levin Theorem. More precisely, strong satisfiability of ∧ ∨ ∧ --terms is complete, while that of ∧ ∨--terms (i.e., those in conjunctive form) can be decided in polynomial time in dimensions d ≥ 2. The decidability of the infinite-dimensional case being still open, we proceed to investigate the case of indefinite finite dimensions. Here, weak satisfiability still belongs to NP R and strong satisfiability is still hard; the latter, in fact, turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations over matrix rings.
Determining the quantum-classical boundary between quantum circuits that can be efficiently simulated classically and those that cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented matrix product state (CAMPS), which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components, and from which Pauli expectation values can be computed in time polynomial in the MPS bond dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with T gates or, equivalently, preceded by multiqubit gates of the form α I + β P . We give a simple and easily computed algebraic criterion that characterizes the individual quantum circuits for which OFD generates an efficient CAMPS—the bond dimension is exponential in the null space of a Galois binary field GF(2) matrix induced by a tableau of the twisted Pauli strings P . This significantly increases the number of circuits with rigorous polynomial-time classical simulations. We also give evidence that the typical N qubit random Clifford circuit doped with N uniformly distributed T gates of polylogarithmic depth or greater has a CAMPS with polynomial bond dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than N T gates. We also propose algorithms for sampling, probability, and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford + T circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.
The states accepted by a quantum circuit are known as the witnesses for the quantum circuit's satisfiability. The assumption BQP does not equal QMA implies that no efficient algorithm exists for constructing a witness for a quantum circuit from the circuit's classical description. However, a similar complexity-theoretic lower bound on the computational hardness of cloning a witness is not known. In this note, we derive a conjecture about cloning algorithms for maximally entangled states over hidden subspaces which would imply that no efficient algorithm exists for cloning witnesses (assuming BQP does not contain NP). The conjecture and result follow from connections between quantum computation and representation theory; specifically, the relationship between quantum state complexity and the complexity of computing Kronecker coefficients.
A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Πij\Pi_{ij}Πij​ on a system of nnn qubits, and the task is to decide whether the Hamiltonian H=∑ΠijH=\sum \Pi_{ij}H=∑Πij​ has a 0-eigenvalue, or all eigenvalues are greater than 1/nα1/n^\alpha1/nα for some α=O(1)\alpha=O(1)α=O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin 12\frac{1}{2}21​, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity O(n4)O(n^4)O(n4) in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and nnn is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time O(n+m)O(n+m)O(n+m), where mmm is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is O((n+m)M(n))O((n+m) M(n))O((n+m)M(n)), where M(n)M(n)M(n) denotes the complexity of multiplying two nnn-bit integers. A conference version of this paper appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP'16), 2016.
Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits nnn, even approximately. We reduce the problem to solving a 333-\class{SAT} instance on n2n^2n2 variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.