1994 yılında bir matematikçi, sıradan bir klasik bilgisayarın yapamayacağı bir şeyi kuantum bilgisayarına nasıl yaptıracağını buldu. Çalışma, prensipte, kuantum mekaniğinin kurallarına dayanan bir makinenin, büyük bir sayıyı verimli bir şekilde asal faktörlerine ayırabildiğini ortaya çıkardı; klasik bir bilgisayar için o kadar zor bir görev ki, günümüzün internet güvenliğinin çoğunun temelini oluşturuyor.
Bunu bir iyimserlik dalgası izledi. Araştırmacılar belki de çok çeşitli sorunları çözebilecek kuantum algoritmaları icat edebileceğimizi düşündüler.
Ancak ilerleme durdu. "Biraz sıkıntılı bir gidişat oldu" dedi Ryan O'Donnell Carnegie Mellon Üniversitesi'nden. “İnsanlar 'Bu harika, eminim ki başka harika algoritmalar da elde edeceğiz.' dediler. Hayır." Bilim adamları, standart bir dizi içinden yalnızca tek ve dar bir sorun sınıfı için dramatik hızlanmalar keşfettiler NP denirBu, faktoring gibi verimli bir şekilde doğrulanabilir çözümlere sahip oldukları anlamına geliyor.
Yaklaşık otuz yıldır durum böyleydi. Daha sonra Nisan ayında araştırmacılar icat Bir kuantum bilgisayarının klasik bir bilgisayardan katlanarak daha hızlı çözebilmesi gereken temelde yeni bir sorun türü. Yalnızca karışık çıktılara dayalı olarak karmaşık bir matematiksel sürecin girdilerinin hesaplanmasını içerir. Sorunun tek başına mı yoksa başka birçok yeni sınırda ilk mi olduğu henüz belirlenmedi.
"Bir heyecan var" dedi Vinod VaikuntanathanMassachusetts Teknoloji Enstitüsü'nde bilgisayar bilimcisi. "Birçok insan orada başka neler olduğunu düşünüyor."
Bilgisayar bilimcileri, onları temsil eden matematiksel modelleri inceleyerek kuantum bilgisayarların neyi daha iyi yaptığını anlamaya çalışırlar. Çoğu zaman, kuantum veya klasik bir bilgisayar modelinin, kehanet adı verilen idealleştirilmiş bir hesaplama makinesiyle eşleştiğini hayal ederler. Oracle'lar, bir girdiyi alıp önceden belirlenmiş bir çıktıyı veren basit matematiksel işlevlere veya bilgisayar programlarına benzer. Rastgele bir davranışa sahip olabilirler; girdi belirli bir rastgele aralığa (mesela 12'den 67'ye) düşerse "evet", değilse "hayır" verirler. Ya da periyodik olabilirler, böylece 1 ila 10 arasındaki bir giriş "evet" sonucunu verir, 11 ila 20 arasındaki bir giriş "hayır" sonucunu verir, 21 ila 30 arasındaki bir giriş tekrar "evet" sonucunu verir vb.
Diyelim ki bu periyodik kehanetlerden birine sahipsiniz ve periyodu bilmiyorsunuz. Yapabileceğiniz tek şey, sayıları beslemek ve ne çıktısını görmek. Bu kısıtlamalarla bir bilgisayar periyodu ne kadar hızlı bulabilir? 1993 yılında, o zamanlar Montreal Üniversitesi'nde olan Daniel Simon, bir kuantum algoritmasının, yakından ilişkili bir sorunun cevabını herhangi bir klasik algoritmadan katlanarak daha hızlı hesaplayabildiğini buldu.
Sonuç, Simon'un kuantum bilgisayarlardan dramatik üstünlüğün nerede beklenebileceğine dair ilk ipuçlarından birini belirlemesini sağladı. Ancak makalesini önde gelen bir konferansa sunduğunda reddedildi. Ancak makale, konferansın program komitesinin kıdemsiz bir üyesinin ilgisini çekti: Peter ŞorO sırada New Jersey'deki Bell Laboratuvarlarında çalışıyordu. Shor, Simon'un algoritmasını, eğer varsa, bir kehanetin periyodunu hesaplamak için uyarlayabileceğini keşfetti. Daha sonra, periyodik kehanete benzer şekilde davranan bir denklemi çözmek için algoritmayı bir kez daha uyarlayabileceğini fark etti: periyodik olan çarpanlara ayırmayı tanımlayan denklem.
Shor'un sonucu tarihiydi. Keşfettiği kuantum algoritması, devasa sayıları hızlı bir şekilde kendilerini oluşturan asal çarpanlara indirgeyebiliyordu; bu, bilinen hiçbir klasik algoritmanın yapamayacağı bir şeydi. Takip eden yıllarda araştırmacılar başka etkili kuantum algoritmaları keşfettiler. Shor'un algoritması gibi bazıları üstel avantaj bile sağladı, ancak hiç kimse periyodik olmayan herhangi bir NP probleminde dramatik bir kuantum avantajını kanıtlayamadı.
Bu ilerleme eksikliği iki bilgisayar bilimcisini, Scott Aaronson Austin'deki Teksas Üniversitesi'nden ve Andris Ambainis Letonya Üniversitesi'nden bir gözlem yapmak üzere. Kuantum avantajının kanıtları her zaman periyodiklik gibi rastgele olmayan bir yapıya sahip kehanetlere bağlı görünüyordu. 2009 yılında onlar conjectured Rastgele veya yapılandırılmamış NP problemlerinde dramatik hızlanmaların olamayacağını. Hiç kimse bir istisna bulamadı.
Onların varsayımları kuantum bilgisayarların gücüne bir sınır koyuyordu. Ancak yalnızca, belirli bir tür yapılandırılmamış NP sorunu (evet veya hayır yanıtı olanlar) için dramatik bir hızlanma olmadığını söyledi. Arama problemi olarak bilinen, daha spesifik, niceliksel yanıtlar bulmayı içeren bir sorun varsa, varsayım geçerli değildi.
Bunu akılda tutarak, araştırmacılar Takashi Yamakawa NTT Sosyal Bilişim Laboratuvarları ve Mark Zhandry NTT Araştırma ve Princeton Üniversitesi'nden oluşan bir ekip, 2005 yılında tanıtılan belirli bir arama problemini denemeye karar verdi. Oded Regev.
Hepsi aynı yöne bakan bir dizi rüzgar gülü hayal edin. Her birini ölçülü bir şekilde itin, ardından sert bir rüzgarın yönlerini etkilemesine izin verin. Regev, nihai yönlerine göre hepsinin başlangıçta nereye işaret ettiğini belirlemek istedi. Bunun gibi sorunlara "hatalarla öğrenme" adı verildi çünkü itme ve rüzgar, orijinal yönde rastgele bir hata kaynağı gibi hareket ediyordu. Hem klasik hem de kuantum algoritmalar için çözmenin zor olduğuna dair kanıtlar var.
Yamakawa ve Zhandry kurulumda ince ayar yaptı. Başlangıç itmelerinin gücünü değiştirerek onları daha öngörülebilir hale getirdiler. Ayrıca rüzgarın rastgele bir kehanet tarafından belirlenmesine de neden oldular, böylece rüzgar bazı durumlarda daha da rastgele olurken diğerlerinde tamamen hareketsiz kaldı.
Bu değişikliklerle araştırmacılar, bir kuantum algoritmasının başlangıç yönünü verimli bir şekilde bulabileceğini keşfettiler. Ayrıca herhangi bir klasik algoritmanın üstel bir faktör kadar yavaş olması gerektiğini de kanıtladılar. Shor gibi onlar da daha sonra algoritmalarını problemin gerçek dünyadaki bir versiyonunu çözecek şekilde uyarladılar; bu versiyon, kehaneti gerçek bir matematiksel denklemle değiştirdi.
Bilgisayar bilimcileri hala sorunu anlamak ve üzerine inşa etmek için çalışıyorlar. Vaikuntanathan, bunu veri sıkıştırma sırasında ortaya çıkan farklı bir bitle karşılaştırıyor: Bilgi sıkıştırılırken, iki bit yanlışlıkla aynı yere sıkıştırılabilir ve bunların üzerine yazılabilir. Bu çarpışmaları önceden tahmin ederek onlardan kaçınabilmeniz sorunu bazı benzerlikler taşıyor. "Bu, temelde buna benzeyen bir sorun sınıfıdır" dedi. “Belki bu sorunlar kuantumsal olarak çözülebilir.”
Yenisi gibi yapılandırılmamış bir sorunun, kuantum bilgisayarların günümüzün acemi versiyonlarında bile çözülebileceğine ve böylece onları test etmek için bir araç sağlayabileceği yönünde umutlar vardı. Buradaki düşünce, yapılandırılmamış problemlerin programlanması için daha az kaynak gerekebileceği veya zaten rastgele oldukları için gürültüye karşı daha az duyarlı olabileceği yönündeydi. Ancak şu ana kadar yeni sorun, mevcut kuantum bilgisayarların çözemeyeceği kadar ileri düzeyde görünüyor. “Bu tuhaf bir sorun. Bunu tanımlamayı düşünmemiştim" dedi Aaronson. "Fakat geriye dönüp baktığımızda çok güzel özelliklere sahip olduğunu görüyoruz."
Sonuç, yapılandırılmamış bir NP probleminde dramatik kuantum avantajının ilk örneğini sağlar. Kuantum dünyasının pratik olarak çözülemez durumdan çözülebilir duruma geldiği başka birçok sorun olabilir mi? Artık böyle düşünmek için daha fazla neden var.
O'Donnell, "Bu, kuantum bilgisayarların ne tür sorunlarda iyi olabileceğine dair inançlarımızı bir şekilde altüst etti" dedi.
