NTT Bilim İnsanları Kuantum Avantajını Doğrulamak İçin Yeni Bir Yolları Olduğunu Söylüyor

Sunnyvale, Kaliforniya – 26 Ekim 2022 – NTT Research, kendi bölgesinden bir bilim insanının Kriptografi ve Bilgi Güvenliği (CIS) Laboratuvarı ve bir meslektaşım NTT Sosyal Bilişim Laboratuvarları (SIL) kuantum avantajı üzerine çığır açan bir makale yazdı. Makale, 31 Ekim–Kasım arasında gerçekleşecek olan yıllık IEEE Bilgisayar Biliminin Temelleri Sempozyumu'nda (FOCS) sunulmak üzere seçilmiştir. Denver'da 3.

Makalenin ortak yazarları, “Yapısız Doğrulanabilir Kuantum AvantajıNTT SIL'de seçkin araştırmacı Dr. Takashi Yamakawa ve kıdemli bilim adamı Dr. Mark Zhandry. NTT Araştırma BDT Laboratuvarı Çalışma kısmen, Dr. Yamakawa'nın misafir araştırma görevlisi olduğu ve Dr. Zhandry'nin bilgisayar bilimleri alanında yardımcı doçent olarak görev yaptığı Princeton Üniversitesi'nde yapıldı. 

Kuantum avantajı (veya kuantum hızlandırma) konusu, kuantum bilgisayarların klasik veya kuantum olmayan bilgisayarlardan daha hızlı çözebileceği problem türleri ve bunların ne kadar hızlı olduğu ile ilgilidir. Söz konusu problemler genellikle deterministik olmayan polinom-zaman (NP) sınıfı olarak tanımlanır. Ne kadar avantaj büyük ölçüde değişebilir. Bir kuantum bilgisayar, klasik bir bilgisayarı bir hafta veya muhtemelen anlaşılmaz derecede üstel bir zaman alan bir dakika veya saniye içinde belirli bir sorunu çözebilir. Bu yazıda, yazarlar bu üstünlüğü doğrulamanın ve bunu verimli bir şekilde yapmanın zorluğunu ele alıyor. Bugüne kadar, kuantum avantajının gösterileri, iki veya daha fazla taraf arasında önemli “yapı” veya ileri geri iletişimi içeriyordu. Yamakawa ve Zhandry makalesinin atılımı, doğrulamanın yapı olmadan mümkün olduğu bir NP zor problemini göstermektir.

Texas Üniversitesi'nden Austin Bilgisayar Bilimleri Profesörü Dr. Scott Aaronson, "Bir NP arama problemi için yalnızca rastgele bir kehanet gerektiren üstel bir kuantum hızlanmasını ilk kez görüyoruz" dedi. Simons Institute for the Theory of Computing'de 13 Haziran 2022'de düzenlenen bir çalıştay sırasında makalenin fotoğrafı. Yamakawa ve Zhandry, yalnızca rastgele bir kahin, yani her sorguya rastgele yanıtlar üreten teorik bir kara kutu gerektirerek, problemlerini yapılandırılmamış hesaplama varsayımları üzerine kurdular. Bu nedenle, sorunları, açık anahtar şifrelemesinde bulunanlar gibi yapılandırılmış işlevler yerine tek yönlü işlevlerle daha yakından hizalanır. Bu tek yönlü hizalama, verimli doğrulamayı kolaylaştırır.

Kazuhiro Gomi, "NTT'ye bağlı kriptografların, özellikle kuantum hesaplama anlayışımızı zenginleştiren bir makalede, bir kez daha 'atılım' etiketini hak eden araştırmalar üzerinde işbirliği yaptığını görmek heyecan verici, dedi Kazuhiro Gomi. , NTT Araştırma Başkanı ve CEO'su. “Bu prestijli IEEE konferansındaki tüm katılımcılara tebrikler ve en iyi dileklerimle.” 

Yamakawa ve Zhandry'nin tasarladığı NP arama problemi, 1) belirli bir hata düzeltme kodunun kod kelimesi olan bir n-sembol dizgisi ve 2) bir n-sembol dizgisi bulmayı gerektiren ikisi bir arada bir problemdi. sembol, rastgele kehanet altında sıfıra eşlenir. Her problem ayrı ayrı kolaydır. Ancak hem bir kod sözcüğü olan hem de sıfıra eşlenen tek bir sembol dizisini bulmak, en azından klasik olarak çok daha zordur. "Kuantum iseniz, bunu polinom zamanda çözebilirsiniz," dedi Dr. Zhandry, "ama klasik iseniz, en azından bu kara kutu modelindeyseniz, üstel zamana ihtiyacınız vardır." Öte yandan, olası bir çözüm verildiğinde, iki sorunun her birini ayrı ayrı çözüp çözmediğini kontrol ederek bunu doğrulamak kolaydır. FOCS için bir makaleye yakışır şekilde, bu çalışmanın temel veya temel olduğunu unutmayın. Dr. Aaronson'ın Simons Enstitüsü'ndeki konuşmasında belirtildiği gibi (bu NTT Araştırması'nda ele alınmıştır). blog makalesi), Yamakawa-Zhandry argümanı bir hızlanma sınıfına girer, matematiksel olarak kolayca kontrol edilebilir, ancak yakın zamanda gerçek bir kuantum bilgisayar tarafından pratik olarak gösterilemez. Bununla birlikte, çığır açan doğrulama planının ötesinde, makale aynı zamanda kuantum hızlanmasının boyutuyla ilgili yeni bir şeye de işaret ediyor.

"Çalışmamızdan önce, faktoring veya kara kutu ayarında nokta bulma gibi NP problemleri için kuantum avantajı örneklerine sahiptik. Ancak, tüm bu örneklerin altında yatan kuantum algoritmasının temelde dönem bulma olduğu ortaya çıktı - ancak bu örneklere dönem bulmanın nasıl uygulanacağını göstermek genellikle önemsiz değildi” dedi. “Makalemiz en az ikinci bir vaka olduğunu gösteriyor. Bunu, kuantum avantajının daha önce düşündüğümüzden daha yaygın olduğuna dair bir umut olduğu şeklinde iyimser bir şekilde yorumlayabilirsiniz.”

IEEE Bilgisayar Topluluğu Bilişimin Matematiksel Temelleri Teknik Komitesi (TCMF) tarafından desteklenen FOCS, teorik bilgisayar bilimi alanında önde gelen bir konferanstır. Bu tür 2022. yıllık toplantı olan FOCS 63 için bildiri çağrısı, kuantum hesaplamayı 17 genel ilgi alanından biri olarak sıraladı. Yamakawa-Zhandry raporunun 31 Ekim 2022'de MT 10:15'te sunulması planlanıyor. Bu etkinlik hakkında daha fazla bilgi edinmek ve kayıt olmak için şu adresi ziyaret edin: ODAK 2022 adresinden özetlerini gönderebilirler.