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

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.