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: Kuantum algoritmalar, Kuantum devreleri, Rastgele yürüyüş modeli, Soğurucular, Quantum algorithms, Quantum circuits, Random walk model, Absorbers
- 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ı: Belirtilmemiş.
Ö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
- Yapay zekanın teorik temelleri
Theoretical fundemantals of artificial intelligence
ERCAN KAYAÖNÜ
Yüksek Lisans
Türkçe
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. A. COŞKUN SÖNMEZ
- Bazı kuantum mekaniksel sistemlerinin bilgisayar benzetişimi
Computer simulation of some quantum mechanical systems
ENDER ÖZTAŞ
Yüksek Lisans
Türkçe
1997
Mühendislik Bilimleriİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
PROF. DR. METİN DEMİRALP
- İki boyutlu iki gruplu nötron difüzyon denkleminin lineer sınır elemanları ile çözümü
The application of linear boundary elements method two dimensional and two group neutron diffusion equation
SIRMA USTAARAMOĞLU
Yüksek Lisans
Türkçe
1997
Nükleer Mühendislikİstanbul Teknik ÜniversitesiFizik Ana Bilim Dalı
DOÇ. DR. BİLGE ÖZGENER
- Efficient batch algorithms for the post-quantum Crystals dilithium signature scheme and Crystals Kyber encryption scheme
Crystals dilithium imza şeması ve Crystals Kyber şifreleme şeması için verimli toplu kuantum ertesi algoritmalar
NAZLI DENİZ TÜRE
Doktora
İngilizce
2024
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı (disiplinlerarası)
DOÇ. DR. OĞUZ YAYLA
PROF. DR. MURAT CENK
- Taban operatörlerine açılım yöntemi ile enerji spektrumunun belirlenmesi: Kuvantum anharmonik salıncı
Başlık çevirisi yok
EBRU NUHOĞLU