Increasing efficiency of combinatorial optimization problems on quantum annealers using classical computers

Google'ın kuantum bilgisayarların klasik bilgisayarlara göre üstünlüğü iddiası, kuantum hesaplama tarihinde büyük bir kilometre taşıdır. İddialara rağmen, kuantum bilgisayarların pratik uygulanabilirliği, düşük kuantum bit sayısı ve yüksek gürültü oranları nedeniyle tartışmalı olmaya devam etmekte. Kuantum hesaplamanın alternatif modeli, yalnızca belirli bir formatta bir optimizasyon problemini çözebilen kuantum tavlamadır. Kuantum tavlama, bu tür cihazların ölçeğinin binlerce kübite kadar çıkması nedeniyle aktif olarak araştırılmaktadır. Bu nispeten yüksek kübit sayısı, kuantum tavlayıcıların daha büyük boyutlardaki sorunları çözmesini sağlar, bu nedenle onları gerçek hayat senaryolarında kullanılabilir hale getirir. Çözülmüş optimizasyon probleminin spesifik formatı, aynı zamanda ikinci dereceden kısıtlanmamış ikili optimizasyon (QUBO) olarak da temsil edilebilen Ising formülasyonu olarak adlandırılır. QUBO, karşılık gelen önyargı ağırlıklarına ve kübitler arasındaki kuadratik ağırlıklara sahip bir kübit kümesinden oluşur. Bu tez, iki farklı kombinatoryal optimizasyon probleminin QUBO formülasyo- nunda ağırlık optimizasyonu için iki şema sunmaktadır. Her iki şema, QUBO'ları çözen bir tavlama cihazı ile arayüzlenen QUBO ağırlıklarını yeniden tanımlayan klasik bir bilgisayarı içerir. İlk kombinatoryal problem, önyargıların görevlerin hesap- lama maliyetlerini temsil ettiği ve ikinci dereceden terimlerin görevler arasındaki iletişimi modellediği görev atama problemidir. İkinci problem, önyargıların kuantum kapılarının aslına uygunluğunu temsil ettiği, ikinci dereceden terimlerin kübit hareketi modellediği devre haritalama problemidir. Ağırlık optimizasyon algoritması (WOA) olarak adlandırılan ilk yaklaşım, kuantum kapılarını fiziksel kübit topolojisine eşlemenin uygunluğundan sorumlu kübit önyargıları ile kübit hareketinden sorumlu ikinci dereceden terimler arasında istenen bir oranı arar. Oranın istenebilirliği, hem kübit hareketinden hem de haritalamadan kaynaklanan toplam aslına uygunluk ile tanımlanır. WOA'nın kuantum devre haritalaması için kuantum tavlama iş akışına eklenmesi, tüm sorunlu örneklerin %72,9'unda kübit hareketinin azalmasına neden oldu. Ayrıca, eşlenen devrenin toplam doğruluğunu IBM Vigo cihazında %39 ve IBM QX2'de %107 oranında artırmaya izin verdi. Deneyler, D-Wave kuantum tavlama yazılım yığınından tabu arama QUBO çözücüsünde gerçekleştirilmiştir. Karınca kolonisi ağırlık optimize edicisinin sonuçları, bir kuantum tavlama cihazının bulunmaması nedeniyle sınırlıdır.