Quantum search algorithm tailored to clause-satisfaction problems

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\left(i\right)$ be a binary function, which is 1 if the $j\mathrm{th}$ clause is satisfied by the assignment $i$, else $f_j\left(i\right)=0$. Then the solution is $r$ for which $f(i=r)=1$, where $f\left(i\right)$ is the and function of all $f_j\left(i\right)$. 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\left(i\right)$ for all $i$ in superposition which requires computing and of all $m$ binary functions $f_j\left(i\right)$. Hence there must be coupling between the computation circuits for each $f_j\left(i\right)$. 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.