Quantum search algorithm tailored to clause satisfaction problems

Abstract

Many important computer science problems can be reduced to 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 of the variables. We want to find an assignment $i$ of variables for which all $m$ clauses are satisfied. Let $f_j(i)$ be a binary function which is $1$ if $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.

References in corpus (3)

• Faster quantum walk algorithm for the two dimensional spatial search
• General framework for quantum search algorithms
• Grover like Operator Using Only Single-Qubit Gates

Cited by in corpus (1)

• Postprocessing can speed up general quantum search algorithms