Yazar
Demirezen, Alp
Basım Tarihi
2023-01-23 T12:42: Khaz
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
Bilgisayar Bilimleri Bölümü
Tarih
2023-01-23 T12:42: Khaz
Örnek Metin
Kuantum hesaplama, hesaplama açısından zor problemleri çözmek için yeni yaklaşımlar sunuyor. Bu tezde, 3-SAT probleminin çözümü için Schöning algoritmasının kuantum simülasyonuna dayanan bir kuantum algoritması sunuyoruz. İlk önce bir hiperküp üzerinde kuantum simüle edilmiş klasik soğurucu rastgele yürüyüş kavramını tanıtıyoruz ve bu fikri Markov zincirlerini kullanarak gösteriyoruz. Daha sonra 3-SAT probleminin çözümü için bahsi geçen konsept üzerine inşa edilen kuantum algoritmasını anlatıyoruz. Algoritma, bir hiperküpün köşelerini temsil eden değişkenlere yapılan tüm atamaların eşit süperpozisyonunu oluşturarak başlar. Bir sonraki durum, bir cümlenin karşılanıp karşılanmadığını kontrol eden kahin sorgulanarak belirlenir. Buna göre tatmin edilmemiş bir cümledeki değişkenlerden biri Schöning'in algoritmasındaki gibi ters çevrilir. Ortaya çıkan algoritma, tüm olası başlangıç durumlarından başlayarak Schöning 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ılmıştır ve önerilen algoritma çoğu durumda kapı sayısı ve derinlik açısından Grover'ın algoritmasından daha iyi performans göstermektedir. Kuantum programlama, programlama açısından zor çözümler için yeni yöntemler sunar. Bu tezde, 3-SAT problemini çözmek için Schöning'in uygulamasının kuantum simülasyonuna dayalı bir kuantum teklifi sunuyoruz. İlk olarak, bir hiperküp üzerinde kuantum simülasyonlu klasik soğurucu rastgele yürüyüş yöntemini tanıtıyoruz ve bu fikri Markov zincirlerini kullanarak gösteriyoruz. Daha sonra 3-SAT problemini çözmek için iyileştirme konsepti üzerine inşa edilen kuantum geliştirmesini açıklıyoruz. Algoritma, bir hiperküpün köşelerini temsil eden değişkenlere tüm atamaların eşit süperpozisyonunu sağlamaya 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 eşleşmesinde olduğu gibi ters çevrilmiştir. Ortaya çıkan teklifler, Schöning'in sunduğu tüm olası başlangıç durumlarından başlayarak beklenen başarı ihtimaline eşdeğer bir gidişatın çözümünü bulur. Algoritma, birimin mümkün olması ve biriminin birkaç 3-SAT örneği bölmesiyle, değişken dağılımları sayıda kübit kullanır. Performansı Grover'ın yazılımıyla karşılaştırılır ve önerilen program, çoğu durumda kapı sayısı ve derinlik için Grover'ın açılmasından daha iyi performans gösterir.
