Bazı arkadaşlarınızla bir labirenti ziyaret ettiğinizi hayal edin. İçeri girdikten kısa bir süre sonra çıkıştan çıkıyorsunuz ve arkadaşlarınızın çıkması için saatlerce bekliyorsunuz. Doğal olarak, gittiğiniz yolu soruyorlar - elbette adımlarınızın izini sürerek onlara yolu gösterebilirsiniz, değil mi?

Kuantum fiziğinin garip yasalarıyla yönetilen bir dünyada durum böyle değil. Yirmi yıl önce, kuantum hesaplama araştırmacıları, bu yasaları, belirli bir tür matematiksel labirentte sıradan bir klasik bilgisayarda çalışan herhangi bir algoritmadan çok daha hızlı geçmek için kullanan bir algoritma geliştirdiler. Ancak bu hızlanmanın bir bedeli var: Hızlı kuantum algoritması çıkışı buluyor ama oraya nasıl geldiği hakkında hiçbir fikri yok.

Araştırmacılar uzun zamandır bu takasın kaçınılmaz olup olmadığını merak ettiler. Yolu unutmadan çıkışı hızlıca bulmak gerçekten imkansız mı?

"Bu soruyu sorma ihtiyacı duyman bile akıllara durgunluk veriyor" dedi. Matthew Coudron, Gaithersburg, Maryland'deki Ulusal Standartlar ve Teknoloji Enstitüsü'nde bir bilgisayar bilimcisi.

Geçen Kasım ayında, Coudron ve iki meslektaşı uzun süredir devam eden bu sorunu çözmek için büyük bir adım attılar: kanıtladı hızlı kuantum algoritmalarının geniş ve doğal bir sınıfındaki hiçbir algoritmanın, kaynaklı ağaç grafiği adı verilen bu özel labirentte bir yol bulamayacağı. Sonuçlar, körü körüne tahmin etmeyen herhangi bir varsayımsal yol bulma algoritmasının, başarılı olma şansına sahip olmak için girişin izini geçici olarak kaybetmesi gerektiğini gösteriyor. Unutmak kaçınılmaz gibi görünüyor.

“Bunu gerçekten kanıtlayabileceklerini tahmin etmemin hiçbir yolu yok” dedi. Simon ApersParis'teki Bilgisayar Bilimlerinin Temelleri Araştırma Enstitüsü'ndeki Ulusal Bilimsel Araştırma Merkezi'nden bir kuantum hesaplama araştırmacısı olan Dr.

Kuantum Artışı

Kuantum bilgisayarlar, güçlerini kısmen, klasik bir bilgisayarın bireysel olarak dikkate alması gereken birçok seçeneği aynı anda keşfetmelerine olanak tanıyan süperpozisyon olarak bilinen bir olguya borçludur. Ama o o kadar basit değil zaman kazanmak için aynı anda birden fazla hesaplama yapmak gibi. Seçimlerin üst üste gelmesinin sonucunu kontrol etmek asla sonuçların üst üste binmesini ortaya çıkarmaz - bunun yerine, her biri farklı bir olasılığa sahip olan olası sonuçlardan yalnızca birini elde edersiniz. Kuantum algoritmaları, bu olasılıklara yapılan katkıların, bir havuzun yüzeyindeki dalgalar gibi birbirini etkileyerek, doğru yanıtı alma olasılığını artırırken diğer tüm sonuçların olasılığını azaltabileceği gerçeğine dayanır.

Müdahalenin doğru bir şekilde çalışması gerektiğinden, her hesaplama görevi bir kuantum hızlandırmaya uygun değildir ve gerçekten de araştırmacılar hala çalışıyor Kuantum algoritmalarının yardımcı olabileceği, kuantum hesaplamanın ilk kez önerilmesinden onlarca yıl sonra. Ama bazı kayda değer başarılar elde ettiler. 1994 yılında Peter Shor bir kuantum algoritması büyük sayıları çarpanlarına ayırmak için - klasik bilgisayarlar için görünürdeki zorluğu modern kriptografinin çoğunun temelini oluşturan bir görev. Shor'un algoritması, sayıları o kadar hızlı bir şekilde çarpanlarına ayırabilir ki, bilinen tüm klasik algoritmalar pratik olarak işe yaramaz hale gelir.

1996'da bilgisayar bilimcisi Lov Grover, ikinci bir potansiyel olarak pratik örnek buldu: kuantum algoritması çok genel bir arama problemi için, birçok özdeş kutudan birinin içine gizlenmiş tek bir öğeyi bulmaya benzer.

Apers, "Klasik olarak, yapabileceğiniz şey rastgele bir tanesini denemek ve iyi olup olmadığına bakmak, sonra tekrar deneyip iyi olup olmadığına bakmak ve iyi bir unsur bulana kadar denemeye devam etmektir" dedi. Bu yaklaşım kutu sayısıyla orantılı olarak zaman alır. Bu sayıyı 100 ile çarptığınızda arama 100 kat daha yavaş olacaktır.

Bir kuantum algoritması ile daha iyisini yapabilirsiniz. Grover, tüm kutuların üst üste binmesini ayarlarsanız, algoritmanın sonunda doğru kutuyu seçeceğini pratik olarak garanti etmek için girişimden yararlanabileceğinizi kanıtladı. Tüm süreç, kutu sayısının kareköküyle orantılı olarak zaman alır: Bu sayıyı 100 kat artırmak, çalışma süresini yalnızca 10 kat artırır.

Grover'ın algoritması, kuantum süperpozisyonunun değerini oldukça basit bir şekilde gösteriyordu, ancak elde ettiği hızlanma nispeten mütevazıydı; en iyi klasik algoritmaların ulaşamayacağı görevler aynı zamanda Grover'ın algoritmasını da sekteye uğratırdı. Shor'un çarpanlara ayırma algoritması, kuantum bilgisayarlarla klasik bilgisayarların yetenekleri arasındaki dramatik uçurumun bir görüntüsünü sunmuştu. Kıvırcık'ın arama probleminin çarpanlara ayırmaya benzer bir çeşidi var mıydı; klasik bilgisayarlar için pratik olarak zorlu ama kuantum bilgisayarlar için kolay mıydı?

1990'ların sonlarında, araştırmacılar bu soruyu grafiklerle ilgili bir soru olarak yeniden formüle ederek keşfetmeye başladılar - noktalar ağları veya çizgilerle birbirine bağlanan, kenar adı verilen düğümler. Herhangi bir arama problemi, başlangıç ​​noktasını temsil eden bir düğüm, varış noktasını temsil eden başka bir düğüm ve yol boyunca her adımda olası seçimleri temsil eden kenarlar ile grafik teorisi dilinde çerçevelenebilir.

Örneğin, Grover'ın problemi, her düğümün diğer tüm düğümlere bağlı olduğu bir grafik aramaya karşılık gelir (çünkü kutuları herhangi bir sırada açabilirsiniz). Belirli bir arama problemi için farklı klasik algoritmalar, karşılık gelen grafiği her seferinde bir düğüm keşfetmek için farklı stratejiler anlamına gelirken, kuantum algoritmaları süperpozisyonda birden fazla kenar boyunca hareket edebilir.

Dallanma

2002 yılında, bilgisayar bilimcilerinden oluşan bir ekip nihayet tespit bir kuantum algoritmasının kolayca çözebileceği, klasik olarak zorlu bir arama problemi. Ağaç adı verilen basit bir grafikle başladılar. Tek bir "kök" düğümden başlayan bir ağaç grafiği, "yapraklar" adı verilen son bir düğüm katmanında sona ermeden önce birçok kez dallanır. Ekip, birbirinin aynı iki ağacı alıp, onları yapraklar birbirine bakacak şekilde konumlandırarak ve ardından bir ağaçtaki her bir yaprağı diğerindeki iki yaprağa rastgele bir işlem kullanarak "kaynatmayı" hayal etti. Daha sonra şu soruyu sordular: Kaynaklı ağaç grafiğinin bir kökünden başlayarak diğerine giden yolu bulabilir misiniz?

Grafiğe kuşbakışı bakmadan, bu arama problemini çözmeye çalışan herhangi bir klasik algoritma, grafiğin orta katmanlarına ulaştıktan sonra umutsuzca kaybolacaktır - tüm kenarlar aynı görünür ve ileriyi gösterenleri ayırt etmenin hiçbir yolu yoktur. geriye doğru gidenler. Bir algoritma yanlışlıkla çıkış düğümüne rastlayabilir, ancak etrafta dolaşmak için harcadığı ortalama süre, ağaçtaki katmanların sayısıyla katlanarak artar.

2002 makalesinin yazarları, basit bir kuantum algoritmasının - süperpozisyonda birçok yolu izleyerek grafik boyunca eşit şekilde yayılan bir "kuantum yürüyüşü" - çıkışa giden yolu çok daha hızlı bulabileceğini kanıtladı. Bunun nedeni, kaynaklı ağaç grafiğinin simetrik düzeninin, akışı ileri yönde yoğunlaştıran yollar arasında girişime yol açmasıdır. Çıkış düğümü, "algoritmanın bir odak noktası gibidir" dedi. Alexander Belov, Letonya Üniversitesi'nde bir bilgisayar bilimcisi.

Bu kuantum yürüyüş algoritmasının, yalnızca katman sayısıyla orantılı olan zamanda çıkışta birleşmesi için iyi bir şans var. Bu, herhangi bir klasik algoritmadan katlanarak daha hızlı olmasını sağlar - Shor'un faktoring algoritmasıyla karşılaştırılabilir bir hızlanma. Ancak kuantum hızlanmasına neden olan girişim, algoritmanın çıkışa giderken kat ettiği yolların tüm kayıtlarını da siler.

Araştırmacılar, her iki dünyanın da en iyisini elde etmenin bir yolu olup olmadığını merak ettiler - girişten çıkışa giden yolu tanımlayan hızlı bir algoritma.

"Eğer bir şekilde çıkışı bulan temel kuantum yürüyüşü ise, bu işe yaramayacak" dedi. Andrew Childs2002 tarihli makalenin yazarlarından biri olan ve Coudron ile yeni sonuç üzerinde çalışan Maryland Üniversitesi, College Park'ta bir bilgisayar bilimcisi. "Ama belki bir şekilde onu güçlendirebilirsin."

Çorbalamak

Soruna ilk yaklaşanlardan biri Ansis Rosmanis, şu anda Nagoya Üniversitesi Matematik Enstitüsü'nde bir bilgisayar bilimcisi. 2010 tarihli bir makalede, Rosmanis bir algoritma sınıfı Standart kuantum yürüyüş algoritmasını nerede olduklarının hatırasıyla tamamlayan "kuantum yılan yürüyüşleri" adını verdi.

Standart kuantum yürüyüş algoritması grafik boyunca akarken, bir sonraki adımı yalnızca şu anda nerede olduğuna bağlıdır - oraya nasıl geldiği önemli değildir. Rosmanis'in yılan yürüyüşlerinde ise aksine, geleceği tahmin etmek için geçmişi bilmeniz gerekir. Spesifik olarak, yılan yürüyüşünün evrimi, yürüyüşün daha önce geçtiği bitişik düğüm dizileri olan "yılanlar" tarafından belirlenir. Diğer açılardan, bu yılanların uzunluğunun yürüyüş boyunca nasıl değiştiği konusunda farklılık gösteren birçok yılan yürüyüşü çeşidi vardır.

Rosmanis, birden fazla yılanın süperpozisyonlarını kullanan kuantum yılan yürüyüşlerinin, yörüngelerini hatırlamalarına rağmen yine de yararlı girişim sergileyebileceğini ve bazı yılan yürüyüşlerinin prensipte çıkışa giden bir yol bulabileceğini gösterdi. Ancak bu kadar hızlı sonuç veren belirli bir yılan yürüyüşü algoritması bulamadı ve böyle bir algoritmanın var olmadığını da kanıtlayamadı. Yılan yürüyüşleri umut verici görünüyordu ama tespit edilemeyecek kadar kaygandı. Rosmanis'in çalışması neredeyse on yıl boyunca yol bulma sorununa ilişkin son söz oldu.

Ardından 2019'da Coudron, kaynaklı ağaç grafiğiyle farklı bir bağlamda karşılaştı: O ve bir meslektaşı kanıtladı çıkışı bulan tüm kuantum yürüme algoritmalarının, diğer problemler için üstel kuantum hızlanmaları sağladığı bilinen algoritmalar arasında evrensel bir özelliğin bulunmadığını. Sonuç, doğrudan yol bulma ile ilgili değildi, ancak Coudron, tüm kaynaklı ağaç grafiği algoritmalarının özellikleri hakkındaki bu kapsamlı ifadeyi kanıtlamasına izin veren matematiksel tekniklerin, yılanın yürüyüp yürümediği (veya yürüdüğü) sorusunu çözmeye de yardımcı olabileceğinden şüphelenmeye başladı. diğer algoritmalar) bir yol bulabilir. O yıl Maryland'e taşındıktan sonra, bu sorunu kesin bir şekilde çözmeyi umarak Childs ile bir işbirliği kurdu.

Childs, Coudron ve lisansüstü öğrencileri Emin Şiraz Gilani problemin kapsamını sınırlamak için iki varsayımda bulunarak başladı. İlk olarak, çıkışta tökezleme umuduyla grafikteki rastgele noktalara ışınlanmaya çalışacak tuhaf algoritmaları görmezden gelmeye karar verdiler. Bu strateji, istismar edilecek bir aksaklık için etrafta dolaşarak bir video oyununu yenmeye çalışmak gibidir - belki teknik olarak mümkün, ancak sorunun ruhuna aykırı. Büyük grafiklerde doğru noktaya gelme olasılığı çok düşük olduğundan, bu tür davranışların yardımcı olabileceğini hayal etmek de zor. Rastgele sıçrayan algoritmaları göz ardı etmek, yazarların "gerçek" algoritmalar olarak adlandırdığı geriye kalan algoritmaları analiz etmeyi kolaylaştırdı - bunlar arasında Rosmanis'in yılan yürüyüşü algoritmaları ve belki de henüz kimsenin keşfetmediği diğerleri vardı.

Yazarların ikinci, daha sağlam varsayımı, hızlı bir yol bulma algoritmasının "köklü" kalacağı, yani girişin izini kaybetmeden çıkış düğümüne giden bir yol oluşturacağıydı. Birçok yılan yürüyüşü köklüdür, ancak prensipte köksüz bir yılan yürüyüşünün çıkışa giden bir yol bulması mümkündür - giriş düğümünden ayrılması ve daha sonra hem girişi hem de çıkışı bulması gerekir.

Üç araştırmacı, her gerçek köklü kuantum algoritması için, gözlemlenebilir davranışını taklit edecek klasik bir algoritma hazırlayabileceklerini kanıtladı. Hiçbir klasik algoritmanın çıkışı hızlı bir şekilde bulamayacağını da kanıtlayabildikleri için, bu, olası kuantum yol bulma algoritmalarının bu geniş sınıfını elemek için yeterliydi. Gerçek köklü algoritmalar, labirentte bir yol bulmaya yetecek kadar müdahale toplayamaz.

İlerideki Yol

Yeni sonuç mutlaka hikayenin sonu değildir. "Uzun bir süre kuantum algoritmaları çalıştıktan sonra bile beni şaşırtmaya devam ediyorlar." Shelby KimmelMiddlebury College'da bir bilgisayar bilimcisi olan bir e-posta yazdı. Araştırmacıların düşündüğü sınıfın dışında, keşfedilmeyi bekleyen dahiyane bir yol bulma algoritması hâlâ olabilir.

Gerçek olmayan algoritmaların çalışma olasılığı son derece düşük gibi görünse de, köksüz bir algoritma belki de ortadan başlayarak girişten çıkışa giden bir yol oluşturabilir. Childs, "Belki onu öyle bir şekilde kurabilirsiniz ki yılan içeri girip köklerinden kurtulur, ama sonra bir şekilde gerinmeye karar verir," dedi Childs. "Bu hala dışlanmış değil."

Araştırmacılar, Childs ve meslektaşlarının 20 yıl önce keşfettiği üstel kuantum hızlandırma için pratik uygulamalar henüz bulamadı, çünkü bu, herhangi bir gerçek dünya ağında var olması muhtemel olmayan, kaynaklı ağaç grafiğinin özel simetrisine bağlı. Ancak çoğu zaman kuantum algoritmalarının yapamayacaklarını anlamanın da değeri vardır. Shor'un büyük sayıları çarpanlara ayırmak için hızlı bir kuantum algoritması keşfi baltalamakla tehdit ediyor son teknoloji kriptografi, kuantum algoritmaları için de zor olduğu bilinen problemlere olan ihtiyacın altını çizdi.

Shor'un algoritmasına karşı savunmasız olmayan bir tür kriptografi, belirli grafiklerdeki noktalar arasındaki yolları bulmanın zor olduğu varsayımına dayanır. Kaynaklı ağaçlar aracılığıyla yol bulmanın kuantum algoritmaları için gerçekten zor olduğunun kanıtı, araştırmacıları şimdiye kadar hiç şansları olmamasına rağmen, kaynaklı ağaç grafiğine dayalı yeni kriptografik protokoller geliştirmeye motive edebilir.

Childs, "Belki bu, bu problemdeki yapı türünün bizim önemsediğimiz kodlama problemlerine uygun olmadığı anlamına gelir" dedi. "Ya da belki de sadece doğru şekilde görmelisin."