Solving 3-SAT problem using a quantum-simulated absorbing classical random walk approach
3-SAT problemini kuantum simülasyonlu bir soğurucu klasik rastgele yürüyüş yaklaşımı kullanarak çözme
- Tez No: 759619
- Danışmanlar: PROF. DR. ERHAN ÖZTOP, DR. ÖZLEM SALEHİ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Özyeğin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 41
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- The role of different modes of bias voltage on the morphology, structure and durability of tin and tialn coatings produced with cathodic arc physical vapor deposition
Farklı hızlandırma voltaj türlerinin katodik ark fiziksel biriktirme yöntemi ile üretilen tin ve tialn kaplamaların morfoloji, yapı ve dayanaklılığı üzerindeki rolü
GOLNAZ TAGHAVI POURIAN AZAR
Doktora
İngilizce
2019
Metalurji Mühendisliğiİstanbul Teknik ÜniversitesiMalzeme Bilimi ve Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA KAMİL ÜRGEN
- A parallel approach to solving satisfiability problems on graphics processing units using neural networks
Sinir ağları kullanarak grafik işleme üniteleri üzerinde gerçeklenebilirlik problemleri çözme için paralel bir yaklaşım
MELİH MERT
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TAFLAN İMRE GÜNDEM
- Dikey dalan sıvı jeti için farklı jet çıkış geometrilerinin havalandırma miktarına etkisinin sayısal olarak incelenmesi
Investigation of the different nozzle geometries for vertical plunging water jet air entrainment with numerical methods
BURAK ALP KARAN
Yüksek Lisans
Türkçe
2017
Kimya Mühendisliğiİstanbul Teknik ÜniversitesiMaden Mühendisliği Ana Bilim Dalı
DOÇ. DR. YAKUP ERHAN BÖKE
DR. ZAFER GEMİCİ
- Sınır eleman yönteminin çok bağımlı bir bölgeye uygulanması
An Extension of boundary element method for multiply connected regions
ŞENOL ATAOĞLU