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:1403.1588 · Leibniz international proceedings in informatics

Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical

Niel de Beaudrap

Published Jan 1, 2014• 3 citations
arXivHTMLPDF

Abstract

The problem 2-QUANTUM-SATISFIABILITY (QSAT[2]) is the generalisation of the 2-CNF-SAT problem to quantum bits, and is equivalent to determining whether or not a spin-1/2 Hamiltonian with two-body terms is frustration-free. imilarly to the classical problem #SAT[2], the counting problem #QSAT[2] of determining the size (i.e. the dimension) of the set of satisfying states is #P-complete. However, if we consider random instances of QSAT[2] in which constraints are sampled from the Haar measure, intractible instances have measure zero. An apparent reason for this is that almost all two-qubit constraints are entangled, which more readily give rise to long-range constraints. We investigate under which conditions product constraints also give rise to efficiently solvable families of #QSAT[2] instances. We consider #QSAT[2] involving only discrete distributions over tensor product operators, which interpolates between classical #SAT[2] and #QSAT[2] involving arbitrary product constraints. We find that such instances of #QSAT[2], defined on Erdös-Renyi graphs or bond-percolated lattices, are asymptotically almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #SAT[2].

DOI
10.4230/lipics.tqc.2014.118

Related papers

Product, generic, and random generic quantum satisfiability

Chris R. Laumann, Andreas Martin Läuchli, Roderich Moessner +2 more

We report a cluster of results on $k$-QSAT, the problem of quantum satisfiability for $k$-qubit projectors which generalizes classical satisfiability with $k$-bit clauses to the quantum setting. First we define the $\mathit{NP}$-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT-unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for $k=3$ and $k=4$ and mild evidence for the existence of a phase which is satisfiable by entangled states alone.

arXiv:0910.2058•Physical Review A•Jun 28, 2010•43 citations

Classical-quantum mixing in the random 2-satisfiability problem

Ionut-Dragos Potirniche, Chris R. Laumann, S. L. Sondhi

Classical satisfiability (SAT) and quantum satisfiability (QSAT) are complete problems for the complexity classes NP and QMA, respectively, and they are believed to be intractable for both classical and quantum computers. Statistical ensembles of instances of these problems have been studied previously in an attempt to elucidate their typical, as opposed to worst-case, behavior. In this paper, we introduce a statistical ensemble that interpolates between classical and quantum. For the simplest 2-SAT--2-QSAT ensemble, we find the exact boundary that separates SAT and UNSAT instances. We do so by establishing coincident lower and upper bounds, in the limit of large instances, on the extent of the UNSAT and SAT regions, respectively.

arXiv:1502.04700•Physical Review A•Oct 1, 2015•1 citation

Testing Quantum Satisfiability

Ashley Montanaro, Changpeng Shao, Dominic Verdon

Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA $$_1$$ 1 -complete for $$k\ge 3$$ k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that $$\epsilon n^k$$ ϵ n k constraints must be removed before a product state solution exists, for some fixed $$\epsilon >0$$ ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.

arXiv:2301.10699•Communications in Mathematical Physics•Sep 1, 2025•2 citations

Random quantum satisfiability

Chris R. Laumann, Roderich Moessner, A. Scarddichio +1 more

Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any} hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.

arXiv:0903.1904•Quantum Information and Computation•Jan 1, 2010•38 citations

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation

Dorian Rudolph, Sevag Gharibian, Daniel Nagaj

Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a $k$-dimensional and $l$-dimensional qudit pair, denoted $(k,l)$-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain $\mathsf{QMA}_1$-hard, in that $(2,5)$-QSAT is $\mathsf{QMA}_1$-complete. In contrast, $2$-SAT on qubits is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that $(3,d)$-QSAT on the 1D line with $d\in O(1)$ is also $\mathsf{QMA}_1$-hard. Finally, we initiate the study of 1D $(2,d)$-QSAT by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. Our first result uses a direct embedding, combining a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset, Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from $Ω(1/T^6)$ to $Ω(1/T^2)$, for $T$ the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on $d'$-dimensional qudits, we show how to embed it into an effective null-space of a 1D $(3,d)$-QSAT instance, for $d\in O(1)$. Our approach may be viewed as a weaker notion of "simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based $\mathsf{QMA}_1$-hardness result, i.e. for frustration-free Hamiltonians.

arXiv:2401.02368•Jan 4, 2024•2 citations

Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT

Atsuya Hasegawa, Jonas Kamminga, François Le Gall +1 more

The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but $O(\sqrt{n})$ qubits participate in only constantly many constraints, while the remaining $O(\sqrt{n})$ qubits each participate in $O(\sqrt{n})$ constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of $n^δ$, for any $δ>0$, our algorithm solves the problem in time $O(2^{(1- \varepsilon)n})$ for some $\varepsilon>0$. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.

quant-pharXiv:2609.36464•Sep 30, 2026•0 citations
The problem 2-QUANTUM-SATISFIABILITY (QSAT[2]) is the generalisation of the 2-CNF-SAT problem to quantum bits, and is equivalent to determining whether or not a spin-1/2 Hamiltonian with two-body terms is frustration-free. imilarly to the classical problem #SAT[2], the counting problem #QSAT[2] of determining the size (i.e. the dimension) of the set of satisfying states is #P-complete. However, if we consider random instances of QSAT[2] in which constraints are sampled from the Haar measure, intractible instances have measure zero. An apparent reason for this is that almost all two-qubit constraints are entangled, which more readily give rise to long-range constraints. We investigate under which conditions product constraints also give rise to efficiently solvable families of #QSAT[2] instances. We consider #QSAT[2] involving only discrete distributions over tensor product operators, which interpolates between classical #SAT[2] and #QSAT[2] involving arbitrary product constraints. We find that such instances of #QSAT[2], defined on Erdös-Renyi graphs or bond-percolated lattices, are asymptotically almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #SAT[2].
We report a cluster of results on kkk-QSAT, the problem of quantum satisfiability for kkk-qubit projectors which generalizes classical satisfiability with kkk-bit clauses to the quantum setting. First we define the NP\mathit{NP}NP-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT-unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for k=3k=3k=3 and k=4k=4k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone.
Classical satisfiability (SAT) and quantum satisfiability (QSAT) are complete problems for the complexity classes NP and QMA, respectively, and they are believed to be intractable for both classical and quantum computers. Statistical ensembles of instances of these problems have been studied previously in an attempt to elucidate their typical, as opposed to worst-case, behavior. In this paper, we introduce a statistical ensemble that interpolates between classical and quantum. For the simplest 2-SAT--2-QSAT ensemble, we find the exact boundary that separates SAT and UNSAT instances. We do so by establishing coincident lower and upper bounds, in the limit of large instances, on the extent of the UNSAT and SAT regions, respectively.
Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA 1_11​ 1 -complete for k≥3k\ge 3k≥3 k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that ϵnk\epsilon n^kϵnk ϵ n k constraints must be removed before a product state solution exists, for some fixed ϵ>0\epsilon >0ϵ>0 ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.
Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA1_11​-complete quantum satisfiability (QSAT) problem introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any} hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.
Quantum 2-SAT on low dimensional systems is QMA1\mathsf{QMA}_1QMA1​-complete: Direct embeddings and black-box simulation
Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a kkk-dimensional and lll-dimensional qudit pair, denoted (k,l)(k,l)(k,l)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA1\mathsf{QMA}_1QMA1​-hard, in that (2,5)(2,5)(2,5)-QSAT is QMA1\mathsf{QMA}_1QMA1​-complete. In contrast, 222-SAT on qubits is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that (3,d)(3,d)(3,d)-QSAT on the 1D line with d∈O(1)d\in O(1)d∈O(1) is also QMA1\mathsf{QMA}_1QMA1​-hard. Finally, we initiate the study of 1D (2,d)(2,d)(2,d)-QSAT by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. Our first result uses a direct embedding, combining a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset, Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from Ω(1/T6)Ω(1/T^6)Ω(1/T6) to Ω(1/T2)Ω(1/T^2)Ω(1/T2), for TTT the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian HHH on d′d'd′-dimensional qudits, we show how to embed it into an effective null-space of a 1D (3,d)(3,d)(3,d)-QSAT instance, for d∈O(1)d\in O(1)d∈O(1). Our approach may be viewed as a weaker notion of "simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA1\mathsf{QMA}_1QMA1​-hardness result, i.e. for frustration-free Hamiltonians.
The local Hamiltonian problem is the canonical QMA\mathsf{QMA}QMA-complete problem, and O(2n)O(2^n)O(2n) time classical algorithms and O(2n/2)O(2^{n/2})O(2n/2) time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but O(n)O(\sqrt{n})O(n​) qubits participate in only constantly many constraints, while the remaining O(n)O(\sqrt{n})O(n​) qubits each participate in O(n)O(\sqrt{n})O(n​) constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of nδn^δnδ, for any δ>0δ>0δ>0, our algorithm solves the problem in time O(2(1−ε)n)O(2^{(1- \varepsilon)n})O(2(1−ε)n) for some ε>0\varepsilon>0ε>0. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.