Yeni Bir Kuantum Algoritması Çok Büyük Bir Sorun Sınıfının Çözümünü Hızlandırıyor

Bu hikayenin orijinal versiyonu Quanta Dergisi'nde yayınlanmıştır.

Bilgisayar bilimcileri için, sorunları çözmek biraz dağcılığa benzer. Önce, tırmanılacak bir zirve belirlemeye benzer şekilde, çözmek için bir sorun seçmeleri gerekir ve sonra onu çözmek için bir strateji geliştirmeleri gerekir. Klasik ve kuantum araştırmacılar, ikisi arasında sağlıklı bir rekabetle, farklı stratejiler kullanarak rekabet ederler. Kuantum araştırmacılar, genellikle kimsenin tırmanmaya değer bulmadığı bir zirveye tırmanarak bir sorunu çözmenin hızlı bir yolunu bildirirler; ardından klasik takımlar daha iyi bir yol bulup bulamayacaklarını görmek için yarışırlar.

Bu yarışma neredeyse her zaman sanal beraberlikle sona erer: Araştırmacılar her şeyden daha hızlı veya daha iyi çalışan bir kuantum algoritması geliştirdiklerini düşündüklerinde, klasik araştırmacılar genellikle ona eşit olan bir algoritma bulurlar. Geçtiğimiz hafta, Science dergisinde yayınlanan iddia edilen bir kuantum hızlandırma, klasik makinelerde benzer hesaplamaların nasıl yapıldığını gösteren iki ayrı gruptan anında şüpheyle karşılandı.

Ancak geçen yıl bilimsel ön baskı sitesi arxiv.org'da yayınlanan bir makalede araştırmacılar hem ikna edici hem de kullanışlı görünen bir kuantum hızlandırma tanımladılar. Araştırmacılar, çok sayıda seçenek arasından en iyi olası çözümü arayan geniş bir optimizasyon problemi sınıfına iyi çözümler bulmada bilinen tüm klasik algoritmalardan daha hızlı çalışan yeni bir kuantum algoritması tanımladılar.

Şimdiye kadar hiçbir klasik algoritma, kodlanmış kuantum interferometrisi (DQI) olarak bilinen yeni algoritmayı tahtından indiremedi. Reichman Üniversitesi'nde matematikçi ve kuantum hesaplamanın önde gelen şüphecilerinden Gil Kalai , bunun "kuantum algoritmalarında bir atılım" olduğunu söyledi. Kuantum algoritmaları hakkındaki raporlar araştırmacıları heyecanlandırıyor, kısmen zor problemler hakkında yeni fikirlere ışık tutabildikleri için ve kısmen de kuantum makineleri etrafındaki tüm vızıltılara rağmen, hangi problemlerin bunlardan gerçekten faydalanacağının net olmaması nedeniyle. Optimizasyon görevlerinde bilinen tüm klasik algoritmalardan daha iyi performans gösteren bir kuantum algoritması, kuantum bilgisayarlarının potansiyelini kullanmada önemli bir adım olacaktır.

Hollanda'daki matematik ve bilgisayar bilimi için ulusal araştırma enstitüsü olan CWI'da teorik bilgisayar bilimcisi olan ve yeni algoritmayla ilgisi olmayan Ronald de Wolf , "Bu konuda heyecanlıyım" dedi. Ancak aynı zamanda araştırmacıların sonunda aynı işi yapan klasik bir algoritma bulmasının hala oldukça mümkün olduğu konusunda uyardı. Ve kuantum donanımının eksikliği nedeniyle, yeni algoritmayı deneysel olarak test edebilmeleri için biraz zaman geçmesi gerekecek.

Kaliforniya Üniversitesi, Berkeley'de bilgisayar bilimcisi olan ve kuantum algoritmalarıyla eşleşen klasik algoritmalar yaratarak gençliğinde ünlenen Ewin Tang'e göre, algoritma klasik tarafta yeni çalışmalara ilham verebilir. Yeni iddialar "klasik algoritmalara inananlara 'Hey, bu makaleye bakmalı ve bu problem üzerinde çalışmalısınız' diyebileceğim kadar ilginç," dedi.

Klasik ve kuantum algoritmaları rekabet ettiğinde, bunu genellikle dikenli bir problemi çözmek için en iyi seçenekleri bulmaya odaklanan bir alan olan optimizasyon savaş alanında yaparlar. Araştırmacılar genellikle, problem büyüdükçe olası çözüm sayısının arttığı problemlere odaklanırlar. Bir teslimat kamyonunun üç günde 10 şehri ziyaret etmesinin en iyi yolu nedir? Paketleri arkada nasıl paketlemelisiniz? Genellikle olası çözümleri akıllıca yollarla karıştırmayı içeren bu problemleri çözmenin klasik yöntemleri hızla savunulamaz hale gelir.

DQI'nin ele aldığı belirli optimizasyon problemi kabaca şöyledir: Bir kağıt parçası üzerinde bir nokta koleksiyonu verilir. Bu noktalardan geçen bir matematiksel fonksiyon bulmanız gerekir. Özellikle, fonksiyonunuz bir polinom olmalıdır; değişkenlerin tam sayı üslerine yükseltilmiş ve katsayılarla çarpılmış bir kombinasyonu. Ancak çok karmaşık olamaz, yani kuvvetler çok yüksek olamaz. Bu size sayfa boyunca hareket ederken yukarı ve aşağı kıvrılan eğri bir çizgi verir. İşiniz en çok noktaya dokunan kıvrımlı çizgiyi bulmaktır.

Bu sorunun varyasyonları bilgisayar biliminde, özellikle hata kodlama ve kriptografide, yani verinin iletilirken güvenli ve doğru bir şekilde kodlanmasına odaklanan alanlarda çeşitli biçimlerde ortaya çıkar. DQI araştırmacıları, temelde, daha iyi bir çizgi çizmenin gürültülü bir kodlanmış mesajı doğru anlamına daha yakın bir yere kaydırmaya benzediğini fark ettiler.

Ama bunların hepsi daha sonra oldu. DQI'ın arkasındaki araştırmacılar algoritmaları üzerinde çalışmaya başladıklarında, akıllarında bu sorun bile yoktu.

Google Quantum AI'da fizikçi ve DQI'nin baş mimarlarından biri olan Stephen Jordan , "Hedef odaklı bir araştırmacının sorunu belirterek başlaması ve ardından kuantum algoritmalarının bunu klasik algoritmalardan daha hızlı çözüp çözemeyeceğini araştırması tamamen makul olurdu," dedi. "Elbette bizim için bu şekilde olmadı. Buna geriye doğru ve dolambaçlı bir yoldan ulaştık."

Jordan, 2023'te Google'a katıldığında ve çalışmaları uzun süredir klasik algoritmalardan daha iyi performans gösteren kuantum algoritmalarına odaklanan Google'daki bir fizikçi olan Eddie Farhi ile çalışacağını öğrendiğinde bu yola girdi. (Farhi bir zamanlar Massachusetts Teknoloji Enstitüsü'nde Jordan'ın doktora danışmanıydı.) Jordan, 2014'te Farhi'nin daha düşük enerjilerin daha iyi çözümlere karşılık geldiği enerjiyi düşünerek bir optimizasyon problemine kuantum saldırısı yaptığını biliyordu. Farhi için enerji, optimizasyonu kuantum fiziğine bağlıyordu.

Ancak Jordan farklı bir şey yapmak istiyordu. Kuantum fiziğine yerleştirilmiş başka bir kavrama yöneldi: her şeyi dalgalar olarak tanımak. Kuantum Fourier dönüşümü adı verilen matematiksel bir araç kullanarak Jordan, iyi bilinen bir optimizasyon problemi sınıfına yönelik tüm olası cevapları kuantum dalgalarına dönüştürmenin bir yolunu buldu. Bunu yaparken kuantum sistemini, daha büyük dalgaların (daha yüksek kuantum genlikleri biçiminde) daha iyi çözümlere karşılık gelecek şekilde manipüle edebildi.

Ancak üstesinden gelinmesi gereken büyük bir zorluk daha vardı. Bir kuantum sisteminde, "En büyük genlik nedir?" sorusunu sormak, sahildeki en büyük dalgayı tanımak kadar basit değildir. Kuantum manzarası inanılmaz derecede karmaşıktır ve en iyi çözümlere karşılık gelecek kuantum genliklerinin nasıl belirleneceği belirsizdi.

Birçok yanlış başlangıçtan sonra Jordan bir atılım yaptı: En iyi çözümleri seçme süreci, kodlanmış mesajlardaki hataları ayıklama sürecine benzer çıktı, buna kod çözme denir. Bu, bilgisayar biliminin iyi çalışılmış bir alanıdır ve Jordan'ın keşfedebileceği tekniklerle doludur. Bir optimizasyon problemini kuantum problemine dönüştürerek ve ardından kod çözme merceğini ona uygulayarak, kuantum algoritmaları geliştirmenin yeni bir yolunu bulmuştu.

Yine Google'da çalışan Noah Shutty ile birlikte Jordan, çeşitli optimizasyon problemlerinde klasik algoritmalara karşı nasıl performans gösterdiklerini görmek için kod çözme şemalarını test etmeye başladı. Hem doğru yaklaşıma hem de işe yaradığı bir probleme ihtiyaçları vardı. Jordan, "Klasik algoritmaların yenilmesinin zor olduğu ortaya çıktı," dedi. "Birkaç ay denedikten sonra, kuantum için hala hiçbir galibiyet elde edememiştik."

Ancak sonunda ikili, 1960'larda kodlanmış bir mesajdaki bireysel hataları bulup düzeltmek için ilk kez tanıtılan bir kod çözme algoritmasında karar kıldı. Bu sorunu bulmak anahtardı. Jordan, "Araştırma yaptığımızda, neredeyse anında başarıya ulaşmış gibi göründük," dedi. Sonunda, bir sorun ve birlikte kuantum hızlandırmaya benzeyen bir yaklaşım bulmuşlardı.

Elbette bu, kurşun geçirmez olduğu anlamına gelmiyordu. Jordan, "Belki de tüm yaklaşımınızı etkili bir şekilde kopyalayabilen klasik bir yöntem vardır," dedi. "Bu tür dekuantizasyonlar her zaman belirgin değildir."

Bu korkuları yatıştırmak için, kodlama teorisi uzmanı (ve Shutty'nin Stanford Üniversitesi'ndeki eski doktora danışmanı) Mary Wootters'a danıştılar. Kuantum hızlanmalarıyla eşleşebilecek bilinen herhangi bir klasik algoritmayı dikkatlice aradı. Avantaj devam etti. Ekibin kontrolleri de bunun devam edeceğini gösteriyor. Tang, "Gerekli özeni gösterdiler," dedi.

Bu analizle desteklenerek, çözmekte oldukları optimizasyon problemine daha dikkatli baktılar. Jordan, bunun çok dar bir alana hitap edebileceğinden ve daha geniş uygulamaları olmayacağından endişelenmişti, ancak Shutty bu kod çözme probleminin şifreleme ve diğer alanlardaki iyi bilinen ve faydalı problemlerin bir çeşidi olduğunu fark etti.

Jordan, yeterince büyük bir kuantum makinesi olmadan DQI'nin teorik bir atılım olarak kalacağını kabul ediyor. "DQI günümüz kuantum bilgisayarlarında çalışamaz" dedi. Ancak yine de ilerlemeye devam ediyorlar. Grup çalışmalarını geçen Ağustos ayında yayınladığından beri, DQI'nin uygulamasını orijinal sorunun ötesine, bu "en iyi yol" sorunlarının daha fazla örneğini içeren daha geniş bir optimizasyon sorunları sınıfına genişlettiler.

Jordan, DQI'nin şu ana kadar bu problemlerde de klasik algoritmaları geçebileceğini umduğunu söyledi.

Şu an için kuantum topluluğu sevinçli olmaya devam ediyor. Kalai, "Klasik algoritmalara göre avantaj gösteren kuantum algoritmaları bulmak son otuz yılın çok heyecan verici bir çabası ve böyle bir avantaj gösteren kesin algoritmaların sayısı çok fazla değil," dedi. "Bu nedenle, her yeni algoritma kutlama sebebidir."

Orijinal hikaye , Simons Vakfı'nın editoryal açıdan bağımsız bir yayını olan Quanta Magazine'den izin alınarak yeniden basılmıştır. Vakfın misyonu, matematik, fizik ve yaşam bilimlerindeki araştırma gelişmelerini ve eğilimlerini ele alarak kamuoyunun bilim anlayışını geliştirmektir.