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

Theory of Computing

Linear-Time Algorithm for Quantum 2SAT

Itai Arad, Miklós Sántha, Aarthi Sundaram, Shengyu Zhang

Published Jan 1, 2018• 5 citations
Publisher

Abstract

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.

DOI
10.4086/toc.2018.v014a001

Related papers

Linear time algorithm for quantum 2SAT

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

A canonical 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}$ on a system of $n$ qubits, and the task is to decide whether the Hamiltonian $H=\sum Π_{ij}$ has a 0-eigenvalue, or it is larger than $1/n^α$ for some $α=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 the 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. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is $O(n^4)$. In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

arXiv:1508.06340•Aug 26, 2015•3 citations

Linear Time Algorithm for Quantum 2SAT

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

A canonical 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 Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = 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 the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

Leibniz international proceedings in informatics•Jan 1, 2016•1 citation

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•10 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

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•10 citations

Quantum algorithm for a set of quantum 2SAT problems*

Yanglin Hu, Zhelun Zhang, Biao Wu

We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is O(n 3.9) for yielding non-trivial solutions for problems with the number of clauses m = dn(n – 1)/2 (d ≲ 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.

arXiv:2009.02600•Chinese Physics B•Dec 30, 2020•7 citations
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.
A canonical 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Π_{ij}Πij​ on a system of nnn qubits, and the task is to decide whether the Hamiltonian H=∑ΠijH=\sum Π_{ij}H=∑Πij​ has a 0-eigenvalue, or it is larger than 1/nα1/n^α1/nα for some α=O(1)α=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 the 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. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n4)O(n^4)O(n4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.
A canonical 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 Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = 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 the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.
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].
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.
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.
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is O(n 3.9) for yielding non-trivial solutions for problems with the number of clauses m = dn(n – 1)/2 (d ≲ 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.