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:1603.06985 · Quantum Information and Computation

A quantum version of Schoning's algorithm applied to quantum 2-SAT

Edward Farhi, Shelby Kimmel, Kristan Temme

Published Oct 1, 2016• 10 citations
arXivHTMLPDF

Abstract

We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves these decision problems with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{−2} ). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Schoning’s probabilistic algorithm for k-SAT.

DOI
10.26421/qic16.13-14-7

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•Feb 14, 2006•17 citations

Solving satisfiability problems by the ground-state quantum computer

Wenjin Mao

A quantum algorithm is proposed to solve the satisfiability (SAT) problems by the ground-state quantum computer. The scale of the energy gap of the ground-state quantum computer is analyzed for the $3\text{\ensuremath{-}}\text{bit}$ exact cover problem. The time cost of this algorithm on the general SAT problems is discussed.

arXiv:quant-ph/0411194•Physical Review A•Nov 17, 2005•6 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 Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability

Ahmed Younes, Jonathan E. Rowe

The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in $O(m^2)$ for an E3-CNF Boolean formula with $m$ clauses and in the worst case runs in $O(n^6)$ for an E3-CNF Boolean formula with $n$ inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of $1-ε$ for small $ε>0$ using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.

arXiv:1507.05061•Jul 16, 2015•4 citations

Bounds on the quantum satisfiability threshold

Sergey B. Bravyi, Cristopher Moore, Alexander C. Russell

Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is to decide whether a particular type of local Hamiltonian has a ground state with zero energy. We consider random quantum k-SAT formulas with n variables and m = αn clauses, and ask at what value of αthese formulas cease to be satisfiable. We show that the threshold for random quantum 3-SAT is at most 3.594. For comparison, convincing arguments from statistical physics suggest that the classical 3-SAT threshold is α\approx 4.267. For larger k, we show that the quantum threshold is a constant factor smaller than the classical one. Our bounds work by determining the generic rank of the satisfying subspace for certain gadgets, and then using the technique of differential equations to analyze various algorithms that partition the hypergraph into a collection of these gadgets. Our use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.

arXiv:0907.1297•Jul 7, 2009•11 citations

Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

Salvatore Mandrà, Gian Giacomo Guerreschi, Alán Aspuru‐Guzik

We present an exact quantum algorithm for solving the Exact Satisfiability problem, which belongs to the important NP-complete complexity class. The algorithm is based on an intuitive approach that can be divided into two parts: the first step consists in the identification and efficient characterization of a restricted subspace that contains all the valid assignments of the Exact Satisfiability; while the second part performs a quantum search in such restricted subspace. The quantum algorithm can be used either to find a valid assignment (or to certify that no solution exists) or to count the total number of valid assignments. The query complexities for the worst-case are respectively bounded by and , where n is the number of variables and the number of linearly independent clauses. Remarkably, the proposed quantum algorithm results to be faster than any known exact classical algorithm to solve dense formulas of Exact Satisfiability. As a concrete application, we provide the worst-case complexity for the Hamiltonian cycle problem obtained after mapping it to a suitable Occupation problem. Specifically, we show that the time complexity for the proposed quantum algorithm is bounded by for 3-regular undirected graphs, where n is the number of nodes. The same worst-case complexity holds for -regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by . Finally, when compared to heuristic techniques for Exact Satisfiability problems, the proposed quantum algorithm is faster than the classical WalkSAT and Adiabatic Quantum Optimization for random instances with a density of constraints close to the satisfiability threshold, the regime in which instances are typically the hardest to solve. The proposed quantum algorithm can be straightforwardly extended to the generalized version of the Exact Satisfiability known as Occupation problem. The general version of the algorithm is presented and analyzed.

arXiv:1512.00859•New Journal of Physics•Jul 1, 2016•30 citations
We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves these decision problems with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{−2} ). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Schoning’s probabilistic algorithm for k-SAT.
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.
The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in O(m2)O(m^2)O(m2) for an E3-CNF Boolean formula with mmm clauses and in the worst case runs in O(n6)O(n^6)O(n6) for an E3-CNF Boolean formula with nnn inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of 1−ε1-ε1−ε for small ε>0ε>0ε>0 using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.
Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is to decide whether a particular type of local Hamiltonian has a ground state with zero energy. We consider random quantum k-SAT formulas with n variables and m = αn clauses, and ask at what value of αthese formulas cease to be satisfiable. We show that the threshold for random quantum 3-SAT is at most 3.594. For comparison, convincing arguments from statistical physics suggest that the classical 3-SAT threshold is α\approx 4.267. For larger k, we show that the quantum threshold is a constant factor smaller than the classical one. Our bounds work by determining the generic rank of the satisfying subspace for certain gadgets, and then using the technique of differential equations to analyze various algorithms that partition the hypergraph into a collection of these gadgets. Our use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.
We present an exact quantum algorithm for solving the Exact Satisfiability problem, which belongs to the important NP-complete complexity class. The algorithm is based on an intuitive approach that can be divided into two parts: the first step consists in the identification and efficient characterization of a restricted subspace that contains all the valid assignments of the Exact Satisfiability; while the second part performs a quantum search in such restricted subspace. The quantum algorithm can be used either to find a valid assignment (or to certify that no solution exists) or to count the total number of valid assignments. The query complexities for the worst-case are respectively bounded by and , where n is the number of variables and the number of linearly independent clauses. Remarkably, the proposed quantum algorithm results to be faster than any known exact classical algorithm to solve dense formulas of Exact Satisfiability. As a concrete application, we provide the worst-case complexity for the Hamiltonian cycle problem obtained after mapping it to a suitable Occupation problem. Specifically, we show that the time complexity for the proposed quantum algorithm is bounded by for 3-regular undirected graphs, where n is the number of nodes. The same worst-case complexity holds for -regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by . Finally, when compared to heuristic techniques for Exact Satisfiability problems, the proposed quantum algorithm is faster than the classical WalkSAT and Adiabatic Quantum Optimization for random instances with a density of constraints close to the satisfiability threshold, the regime in which instances are typically the hardest to solve. The proposed quantum algorithm can be straightforwardly extended to the generalized version of the Exact Satisfiability known as Occupation problem. The general version of the algorithm is presented and analyzed.