Solving 3-SAT problem using a quantum-simulated absorbing classical random walk approach

Name: Solving 3-SAT problem using a quantum-simulated absorbing classical random walk approach
Author: Demirezen, Alp

İsim	Solving 3-SAT problem using a quantum-simulated absorbing classical random walk approach
Yazar	Demirezen, Alp
Basım Tarihi:	2023-01-23T12:42:59Z
Tür	Belge
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Kayıt Numarası	317f44b9-0999-40f8-9fad-f2cc40c6152e
Lokasyon	Department of Computer Science
Tarih	2023-01-23T12:42:59Z
Örnek Metin	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., Kuantum hesaplama, hesaplama açısından zor problemleri çözmek için yeni yaklaşımlar sunar. Bu tezde, 3-SAT problemini çözmek için Schöning'in algoritmasının kuantum simülasyonuna dayanan bir kuantum algoritması sunuyoruz. İlk olarak, bir hiperküp üzerinde kuantum simülasyonlu klasik soğurucu rastgele yürüyüş kavramını tanıtıyoruz ve bu fikri Markov zincirlerini kullanarak gösteriyoruz. Daha sonra 3-SAT problemini çözmek için bahsedilen konsept üzerine inşa edilen kuantum algoritmasını açıklıyoruz. Algoritma, bir hiperküpün köşelerini temsil eden değişkenlere tüm atamaların eşit süperpozisyonunu oluşturarak başlar. Bir sonraki durum, bir tümcenin karşılanıp karşılanmadığını kontrol eden kahin sorgulanarak belirlenir. Buna göre, bir doyumsuz tümceden gelen değişkenlerden biri, Schöning'in algoritmasında olduğu gibi ters çevrilir. Ortaya çıkan algoritma, tüm olası başlangıç durumlarından başlayarak Schöning'in algoritmasının beklenen başarı olasılığına eşdeğer bir olasılıkla çözümü bulur. Algoritma, sıfırlamanın mümkün olması ve performansının birkaç 3-SAT örneği aracılığıyla gösterilmesi koşuluyla, değişken sayısında doğrusal sayıda kübit kullanır. Performansı Grover'ın algoritmasıyla karşılaştırılır ve önerilen algoritma, çoğu durumda kapı sayısı ve derinlik için Grover'ın algoritmasından daha iyi performans gösterir.

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Solving 3-SAT problem using a quantum-simulated absorbing classical random walk approach

Yazar Demirezen, Alp

Basım Tarihi 2023-01-23T12:42:59Z

Tür Belge

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Kayıt Numarası 317f44b9-0999-40f8-9fad-f2cc40c6152e

Lokasyon Department of Computer Science

Tarih 2023-01-23T12:42:59Z

Örnek Metin 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., Kuantum hesaplama, hesaplama açısından zor problemleri çözmek için yeni yaklaşımlar sunar. Bu tezde, 3-SAT problemini çözmek için Schöning'in algoritmasının kuantum simülasyonuna dayanan bir kuantum algoritması sunuyoruz. İlk olarak, bir hiperküp üzerinde kuantum simülasyonlu klasik soğurucu rastgele yürüyüş kavramını tanıtıyoruz ve bu fikri Markov zincirlerini kullanarak gösteriyoruz. Daha sonra 3-SAT problemini çözmek için bahsedilen konsept üzerine inşa edilen kuantum algoritmasını açıklıyoruz. Algoritma, bir hiperküpün köşelerini temsil eden değişkenlere tüm atamaların eşit süperpozisyonunu oluşturarak başlar. Bir sonraki durum, bir tümcenin karşılanıp karşılanmadığını kontrol eden kahin sorgulanarak belirlenir. Buna göre, bir doyumsuz tümceden gelen değişkenlerden biri, Schöning'in algoritmasında olduğu gibi ters çevrilir. Ortaya çıkan algoritma, tüm olası başlangıç durumlarından başlayarak Schöning'in algoritmasının beklenen başarı olasılığına eşdeğer bir olasılıkla çözümü bulur. Algoritma, sıfırlamanın mümkün olması ve performansının birkaç 3-SAT örneği aracılığıyla gösterilmesi koşuluyla, değişken sayısında doğrusal sayıda kübit kullanır. Performansı Grover'ın algoritmasıyla karşılaştırılır ve önerilen algoritma, çoğu durumda kapı sayısı ve derinlik için Grover'ın algoritmasından daha iyi performans gösterir.