Ana soru: Bir kuantum bilgisayar nasıl tanımlanır; klasik bilgisayardan ne farkı olur?
Klasik bilgisayarın matematiksel modeli Turing makinesidir. Deutsch 1985'te şunu sordu: fizik kuantum mekaniğine göre işliyorsa, hesaplamanın en genel modeli de kuantum mekaniğine dayanmalı değil mi? Yazı, Church–Turing hipotezini bir fizik ilkesi olarak yeniden ifade eder ve evrensel bir kuantum hesap makinesi tanımlar.
Bu sayfada16. Evrensel Kuantum Bilgisayar · Deutsch 1985 — Quantum theory, the Churc · 17. Shor Algoritması …
Proceedings of the Royal Society A 400, 97–117 kuram
Church–Turing hipotezini fiziksel bir ilke olarak formüle edip kuantum Turing makinesi ve evrensel kuantum bilgisayar kavramlarını getiren yazı.
Yazının çıkış noktası şudur: Church–Turing hipotezi, "hesaplanabilir" olan her şeyin bir Turing makinesince hesaplanabileceğini söyler. Deutsch, bu hipotezin altında örtük bir fizik iddiası bulunduğunu savunur ve bunu açıkça bir ilke olarak yazar: "her sonlu biçimde gerçekleştirilebilir fiziksel sistem, sonlu araçlarla çalışan evrensel bir model hesap makinesi tarafından tam olarak benzetilebilir."
Yazar, klasik fiziğin ve evrensel Turing makinesinin bu ilkeyi karşılamadığını belirtir; çünkü ilki sürekli, ikincisi kesiktir. Buna karşılık Turing makinelerinin kuantum genellemesi olan bir hesap makineleri sınıfı tanımlar ve kuantum kuramı ile "evrensel kuantum bilgisayarın" bu ilkeyle uyumlu olduğunu gösterir.
Bu makinelerin, hiçbir Turing makinesinin yapamayacağı özellikleri olduğu söylenir. Bunlar arasında özyinelemeli olmayan işlevlerin hesaplanması yoktur; ama "kuantum paralellik" vardır: belirli olasılıksal görevler, evrensel kuantum bilgisayarla, onun klasik bir kısıtlamasına göre daha hızlı yapılabilir. Yazar, bu paralelliğin sezgisel açıklamasının Everett yorumu dışındaki yorumlara ağır bir yük getirdiğini ileri sürer; bu bir yorum iddiasıdır ve tartışmalıdır, makale bu konuda deneysel bir sonuç sunmaz.
Yazı son olarak kuantum hesaplama kuramının fiziğin geri kalanıyla bağlarını inceler; kuantum karmaşıklık kuramının, bir fiziksel sistemin "karmaşıklığının" ya da "bilgisinin" klasik karmaşıklık kuramından daha makul bir tanımını verdiği öne sürülür.
Yazının iki ayrı iddiası ayrı değerlendirilir: kuantum hesap modelinin tanımı ve bu modelin klasikten farklı yaptığı hesaplar matematiksel bir sonuçtur; Everett yorumuyla ilgili yorum ise bir görüştür ve tartışmalıdır.
Sonra: Bernstein ve Vazirani 1993'te bu modeli karmaşıklık kuramı açısından yeniden ele aldı (bu dosyada konu 19).
17. Shor Algoritması
Ana soru: Büyük sayılar hızlıca çarpanlara ayrılabilir mi?
Bir sayıyı asal çarpanlarına ayırmak, bilinen klasik yöntemlerle büyük sayılar için çok uzun sürer; RSA gibi yaygın şifrelemeler bu zorluğa dayanır. Shor 1994'te varsayımsal bir kuantum bilgisayarda aynı işin, sayının basamak sayısına göre çokterimli (polinom) sürede yapılabileceğini gösterdi. Bu, kuantum hesaplamaya ilginin en güçlü nedenlerinden biri oldu.
Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), 124–134; tam sürüm: SIAM J. Comput. 26 (1997) 1484–1509, arXiv:quant-ph/9508027 kuram
Tam sayıları çarpanlarına ayırmak ve ayrık logaritma hesaplamak için kuantum bilgisayarda polinom zamanlı algoritmalar veren yazı.
Yazının başlangıç sorusu, bilgisayarın evrensel bir hesap aygıtı olup olmadığıdır: klasik bir bilgisayar, fiziksel herhangi bir hesaplama aygıtını en çok çokterimli bir zaman kaybıyla benzetebilir mi? Kuantum mekaniği hesaba katıldığında bu belirsizdir. Yazı iki sorunu ele alır: tam sayıların çarpanlara ayrılması ve ayrık logaritmanın bulunması. İkisi de klasik bilgisayarda zor sayılır ve birçok şifreleme önerisinin temelidir.
Yazar, her iki sorun için varsayımsal bir kuantum bilgisayarda, girdi büyüklüğüne, yani sayının basamak sayısına göre çokterimli sayıda adım atan rastgelelikli algoritmalar verir. 1994 bildirisi bunları "Las Vegas" algoritmaları olarak sunar ve bunların kuantum şifre çözmenin ilk örnekleri olduğunu belirtir.
Yöntemin çekirdeği şöyle özetlenebilir: çarpanlara ayırma, belirli bir fonksiyonun periyodunu bulmaya indirgenir. Kuantum bilgisayar, fonksiyonu birçok girdi üzerinde süperpozisyon hâlinde hesaplar; sonra kuantum Fourier dönüşümü, periyodu ortaya çıkaran girişim örüntüsünü okunur kılar. Periyot bulunduktan sonra geri kalan işlem sıradan klasik hesaptır. Bu özet, yazının metninin değil, algoritmanın bilinen yapısının anlatımıdır.
Yazı bir donanım gerçekleştirmesi sunmaz. Klasik bilgisayarda çarpanlara ayırmanın gerçekten zor olduğunu da göstermez; bu zorluk genel olarak varsayılır. Yazının gösterdiği, kuantum bilgisayarda bu problemlerin çokterimli sürede çözülebileceğidir.
Sonucun önemi iki yönlüdür: kuantum hesabın klasik hesaptan, yaygın olarak varsayılan zorluktaki bir problemde, üstel mertebede hızlı olabileceğini gösterir; öte yandan bu hız yalnızca yeterince büyük ve hata düzeltmeli bir kuantum bilgisayarla elde edilebilir. Yazının kendisi böyle bir makine kurmaya dair bir öneri değildir.
Sonra: Yazının tam hâli 1997'de SIAM Journal on Computing'de yayımlandı. Bu algoritmayı gerçek boyutlarda çalıştırmak için gereken hata düzeltme, bu dosyadaki konu 15'in alanıdır.
18. Grover Algoritması
Ana soru: Arama problemleri hızlandırılabilir mi?
Sıralanmamış bir listede aranan öğeyi bulmak için, öğeleri tek tek yoklamaktan iyi bir klasik yol yoktur. Grover 1996'da bir kuantum bilgisayarın bu işi öğe sayısının karekökü kadar adımda yapabildiğini gösterdi. Hız kazancı Shor algoritmasındaki gibi üstel değil, karekök mertebesindedir; ama genel bir arama problemi için geçerlidir.
Proc. 28th Annual ACM Symposium on Theory of Computing (STOC '96), 212–219 kuram
Sıralanmamış bir veri tabanında arama için O(√N) adımlık bir kuantum algoritması veren yazı.
Yazar, sorunu bir telefon rehberi örneğiyle anlatır: N isim rastgele sıralanmış ve aranan kişinin numarası bulunmak isteniyor. Yüzde elli başarı olasılığı için, klasik bir algoritma (belirlenimci ya da olasılıksal) en az N/2 ismi yoklamak zorundadır.
Kuantum sistemler süperpozisyonda bulunabildiği için, çok sayıda ismi aynı anda "yoklayabilir". Yazının önerdiği algoritmada çeşitli işlemlerin fazları dikkatle ayarlanır: başarılı hesaplamalar birbirini güçlendirir, diğerleri rastgele biçimde birbirini söndürür. Sonuç olarak aranan numara yalnız O(√N) adımda elde edilebilir. Yani klasik N/2 yerine karekök mertebesinde adım gerekir. Algoritmanın bilinen yapısı, aynı iki işlemin yinelenmesidir: aranan öğenin fazını çevirmek ve bütün öğelerin ortalamasına göre genlikleri yansıtmak; her turda aranan öğenin genliği biraz artar.
Yazı ayrıca bu algoritmanın olası en hızlı kuantum algoritmasının küçük bir sabit çarpanı içinde olduğunu söyler. Yani genel (yapısız) bir arama için daha büyük bir kuantum hızlanması beklenmez; kazanç karekökle sınırlıdır.
Hız kazancı karekök mertebesindedir; bu yüzden pratik anlamı, problemin boyutuna ve kuantum işlem maliyetine bağlıdır. Yazının özeti yalnız adım sayısı üzerine konuşur; bir cihaz tasarımı vermez.
Bu yazının Shor algoritmasından farkı, hızlanmanın özel bir matematiksel yapıya (periyodiklik) dayanmaması, ama buna karşılık yalnızca karekök kadar olmasıdır. Bu ikisi birlikte okunduğunda, kuantum bilgisayarın hangi problemlerde ne kadar kazanç sağlayabildiği sorusunun cevabı probleme göre değiştiği görülür. Karekök hızlanmanın anlamı şöyle de okunabilir: bir milyon öğelik bir listede klasik arama yarım milyon adım düzeyinde sürerken, kuantum arama bin adım düzeyindedir; bu, büyüklük sırasını gösteren bir örnektir, yazıdaki bir sayı değildir.
Sonra: Algoritma, genel arama ve sayma problemlerinde bir araç olarak sonraki çalışmalarda yaygın biçimde kullanılan bir yapı taşı oldu.
19. BQP: Kuantum Karmaşıklık Sınıfı
Ana soru: Kuantum bilgisayarlar tam olarak ne kadar güçlü?
Karmaşıklık kuramı, problemleri çözmek için gereken kaynağa göre sınıflara ayırır. BQP, bir kuantum bilgisayarın küçük bir hata payıyla verimli (çokterimli sürede) çözebildiği problemlerin sınıfıdır. Bernstein ve Vazirani bu sınıfı tanımladı ve klasik sınıflarla ilişkisini inceledi.
Proc. 25th Annual ACM Symposium on Theory of Computing (STOC '93), 11–20; tam sürüm: SIAM J. Comput. 26 (1997) 1411–1473 kuram
Kuantum Turing makinelerinin karmaşıklık kuramını kuran ve BQP sınıfını klasik sınıflarla ilişkilendiren yazı.
Yazı, kuantum hesaplamayı karmaşıklık kuramı açısından inceler. Birinci sonuç, Deutsch'un kuantum Turing makinesi modelinde verimli bir evrensel kuantum Turing makinesinin var olduğudur. Yazarlar bu yapının klasik karşılığından çok daha karmaşık olduğunu belirtir; döngü, dallanma ve bileşim gibi basit ilkelerin bile kuantum bağlamda zahmetli olduğunu gösterirler.
İkinci sonuç, hassasiyetle ilgilidir. Geçiş genliklerinin ne kadar kesin belirtilmesi gerekir? T adımlık bir hesap için O(log T) bit kesinliğin yettiği gösterilir; böylece kuantum Turing makinesinin analog değil, kesik bir hesaplama modeli sayılabileceği savunulur.
Üçüncü sonuç, klasik modelle ayrımdır. Bir kahin (oracle) varsayıldığında, kuantum Turing makinesinin çokterimli sürede çözdüğü ama hata paylı olasılıksal klasik Turing makinesinin (BPP) çokterimli sürede çözemediği bir problem bulunur. Bu, modern karmaşıklık kuramı anlamında Church–Turing tezini kuantum modelin aştığına dair ilk biçimsel kanıt olarak sunulur; kahinli bir ayrımdır, kahinsiz değildir.
Son olarak BQP tanımlanır ve BPP ⊆ BQP ⊆ P^#P ilişkisi gösterilir. Bunun anlamı, kuantum Turing makinelerinin klasik olasılıksal makinelerden kahinsiz olarak daha güçlü olduğunun matematiksel olarak gösterilmesinin, karmaşıklık kuramında büyük bir ilerleme olmadan mümkün olmadığıdır.
Bu sonuçların pratik anlamı şudur: BQP'nin bilinen klasik sınıflardan kesin biçimde ayrılıp ayrılmadığı bu yazıdan sonra da açık bir sorudur. Yazarlar bunun, kahin gerektirmeyen bir kanıtının, kuramda büyük bir ilerleme anlamına geleceğini açıkça belirtir. Okuyucu için not: BPP, klasik bilgisayarın rastgelelikle ve küçük hata payıyla çokterimli sürede çözdüğü problemler sınıfıdır; P^#P ise çok güçlü, bilinen verimli yöntemlerin çok ötesinde bir klasik sınıftır, yani BQP'nin üst sınırı oldukça gevşektir.
Sonra: Tam metin 1997'de SIAM Journal on Computing'de yayımlandı. Okunan özet SIAM sürümünün özetidir; 1993 bildirisinin kendi metni ayrıca incelenmedi.
20. Kuantum Üstünlüğü (Quantum Supremacy)
Ana soru: Klasik bilgisayarların yapamayacağı bir şey gerçekten yapıldı mı?
Kuantum üstünlüğü, bir kuantum cihazın belirli bir görevi, bilinen en iyi klasik yöntemle makul sürede yapılamayacak kadar hızlı çözmesidir. Görevin yararlı olması gerekmez. Google'ın 2019 tarihli Nature makalesi bunun ilk deneysel iddiasıdır; IBM araştırmacıları aynı yıl, klasik benzetimin iddia edilenden çok daha kısa sürebileceğini ileri sürdü.
53 kübitlik süperiletken Sycamore işlemcisinde rastgele devre örneklemesi yaparak kuantum üstünlüğü iddia eden Google makalesi.
Makale, kuantum bilgisayarların belirli görevleri klasik bilgisayarlardan üstel olarak hızlı yapabileceği vaadinin deneysel bir sınaması olarak sunulur. Zorluk, yüksek doğrulukla çalışan ve çok büyük bir hesap uzayında kuantum algoritmaları çalıştırabilen bir işlemci kurmaktır.
Yazarlar, programlanabilir süperiletken kübitlerden oluşan bir işlemci kullanır ve 53 kübit üzerinde kuantum durumlar üretir; karşılık gelen hesap uzayının boyutu 2^53, yani yaklaşık 10^16'dır. Görev, rastgele seçilmiş bir kuantum devresini çalıştırıp ölçüm sonuçlarını örneklemektir. Sycamore işlemcisi bir devre örneğini bir milyon kez örneklemek için yaklaşık 200 saniye harcar. Yazarlar, kendi kıyaslamalarına göre aynı görevin en gelişmiş klasik süper bilgisayarda yaklaşık 10.000 yıl süreceğini tahmin eder. Ortaya çıkan olasılık dağılımı, klasik benzetimlerle sınanır.
Yazarlar bu sonucu, bilinen bütün klasik algoritmalara göre dramatik bir hız artışı ve kuantum üstünlüğünün bu özel hesaplama görevi için deneysel gerçekleştirilmesi olarak niteler. İki noktaya dikkat etmek gerekir. Birincisi, görev yararlı bir uygulamayı hedeflemez; kuantum devresinin çıktısını örneklemek, hızın ölçüldüğü bir ölçüttür. İkincisi, 10.000 yıl rakamı bir tahmindir ve klasik tarafta daha iyi algoritmaların bulunmasıyla değişebilir; nitekim sonradan tartışma konusu oldu.
Makalenin iddiasının kapsamını belirleyen ifade "bu özel hesaplama görevi için" ifadesidir. Yazarlar yararlı bir problemin çözüldüğünü değil, belirli bir örnekleme görevinde bir hız farkı gözlendiğini bildirir. Makale ayrıca doğrulama sorununu ele alır: bu ölçekte sonucu klasik olarak hesaplamak imkânsıza yakın olduğundan, doğruluk daha küçük devrelerde ve basitleştirilmiş sürümlerde sınanır; bu özet bu ayrıntıya girmez.
Sonra: Aynı yıl Pednault ve arkadaşları, ikincil depolama kullanan benzetimle bu devrelerin bir süper bilgisayarda günler içinde benzetilebileceğini ileri sürdü.
Sycamore devrelerinin klasik bir süper bilgisayarda ikincil depolama kullanılarak günler içinde benzetilebileceğini öne süren yanıt.
Yazarların önceki bir çalışması, ikincil depolamanın (disklerin) klasik benzetimle pratik olarak çalıştırılabilen kuantum devrelerinin aralığını genişletebildiğini göstermişti. Bu yazı o teknikleri geliştirir ve 53 ve 54 kübitli Sycamore devrelerine uygular. Yazı, Google'ın Nature makalesinin yayımlanmasından kısa süre önce, önbaskı olarak çıkmıştır.
İlgilenilen devre örüntüsü (ABCDCDAB adı verilen dolaşıklık deseni), diğer yaklaşımlarla klasik olarak benzetilmesi güç çıkmış olan türdendir. Yazarların çözümlemesine göre Oak Ridge Ulusal Laboratuvarı'ndaki Summit süper bilgisayarında bu devreler, keyfî derinliğe kadar yüksek doğrulukla ve bütün genlikler çıktı olarak verilecek biçimde, birkaç gün içinde benzetilebilir.
Bu bir deney değil, bir hesap çözümlemesidir. Makaledeki "birkaç gün" tahmini, Google makalesindeki "yaklaşık 10.000 yıl" tahmininin karşısına konmuş bir karşı tahmindir. İki tahmin de aynı görevin farklı klasik algoritmalarla maliyetine dayandığından, tartışma bir deney sonucuna değil, bu görevde hangi klasik yöntemin en iyi olduğuna ve kaç doğrulukla hesaplanması gerektiğine dairdir.
Bu karşıt çalışma, "kuantum üstünlüğü" iddialarının klasik algoritmaların ilerlemesine göre değiştirilebilen bir eşik olduğunu gösteren örnek olarak anılır. Okuyucu için not: devre derinliği, kuantum devresinin ardışık kapı katmanı sayısıdır; derinlik arttıkça klasik benzetim genellikle zorlaşır.
Sonra: Tartışma sonraki yıllarda klasik benzetim tekniklerinin geliştirilmesiyle sürdü; bu dosyada ayrıntısı yoktur.