Quantum search algorithm tailored to clause-satisfaction problems
Avatar Tulsi · Physical Review A · 2015
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.