Algoritma Shor

Bagian 1: Algoritma Shor – “Pemecah Kriptografi”

Algoritma Shor, ditemukan oleh Peter Shor pada tahun 1994, adalah algoritma kuantum yang mampu memfaktorkan bilangan bulat besar menjadi faktor-faktor primanya dengan waktu yang sangat singkat.

Mengapa Ini Penting?

Kriptografi modern (misalnya, sistem keamanan perbankan online, WhatsApp, HTTPS) bertumpu pada satu asumsi: sulitnya memfaktorkan bilangan besar.

Contoh: Saya beri Anda bilangan 15. Faktornya adalah 3 x 5. Mudah.
Contoh sulit: Saya beri Anda bilangan 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541. Ini adalah bilangan RSA-100 (100 digit). Komputer klasik terbaik butuh waktu bertahun-tahun untuk memfaktorkannya. Sistem keamanan RSA menggunakan bilangan dengan 300-600 digit.

Logika keamanan RSA:

Saya ambil dua bilangan prima besar, p dan q (rahasia).
Saya kalikan: N = p × q (N dipublikasikan sebagai kunci publik).
Untuk memecahkan sandi, penyerang harus mencari p dan q dari N.
Karena komputer klasik lambat memfaktorkan, pesan dianggap aman.

Algoritma Shor menghancurkan asumsi ini. Komputer kuantum dengan ribuan qubit stabil bisa memfaktorkan RSA-600 dalam hitungan jam.

Cara Kerja Algoritma Shor (Intuisi, Tanpa Rumus Rumit)

Algoritma Shor tidak langsung mencari faktor. Ia melakukan trik cerdas dengan memanfaatkan superposisi dan transformasi Fourier kuantum.

Langkah-langkah konseptual:

Tebak angka acak (sebut saja a). Kita gunakan komputer klasik untuk ini. Angkanya tidak perlu benar.
Cari “periode” fungsi (Ini inti kuantumnya): Kita buat fungsi f(x) = a^x mod N. Fungsi ini, jika dihitung, akan menghasilkan pola yang berulang (periodik) dengan periode r. Menemukan periode r ini adalah pekerjaan super berat untuk komputer klasik, tetapi sangat cepat untuk komputer kuantum.
- Komputer klasik harus menghitung a^1, a^2, a^3,... satu per satu sampai polanya berulang. Itu butuh miliaran langkah untuk N besar.
- Komputer kuantum menyiapkan semua x dari 0 sampai N^2 secara superposisi (ribuan miliar nilai sekaligus). Lalu ia hitung semua f(x) secara simultan. Kemudian ia gunakan Transformasi Fourier Kuantum (QFT) untuk mengukur “frekuensi” utama dari pola tersebut, yang langsung memberikan periode r.
Gunakan periode r untuk mencari faktor: Begitu kita punya r, ada perhitungan matematika sederhana (menggunakan algoritma Euclid) yang akan menghasilkan faktor-faktor prima dari N dengan probabilitas tinggi.

Analogi Sederhana:

Komputer klasik: Seperti mencari periode gelombang dengan mengukur satu per satu puncak gelombang, dari awal sampai akhir. Butuh waktu lama.
Komputer kuantum (Shor): Seperti menangkap seluruh gelombang, lalu memasang filter frekuensi. Dalam satu kali pengukuran, Anda langsung melihat frekuensi dominannya. Itulah periodenya.

Dampak Algoritma Shor

Bidang	Dampak
Keamanan Digital	RSA, ECC (Elliptic Curve Cryptography), dan sebagian besar kriptografi asimetris saat ini akan menjadi usang. Semua data yang pernah dikirim dengan aman di masa lalu bisa didekripsi di masa depan (“harvest now, decrypt later”).
Respons	Perkembangan Kriptografi Pasca-Kuantum (PQC) – algoritma baru yang tahan terhadap serangan komputer kuantum (misal, berbasis lattice, hash, atau kode). NIST sudah memilih beberapa calon standar.
Keuntungan	Bisa juga untuk kebaikan: memfaktorkan bilangan besar bisa memecahkan masalah matematika fundamental.

Bagian 2: Koreksi Kesalahan Kuantum (Quantum Error Correction – QEC)

Inilah “Achilles’ Heel” komputer kuantum. Tanpa QEC, komputer kuantum tidak akan pernah bisa diskalakan ke ukuran yang berguna (ratusan ribu atau jutaan qubit).

Masalah Utama: Dekohorensi dan Kesalahan

Dunia kuantum sangat rapuh. Qubit bisa kehilangan superposisinya karena:

Getaran termal (panas)
Fluktuasi medan elektromagnetik
Radiasi latar (kosmik sekalipun)
Ketidaksempurnaan manufaktur

Kesalahan pada qubit bukan hanya “bit flip” (0 jadi 1 atau 1 jadi 0), tetapi juga “phase flip” (perubahan tanda fase dalam superposisi). Lebih rumit lagi, karena mengukur qubit akan merusak superposisinya, Anda tidak bisa langsung mengecek apakah suatu qubit error dengan cara biasa.

Solusi Brilian: Logika “Bersembunyi” dalam Banyak Qubit Fisik

Prinsip dasar QEC: Jangan simpan informasi di satu qubit saja. Sebarkan informasi logis ke banyak qubit fisik yang terjerat (entangled).

Contoh Paling Sederhana: Kode Repetisi Kuantum (Kode 3-Qubit)

Meskipun ini terlalu sederhana untuk koreksi penuh, ia mengilustrasikan konsepnya.

Konsep Klasik (Kode Repetisi 3-bit)	Konsep Kuantum (Kode Repetisi 3-qubit)
Simpan bit 0 sebagai `000`, bit 1 sebagai `111`.	Simpan qubit logis `0>` sebagai `000>` + `111>` (superposisi). Simpan `1>` sebagai `000>` – `111>`).
Jika satu bit terbalik (misal `010`), mayoritasnya masih 0. Kita lihat dan perbaiki.	Masalah: Jika saya lihat (ukur) qubit fisik untuk cek mayoritas, superposisi hancur.
Solusi Kuantum: Gunakan qubit bantu (ancilla) dan gerbang kuantum khusus (CNOT) untuk mengukur sindrom error tanpa mengukur qubit data itu sendiri. Anda hanya tahu “apakah ada yang error?” dan “qubit mana?”, tetapi tidak tahu isi informasinya.

Kode Permukaan (Surface Code) – Paling Populer Saat Ini

Ini adalah arsitektur QEC yang digunakan oleh Google, IBM, dan lainnya.

Susunan 2D: Qubit data disusun dalam kisi persegi. Di antara mereka, ada qubit pengukur (sindrom).
Cara Kerja: Qubit pengukur terus-menerus melakukan operasi keterikatan dengan qubit tetangganya. Hasil pengukuran sindrom ini (disebut “stabilizer”) memberi tahu lokasi dan jenis error (bit flip atau phase flip) tanpa mengganggu data kuantum.
Koreksi: Begitu error terdeteksi, sinyal dikirim untuk membalik kembali qubit yang error (dengan gerbang X atau Z).

Tantangan Besar Ambang Batas (Threshold Theorem)

Ada angka ajaib yang disebut “ambang batas kesalahan” (threshold error rate). Untuk kode permukaan, sekitar 1% . Maksudnya:

Jika tingkat kesalahan qubit fisik > 1%: Menambahkan lebih banyak qubit untuk koreksi justru akan membuat sistem makin parah (error merambat).
Jika tingkat kesalahan qubit fisik < 1%: Maka menambahkan lebih banyak qubit untuk koreksi akan menekan tingkat kesalahan logis secara eksponensial.

Implikasi: Saat ini qubit fisik terbaik masih memiliki tingkat kesalahan sekitar 0.1% – 1%. Kita hampir melewati ambang batas. Begitu melewatinya, kita bisa mulai melakukan skalasi.

Berapa banyak qubit fisik untuk satu qubit logis?
Dengan kode permukaan modern, untuk mencapai tingkat kesalahan yang dapat diandalkan (misal, 1 dari triliun operasi salah), dibutuhkan sekitar 1.000 – 10.000 qubit fisik untuk membuat 1 qubit logis.

Implikasi Besar: Komputer kuantum yang bisa memecahkan RSA (Algoritma Shor) diperkirakan membutuhkan 20-50 juta qubit fisik (untuk menghasilkan ~20.000 qubit logis yang stabil). Saat ini, komputer kuantum terbaik memiliki ~1.000 qubit fisik.

Tabel Ringkasan Tantangan

Tantangan	Penjelasan	Status Saat Ini
Kesalahan Fisik	Dekohorensi, noise lingkungan.	~0.1% – 1% per gerbang. Mendekati ambang batas.
Ambang Batas	Butuh tingkat error di bawah ~1% agar koreksi efektif.	Hampir tercapai di lab (misal, superconducting qubit).
Overhead Qubit	1 qubit logis butuh ribuan qubit fisik.	Masih jauh dari skala yang dibutuhkan.
Kecepatan	QEC membutuhkan pengukuran konstan (setiap mikrodetik).	Elektronik kontrol masih menjadi batasan.

Kesimpulan Akhir dari Dua Topik Ini

Algoritma Shor menunjukkan bahwa komputer kuantum secara teoritis mampu menghancurkan keamanan digital modern. Ini adalah “senjata pemusnah massal” matematika.
Koreksi Kesalahan Kuantum menunjukkan bahwa komputer kuantum skala besar secara praktis masih membutuhkan terobosan teknik dan material. Kita baru di era “NISQ” (Noisy Intermediate-Scale Quantum) – mesin yang berisik, dengan 50-1000 qubit, yang belum bisa menjalankan Shor untuk RSA, tetapi sudah bisa menjalankan algoritma lain (seperti simulasi kimia sederhana atau optimasi).

Prospek: Banyak ilmuwan memperkirakan dalam 10-20 tahun kita akan memiliki komputer kuantum dengan jutaan qubit yang mampu menjalankan Shor. Tepat sebelum itu terjadi, dunia harus sudah beralih ke kriptografi pasca-kuantum. Inilah lomba yang sedang berlangsung saat ini.

Kriptografi Pasca-Kuantum (PQC)

Bagian 1: Kriptografi Pasca-Kuantum (PQC) – Memperkuat Pertahanan Digital

Seperti yang telah dijelaskan, algoritma Shor mengancam akan menghancurkan sistem kriptografi yang kita andalkan saat ini (RSA, ECC). Kriptografi Pasca-Kuantum adalah upaya global untuk menciptakan algoritma baru yang aman dari serangan komputer kuantum di masa depan [4][8].

A. Alasan PQC Berbeda dari Kriptografi “Kuantum”

Penting untuk diluruskan: PQC tidak menggunakan komputer kuantum. PQC adalah algoritma matematika canggih yang dirancang untuk berjalan di komputer klasik (laptop, server) yang ada saat ini, tetapi aman terhadap serangan dari komputer kuantum di masa depan.

B. Lima Kelas Utama Algoritma PQC

Beberapa keluarga algoritma sedang dievaluasi, masing-masing dengan mekanisme matematika dan keseimbangan kinerja yang berbeda [4][8].

Kelas Algoritma	Prinsip Dasar	Kelebihan	Kelemahan	Contoh
Berbasis Lattice	Menggunakan masalah matematika pada struktur kisi multidimensi. Sulit ditemukan vektor terpendeknya.	Kinerja terbaik (kunci kecil, cepat), serbaguna (enkripsi & tanda tangan), menjadi standar utama.	Kerentanan kriptanalisis masih terus diteliti.	ML-DSA (FIPS 204), FN-DSA [5][10]
Berbasis Kode	Menggunakan teori kode koreksi kesalahan. Sulit mendekode pesan yang sengaja ditambahkan error.	Keamanan sudah teruji puluhan tahun.	Ukuran kunci sangat besar (ratusan KB hingga MB).	McEliece [8]
Berbasis Hash	Hanya menggunakan fungsi hash kriptografis. Keamanannya paling mudah dipahami.	Sangat terpercaya, asumsi keamanannya minimal.	Tanda tangan digital sangat besar dan lambat.	SPHINCS+ [8]
Multivariat	Sistem persamaan kuadrat dengan banyak variabel. Sulit dipecahkan.	Tanda tangan cepat dan kecil.	Kunci publik besar, beberapa varian sudah ada yang ditembus.	UOV, MAYO [1][10]
Berbasis Isogeni	Menjelajahi peta (isogeni) antara kurva elliptic.	Ukuran kunci paling kecil (hanya 148 byte untuk tingkat keamanan 1).	Komputasi sangat lambat dan rumit.	SQIsign [10]

Visualisasi Sederhana:

Berbasis Lattice adalah “mobil balap”: sangat cepat dan efisien, kemungkinan akan menjadi pilihan utama untuk penggunaan umum.
Berbasis Isogeni adalah “sepeda motor lipat”: sangat mungil (kuncinya kecil), tetapi butuh effort lebih untuk mengendarainya.

C. Standarisasi oleh NIST: Proses Seleksi yang Ketat

Institut Standar dan Teknologi Nasional AS (NIST) memimpin upaya global untuk menstandardisasi PQC [4].

Putaran 1 & 2 (2017-2022): NIST menerima 82 usulan, menyaringnya, dan pada Juli 2022 memilih 4 algoritma untuk distandardisasi. Yang paling terkenal adalah CRYSTALS-Kyber (enkripsi, sekarang menjadi ML-KEM) dan CRYSTALS-Dilithium (tanda tangan digital, sekarang menjadi ML-DSA) [8][10].
Putaran 3 Khusus Tanda Tangan Digital (Saat Ini – Mei 2026): Untuk diversifikasi, NIST mengadakan proses khusus untuk tanda tangan digital [1][10].
- 9 kandidat terpilih untuk putaran ketiga, termasuk HAWK (berbasis lattice), SQIsign (berbasis isogeni), dan MAYO, UOV, SNOVA (multivariat) [1][10].
- Mengapa perlu diversifikasi? Jika suatu hari kelak ditemukan cara untuk menembus satu jenis matematika (misalnya, lattice), kita masih punya algoritma cadangan dari jenis matematika yang berbeda (misalnya, isogeni atau hash). “Jangan taruh semua telur dalam satu keranjang” [5][10].
- Proses evaluasi ini diperkirakan berlangsung sekitar dua tahun [1].

Kesimpulan PQC: Kita sedang dalam transisi besar-besaran. Standar utama (ML-DSA, ML-KEM) sudah siap. Proses diversifikasi masih berjalan. Dalam 5-10 tahun ke depan, hampir semua perangkat lunak dan perangkat keras akan bermigrasi ke algoritma PQC ini.

Bagian 2: Arsitektur Fisik Komputer Kuantum – “Kuda-Kuda” di Balik Mesin

Kita telah membahas logika level atas (algoritma) dan kebutuhan untuk koreksi error. Sekarang kita lihat bagaimana semua itu diimplementasikan di dunia fisik. Ini adalah pertarungan antara beberapa teknologi yang sangat berbeda, masing-masing dengan kelebihan dan tantangannya sendiri [3][9].

Perbandingan 5 Platform Qubit Utama

Para ilmuwan dan perusahaan teknologi besar sedang berlomba menyempurnakan berbagai “ras” qubit. Tabel di bawah ini merangkum situasi terkini (sekitar 2024-2026) [2][3][6].

Platform Qubit	Bagaimana Cara Kerjanya?	Kelebihan Utama	Tantangan Utama	Contoh Pemain Utama
Superkonduktor	Sirkuit listrik mikroskopis yang menjadi superkonduktor pada suhu sangat dingin. Sirkuit ini berperilaku seperti osilator kuantum.	Paling matang, gerbangnya cepat, mudah dibuat dengan teknologi semikonduktor yang sudah ada.	Pendinginan super kompleks (perlu suhu mendekati 0 Kelvin), dan skalabilitas wiring terbatas.	IBM, Google, Amazon, Rigetti [3]
Ion Terperangkap	Ion (atom bermuatan) dilayang-layangkan di ruang hampa menggunakan medan elektromagnetik dan dimanipulasi dengan laser.	Fidelitas tertinggi (error sangat rendah), semua qubit bisa terhubung satu sama lain.	Gerbangnya lambat, dan sistem laser yang besar dan rumit menyulitkan skalabilitas ke ribuan qubit.	IonQ, Quantinuum, Honeywell [3]
Atom Netral	Atom netral ditahan dalam susunan 2D atau 3D menggunakan “penjepit” optik (sinar laser terfokus).	Mudah diskalakan ke ribuan atom, fleksibel dalam pengaturan.	Masih dalam tahap pengembangan maturitas, kompleksitas laser, kecepatan gerbang sedang.	Atom Computing, Pasqal, QuEra [2][3]
Fotonik	Menggunakan partikel cahaya (foton) sebagai qubit. Informasi dibawa oleh properti foton seperti polarisasi.	Bisa beroperasi pada suhu ruang, interkoneksi jarak jauh sangat alami (cocok untuk jaringan kuantum).	Gerbang antar-foton bersifat probabilistik (kadang berhasil, kadang gagal) dan tingkat kehilangan (loss) masih tinggi.	PsiQuantum, Xanadu [2][6]
Spin Silikon	Menggunakan spin elektron (atau inti atom) dalam titik-titik kuantum yang dibuat dari material silikon.	Kompatibel dengan fabrikasi chip silikon yang sudah ada (seperti chip komputer saat ini), sangat menjanjikan untuk skala massal.	Masih dalam tahap awal, fidelitas dan kompleksitas kontrol masih perlu ditingkatkan secara signifikan.	Intel (Tunnel Falls) , UNSW, Delft [3]

Efisiensi Energi: Perspektif Baru

Sebuah studi tahun 2026 memperkenalkan metrik “algoritma per joule” untuk mengukur efisiensi energi berbagai platform [6]. Hasilnya sangat menarik dan menjadi pertimbangan baru selain kecepatan mentah:

Spin Silikon memimpin dengan ~100 algoritma/joule. (Sangat hemat energi) [6]
Superkonduktor & Ion Terperangkap di peringkat kedua dengan ~10 algoritma/joule. (Kinerja tinggi, tetapi boros energi) [6]
Atom Netral ~1 algoritma/joule.
Fotonik ~0.1 algoritma/joule.

Pesan penting: Memilih platform qubit tidak hanya tentang kecepatan, tetapi juga tentang biaya energi dan kompleksitas infrastruktur (misalnya, cryostat untuk superkonduktor). Ini akan menjadi faktor penentu dalam 10-20 tahun ke depan [6].

Darimana Angka Jutaan Qubit Berasal?

Ingat kebutuhan 20 juta qubit fisik untuk menjalankan algoritma Shor? Itu berasal dari perkalian dua faktor:

Overhead Koreksi Error: Membutuhkan ~1.000 qubit fisik untuk membuat 1 qubit logis yang stabil (seperti yang disebutkan di bagian sebelumnya).
Kebutuhan Algoritma Shor: Diperkirakan butuh ~20.000 qubit logis untuk memecahkan RSA-2048.Perhitungan sederhana: 20.000 (logis) × 1.000 (fisik/logis) = 20.000.000 qubit fisik.

Itulah mengapa kita masih berada di era NISQ (Noisy Intermediate-Scale Quantum) , dengan mesin 50-1.000 qubit yang “berisik” (belum sempurna) dan masih belum bisa menjalankan Shor [3][7].

Diagram Konseptual: Jalur Menuju Komputer Kuantum

Untuk memudahkan memahami hubungan antara semua konsep yang telah kita bahas, perhatikan diagram alur berikut:

Penjelasan Diagram:

Tingkat Aplikasi: Masalah dunia nyata (misal, memecahkan RSA) diterjemahkan ke dalam algoritma kuantum seperti Shor.
Tingkat Logis: Algoritma membutuhkan operasi pada qubit logis yang sempurna (bebas error). Karena qubit fisik mudah error, kita membutuhkan lapisan Koreksi Kesalahan Kuantum.
Tingkat Fisik: Koreksi error diimplementasikan dengan menggabungkan banyak qubit fisik yang tidak sempurna (ratusan atau ribuan) untuk membentuk satu qubit logis. Qubit fisik ini direalisasikan melalui berbagai platform teknologi seperti superkonduktor, ion terperangkap, dll.

Kesimpulan Akhir (PQC + Arsitektur Fisik)

Kita sekarang memiliki peta jalan yang lengkap:

Ancaman (Algoritma Shor): Mesin kuantum di masa depan bisa menghancurkan keamanan digital kita.
Pertahanan (Kriptografi Pasca-Kuantum): Dunia sedang bersiap dengan algoritma baru (seperti ML-DSA dari keluarga lattice) yang aman dari serangan kuantum. Proses standardisasi oleh NIST sedang memasuki babak akhir.
Mesin (Arsitektur Fisik): Komputer kuantum dibangun di atas berbagai platform fisik (Superkonduktor, Ion Terperangkap, Atom Netral, dll.). Saat ini, kita masih di era NISQ, dengan mesin yang belum cukup besar dan stabil untuk menjalankan algoritma Shor. Dibutuhkan lompatan besar dalam koreksi kesalahan dan skalabilitas untuk mencapai jutaan qubit yang diperlukan.

Jadi, meskipun ancamannya nyata, kita memiliki waktu (diperkirakan 10-20 tahun) untuk memigrasi sistem kita ke kriptografi yang kebal kuantum, sementara para ilmuwan terus berjuang membangun mesin kuantum yang praktis dan bertenaga.