Mengapa komputer kuantum masih belum bisa memfaktorkan 21

• Fenomena yang tampak seolah tidak ada kemajuan sejak 2001, ketika komputer kuantum berhasil memfaktorkan 15
• Rangkaian untuk memfaktorkan 21 memerlukan 100 kali lebih banyak gerbang entanglement dibanding saat memfaktorkan 15
• Perbedaan ini berasal dari kompleksitas perkalian modular bersyarat dan optimasi khusus yang hanya berlaku untuk 15
• Koreksi kesalahan kuantum dan keterbatasan perangkat keras juga makin menaikkan hambatan untuk memfaktorkan 21
• Sebagian besar laporan pemfaktoran 21 hingga kini sebenarnya memakai trik tanpa benar-benar melakukan perkalian dalam arti yang sesungguhnya

---

Mengapa komputer kuantum masih belum bisa memfaktorkan 21

Mengapa pemfaktoran 21 belum muncul setelah pemfaktoran 15

• Pada 2001 ada eksperimen pemfaktoran 15 dengan komputer kuantum
• Meski sudah tahun 2025, masih belum ada contoh sukses pemfaktoran 21
• Hal ini membuat persepsi bahwa komputer kuantum sama sekali tidak mengalami kemajuan
• Namun, jika rangkaian untuk memfaktorkan 15 dan 21 dibandingkan, ada alasan yang jauh lebih mengejutkan

Perbedaan struktural antara rangkaian pemfaktoran 15 dan rangkaian pemfaktoran 21

• Rangkaian pemfaktoran 15 dapat diimplementasikan hanya dengan 21 gerbang kuantum (21 gerbang entanglement)
  • Terdiri dari 6 gerbang entanglement qubit (gerbang CNOT dan CPHASE) dan
  • 2 gerbang Toffoli (masing-masing diuraikan menjadi 6 gerbang entanglement), total 21 gerbang entanglement
• Rangkaian pemfaktoran 21 memerlukan 191 CNOT, 369 Toffoli, total 2405 gerbang entanglement
  • Menimbulkan beban 115 kali lebih banyak gerbang entanglement dibanding memfaktorkan 15
  • Ukuran rangkaian tidak sekadar naik 25% atau 2 kali lipat, tetapi menjadi lebih dari 100 kali lebih mahal
• Bahkan dengan mempertimbangkan tingkat optimasi rangkaian, perbedaan hingga 500 kali juga tampak realistis

Mengapa selisihnya bisa sebesar itu

• Dalam rangkaian pemfaktoran kuantum (algoritme Shor), biaya yang dominan adalah perkalian modular bersyarat
  • Untuk bilangan N dengan n-bit, perkalian modular harus dilakukan ke akumulator beberapa kali secara bersyarat
  • Dalam kasus 15, dari 8 perkalian bersyarat, 6 dapat ditangani sebagai perkalian dengan 1 (tidak melakukan apa pun)
    • Perkalian pertama dapat diimplementasikan hampir gratis karena input-nya 1
    • Perkalian kedua (satu-satunya yang tersisa) juga bisa ditangani dengan murah melalui dua CSWAP
    • Akibatnya, biaya nyata hanya perlu dibayar untuk 2 operasi
    • Struktur ini adalah sifat khusus yang hanya berlaku untuk 15; karena banyak perkalian yang nilainya dekat dengan 1, bebannya jauh lebih ringan
• Namun, dalam kasus 21 semua perkalian bukan 1 dan nilainya beragam, sehingga semua perkalian menimbulkan biaya
  • Semua 8 operasi perkalian menimbulkan biaya; kenaikannya bukan sekadar 4–5 kali, melainkan 20–100 kali
  • Perkalian seperti kali 4 atau 16 tidak memiliki struktur yang bisa diimplementasikan dengan CSWAP (conditional swap)
  • Kompleksitas perkalian berbeda-beda untuk tiap operasi, dan optimasinya tidak mudah

Batasan nyata perangkat keras dan koreksi kesalahan

• Pemfaktoran 15 pada masa lalu (2001) diimplementasikan dengan komputer kuantum NMR, yang punya banyak keterbatasan untuk penskalaan
• Lebih jauh lagi, kebutuhan akan koreksi kesalahan kuantum juga makin besar
  • Jika jumlah gerbang 100 kali lebih banyak, tingkat kesalahannya juga harus 100 kali lebih rendah
  • Dalam praktiknya, jumlah qubit pun bisa perlu ditingkatkan 100 kali, sehingga total biaya berpotensi naik hingga 10.000 kali

Kontroversi upaya pemfaktoran dan hasil-hasil yang keliru

• Beberapa makalah terbaru mengklaim berhasil memfaktorkan 21 dengan komputer kuantum, tetapi
  • pada kenyataannya mereka sering menghilangkan langkah perkalian dalam algoritme atau menyederhanakan rangkaian karena hasilnya sudah diketahui sebelumnya
  • tanpa benar-benar melakukan operasi perkalian, hal itu tidak bisa dianggap sebagai pemfaktoran
  • ini adalah hasil formalitas yang mengabaikan perbedaan mendasar antara sekadar "pencarian periode" dan esensi pemfaktoran
• Beberapa makalah bahkan terang-terangan memakai trik, dan ada pula makalah satir yang menanggapi penelitian tersebut
  • Ada berbagai makalah satir seperti eksperimen replikasi rekor juara pemfaktoran
  • Benchmark seperti variational factoring terus bermunculan meski tidak punya dasar untuk menunjukkan kemampuan penskalaan

Apa indikator kemajuan komputer kuantum yang benar

• Pada titik ini, pemfaktoran bukan benchmark utama kemajuan komputer kuantum
  • Setelah melewati 15, biaya melonjak tajam sehingga verifikasi praktis menjadi sulit
• Sebaliknya, penerapan koreksi kesalahan kuantum (misalnya peningkatan surface code) atau
  • perubahan arsitektur perangkat keras yang menyelesaikan masalah penskalaan (misalnya penggantian atom netral secara berkelanjutan)
  • adalah titik pengamatan yang lebih penting untuk menunjukkan kemajuan yang nyata

[GN⁺]

Komentar Hacker News

• Ini karena sejauh ini mereka bahkan belum pernah benar-benar memfaktorkan bilangan yang lebih kecil. Jika proses kompilasi program hanya bisa berjalan bila sudah mengetahui jawabannya terlebih dahulu, maka itu bukan faktorisasi sungguhan, melainkan sekadar "mencetak 3"

• Saya penasaran berapa banyak quantum gate yang benar-benar dibutuhkan untuk memfaktorkan bilangan yang bermakna secara kriptografis. Saya juga ingin tahu apakah ada jalur yang benar-benar realistis menuju munculnya komputer kuantum yang berguna dalam abad ini

  • Sebagai contoh, dapat disebutkan estimasi pada Table 5 dari makalah yang menyatakan bahwa faktorisasi RSA 2048 memerlukan sekitar 7 miliar Toffoli gate (tautan makalah). Cara untuk mencapai operasi dalam jumlah miliaran adalah quantum error correction, dan makalah itu menyebut surface code distance 25 sudah cukup. Dalam kasus ini, 1.400 qubit logis berkembang menjadi sekitar 1 juta qubit fisik yang berisik. Presentasi Samuel Jacques di PQCrypto juga layak dirujuk (YouTube). Saya adalah penulis blog ini dan makalah terkaitnya
  • Ada dua alasan mengapa pertanyaan ini sulit. Pertama, tidak ada batas yang jelas untuk apa yang disebut 'bermakna secara kriptografis'. Kedua, arsitektur QC yang benar-benar mampu melakukan operasi ini juga belum diketahui secara jelas. Ini agak mirip dengan memperkirakan jumlah gerbang logika klasik yang dibutuhkan untuk membuat jaringan saraf pada tahun 1985. Meski begitu, tampaknya jelas bahwa dibutuhkan lebih dari jutaan gate. Ketiga, ada trade-off dalam quantum error correction antara tingkat kesalahan qubit mentah yang lebih rendah dan jumlah gate yang dibutuhkan untuk membangun qubit virtual dengan koreksi kesalahan yang andal. Kita belum tahu seberapa rendah tingkat kesalahan qubit mentah bisa dicapai di masa depan. Jika komputer kuantum mengalami kemajuan serupa dengan perkembangan komputer selama 75 tahun terakhir, maka diperkirakan kriptografi lama akan sepenuhnya lumpuh sekitar tahun 2100. Sampai ada satu inovasi besar seperti transistor, prediksi tetap sulit. Perkembangan teknologi selalu tampak mustahil, sampai seseorang pertama kali menemukan caranya. (penjelasan UNIVAC I)
  • Tweet terkait terbaru juga bisa dirujuk (tautan tweet). Dari sudut pandang orang awam, jalur tersebut tampak tertutup oleh beberapa terobosan besar dalam ilmu material
  • Untuk RSA 4096, secara kasar dibutuhkan 10^7 qubit dengan tingkat kesalahan 10^-4. Sudah dimungkinkan melakukan perhitungan kimia kuantum yang berguna hanya dengan sekitar 100 qubit, dan seiring algoritma post-quantum makin menyebar, motivasi untuk mengembangkan komputer kuantum pemecah kriptografi juga menurun. Saya rasa komputasi kuantum akan berkembang lebih cepat ke arah yang tidak terkait dengan kriptografi
  • Angka terbarunya adalah membutuhkan sekitar 1 juta qubit pada tingkat kesalahan 1e-4 (tautan makalah). Jumlah gate diukur berbeda-beda di tingkat kode tergantung operasi sebenarnya, dan dengan "clock" 1MHz (waktu siklus kode), total waktu komputasinya sekitar satu minggu. Mencapai waktu komputasi ini adalah metrik yang lebih sulit daripada jumlah qubit. Berkat efek ajaib quantum error correction (jumlah qubit turun drastis ketika tingkat error makin rendah), peningkatan satu tingkat pada kualitas qubit dapat membuat jumlah qubit yang dibutuhkan anjlok. Sebaliknya, jika operasi harus dibagi ke beberapa sistem, keadaannya akan memburuk drastis

• Makalah 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' menarik (baca makalah)

• Saya tertarik pada ukuran sirkuit dan kelayakan realisasi untuk memfaktorkan angka yang bermakna secara kriptografis seperti RSA1024

  • Estimasi biaya RSA1024 dihitung bukan dengan sekadar menskalakan dari bilangan kecil (seperti 4-bit), tetapi melalui desain sirkuit yang sesuai dengan skala sebenarnya. Artinya, masalah diskontinuitas yang dibahas dalam tulisan ini sudah tercermin secara implisit. Jadi, postingan ini tidak memengaruhi estimasi biaya yang sudah ada
  • (Catatan: optimasi sirkuit faktorisasi 21 kemungkinan sulit diterapkan saat memfaktorkan bilangan besar. Dibanding sirkuit faktorisasi 15, biaya 500 kali lipat mungkin lebih realistis. Tentu saja, overhead 100 kali pun sudah cukup untuk menjelaskan poin utamanya. Ucapan terima kasih khusus kepada Noah Shutty yang telah melakukan pencarian komputasi mahal untuk optimasi sirkuit tersebut)
  • Sedikit keluar dari topik, tetapi saya penasaran apakah para kriptografer yakin bahwa bahkan pusat data superbesar pun secara praktis tidak mampu memfaktorkan RSA1024 belakangan ini. Saat ini, bahkan algoritma tercepat pun tidak bisa memfaktorkannya dalam waktu yang realistis. Namun, saya ingin tahu apakah ada konsensus bahwa dalam waktu dekat tidak akan ada peningkatan revolusioner pada algoritma tersebut

• Saya penasaran apakah suatu hari komputer kuantum bisa menargetkan post-quantum RSA (makalah terkait). Ada juga pandangan bahwa operasi RSA biasa (pembuatan kunci, enkripsi, dekripsi) secara asimetris lebih menguntungkan terhadap algoritma Shor, sehingga cukup memakai kunci yang sangat besar. Ini memberi efek mirip Merkle puzzle, dengan syarat tambahan bahwa penyerang harus menyerang menggunakan komputer kuantum. Dulu saya pernah membuat kunci publik RSA gigabit (file kunci). Formatnya: jumlah byte kunci 4-byte little-endian, lalu kuncinya, lalu invers kunci (mod 256^bytes). Eksponen publiknya adalah 3

  • Post-Quantum RSA adalah lelucon yang dibuat djb untuk menjawab pertanyaan "kalau pakai kunci besar saja bukannya aman?". Dirancang agar butuh 100 jam untuk satu kali enkripsi dengan kunci 1TB. Bahkan komputer kuantum pun tidak bisa membobolnya

• Saya cukup terhibur melihat typo "error corection"

• Saya sulit memahami bagian "biaya sirkuit 500 kali dibanding faktorisasi-15". Penulis sudah memberi contoh 115 kali, jadi saya penasaran bagaimana optimasi tambahan justru bisa menghasilkan hasil yang lebih buruk

  • Ini berarti jumlah kerja optimasi yang luar biasa besar yang dicurahkan untuk membuat sirkuit faktorisasi bilangan kecil secara realistis tidak mungkin dilakukan untuk bilangan besar. Jadi, secara umum masuk akal bahwa saat bilangan yang akan difaktorkan membesar, dibutuhkan kira-kira 500 kali lebih banyak gate (bukan sekadar sedikit seperti 115 kali)
  • Pada skala besar, efek optimasi memang akan berkurang, dan keuntungannya tidak akan sebesar sirkuit N=21
  • Implementasi minimal itu rapuh dan sulit menjamin keandalan. Pengembangan sirkuit praktis memerlukan banyak riset untuk mengamankan qubit yang stabil, dan konsep seperti "decoherence time" juga disebut. Karena itu, jumlah qubit hampir pasti akan meningkat secara eksplosif
  • Angka 115 kali adalah hasil dari banyak optimasi yang (tidak realistis)

• Saya bertanya-tanya apakah inti postingan ini menyiratkan bahwa kebutuhan sirkuit Big-O untuk faktorisasi Schorr bersifat superpolinomial

  • Menurut isi tulisannya, biaya gate terutama berasal dari O(n) operasi perkalian modular, dan setiap operasi dapat diimplementasikan dengan O(n^2) gate. Secara keseluruhan, bahkan dalam kasus terburuk tampaknya tetap sekitar kompleksitas kubik

• Alasan adopsi kriptografi PQ (post-quantum) bukan semata karena yakin QC pasti segera hadir. Tidak pasti kapan QC akan muncul karena bergantung pada laju perkembangan teknologinya. Tujuan teknologi kriptografi adalah mencari metode yang secara teoretis pun hampir mustahil dipecahkan, dan jika secara teoretis serangan dimungkinkan maka secara fisik pun ada kemungkinan, sehingga harus diantisipasi. Untuk ECC dan RSA, jalur teoretis serangannya sudah diketahui, jadi dianggap bisa diserang meskipun perangkat nyatanya belum ada. Karena itu, sangat masuk akal untuk bersiap sebelumnya saat QC belum ada. Sebaliknya, untuk SHA2, AES, ChaCha, dan sebagainya, belum terlihat jalur serangan yang realistis sehingga belum ada rencana penggantian segera. Enkripsi bukan satu-satunya, atau bahkan bukan arah aplikasi terpenting dari QC. Ada harapan bahwa inovasi yang belum kita ketahui masih bisa muncul di berbagai bidang seperti sistem fisik, pelipatan protein, machine learning, dan lain-lain

  • Saya penasaran apakah bidang seperti pelipatan protein masih punya ruang perkembangan lebih jauh ke depan (bahkan setelah AlphaFold). (artikel rujukan)

  • Untuk kriptografi kunci simetris (AES, ChaCha, SHA-2), serangan kuantum pada dasarnya menimbulkan efek pelemahan setara setengah panjang kunci (seperti pada kasus 3DES dan 2DES). Dalam praktiknya, performa komputer kuantum nyata tidak sepenuhnya setara atau identik, jadi tidak bisa dipastikan sesederhana sekadar separuh, tetapi mengganti ke AES-256 sudah cukup sehingga tidak menjadi masalah. Namun yang perlu benar-benar difokuskan adalah Key Exchange. Alasannya, Key Exchange digunakan untuk menyepakati kunci rahasia tanpa kedua pihak langsung mengungkapkan kuncinya. Jika ada Quantum Computer, percakapan masa lalu yang sempat direkam juga bisa dibaca. Jika algoritma tanda tangan dibobol, kita tidak otomatis bisa kembali ke masa lalu untuk memalsukan tanda tangan lama, tetapi jika Key Exchange dibobol, semua percakapan masa lalu ikut terekspos, sehingga itu yang paling penting untuk segera diganti dengan alternatif yang aman