Browsing by Author "Demirezen, Alp"

Now showing 1 - 1 of 1

Metadata only
Solving 3-SAT problem using a quantum-simulated absorbing classical random walk approach
Demirezen, Alp; Öztop, Erhan; Öztop, Erhan; Aydoğan, Reyhan; Say, C. C.; Department of Computer Science; Demirezen, Alp
Quantum computing offers novel approaches for solving computationally hard problems. In this thesis, we present a quantum algorithm based on the quantum simulation of Schöning's algorithm for solving the 3-SAT problem. We first introduce the concept of quantum-simulated classical absorbing random walk on a hypercube and illustrate the idea using Markov chains. Then we describe the quantum algorithm that is built on the mentioned concept for solving the 3-SAT problem. The algorithm starts by creating the equal superposition of all assignments to the variables representing the vertices of a hypercube. The next state is determined by querying the oracle that checks whether a clause is satisfied or not. Accordingly, one of the variables from an unsatisfied clause is flipped as in Schöning's algorithm. The resulting algorithm finds the solution with a probability that is equivalent to the expected success probability of Schöning's algorithm starting at all possible initial states. The algorithm uses a linear number of qubits in the number of variables provided that reset is possible and its performance is demonstrated through several 3-SAT instances. Its performance is compared to Grover's algorithm, and the proposed algorithm outperforms Grover's algorithm in most cases for the number of gates and depth.