Record Details


Field	Value

Title	Quantum search algorithm tailored to clause-satisfaction problems

Creator	TULSI, A

Description	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 xk. 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 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.

Publisher	AMER PHYSICAL SOC

Date	2016-01-15T08:28:07Z 2016-01-15T08:28:07Z 2015

Type	Article

Identifier	PHYSICAL REVIEW A, 91(5) 1050-2947 1094-1622 http://dx.doi.org/10.1103/PhysRevA.91.052322 http://dspace.library.iitb.ac.in/jspui/handle/100/18164

Language	en

ICAR Research Data Repository for Knowledge Management