Qubit-Verimli Varyasyonel MaxCut Sezgisel Algoritması

Neden küçük kuantum çipleri büyük bulmacalar için önemlidir

Gerçek dünya problemlerinin çoğu—bilgisayar devrelerini yerleştirmekten malzemeleri modellemeye kadar—bir ağı iki gruba ayırıp bu iki grup arasındaki bağlantıların sayısını mümkün olduğunca artırmaya indirgenir. MaxCut olarak bilinen bu zorluk, klasik bilgisayarlar için ünlü şekilde zordur. Makale, yalnızca birkaç kuantum biti (kubiti) kullanarak şaşırtıcı derecede büyük ağları işleyebilen yeni bir kuantum-ilhamlı yöntem sunuyor; bu da hem kuantum hem de klasik optimizasyon araçlarını test etmek ve geliştirmek için yeni bir yol sağlıyor.

Ağı iki kullanışlı yarıya bölmek

MaxCut basitçe şu soruyu sorar: bir dizi noktaya (düğümlere) çizgilerle (kenarlarla) bağlıysanız, her düğümü, örneğin mavi veya beyaz olarak nasıl renklendirmelisiniz ki mümkün olduğunca çok çizgi farklı renkteki düğümleri bağlasın? Bu en iyi bölünme, devre tasarımı ve istatistiksel fizik gibi alanlarda değerlidir fakat ağ büyük olduğunda kesin olarak bulması çok zordur. Yaygın kullanılan klasik yaklaşımlardan biri olan Goemans–Williamson (GW) algoritması, problemi zekice gevşetir ve gerçek en iyinin en az yaklaşık %88’i kadar iyi bir kesit bulmayı garanti eder. Kuantum hesaplama bu tür problemlere saldırmak için yeni yollar vaat ediyor, ancak mevcut aygıtlar gürültülü ve boyut olarak sınırlı olduğundan, büyük ve derin devreleri çalıştırmak zordur.

Sadece birkaç kubitle büyük grafikleri çözmek

Klasik kuantum yaklaşımları, örneğin Quantum Approximate Optimization Algorithm (QAOA), ağdaki her düğüm için bir kubit gerektirir; bu yüzden 1.000 düğümlü bir grafik 1.000 kubit gerektirir—bu da bugünün makinelerinin çok ötesindedir. Qubit-Verimli MaxCut (QEMC) adı verilen yeni yöntem bu ölçeklenmeyi tersine çevirir: düğüm sayısının logaritmasına yakın sayıda kubit kullanır, yani 11 kubit 2.000’den fazla düğüm hakkında bilgi kodlayabilir. Her kubiti tek bir düğüme bağlamak yerine QEMC, tüm kuantum durumunu kompakt bir adres alanı olarak kullanır ve farklı düğümlerin bu küçük kayıtın farklı temel durumlarına karşılık gelmesine izin verir. Bu kubit tasarrufu devreleri sığ ve gürültülü donanımda çalıştırması daha kolay tutar, aynı zamanda çok büyük grafikleri temsil etmeyi sağlar.

Sabit durumlar yerine olasılıkla düğümlerin renklendirilmesi

Temel yenilik, QEMC’nin her düğümün “rengini” nasıl kodladığıdır. Her düğümü tek bir kuantum durumunda kesin olarak mavi veya beyaz olmaya zorlamak yerine, yöntem her düğümün renginin ölçümde gözlenme olasılığına göre çıkarılmasına izin verir. Temel durumu düşük olasılıkla görülen bir düğüm bir renk; daha yüksek olasılıkla görülen bir düğüm diğer renk olarak değerlendirilir. İki rejimi ayıran bir eşik değeri vardır. Bu, birçok farklı kuantum durumunun esasen aynı grafik bölmesini temsil ettiği anlamına gelir. QEMC’nin minimize ettiği maliyet fonksiyonu, bağlı düğümlerin bu olasılık eşiğinin zıt taraflarında yer almaya teşvik edecek şekilde inşa edilmiştir; bu da iki renk grubu arasından geçen kenar sayısını artırma eğilimindedir ve dolayısıyla kesiti iyileştirir.

Gerçek ve simüle makinelerde performans testi

Yazarlar QEMC’yi iki cephede test eder: gerçek kuantum işlemcilerde ve kuantum devrelerinin klasik simülasyonlarında. 32 düğüme kadar küçük düzenli grafiklerde (sadece 2 ila 5 kubit kullanarak), IBM süperiletken donanımında çalıştırılan QEMC, exhaustive search ile bulunan en iyi olası yanıtlara eşdeğer veya onlara çok yakın kesitler bulur; rastgele tahminden ve QAOA’ya dayalı önceki kuantum çalışmalardan belirgin şekilde daha iyi performans gösterir. Gürültüsüz simülasyonlarda QEMC, bu küçük grafikler için tutarlı şekilde optimal kesitin %97’sinin üzerinde sonuçlar elde eder. Kodlamanın gücü daha büyük grafiklerde daha da belirgindir: 2.048 düğüme kadar 9-regular grafikte, QEMC’nin klasik simülasyonları ortalama ve en iyi kesitlerde GW’yi birkaç puanla geride bırakır ve farklı yoğunluklardaki 128 düğümlü rastgele grafikte de benzer avantajlar gözlenir.

Hız, sınırlamalar ve kuantum-ilhamlı vaat

Başarısına rağmen QEMC henüz resmi bir kuantum hızlanması sunmuyor. Yaklaşık log N kubit kullandığı için, devrelerinin klasik simülasyonu da kabaca düğüm sayısıyla ölçeklenir ve maliyet fonksiyonunu değerlendirmek için gereken süre kenar sayısıyla artar. Ampirik çalışmalar, GW seviyesindeki performansa ulaşmanın toplam süresinin grafik boyutuyla yaklaşık kare ölçeğinde arttığını öne sürüyor; bu hala birçok problem için pratik sınırlar içinde kalıyor. Bu, QEMC’nin mevcut formunda kuantum üstünlüğünün kanıtı olmaktan çok güçlü bir kuantum-ilhamlı sezgisel yöntem olarak hizmet ettiğini gösterir.

Bu çalışma geleceğe ne ifade ediyor

Uzman olmayan birine ana mesaj şudur: küçük, gürültülü kuantum aygıtları, güçlerine uygun algoritmalar tasarlarsak hâlâ bilimsel olarak faydalı olabilir. Düğüm renklerini sert bit değerleri yerine esnek olasılık aralıklarında kodlayarak, QEMC çok az kubit kullanarak çok büyük ağ problemleriyle başa çıkıyor ve donanım gürültüsüne doğal olarak tolerans gösteriyor. Yöntem kuantum optimizasyon algoritmalarını test etmek için yeni bir kıyas noktası belirliyor ve aynı fikirler temelinde pratik bir klasik algoritma da sunuyor. Daha genel olarak, bilgiyi nasıl kodladığımızı yeniden düşünmenin—sadece daha büyük makineler yapmaktan ziyade—zor hesaplama problemlerini çözmek için umut verici yollar açabileceğini gösteriyor.

Atıf: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Anahtar kelimeler: MaxCut, kuantum optimizasyonu, varyasyonel algoritmalar, graf bölümlendirme, kuantum ilhamlı hesaplama