Sekizinci doktora yılında, kuantum hesaplamadaki en temel problemlerden birini çözdü.
Urmila Mahadev, kuantum hesaplama alanındaki en temel problemlerden birini çözmek için lisansüstü okulda sekiz yıl geçirdi: Bir kuantum bilgisayarın kuantum hesaplama yapıp yapmadığını nasıl anlarsınız?
Urmila Mahadev seminerde. | Görsel hakları: Jana Aenbrennerová / Quanta Magazine
2017 baharında, Urmila Mahadev kendisini çoğu lisansüstü öğrencinin oldukça iyi bulacağı bir konumda buldu. Kuantum hesaplama alanındaki büyük bir sorunu çözdü. Kuantum hesaplama, bilgisayarları inceleme bilimidir ve kuantum fiziğinin garip yasalarından güçlü hesaplama gücü elde eder.
Austin'deki Texas Üniversitesi'nde bilgisayar bilimcisi olan Scott Aaronson'a göre, Mahadev'in Kör hesaplama Yeni sonuçlarının ve önceki tezinin birleşimi onu açıkça "yükselen bir yıldız" yapıyor
O sırada 28 yaşında olan Mahadev, Berkeley'deki California Üniversitesi'nde yedi yıldır yüksek lisans öğrencisiydi - çoğu öğrencinin umutsuzca mezun olmak istediği aşamanın çok ötesinde. Doktora danışmanı Umesh Vazirani'nin dediği gibi, sonunda "çok güzel bir doktora tezi" var.
Ama o yıl Mahadev mezun olmadı, henüz bitmediği için mezun olmayı düşünmedi bile.
Kuantum hesaplama + kriptografi
Beş yıldan fazla bir süredir farklı bir araştırma hedefi daha var. Aaronson, çözmek istediği soruna "kuantum hesaplama alanındaki en temel sorunlardan biri" adını veriyor ve bu: Bir kuantum bilgisayarın hesaplamalar yapmasına izin verirseniz, talimatlarınıza gerçekten uyup uymadığını veya gerçekten herhangi bir kuantum hesaplaması yapıp yapmadığını nasıl anlarsınız?
Araştırmacılar, kuantum bilgisayarların yıllar içinde katlanarak hızlanabileceğini ve kara deliklerin etrafındaki davranışı simüle etmek, proteinlerin nasıl katlandığı vb. Gibi birçok soruyu yanıtlayabileceğini umuyor. Fakat bir kuantum bilgisayar, klasik bir bilgisayarın yapamayacağı hesaplamaları tamamlayabildiğinde, hesaplamalarının doğru olup olmadığını nasıl bileceğiz?
Sıradan bir bilgisayara güvenmiyorsanız, teoride, her hesaplama adımını kendiniz kontrol edebilirsiniz. Bununla birlikte, kuantum sistemleri bu tür denetimlere temelde direnir.
Her şeyden önce, bir kuantum bilgisayarın dahili çalışma mekanizması son derece karmaşıktır: Birkaç yüz kubitlik bir bilgisayar için, iç durumunun bir tanımını yazmak, tüm görünür evrenden daha büyük bir sabit disk gerektirir. Ayrıca bu açıklamayı yazmak için yeterli alan olsa bile, onu almanın bir yolu yoktur. Genel olarak, bir kuantum bilgisayarın iç durumu, birçok farklı kuantum dışı "klasik" durumun üst üste gelmesidir. (Schrödinger'in hem "ölü" hem de "canlı" kedisi gibidir.) Ancak kuantum durumu ölçüldüğünde, klasik durumlardan birine çökecektir. 300 kübitlik bir kuantum bilgisayara baktığınızda, özünde gördüğünüz şey sadece 300 klasik bit, yani 0 ve 1 olacaktır.
Vazirani, "Kuantum bilgisayarlar çok güçlü ama aynı zamanda çok gizemlidir" dedi.
Bu sınırlamalar göz önüne alındığında, bilgisayar bilimcileri uzun zamandır bir kuantum bilgisayarın iddia ettiği şeyi yaptığını kanıtlamak için herhangi bir katı garanti vermesinin mümkün olup olmadığını merak ediyorlardı. Kudüs İbrani Üniversitesi'nde bilgisayar bilimcisi olan Dorit Aharonov sordu: " Kuantum ve klasik dünya arasındaki etkileşim, diyaloğu sağlayacak kadar güçlü mü? "
Yüksekokulun ikinci yılında Mahadev, nedenini tam olarak anlamadığı bu sorudan büyülendi. Sonraki yıllarda bir yöntemi birbiri ardına denedi. Dedi ki: "Çoğu zaman doğru şeyi yaptığımı hissettim, ama sonra bir hata yaptım, bazen hızlı, bazen bir yıl sonra."
Ancak Mahadev pes etmeyi reddetti. Vazirani'nin daha önce hiç görmediği kalıcı bir kararlılık sergileyen Vazirani, "Bu anlamda Mahadev kesinlikle farklı" dedi.
Şimdi, sekiz yıllık yüksek lisans eğitiminin ardından, Mahadev sonunda başarılı oldu! O teklif etti Etkileşimli protokol , Bu anlaşma ile kuantum hesaplama yeteneklerine sahip olmayan kullanıcılar da Kuantum bilgisayarların istediklerini yapmasını sağlamak için klasik kriptografi kullanın , Ve kuantum bilgisayarların, sanki bir koşum takımı ile keyfi bir şekilde dörtnala koşuyormuş gibi, emirlerini yerine getirdiklerine inanıyorlar. Vazirani, Mahadev'in yönteminin kullanıcılara "bilgisayarın kurtulamayacağı bir yol" sağladığını söyledi.
Mahadev tarafından önerilen anlaşma. | Resim kaynağı: https://arxiv.org/pdf/1804.01082.pdf
Aaronson, bir yüksek lisans öğrencisinin böyle bir görevi tek başına tamamlayabilmesinin "çok şok edici" olduğunu söyledi.
Mahadev şu anda Berkeley Üniversitesi'nde doktora sonrası araştırmacı. Son zamanlarda, önerisini teorik hesaplama alanındaki en büyük konferanslardan biri olan Bilgisayar Bilimi Vakfı'nın yıllık seminerinde sundu. Çalışmaları, bu konferansta teorik bir bilgisayar bilimcisi için nadir bir onur olan "En İyi Makale" ve "En İyi Öğrenci Bildirisi" ödüllerini kazandı.
Kaliforniya Teknoloji Enstitüsü'nde geçmişte Mahadev ile çalışan bilgisayar bilimcisi Thomas Vidick, bir blog gönderisinde Mahadev'in araştırma sonuçlarının "son yıllarda kuantum hesaplama ve teorik bilgisayar biliminin kesişme noktasında ortaya çıkan en çarpıcı fikirlerden biri" olduğunu yazdı.
Kuantum hesaplama alanındaki araştırmacılar, sadece Mahadev'in protokolünün sorunu çözebileceği için değil, aynı zamanda bu sorunu çözmek için benimsediği yepyeni yaklaşım nedeniyle de heyecanlılar. Vidick şunu yazdı: Kuantum hesaplama alanında klasik kriptografi kullanın Bu gerçekten çok yeni bir fikir, "Umarım bu fikirlere dayanarak daha fazla sonuç üretilmeye devam eder."
Kanıtlamanın uzun yolu
Mahadev, Los Angeles'ta bir doktorun ailesinde büyüdü ve bir çalışma alanından diğerine sürüklendiği Güney Kaliforniya Üniversitesi'ne gitti. İlk başta sadece doktor olmak istemediğine ikna olmuştu. Daha sonra, bilgisayar bilimcisi Leonard Adleman RSA şifreleme algoritması Üç yaratıcıdan biri - öğretilen bir kursun teorik bilgisayar bilimiyle ilgilenmesini sağladı. Daha sonra Berkeley'deki California Üniversitesi'ne yüksek lisans öğrencisi olmak için başvurdu ve uygulama materyallerinde kuantum hesaplama hariç teorik bilgisayar biliminin tüm yönleriyle ilgilendiğini açıkladı. Çünkü kuantum hesaplama "kulağa çok garip bir şey gibi geliyor, en az bildiğim şey bu."
Ancak Berkeley'e vardığında Vazirani'nin basit açıklaması, fikrini hızla değiştirdi. Onu bir soruyla tanıştırdı-- Kuantum hesaplamayı doğrulamak için bir anlaşma nasıl bulunur? Vazirani, bu sorunun "hayal gücüne ilham verdiğini" söyledi.
Mahadev şöyle açıkladı: "Protokoller bulmaca gibidir. Bana göre, bu tür problemler diğerlerinden daha kolay görünüyor, çünkü protokoller hakkında hemen düşünmeye başlayabilir ve sonra onları çözebilir, böylece nasıl çalıştıklarını keşfedebilirsiniz. "Bu konuyu doktora araştırma konusu olarak seçti ve Vazirani'nin" uzun yol "dediği şeyi başlattı.
Urmila Mahadev. | Resim kaynağı: Quanta Magazine
Bir kuantum bilgisayar, klasik bir bilgisayarın çözemediği bir sorunu çözebilirse, çözümün test edilmesinin zor olacağı anlamına gelmez. İçin Büyük sayıların ayrıştırılması Örnek olarak, büyük bir kuantum bilgisayar bu sorunu verimli bir şekilde çözebilir, ancak klasik bilgisayarların bu görevi yerine getiremediği düşünülmektedir.
Klasik bir bilgisayar büyük bir sayıyı çarpanlara ayıramasa da, bir kuantum bilgisayarın çarpanlara ayırmasının doğru olup olmadığını kontrol edebilir - sadece doğru cevabı alıp almadıklarını görmek için bu faktörleri çarpın.
Bununla birlikte, bilgisayar bilimcileri, kuantum bilgisayarların çözebileceği birçok sorunun bu özelliğe sahip olmadığına inanıyor (ve son zamanlarda kanıta doğru bir adım attılar). Başka bir deyişle, klasik bir bilgisayar bu sorunları çözemez, önerilen bir çözümün doğru olup olmadığını bile yargılayamaz.
Bu bağlamda, 2004 hakkında, Çember Teorik Fiziği Enstitüsü'nden fizikçi Daniel Gottesman bir soru sordu: Kuantum olmayan gözlemcilere, bir kuantum bilgisayarın iddia ettiği şeyi gerçekten başardığını kanıtlayabileceği herhangi bir tür anlaşma önermek mümkün müdür?
Dört yıl içinde, kuantum hesaplamadaki araştırmacıların kısmi cevapları oldu. İki farklı ekip, bir kuantum bilgisayarın hesaplamalarını kanıtlamasının mümkün olduğunu, ancak tamamen klasik bir doğrulama cihazıyla değil, kendi çok küçük kuantum bilgisayarına girebilen bir doğrulama cihazıyla kanıtlanabileceğini kanıtladı. Araştırmacılar daha sonra bu yöntemi geliştirdiler ve ihtiyaç duyulan tüm doğrulama ekipmanının her seferinde tek bir kübit ölçebilme yeteneği olduğunu kanıtladılar.
2012'de Vazirani dahil bir grup araştırmacı, kuantum hesaplamanın birbiriyle iletişim kuramayan bir çift kuantum bilgisayar tarafından gerçekleştirilmesi durumunda, tamamen klasik bir doğrulama cihazının kuantum hesaplamayı kontrol edebileceğini kanıtladı. Gottesman, bu makalenin yönteminin bu özel durum için tasarlandığını, bu sorunun çıkmaza girdiğini ve bazılarının daha ileri gidemeyeceğini düşündüğünü söyledi.
Bu sıralarda Mahadev bu doğrulama sorunuyla karşılaştı. İlk başta, kuantum bilgisayarların ne yapıp ne yapamayacağını varsaymayan "koşulsuz" bir sonuç almaya çalıştı.
Vazirani konuyu bir süre araştırdıktan ve herhangi bir ilerleme kaydettikten sonra, farklı bir olasılık kullanma önerisinde bulundu. "Kuantum sonrası" şifreleme (Kuantum sonrası şifreleme). Araştırmacılar bunun bir Kuantum bilgisayarların bile kıramayacağı şifreleme yöntemleri Henüz emin olmasalar da.
Çevrimiçi işlemler gibi bilgileri şifrelemek için kullanılan RSA şifreleme algoritması gibi yöntemler post-kuantum değildir, yani bir kuantum bilgisayar bu şifreleme yöntemini kırabilir çünkü güvenlikleri büyük sayıları faktoring işleminin zorluğuna bağlıdır. .
2016'da Mahadev ve Vazirani, daha sonra çok önemli olduğu kanıtlanan başka bir sorunu çözerken ilerleme kaydetti.
Kuantum bilgisayarların sözde yapı oluşturmasına izin vermek için şifreleme kullanan bir yöntem geliştirmek için şu anda OpenAI'de çalışan bir bilgisayar bilimcisi olan Paul Christiano ile birlikte çalıştılar. " Şifreli durum (Gizli devlet) ", Bu şifreli durumun açıklaması klasik doğrulama cihazı tarafından bilinir, ancak kuantum bilgisayarın kendisi tarafından bilinmemektedir. .
Programları sözde "Gizli kapı" işlevi (Trapdoor işlevi), bu işlevi yürütmek kolaydır, ancak anahtar bilinmedikçe tersine çevirmek çok zordur. (Araştırmacılar, daha sonra önerilecek olan uygun bir gizli kapı işlevinin nasıl inşa edileceğini bilmiyorlar.) Ek olarak, bu işlevin "ikiye bir" olması gerekir, yani her bir çıktı iki farklı girdiye karşılık gelir. . Örneğin, y = x² kare fonksiyonu için, 0 sayısı (örneğin 9) dışındaki her çıkışın karşılık gelen iki girişi (3 ve 3) vardır.
Böyle bir işlevle, kuantum bilgisayarı aşağıdaki adımlara göre şifreli bir durum oluşturabilir:
- İlk olarak, bilgisayarın olası tüm işlev girdilerinin üst üste binmesini sağlasın (bu karmaşık görünebilir, ama aslında kolaydır);
- Ardından, bilgisayarın işlevi bu devasa süperpozisyona uygulamasına izin verin ve fonksiyonun tüm olası çıktılarının süperpozisyonu yeni bir durum oluşturur.
Girdinin üst üste binmesi ve çıktının üst üste gelmesi dolanma yaratacaktır, bu da birinin ölçülmesinin diğerini hemen etkileyeceği anlamına gelir.
Ardından, bilgisayardan çıkış durumunu ölçmesini ve sonucu bize söylemesini isteyin. Bu ölçüm, çıktı durumunun tüm olası çıktılardan birine düşmesine neden olur ve giriş durumu, birbirleriyle dolaşık oldukları için hemen onunla eşleşecek şekilde daralır. Örneğin, kare denklem için, ölçülen çıktı durumu 9 ise, giriş durumu 3 ve 3 süperpozisyon durumuna çökecektir.
Bununla birlikte, gizli kapı işlevini kullanırsak, gizli kapının gizli anahtarına sahip oluruz, böylece giriş durumunu oluşturan iki süperpozisyon durumunu kolayca bulabiliriz. Ancak kuantum bilgisayarlar bunu yapamaz. Bir kuantum bilgisayar, bileşimini bulmak için girdinin üst üste binmesini basitçe ölçemez, çünkü ölçüm, girdinin üst üste binmesini daha da daraltarak bilgisayarı yalnızca bir giriş durumuyla bırakır ve diğerini bulamaz. .
Mahadev 2017'de " Yanlış öğrenme (Hatalarla Öğrenme, LWE) "şifreleme teknolojisi, şifrelenmiş durum yönteminin özünde gizli bir kapı işlevi oluşturmanın bir yolunu buldu. Gizli kapı işlevini kullanarak," kör "bilgi işlemin kuantum versiyonunu oluşturarak bulut bilişim kullanıcılarının Bulut bilgisayarların, bilgi işlem sırasında bile verileri okuyamaması için verilerini koruyun.
Kısa bir süre sonra Mahadev, Vazirani ve Christiano, bu gizli kapı işlevlerini daha da iyileştirmek ve kuantum bilgisayarların doğrulanabilir gerçek rastgelelik oluşturmasına olanak tanıyan bir yöntem geliştirmek için Vidick ve Zvika Brakerski (İsrail'deki Weizmann Bilim Enstitüsü'ndeki bilim adamları) ile işbirliği yaptı. Güvenli yöntem sayısı.
Mahadev bu sonuçlardan mezun olabilirdi, ancak doğrulama sorunu çözülene kadar çalışmaya devam etmeye kararlı. Dedi ki: "Asla mezun olmak istemedim çünkü hedefim asla mezun olmamaktı."
Bu sorunun çözülüp çözülmeyeceğini bilmiyorum. Bazen stresli olabilir, ancak "İlgilendiğimi öğrenmek için zaman harcıyorum, bu yüzden gerçekten zaman kaybı değil." Dedi.
Nasıl şifrelenir?
Mahadev, şifreli durum yönteminden bir kimlik doğrulama protokolüne ulaşmaya çalışan çeşitli yöntemler denedi, ancak bir süre hiçbir şey bulamadı. Ardından bir fikri vardı: Araştırmacılar, doğrulama cihazının kübitleri ölçebiliyorsa kuantum bilgisayarları test edebileceğini kanıtladılar. Tanım olarak, klasik bir doğrulama cihazı bu kabiliyetten yoksundur. fakat, Ya bu klasik doğrulama cihazı bir şekilde bir kuantum bilgisayarı kendi başına ölçüm yapmaya zorlarsa ve ardından ölçüm sonuçlarını dürüstçe rapor ederse?
Mahadev, en zor kısmın, Kuantum bilgisayarı, doğrulama cihazının ne tür bir ölçüm gerektireceğini bilmeden önce, kuantum bilgisayarın ölçeceği durumu belirlemesine izin verin. . Aksi takdirde, kuantum bilgisayar doğrulama cihazını kolayca kandırabilir. Şifrelenmiş durum yöntemi burada devreye giriyor: Mahadev'in protokolü, bir kuantum bilgisayarın önce şifrelenmiş bir durum oluşturmasını ve ardından onu ölçülmesi gereken durumla dolaştırmasını gerektirir. Ancak o zaman bilgisayar hangi ölçümü yapacağını bilecektir.
Kuantum bilgisayarı şifrelenmiş durumun bileşimini bilmediğinden, ancak doğrulama cihazı bildiğinden, Mahadev bunu kanıtladı Kuantum bilgisayarlar, açık bir aldatma izleri bırakmadan ciddi aldatmacalar yapamazlar.
Vidick, özünde, bilgisayarın ölçmek istediği kübitlerin "kriptografik bir taş olarak ayarlandığını" yazıyor. Bu nedenle, ölçüm sonuçları bir doğruluk kanıtı gibi görünüyorsa, doğrulama cihazı gerçekte olduklarından emin olabilir. "Ne harika bir fikir! Urmila bunu her açıkladığında şaşkına dönmüştüm."
Kuantum bilgisayarların kıramayacağı şifreler?
Mahadevin kimlik doğrulama protokolü, rastgele sayı üreteçleri ve gizli şifreleme yöntemleriyle birlikte Kuantum bilgisayarların LWE'yi kıramayacağı varsayımına bağlıdır . Şu anda LWE, kuantum sonrası kriptografi için öncelikli bir aday olarak kabul ediliyor ve yakında Ulusal Standartlar ve Teknoloji Enstitüsü (NIST) tarafından kuantum bilgisayarların kırabileceği yöntemlerin yerini alarak yeni şifreleme standardı olarak benimsenebilir. .
Gottesman, bunun, bu şifreleme yönteminin kuantum bilgisayarlara gerçekten direnebileceğini garanti etmediği konusunda uyardı, "ancak şu ana kadar bu yöntem güvenilir ve hiç kimse bu yöntemin kırılabileceğine dair kanıt bulamadı".
Vidick, her durumda, anlaşmanın LWE'ye dayanmasının Mahadev'in çalışmaları için bir kazan-kazan getirdiğini yazdı. Bir kuantum bilgisayarın protokolü aldatmasının tek yolu, kuantum hesaplama alanındaki birinin LWE'yi kırmanın bir yolunu bulmasıdır ki bu başlı başına büyük bir başarı olacaktır.
Mahadev'in anlaşmasının yakın gelecekte gerçek bir kuantum bilgisayarda uygulanması olası görünmüyor. Şu anda, bu protokol çok fazla hesaplama gücü gerektiriyor, bu yüzden çok pratik değil. Ancak önümüzdeki birkaç yıl içinde, kuantum bilgisayarlar büyüdükçe ve araştırmacılar protokolü basitleştirdikçe, durum değişebilir.
Aaronson, Mahadev'in anlaşmasının önümüzdeki beş yıl içinde mümkün olmayabileceğini, ancak "varsayımsal dünyada tamamen imkansız değil. Her şey yolunda giderse, kuantum bilgisayar evriminin bir sonraki aşamasında, bu sorunu düşünmeye başlayabilirsiniz" dedi.
Alanın şu anda ne kadar hızlı geliştiğini düşünürsek, bu aşama daha erken gelebilir. Ne de olsa Vidick, sadece beş yıl önce araştırmacıların, kuantum bilgisayarların klasik bilgisayarların çözemediği herhangi bir sorunu çözmesinin yıllar alacağına inandıklarını söyledi. Şimdi, insanlar bunun bir veya iki yıl içinde olacağını düşünüyor.
Mahadev'e gelince, en sevdiği sorunu çözmek onu biraz kaybetti. Bu problemi çalışması için uygun kılan şeyin ne olduğunu anlayabileceğini umuyor. "Şimdi yeni bir soru bulmalıyım, bu yüzden cevabı bilmeyi umuyorum."
Bununla birlikte, teorik bilgisayar bilimcileri, Mahadev'in kuantum hesaplama ve kriptografiyi birleştirmesini, hikayenin sonundan ziyade bu renkli düşünce çizgilerinin bir ön keşfi olarak görüyorlar.
Çeviri: Crow Boy
Orijinal bağlantı:
https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/
