Kuantum bilgisayarlar neden hâlâ 21’i asal çarpanlarına ayıramadı?

• 2001’de bir kuantum bilgisayarla 15’in asal çarpanlarına ayrılmasından sonra ilerleme yokmuş gibi görünen durum açıklanıyor
• 21’i asal çarpanlarına ayıran bir devre, 15’i ayırırken gerekenden 100 kat daha fazla dolanıklık kapısı gerektiriyor
• Bu fark, koşullu modüler çarpma işleminin karmaşıklığından ve yalnızca 15 için geçerli özel optimizasyonlardan kaynaklanıyor
• Kuantum hata düzeltme ve donanım sınırları da 21’in çarpanlara ayrılmasına giden eşiği daha da yükseltiyor
• Bugüne kadar bildirilen 21 çarpanlara ayırma sonuçlarının çoğu, gerçek anlamda çarpma yapmadan hile kullanılan örneklerdi

---

Kuantum bilgisayarlar neden hâlâ 21’i asal çarpanlarına ayıramadı?

15’in çarpanlara ayrılmasından sonra 21’in neden gelmediği

• 2001’de bir kuantum bilgisayarla 15’i asal çarpanlarına ayıran bir deney yapıldı
• 2025 olmuş olmasına rağmen hâlâ 21’in çarpanlara ayrılması için başarılı bir örnek yok
• Bu durumdan hareketle, kuantum bilgisayarlarda hiç ilerleme olmadığı yönünde bir algı yayılmış durumda
• Ancak gerçekte 15 ve 21 için çarpanlara ayırma devreleri karşılaştırıldığında, bunun arkasında çok daha şaşırtıcı bir neden var

15 için çarpanlara ayırma devresi ile 21 için devre arasındaki yapısal fark

• 15’i çarpanlara ayıran devre yalnızca 21 kuantum kapısıyla (21 dolanıklık kapısı) gerçekleştirilebiliyor
  • 6 iki-kübit dolanıklık kapısı (CNOT ve CPHASE kapıları) ve
  • 2 Toffoli kapısından (her biri 6 dolanıklık kapısına ayrıştırılıyor), toplam 21 dolanıklık kapısından oluşuyor
• 21’i çarpanlara ayıran devre için 191 CNOT, 369 Toffoli, toplam 2405 dolanıklık kapısı gerekiyor
  • Bu, 15’i çarpanlara ayırmaya göre 115 kat daha fazla dolanıklık kapısı yükü anlamına geliyor
  • Devre boyutu yalnızca %25 ya da 2 kat artmıyor; 100 kattan fazla pahalı hâle geliyor
• Devre optimizasyon düzeyi hesaba katılsa bile, gerçekte 500 kata varan fark mümkün görünüyor

Bu kadar büyük fark neden ortaya çıkıyor?

• Kuantum çarpanlara ayırma devrelerinde (Shor algoritması) baskın maliyet kalemi koşullu modüler çarpma işlemi
  • n bitlik bir N sayısı için, biriktirici üzerinde birçok kez koşullu modüler çarpma yapılması gerekiyor
  • 15 durumunda, 8 koşullu çarpmanın 6’sı 1 ile çarpma (yani hiçbir işlem yok) olarak ele alınabiliyor
    • İlk çarpma, giriş 1 olduğu için neredeyse bedava uygulanabiliyor
    • İkinci (kalan tek örnek) de iki CSWAP ile ucuza gerçekleştirilebiliyor
    • Sonuç olarak gerçekte yalnızca 2 tanesi için maliyet ödeniyor
    • Bu yapı yalnızca 15’e özgü özel bir özellik; 1’e yakın çok sayıda çarpma olduğundan yük belirgin biçimde azalıyor
• Ancak 21 durumunda çarpmaların hiçbiri 1 değil ve değerleri farklı, bu yüzden her çarpma maliyet yaratıyor
  • 8 çarpma işleminin tamamı maliyetli; artış yalnızca 4-5 kat değil, 20-100 kat düzeyinde
  • 4 ya da 16 ile çarpma gibi işlemler CSWAP (koşullu takas) ile gerçekleştirilebilen bir yapıda değil
  • Çarpmanın karmaşıklığı her işlemde farklılaşıyor ve optimizasyon kolay değil

Donanım ve hata düzeltmede pratik sınırlar

• Geçmişteki (2001) 15 çarpanlara ayırma deneyi NMR kuantum bilgisayarı ile gerçekleştirildi ve ölçeklenme açısından ciddi sınırlara sahipti
• Bunun ötesinde, kuantum hata düzeltme gereksinimi de büyüyor
  • Kapı sayısı 100 kat artarsa hata oranının da 100 kat daha düşük olması gerekiyor
  • Gerçekte kübit sayısının da 100 kat artırılması gerekebileceğinden, toplam maliyet 10.000 kata kadar çıkabiliyor

Çarpanlara ayırma denemeleri etrafındaki tartışmalar ve hatalı sonuçlar

• Son dönemde bazı makaleler kuantum bilgisayarla 21’i çarpanlara ayırmada başarı iddia etse de
  • pratikte çoğu, algoritmanın çarpma adımını atlıyor ya da sonucu önceden bilip devreyi sadeleştiriyor
  • Gerçek çarpma işlemi yapılmadığı sürece buna çarpanlara ayırma denemez
  • Yalnızca “periyot bulma” ile çarpanlara ayırmanın özündeki farkı göz ardı eden yüzeysel sonuçlar bunlar
• Bazı makalelerde açıkça hileye başvuruluyor; hatta bu çalışmaları tiye alan hiciv makaleleri bile yayımlandı
  • Çarpanlara ayırma şampiyonu kayıtlarının kopyalanmasına dair deneyler gibi çeşitli hiciv makaleleri var
  • Variational factoring gibi, ölçeklenebilirliğe dair dayanağı olmayan benchmark’lar tekrar tekrar ortaya çıkıyor

Kuantum bilgisayarlardaki gerçek ilerlemenin göstergesi ne olmalı?

• Bugün itibarıyla çarpanlara ayırma, kuantum bilgisayar ilerlemesi için başlıca benchmark değil
  • 15’in ötesine geçildiğinde maliyet patladığı için pratik doğrulama zorlaşıyor
• Bunun yerine kuantum hata düzeltmenin devreye alınması (ör. surface code iyileştirmeleri) ya da
  • ölçeklenme sorununu çözen donanım mimarisi değişiklikleri (ör. nötr atomların sürekli değiştirilmesi gibi)
  • gerçek ilerlemeyi gösteren daha önemli gözlem noktaları olarak öne çıkıyor

[GN⁺]

Hacker News görüşleri

• Bunun nedeni, şimdiye kadar daha küçük sayıları bile gerçekten çarpanlarına ayırmamış olmamız. Eğer bir programın derleme süreci çalışmak için cevabı zaten bilmek zorundaysa, bu gerçek bir çarpanlara ayırma değil, sadece "3 yazdır"maktır diye düşünüyorum

• Gerçekten kriptografik açıdan anlamlı bir sayıyı çarpanlarına ayırmak için kaç quantum gate gerektiğini merak ediyorum. Bu yüzyıl içinde işe yarar bir kuantum bilgisayarın ortaya çıkmasına dair pratikte bir yol olup olmadığını da bilmek isterim

  • 2048 bit RSA'nın çarpanlara ayrılması için yaklaşık 7 milyar Toffoli gate gerektiğine dair makaledeki Table 5 tahmini örnek verilebilir (makale bağlantısı). On milyarlarca işlemi başarmanın yolu kuantum hata düzeltmedir ve makaleye göre distance 25 surface code yeterlidir. Bu durumda 1.400 mantıksal kübitten yaklaşık 1 milyon gürültülü fiziksel kübite ölçeklenir. PQCrypto'daki Samuel Jacques konuşmasına da bakmaya değer (YouTube). Ben bu blogun ve ilgili makalenin yazarıyım
  • Bu sorunun zor olmasının iki nedeni var. Birincisi, 'kriptografik olarak anlamlı' sınırını çizmek mümkün değil. İkincisi, bu işlemi gerçekten yapabilecek bir QC mimarisinin nasıl olacağı henüz net olarak bilinmiyor. Bir bakıma 1985'te sinir ağları yapmak için kaç klasik mantık kapısı gerekeceğini tahmin etmeye benziyor. Yine de milyonlarca gate'in üzerinde bir ihtiyaç olacağı açık görünüyor. Üçüncü olarak, kuantum hata düzeltmede daha düşük ham kübit hata oranı ile güvenilir hata düzeltilmiş sanal kübitler kurmak için gereken gate sayısı arasında bir ödünleşim var. Gelecekte ham kübit hata oranlarının ne kadar düşeceğini şu anda bilmiyoruz. Son 75 yıldaki bilgisayar gelişimine benzer bir ilerleme kuantum bilgisayarlarda da yaşanırsa, 2100 civarında mevcut kriptografi tamamen etkisiz hale gelebilir diye tahmin ediyorum. Transistör gibi tek seferlik büyük bir yenilik ortaya çıkana kadar öngörü yapmak zor. Teknolojik ilerleme hep imkansız görünür, ta ki biri ilk yöntemi bulana kadar. (UNIVAC I açıklaması)
  • İlgili yakın tarihli bir tweet'e de bakılabilir (tweet bağlantısı). Sıradan birinin gözünden bakınca bu yol, çok sayıda büyük malzeme bilimi atılımının arkasında gizlenmiş gibi görünüyor
  • RSA 4096 için kabaca 10^7 kübit ve 10^-4 hata oranı gerekiyor. Daha şimdiden yaklaşık 100 kübit ile faydalı kuantum kimyası hesapları yapılabiliyor ve post-quantum algoritmalar yaygınlaştıkça şifre kırmaya yönelik kuantum bilgisayar geliştirme motivasyonu azalıyor. Kuantum bilişimin, kriptografi dışındaki alanlarda daha hızlı ilerleyeceğini düşünüyorum
  • Güncel rakamlar, 1e-4 hata oranında yaklaşık 1 milyon kübit gerektiğini gösteriyor (makale bağlantısı). Gate sayısı, kod seviyesinde gerçek işleme bağlı olarak farklı ölçülüyor ve 1MHz "clock" (kod çevrimi süresi) temelinde tüm hesaplama yaklaşık bir hafta sürüyor. Hesaplama süresine ulaşmak, kübit sayısına ulaşmaktan daha zor bir metrik. Kuantum hata düzeltmenin büyüleyici etkisi sayesinde (hata oranı düştükçe kübit sayısı ciddi biçimde azalıyor) kübit kalitesinde bir kademe ilerleme, gereken kübit sayısını keskin biçimde düşürüyor. Buna karşılık, işlemleri birden fazla sisteme bölmek zorunda kalırsanız durum çok daha kötüleşiyor

• 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' makalesi ilginç (makaleyi oku)

• RSA1024 gibi kriptografik olarak anlamlı sayıların çarpanlara ayrılması için devre boyutu ve uygulanabilirlikle ilgileniyorum

  • RSA1024 için maliyet tahminleri, küçük sayılardan (örneğin 4 bit) basit ölçekleme ile değil, gerçek ölçeğe uygun devre tasarımları üzerinden yapılıyor. Yani bu yazıda sözü edilen süreksizlik sorunu zaten örtük olarak hesaba katılmış durumda. Bu nedenle bu gönderi mevcut maliyet tahminlerini etkilemiyor
  • (Not: 21'i çarpanlara ayıran devrenin optimizasyonunu büyük sayıları çarpanlara ayırırken uygulamak zor olacaktır. 15'i çarpanlara ayıran devreye göre 500 kat maliyet daha gerçekçi olabilir. Elbette 100 kat ek yük bile ana fikri açıklamak için yeterli. Noah Shutty'ye, söz konusu devre optimizasyonu için pahalı bilgisayar araması yaptığı için özellikle teşekkürler)
  • Konudan biraz sapıyor ama, kriptografların yakın zamanda dev veri merkezleriyle bile RSA1024'ü çarpanlara ayırmanın pratikte imkansız olduğundan emin olup olmadığını merak ediyorum. Şu an en hızlı algoritmalar bile bunu gerçekçi bir sürede yapamıyor. Ama bu algoritmalarda yakında çığır açıcı bir iyileşme olmayacağı konusunda bir uzlaşma var mı, görüşleri merak ediyorum

• Bir gün kuantum bilgisayarların post-quantum RSA'yı hedef alıp alamayacağını merak ediyorum (ilgili makale). Normal RSA işlemlerinin (anahtar üretimi, şifreleme, şifre çözme) Shor algoritmasına karşı asimetrik biçimde avantajlı olduğu, dolayısıyla yeterince büyük anahtarların yeterli olabileceği görüşü de var. Bu biraz Merkle puzzles'a benzer bir etki yaratıyor ve saldırganın mutlaka kuantum bilgisayar kullanması şartını ekliyor. Bir zamanlar gigabit RSA açık anahtarı üretmiştim (anahtar dosyası). Biçim şöyle: 4 bayt little-endian anahtar bayt sayısı, ardından anahtar ve anahtarın tersi (256^bytes mod). Açık üs 3

  • Post-Quantum RSA, djb'nin "sadece büyük anahtarlar kullansak güvenli olmaz mı" sorusuna cevap olarak ürettiği bir şaka. 1TB anahtarla, her şifreleme işleminin 100 saat sürmesi için tasarlanmış. Kuantum bilgisayarla da kırılamaz

• "error corection" yazım hatasını görmek oldukça komikti

• "Factoring-15 ile karşılaştırıldığında 500 kat devre maliyeti" kısmını anlamakta zorlanıyorum. Yazar zaten 115 katlık bir örnek vermişken, ek optimizasyon nasıl daha kötü bir sonuç doğuruyor, merak ediyorum

  • Bu, küçük sayıların çarpanlara ayrılması için devre oluşturmaya harcanan devasa optimizasyon emeğinin büyük sayılar için pratikte mümkün olmadığını ifade ediyor. Yani genel olarak, çarpanlara ayrılacak sayı büyüdüğünde yaklaşık 500 kat daha fazla gate gerekmesi sezgisel olarak daha doğru (115 kat kadar az değil)
  • Gerçekten büyük ölçekte optimizasyonun etkisi azalır ve N=21 devresindeki kadar büyük kazanç sağlamaz
  • En minimal uygulama kararsızdır ve güvenilirlik garantisi vermez. Pratik devre geliştirme için kararlı kübitler elde etmeye yönelik çok araştırma gerekir ve "decoherence time" gibi kavramlar da gündeme gelir. Bu yüzden kübit sayısının patlayıcı biçimde artması kaçınılmazdır
  • 115 kat, çok sayıda (gerçekçi olmayan) optimizasyon uygulanmasının sonucudur

• Bu gönderinin ana fikrinin, Shor'un çarpanlara ayırma yöntemi için Big-O devre gereksiniminin süper polinomsal olduğunu ima edip etmediğini merak ediyorum

  • Yazıya göre gate maliyeti esas olarak O(n) adet modüler çarpma işleminden geliyor ve her bir işlem O(n^2) gate ile gerçekleştirilebiliyor. Toplamda, en kötü durumda bile yaklaşık kübik karmaşıklık gibi görünüyor

• PQ (post-quantum) kriptografinin benimsenme nedeni, mutlaka yakında bir QC çıkacağından emin olunması değil. Teknoloji geliştirme hızına bağlı olarak QC'nin ne zaman geleceği belirsiz. Kriptografinin amacı, teorik olarak bile neredeyse kırılamaz yöntemler bulmaktır; teorik olarak bir saldırı mümkünse fiziksel olarak da bir gün mümkün olabilir, bu yüzden hazırlık yapılır. ECC ve RSA için teorik saldırı yolu gösterildiği için, ortada gerçek cihaz olmasa da bunların kırılabilir olduğu kabul ediliyor. Bu nedenle QC henüz yokken önceden hazırlanmak gayet makul bir yaklaşım. Öte yandan SHA2, AES, ChaCha gibi sistemler için pratik bir saldırı yolu görünmediğinden, şu anda bunları değiştirmeye yönelik bir plan yok. Şifreleme, QC'nin tek ya da en önemli uygulama alanı değil. Fiziksel sistemler, protein katlanması, makine öğrenimi gibi alanlarda da henüz bilmediğimiz yeniliklerin çıkabileceği umuluyor

  • Protein katlanması gibi alanlarda ileride daha fazla gelişme potansiyeli olup olmadığını merak ediyorum (AlphaFold'dan sonra da). (ilgili yazı)

  • Simetrik anahtarlı şifrelerde (AES, ChaCha, SHA-2) kuantum saldırılar fiilen anahtar uzunluğunu yarıya indirme etkisi yaratır (3DES ve 2DES örneklerinde olduğu gibi). Pratikte gerçek kuantum bilgisayarların performansı eşdeğer ya da aynı olmayacağından bunun tam olarak yarıya düşeceği söylenemez ama AES-256'ya geçmek mümkün olduğundan sorun değil. Asıl odaklanılması gereken yer Key Exchange. Çünkü Key Exchange, gizli anahtarı tarafların doğrudan paylaşmadan anlaşması için kullanılır. Eğer Quantum Computer varsa, geçmişte kaydedilmiş konuşmaları da okuyabilir. Bir imza algoritmasını kırmak, geçmişe dönüp imza atmayı sağlamaz; ama Key Exchange kırılırsa geçmiş konuşmaların tamamı açığa çıkar. Bu yüzden Key Exchange için güvenli bir alternatif acilen gerekiyor