Kuantum Bilgisayarlar – 6

Ali Fevzi, 29 Kasım 2015

Clay Matemetik Enstitüsü 2000 yılında, halen çözülememiş 7 adet matematik problemi yayınladı. Her biri için, çözene 1 milyon dolar para ödülü koydu. 2010’da bir tanesine çözüm bulundu. Geri kalan 6 tanesi duruyor ve ödül halen geçerli. Çözüm bekleyenlerden bir tanesi, serinin önceki yazılarında bahsettiğimiz, hesaplanabilir zorluk açısından NP-zor (Non-polinomial) problemleri, hesaplanabilir P-zor (Polinomial) problemine indirgeyebilecek bir algoritma var mı? Günümüz bilim dünyası bu soruya yanıt arıyor fakat ödülü kazanmak için değil, mevcut teknolojilerin daha “akıllı” olması ve daha iyi sonuçlar elde etmesini sağlayacak en iyileme (optimizasyon) problemlerini çözebilmek için. Çünkü bu optimizasyon problemlerinin önemli bir kısmı NP-Zor kümesi altında yer almaktadır.

NP-Zor problemler arasından bazıları NP-Tam olarak (NP-Complete) ifade edilir. Bu şekilde ifade edilmesinin sebebi, NP-Tam problemlerin gösterim şekli ile ilgilidir. Diğer tüm NP-Zor problemler, lineer ekleme ve çıkarmalar ile (polinomial zamanda çözülebilecek şekilde), NP-Tam şeklinde gösterilebilmektedir. Çok basit olarak örnekleyecek olursak, Türkiye’nin herhangi bir yerinden Amerika’ya gitmek bizim çözmemiz gereken NP-Zor problemimiz olsun. Bu durumda, İstanbul’dan Amerika’ya gitmeyi, NP-Tam olarak ifade edebiliriz. Çünkü İstanbul’dan Amerika’ya gitmenin bir çözümünü bulabilirsek, Ankara’dan, Bursa’dan, Artvin’den ya da Türkiye’nin herhangi bir yerinden Amerika’ya gitmenin bir çözümünü kolaylıkla bulmuş oluruz. (Önce İstanbul’a git ve Amerika’ya gitme çözümünü kullan diyebiliriz.)

NP-Tam olarak nitelendirilen ve çözüm bulunduğunda tüm NP-Zor problemlere uygulanabilecek en meşhur ve üzerinde en çok araştırma yapılan problem GSP, Gezgin Satıcı Problemidir (TSP- Travelling Salesman Problem). GSP, n adet şehir arasındaki mesafelerin bilindiği durumda, şehirlerin her birine yalnız bir kez uğramak şartıyla, başlangıç noktasına geri dönülmesi esasına dayalı, tur boyunca kat edilen toplam yolun en kısa olduğu şehir sıralamasının (optimal rota) bulunmasının amaçlandığı bir problemdir. Ulaşım ve lojistik uygulamaları, ekip/misyon planlama, araç ve havaalanı rotalama, kuruluş yeri (baz istasyonu) belirleme gibi bir çok problemde geniş bir alanda doğrudan uygulama olanağı olduğu gibi diğer NP-zor problemlerinde çözülmesi için rahatlıkla uyarlanabilir. Problemdeki şehirleri nokta ve aralarındaki yolu da çizgi şeklinde grafiksel olarak gösterebiliriz. Böyle bir graf üzerindeki her noktadan sadece bir kez geçen ve başladığı noktada biten tura Hamilton turu denir. GSP’de amacımız en kısa Hamilton turunu bulmak oluyor. Görünüşte çözümü çok kolay gibi duran bu problemi zorlaştıran, şehir sayısı arttıkça, artan şehir sayısına paralel olarak olası çözüm kümesinin üstsel bir şekilde artıyor olmasıdır. Bunun sonucu olarak, belli bir şehir sayısından sonra, tüm sonuçların tek tek denenip, en uygun sonucun hesaplanabilmesi, günümüz bilgisayarları için imkânsız hale geliyor. Klasik tarz bir bilgisayarda, klasik yöntemlerle, 25 adet bir şehir için bile, problemin çözümü tabloda (tablo 1) görüleceği gibi mümkün olmamaktadır.

 

Bilgisayarların aksine, 25 adet şehir arasında, güzel bir grafik gösterimi yardımıyla, en kısa rotayı, bir insan, bir günden çok daha kısa bir sürede bile bulabilir. Çünkü insan, tüm ihtimaller arasından, milyonlarca gereksiz alternatifi hiç düşünmez bile. Zeki yaratılmış bir varlık olduğu için, sadece en olası çözümleri üzerinde yoğunlaşır. Bir bilgisayar için durum böyle değildir. Tüm ihtimalleri denemek ve değerlendirmek zorundadır. Bilgisayarın tüm ihtimaller üzerinde değil, sadece sonuca yönelik ihtimaller üzerinde araştırma yapabilmesi için biraz “akıllı” olması gerekiyor. Sadece hızlı çalışması yeterli olmuyor. Aynı zamanda “bilinçli” çalışması da gerekiyor. Henüz insan beynini taklit etmekte yetersiz olan bilim insanları, bu engeli aşabilmek için, araştırmalarını, doğada var olan ve çalışan doğal sistemlere ve bu sistemlerde cereyan eden olaylara yöneltmişlerdir. Çünkü, tabiatta var olan karmaşık sistemler, doğal optimizasyon problemleri, canlı yapılar tarafından, rahatlıkla çözüldüğü gözlenmektedir.

“Doğada maksimum ya da minimum duyusunun bulunmadığı hiç bir olay yoktur”
Leonhard Euler (Matematikçi)

Öngörülen amaçları gerçekleştirmek için, zaman dâhil sınırlı kaynakları, maksimum kazanç ve minimum zarar ile kullanabilmek “zekâ” gerektirir. Sevk-i ilahi olarak, optimizasyon problemlerini çözmeyi becerebilen (yüksek bir zekâya işaret eden), canlılardan ve fenomenlerden yola çıkılarak oluşturulan optimizasyon yöntemlerine yada algoritmalara sezgisel yöntem yada algoritmalar denmektedir. Bu algoritmaların geliştirilmesi, yapay zekâ bilim dalında, çok geniş bir araştırma konusu olarak yer almaktadır. Sürü halinde yaşayan hayvanların göstermiş olduğu zeki davranışlardan esinlenerek oluşturulan; Karınca koloni optimizasyonu, arı koloni algoritması, genetik çeşitliliği sağlayan operatörlere dayalı; Genetik algoritmalar, metallerin ısıl işleminde ortaya çıkan minimum enerjili konfigürasyona erişimi temel alan yapay ısıl işlem algoritması (Tavlama benzetimi) yada bağışıklık sisteminden yola çıkılan yapay bağışıklık algoritmasını örnek olarak verebiliriz. Bunlardan hiçbiri şuan için P=NP denklemine çözüm olamasa da, pek çok NP probleme kısa sürede uygun bir sonuç bulabilmektedir.

D-Wave firması, geçtiğimiz son 3 senedir satışa sunduğu “kuantum bilgisayarlar” ile klasik bilgisayarlar üzerinde çalışan, yukarıda saydığımız çözüm algoritmalarına alternatif olabilecek, yeni kuantum yaklaşımlar ve algoritmalara da kapı açmış oldu. Henüz emekleme aşamasında olan kuantum bilgisayarlar üzerinde, bu konuda ilk denemeleri 2013 yılında bilgisayar bilimci Catherine McGeoch yaptı. 439 qbit ile işlem yapan, Vesuvius 5 çipli D-WaveTwo sistemi ile CPLEX, METSlib Tabu, Akmaxsat gibi yapay zeka programları çalıştıran Intel Xeon E5-2690 işlemcinin, GSP problemine optimum çözüm bulma hızlarını karşılaştırdı. Klasik bilgisayarın yarım saatte çözüm bulabildiği bu NP-zor probleme, yarım saniyede cevap veren bilgisayar (4000 kat daha hızlı) gelecek adına ümit verdi. Fiyat kıyaslaması yapıldığında 6666 kat daha pahalı olan bir kuantum bilgisayardan beklenen performans adına henüz kendi yeterliliğini tüm problemlerde ispat edemese de, fikir olarak bile ortaya atılalı 20 yıl olan bir teknoloji için büyük başarı olarak kabul edildi.