Bilgisayar bilimcileri, kuantum bilgisayarların klasik muadillerinden çok daha hızlı çözebileceği yeni bir problem türü buldular.
1994 yılında bir matematikçi, sıradan bir klasik bilgisayarın yapamayacağı bir şeyi kuantum bilgisayarının nasıl yapabileceğini buldu. Çalışma, prensipte kuantum mekaniğinin kurallarına dayanan bir makinenin, çok büyük bir sayıyı verimli bir şekilde asal çarpanlarına ayırabileceğini ortaya koydu– bu işlem klasik bilgisayarlar için o kadar zor bir iş ki, sayıların asal çarpanlarını bulma problemi, günümüzün internet güvenliğinin temelini oluşturuyor.
Bunu bir iyimserlik dalgası izledi. Araştırmacılar, çok çeşitli farklı sorunları çözebilecek kuantum algoritmaları icat edebileceğimizi düşündüler.
Ama ilerleme durdu. Carnegie Mellon Üniversitesi’nden Ryan O’Donnell, “Biraz aylak bir gidişat oldu. İnsanlar, ‘Bu harika, eminim başka türlü harika algoritmalar alacağız’ dediler. Hayır” dedi. Bilim adamları, NP adı verilen standart bir kümenin içinden yalnızca tek, dar bir problem sınıfı için çarpıcı hızlanmalar keşfettiler; bu, çarpanlara ayırma gibi verimli bir şekilde doğrulanabilir çözümlere sahip oldukları anlamına geliyordu.
Yaklaşık otuz yıldır durum bu şekildeydi. Ardından Nisan ayında araştırmacılar, kuantum bilgisayarın klasik olandan üstel olarak daha hızlı çözmesi beklenen, temelde yeni bir tür problem icat etti. Bu problem, karmaşık bir matematiksel sürecin girdilerini, yalnızca karmaşık çıktılarına dayalı olarak hesaplamayı içerir. Sorunun tek başına mı yoksa diğer pek çok yeni sınırda bir ilk mi olduğu henüz belirlenmedi.
Massachusetts Institute of Technology’de bilgisayar bilimcisi olan Vinod Vaikuntanathan, “Bir heyecan duygusu var. Birçok insan orada başka ne olduğunu düşünüyor” dedi.
Bilgisayar bilimcileri, onları temsil eden matematiksel modelleri inceleyerek kuantum bilgisayarların neyi daha iyi yaptığını anlamaya çalışıyorlar. Çoğu zaman, “oracle” adı verilen idealleştirilmiş bir hesaplama makinesiyle eşleştirilmiş bir kuantum veya klasik bilgisayar modeli hayal ederler. “Oracle”lar, basit matematiksel fonksiyonlar veya bilgisayar programları gibidir, girdi alır ve önceden belirlenmiş bir çıktı verir.
Diyelim ki bu periyodik Oracle’lardan birine sahipsiniz ve spesifik periyodu bilmiyorsunuz. Yapabileceğiniz tek şey, sayıları beslemek ve çıktısını görmek. Bu kısıtlamalarla, bir bilgisayar istenen periyodu ne kadar hızlı bulabilir? 1993 yılında, o zamanlar Montreal Üniversitesi’nden Daniel Simon, bir kuantum algoritmasının, yakından ilişkili bir problemin cevabını herhangi bir klasik algoritmadan üstel olarak daha hızlı hesaplayabildiğini buldu.
Periyodik Oracle’lar, bir kümedeki her sayı için aynı çıktıyı döndürür.
Sonuç, Simon’ın kuantum bilgisayarlar için dramatik üstünlüğün beklenebileceği ilk ipuçlarından birini belirlemesini sağladı. Ancak makalesini önde gelen bir konferansa sunduğunda reddedildi. Bununla birlikte makale, konferansın program komitesinin genç bir üyesini ilgilendirdi- o sırada New Jersey’deki Bell Laboratories’de bulunan Peter Shor. Eğer varsa, bir Oracle’ın periyodunu hesaplamak için Simon’ın algoritmasını uyarlayabileceğini keşfetti. Ardından, periyodik bir Oracle’a benzer şekilde davranan bir denklemi çözmek için algoritmayı bir kez daha uyarlayabileceğini fark etti ve bu asal çarpanlarına ayırmayı periyodik olarak tanımlayan denklemdi.
Shor’un keşifi tarihi bir milat taşı oldu. Keşfettiği kuantum algoritması, devasa sayıları hızla asal çarpanlarına indirgeyebiliyordu, bu bilinen hiçbir klasik algoritmanın yapabileceğibir şey değildi. Takip eden yıllarda, araştırmacılar başka verimli kuantum algoritmaları keşfettiler. Shor’un algoritması gibi bazıları üstel bir avantaj bile sağladı, ancak hiç kimse periyodik olmayan herhangi bir NP probleminde dramatik bir kuantum avantajı kanıtlayamadı. Bazılarında, Shor’un algoritması gibi, algoritma üstel bir avantaj sağladı, ancak hiç kimse periyodik olmayan herhangi bir NP probleminde dramatik bir kuantum avantajı kanıtlayamadı.
Bu ilerleme eksikliği, iki bilgisayar bilimcisi olan Austin, Texas Üniversitesi’nden Scott Aaronson ve Letonya Üniversitesi’nden Andris Ambainis’i bir gözlem yapmaya yöneltti. Kuantum avantajının kanıtları her zaman, periyodiklik gibi bir tür rastgele olmayan yapıya sahip Oracle’lara bağlı görünüyordu. 2009’da rastgele veya yapılandırılmamış NP problemlerinde dramatik hızlanmaların olamayacağını tahmin ettiler. Kimse bir istisna bulamadı.
Onların varsayımları, kuantum bilgisayarların güçlerine bir sınır koydu. Ancak, yalnızca belirli bir tür yapılandırılmamış NP sorunu için- evet veya hayır yanıtı olanlar için- dramatik bir hızlanma olmadığı söylendi. Bir problem, arama problemi olarak bilinen daha spesifik, nicel cevapları bulmayı içeriyorsa, bu varsayım geçerli değildi.
Video: Kuantum bilgisayarlar yeni nesil süper bilgisayarlar değil- tamamen başka bir şey. Potansiyel uygulamaları hakkında konuşmaya başlamadan önce, kuantum hesaplama teorisini yönlendiren temel fiziği anlamamız gerekiyor.
Bunu akılda tutarak, NTT Social Informatics Laboratories’den araştırmacılar Takashi Yamakawa,NTT Research ve Princeton Üniversitesi’nden Mark Zhandry, 2005 yılında Oded Regev tarafından tanıtılan belirli bir arama problemini denemeye karar verdiler.
Hepsi aynı yöne bakan bir dizi rüzgâr gülü hayal edin. Her birine ölçülü bir itme verin, sonra sert bir rüzgârın yönlerini etkilemesine izin verin. Regev, nihai yönlerine dayanarak hepsinin başlangıçta nereye işaret ettiğini belirlemek istedi. Bunun gibi problemler “hatalarla öğrenme” olarak adlandırılır, çünkü itme ve rüzgâr orijinal yönde rastgele bir hata kaynağı gibi davranır. Hem klasik hem de kuantum algoritmaları için bu tarz problemleri çözmenin zor olduğuna dair kanıtlar bulunmakta.
Yamakawa ve Zhandry kurulumda ince ayar yaptı. Başlangıç vuruşlarının gücünü değiştirerek onları daha öngörülebilir hale getirdiler. Ayrıca rüzgârın rastgele bir oracle tarafından belirlenmesine neden oldular, böylece bazı durumlarda daha da rastgele ama diğerlerinde tamamen uykudaydı.
Bu değişikliklerle araştırmacılar, bir kuantum algoritmasının başlangıçtaki yönü verimli bir şekilde bulabileceğini keşfettiler. Ayrıca herhangi bir klasik algoritmanın üstel olarak daha yavaş olması gerektiğini kanıtladılar. Shor gibi, daha sonra algoritmalarını problemin gerçek dünyadaki bir versiyonunu çözmek için uyarladılar ve bu durum oracle’ı gerçek bir matematiksel denklemle değiştirdi.
Bilgisayar bilimcileri hala sorunu anlamlandırmak ve geliştirmek için çalışıyorlar. Vaikuntanathan bunu veri sıkıştırma yaparken ortaya çıkan farklı bir durumla karşılaştırır: Bilgi sıkıştırılırken, yanlışlıkla iki bit aynı yere sıkıştırılarak üzerine yazılabilir. Bu çarpışmaları önleyebilmek adına önceden tahmin etme sorunu bu sorunla biraz benzerlik taşıyor. Vaikuntanathan “Bu, temelde buna benzeyen bir problemler sınıfı. Belki bu problemler kuantum kullanılarak çözülebilir” dedi.
Yenisi gibi yapılandırılmamış bir sorunun, kuantum bilgisayarların günümüzün acemi sürümlerinde bile çözülebileceği ve böylece onları test etmek için bir araç sağlayabileceği umutları vardı. Buradaki düşünce, yapılandırılmamış sorunların programa daha az kaynak götürebileceği veya zaten rastgele oldukları için gürültüye karşı daha az duyarlı olabileceğiydi. “Garip bir sorun. Bunu tanımlamayı düşünmemiştim. Ama geçmişe bakıldığında, bazı çok güzel özellikleri var,” dedi Aaronson.
Sonuç, yapılandırılmamış bir NP probleminde dramatik bir kuantum avantajının ilk örneğini sağlar. Kuantum dünyasının pratik olarak çözülemez konumundan çözülebilir hale getirilebilir başka birçok problem olabilir mi? Şimdi böyle düşünmek için daha fazla neden var.
O’Donnell, “Kuantum bilgisayarların ne tür problemlerde iyi olabileceğine dair inançlarımızı biraz alt üst etti” dedi.
Çeviren: Hüseyin Türker
Editör: Berfu Deniz Kara
Kaynak:
Quantum Algorithms Conquer a New Kind of Problem
Yoruma kapalı.