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:2610.05430

Strong Refutation for Random Quantum 3-SAT at Constant Density

Siu On Chan, Jeff Xu

Published Oct 4, 2026• 0 citations
arXivHTMLPDF

Abstract

We give a classical polynomial-time algorithm that strongly refutes random quantum $3$-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random $3$-SAT hypothesis. This stands in sharp contrast to classical random $3$-SAT, for which polynomial-time strong refutation is known only at constraint density $Δ\gtrsim n^{1/2}$. Although quantum $3$-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.

DOI
10.48550/arxiv.2610.05430

Related papers

Efficient algorithm for a quantum analogue of 2-SAT

Sergey B. Bravyi

Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. We present a classical algorithm solving quantum 2-SAT in a polynomial time. It generalizes the well-known algorithm for the classical 2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.

arXiv:quant-ph/0602108•Contemporary mathematics - American Mathematical Society•Jan 1, 2011•179 citations

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

Quantum 3-SAT Is QMA$_1$-Complete

David Gosset, Daniel Nagaj

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum $k$-SAT problem, each constraint is specified by a $k$-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum $k$-SAT with $k\geq 4$ is QMA$_1$-complete [S. Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT, eprint arXiv:quant-ph/0602108, 2006]. Quantum 3-SAT was known to be contained in QMA$_1$ [Bravyi, 2006], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA$_1$-hard, and therefore complete for this complexity class.

SIAM Journal on Computing•Jan 1, 2016•16 citations

A Linear Time Algorithm for Quantum 2-SAT

Niel de Beaudrap, Sevag Gharibian

The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].

arXiv:1508.07338•Leibniz international proceedings in informatics•Aug 28, 2015•20 citations

Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking

Shang-Wei Lin, Ji-Qing Yan, Yean-Ru Chen +2 more

Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.

quant-pharXiv:2604.18218•Apr 21, 2026•0 citations

Quantum 3-SAT Is QMA1-Complete

David Gosset, Daniel Nagaj

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA1-complete [4]. Quantum 3-SAT was known to be contained in QMA1[4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.

arXiv:1302.0290•Annual Symposium on Foundations of Computer Science•Oct 1, 2013•63 citations
We give a classical polynomial-time algorithm that strongly refutes random quantum 333-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random 333-SAT hypothesis. This stands in sharp contrast to classical random 333-SAT, for which polynomial-time strong refutation is known only at constraint density Δ≳n1/2Δ\gtrsim n^{1/2}Δ≳n1/2. Although quantum 333-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.
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.
Quantum 3-SAT Is QMA1_11​-Complete
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum kkk-SAT problem, each constraint is specified by a kkk-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum kkk-SAT with k≥4k\geq 4k≥4 is QMA1_11​-complete [S. Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT, eprint arXiv:quant-ph/0602108, 2006]. Quantum 3-SAT was known to be contained in QMA1_11​ [Bravyi, 2006], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1_11​-hard, and therefore complete for this complexity class.
The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].
Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA1-complete [4]. Quantum 3-SAT was known to be contained in QMA1[4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.