3-SAT problemini kuantum simülasyonlu bir soğurucu klasik rastgele yürüyüş yaklaşımı kullanarak çözme

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.