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:1503.06395 · Physical Review A

Quantum search algorithm tailored to clause-satisfaction problems

Avatar Tulsi

Published May 22, 2015• 4 citations
arXivHTMLPDF

Abstract

Many important computer science problems can be reduced to the clause-satisfaction problem. We are given $n$ Boolean variables ${x}_{k}$ and $m$ clauses ${c}_{j}$ where each clause is a function of values of some ${x}_{k}$. We want to find an assignment $i$ of ${x}_{k}$ for which all $m$ clauses are satisfied. Let ${f}_{j}(i)$ be a binary function, which is 1 if the $j\mathrm{th}$ clause is satisfied by the assignment $i$, else ${f}_{j}(i)=0$. Then the solution is $r$ for which $f(i=r)=1$, where $f(i)$ is the and function of all ${f}_{j}(i)$. In quantum computing, Grover's algorithm can be used to find $r$. A crucial component of this algorithm is the selective phase inversion ${I}_{r}$ of the solution state encoding $r$. ${I}_{r}$ is implemented by computing $f(i)$ for all $i$ in superposition which requires computing and of all $m$ binary functions ${f}_{j}(i)$. Hence there must be coupling between the computation circuits for each ${f}_{j}(i)$. In this paper, we present an alternative quantum search algorithm which relaxes the requirement of such couplings. Hence it offers implementation advantages for clause-satisfaction problems.

DOI
10.1103/physreva.91.052322

Related papers

Finding solutions to MaxSAT in a quantum computer

Leonardo Clemente, Salvador Elías Venegas-Andraca

Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.

•Jul 10, 2024•0 citations

Solving mathematical problems with quantum search algorithm

Rubens Viana Ramos, Paulo Benicio Melo de Sousa, David Sena Oliveira

Quantum computation has attracted much attention since it was shown by Shor and Grover the possibility to implement quantum algorithms able to realize, respectively, factoring and searching in a faster way than any other known classical algorithm. It is possible to use Grover algorithm, taking profit of its ability to find a specific value in a unordered database, to find, for example, the zero of a logical function; the minimal or maximal value in a database or to recognize if an odd number is prime or not. Here we show quantum algorithms to solve those cited mathematical problems. The solution requires the use of a quantum bit string comparator being used as oracle. This quantum circuit compares two quantum states and identifies if they are equal or, otherwise, which of them is the largest. Moreover, we also show the quantum bit string comparator allow us to implement conditional statements in quantum computation, a fundamental structure for designing of algorithms.

arXiv:quant-ph/0605003•Apr 29, 2006•4 citations

Solving equations approximately with Grover’s search algorithm

Jed Brody, Wenye Song

Abstract To enrich curricular materials for quantum computing education, we show how Grover’s algorithm can be used to find approximate solutions to algebraic and transcendental equations. This significantly expands the range of exercises based on Grover’s algorithm, which typically solves problems with exact binary solutions. These exercises teach and unify a diverse skillset, including binary representation of fractional and negative numbers, implementation of Boolean operations with quantum gates, and comprehensive design of quantum circuits to implement Grover’s algorithm.

European Journal of Physics•Oct 3, 2025•0 citations

Quantum Algorithm for Maximum Satisfiability

Abdirahman Alasow, Marek A. Perkowski

Satisfiability (SAT) problem in engineering and computer science is to find the set of assignment values of input variables for the given Boolean function that evaluate this function to TRUE or prove that such satisfying values do not exist. For POS SAT Problem, we propose a novel quantum algorithm for the maximum satisfiability (MAX-SAT) which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with the information how far the given Boolean function is from the SAT satisfaction. We use Grover's algorithm with a new block called quantum counter in the oracle circuit.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2022•7 citations

A parallel and distributed fixed-point quantum search algorithm for solving SAT problems

He Wang, Jinyang Yao

Boolean satisfiability (SAT) problem is of fundamental importance in computer science and many application domains. For Grover's algorithm, solving the SAT problem requires $\mathcal{O}(\sqrt{2^n})$ queries--where n denotes the number of logic variables in the problem. However, Grover's algorithm suffers from the Souffle problem: specifically, when the number of solutions is unknown, terminating the algorithm too early or too late leads to a significant reduction in the probability of obtaining a solution. In this paper, we propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem. By exploiting entanglement, each clause in the conjunctive normal form (CNF) formula can be processed independently, leading to a significant reduction in circuit depth. We also discuss how to perform the algorithm in distributed manner. These make the PFPS algorithm particularly suitable for the noisy intermediate-scale quantum (NISQ) era.

quant-pharXiv:2604.09980•Apr 14, 2026•0 citations

Quantum Algorithm for Linear Systems of Equations

Aram W. Harrow, Avinatan Hassidim, Seth Lloyd

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix $A$ and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ for some matrix $M$. In this case, when $A$ is sparse, $N\ifmmode\times\else\texttimes\fi{}N$ and has condition number $\ensuremath{\kappa}$, the fastest known classical algorithms can find $\stackrel{\ensuremath{\rightarrow}}{x}$ and estimate ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ in time scaling roughly as $N\sqrt{\ensuremath{\kappa}}$. Here, we exhibit a quantum algorithm for estimating ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ whose runtime is a polynomial of $\mathrm{log}(N)$ and $\ensuremath{\kappa}$. Indeed, for small values of $\ensuremath{\kappa}$ [i.e., $\mathrm{poly}\mathrm{log}(N)$], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.

arXiv:0811.3171•Physical Review Letters•Oct 7, 2009•3,798 citations
Many important computer science problems can be reduced to the clause-satisfaction problem. We are given nnn Boolean variables xk{x}_{k}xk​ and mmm clauses cj{c}_{j}cj​ where each clause is a function of values of some xk{x}_{k}xk​. We want to find an assignment iii of xk{x}_{k}xk​ for which all mmm clauses are satisfied. Let fj(i){f}_{j}(i)fj​(i) be a binary function, which is 1 if the jthj\mathrm{th}jth clause is satisfied by the assignment iii, else fj(i)=0{f}_{j}(i)=0fj​(i)=0. Then the solution is rrr for which f(i=r)=1f(i=r)=1f(i=r)=1, where f(i)f(i)f(i) is the and function of all fj(i){f}_{j}(i)fj​(i). In quantum computing, Grover's algorithm can be used to find rrr. A crucial component of this algorithm is the selective phase inversion Ir{I}_{r}Ir​ of the solution state encoding rrr. Ir{I}_{r}Ir​ is implemented by computing f(i)f(i)f(i) for all iii in superposition which requires computing and of all mmm binary functions fj(i){f}_{j}(i)fj​(i). Hence there must be coupling between the computation circuits for each fj(i){f}_{j}(i)fj​(i). In this paper, we present an alternative quantum search algorithm which relaxes the requirement of such couplings. Hence it offers implementation advantages for clause-satisfaction problems.
Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.
Quantum computation has attracted much attention since it was shown by Shor and Grover the possibility to implement quantum algorithms able to realize, respectively, factoring and searching in a faster way than any other known classical algorithm. It is possible to use Grover algorithm, taking profit of its ability to find a specific value in a unordered database, to find, for example, the zero of a logical function; the minimal or maximal value in a database or to recognize if an odd number is prime or not. Here we show quantum algorithms to solve those cited mathematical problems. The solution requires the use of a quantum bit string comparator being used as oracle. This quantum circuit compares two quantum states and identifies if they are equal or, otherwise, which of them is the largest. Moreover, we also show the quantum bit string comparator allow us to implement conditional statements in quantum computation, a fundamental structure for designing of algorithms.
Abstract To enrich curricular materials for quantum computing education, we show how Grover’s algorithm can be used to find approximate solutions to algebraic and transcendental equations. This significantly expands the range of exercises based on Grover’s algorithm, which typically solves problems with exact binary solutions. These exercises teach and unify a diverse skillset, including binary representation of fractional and negative numbers, implementation of Boolean operations with quantum gates, and comprehensive design of quantum circuits to implement Grover’s algorithm.
Satisfiability (SAT) problem in engineering and computer science is to find the set of assignment values of input variables for the given Boolean function that evaluate this function to TRUE or prove that such satisfying values do not exist. For POS SAT Problem, we propose a novel quantum algorithm for the maximum satisfiability (MAX-SAT) which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with the information how far the given Boolean function is from the SAT satisfaction. We use Grover's algorithm with a new block called quantum counter in the oracle circuit.
Boolean satisfiability (SAT) problem is of fundamental importance in computer science and many application domains. For Grover's algorithm, solving the SAT problem requires O(2n)\mathcal{O}(\sqrt{2^n})O(2n​) queries--where n denotes the number of logic variables in the problem. However, Grover's algorithm suffers from the Souffle problem: specifically, when the number of solutions is unknown, terminating the algorithm too early or too late leads to a significant reduction in the probability of obtaining a solution. In this paper, we propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem. By exploiting entanglement, each clause in the conjunctive normal form (CNF) formula can be processed independently, leading to a significant reduction in circuit depth. We also discuss how to perform the algorithm in distributed manner. These make the PFPS algorithm particularly suitable for the noisy intermediate-scale quantum (NISQ) era.
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix AAA and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ for some matrix MMM. In this case, when AAA is sparse, $N\ifmmode\times\else\texttimes\fi{}N$ and has condition number $\ensuremath{\kappa}$, the fastest known classical algorithms can find $\stackrel{\ensuremath{\rightarrow}}{x}$ and estimate ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ in time scaling roughly as $N\sqrt{\ensuremath{\kappa}}$. Here, we exhibit a quantum algorithm for estimating ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ whose runtime is a polynomial of log(N)\mathrm{log}(N)log(N) and $\ensuremath{\kappa}$. Indeed, for small values of $\ensuremath{\kappa}$ [i.e., polylog(N)\mathrm{poly}\mathrm{log}(N)polylog(N)], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.