Thesis Defense - Alp Demirezen (MSCS)

Alp Demirezen  – M.Sc. Computer Science

Prof. Erhan Öztop – Advisor

Dr. Özlem Salehi Köken – Co-Advisor

Date: 25.05.2022

Time: 10:30

Location: AB1 245

Solving 3-SAT Problem Using A Quantum-Simulated Absorbing Classical Random Walk Approach

Thesis Committee

Prof. Erhan Öztop, Özyeğin University

Assistant Prof. Reyhan Aydoğan, Özyeğin University

Prof. Ahmet Celal Cem Say, Boğaziçi University

Abstract:

Quantum computing offers novel approaches for solving computationally hard problems. In this thesis, we present a quantum algorithm for the 3-SAT problem inspired by Schöning's algorithm. 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 for solving the 3-SAT problem that is based on the mentioned concept. The algorithm starts by creating the equal superposition of all assignments to the variables, that represent 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 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.

Bio:

Alp Demirezen received his B.Sc. degree in Computer Science from Özyeğin University in June 2020. He has been pursuing his M.Sc. degree in Computer Science at Özyeğin University since September 2020, under the supervision of Prof. Erhan Öztop and Dr. Özlem Salehi Köken. His research area is quantum computation.