Algoritma Shor

Estimasi penggunaan: Tiga detik pada prosesor Eagle r3 (CATATAN: Ini hanya perkiraan. Waktu eksekusi kamu bisa berbeda.)

Algoritma Shor, yang dikembangkan oleh Peter Shor pada tahun 1994, adalah algoritma kuantum revolusioner untuk memfaktorkan bilangan bulat dalam waktu polinomial. Signifikansinya terletak pada kemampuannya memfaktorkan bilangan bulat besar secara eksponensial lebih cepat dari algoritma klasik mana pun yang diketahui, mengancam keamanan sistem kriptografi yang banyak digunakan seperti RSA, yang bergantung pada sulitnya memfaktorkan bilangan besar. Dengan menyelesaikan masalah ini secara efisien pada komputer kuantum yang cukup powerful, algoritma Shor berpotensi merevolusi bidang-bidang seperti kriptografi, keamanan siber, dan matematika komputasi — menegaskan kekuatan transformatif dari komputasi kuantum.

Tutorial ini berfokus pada demonstrasi algoritma Shor dengan memfaktorkan 15 di komputer kuantum.

Pertama, kita mendefinisikan masalah pencarian orde dan membangun Circuit yang sesuai dari protokol estimasi fase kuantum. Selanjutnya, kita menjalankan Circuit pencarian orde di hardware nyata menggunakan Circuit dengan kedalaman terpendek yang bisa kita transpilasikan. Bagian terakhir melengkapi algoritma Shor dengan menghubungkan masalah pencarian orde ke faktorisasi bilangan bulat.

Kita mengakhiri tutorial ini dengan diskusi tentang demonstrasi lain dari algoritma Shor di hardware nyata, berfokus pada implementasi generik maupun yang disesuaikan untuk memfaktorkan bilangan bulat tertentu seperti 15 dan 21. Catatan: Tutorial ini lebih berfokus pada implementasi dan demonstrasi Circuit yang berkaitan dengan algoritma Shor. Untuk sumber edukasi yang lebih mendalam tentang materi ini, silakan lihat kursus Fundamentals of quantum algorithms oleh Dr. John Watrous, dan makalah-makalah di bagian Referensi.

Persyaratan

Sebelum memulai tutorial ini, pastikan kamu sudah menginstal:

• Qiskit SDK v2.0 atau lebih baru, dengan dukungan visualisasi
• Qiskit Runtime v0.40 atau lebih baru (pip install qiskit-ibm-runtime)

Persiapan

# Added by doQumentation — required packages for this notebook
!pip install -q numpy pandas qiskit qiskit-ibm-runtime

import numpy as np
import pandas as pd
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFT, UnitaryGate
from qiskit.transpiler import CouplingMap, generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Langkah 1: Memetakan input klasik ke masalah kuantum

Latar belakang

Algoritma Shor untuk faktorisasi bilangan bulat menggunakan masalah perantara yang dikenal sebagai masalah pencarian orde. Di bagian ini, kita mendemonstrasikan cara menyelesaikan masalah pencarian orde menggunakan estimasi fase kuantum.

Masalah estimasi fase

Dalam masalah estimasi fase, kita diberikan keadaan kuantum $\ket{\psi}$ dari $n$ Qubit, bersama dengan Circuit kuantum yang bekerja pada $n$ Qubit. Kita dijanjikan bahwa $\ket{\psi}$ adalah vektor eigen dari matriks uniter $U$ yang menggambarkan aksi Circuit tersebut, dan tujuan kita adalah menghitung atau mendekati nilai eigen $\lambda = e^{2 \pi i \theta}$ yang berkorespondensi dengan $\ket{\psi}$. Dengan kata lain, Circuit harus menghasilkan aproksimasi dari bilangan $\theta \in [0, 1)$ yang memenuhi $U \ket{\psi}= e^{2 \pi i \theta} \ket{\psi}.$ Tujuan dari Circuit estimasi fase adalah untuk mengaproksimasi $\theta$ dalam $m$ bit. Secara matematis, kita ingin menemukan $y$ sedemikian sehingga $\theta \approx y / 2^m$, di mana $y \in {0, 1, 2, \dots, 2^{m-1}}$. Gambar berikut menunjukkan Circuit kuantum yang mengestimasi $y$ dalam $m$ bit dengan melakukan pengukuran pada $m$ Qubit. Pada Circuit di atas, $m$ Qubit teratas diinisialisasi dalam keadaan $\ket{0^m}$, dan $n$ Qubit terbawah diinisialisasi dalam $\ket{\psi}$, yang dijanjikan sebagai vektor eigen dari $U$. Komponen pertama dalam Circuit estimasi fase adalah operasi uniter terkontrol yang bertanggung jawab melakukan phase kickback ke Qubit kontrol yang bersesuaian. Uniter-uniter terkontrol ini dipangkatkan sesuai posisi Qubit kontrol, mulai dari bit paling tidak signifikan hingga bit paling signifikan. Karena $\ket{\psi}$ adalah vektor eigen dari $U$, keadaan $n$ Qubit bawah tidak terpengaruh oleh operasi ini, tetapi informasi fase dari nilai eigen merambat ke $m$ Qubit teratas. Ternyata, setelah operasi phase kickback melalui uniter-uniter terkontrol, semua keadaan yang mungkin dari $m$ Qubit teratas saling ortogonal untuk setiap vektor eigen $\ket{\psi}$ dari uniter $U$. Oleh karena itu, keadaan-keadaan ini dapat dibedakan dengan sempurna, dan kita dapat memutar basis yang mereka bentuk kembali ke basis komputasi untuk melakukan pengukuran. Analisis matematis menunjukkan bahwa matriks rotasi ini berkorespondensi dengan transformasi Fourier kuantum invers (QFT) dalam ruang Hilbert berdimensi $2^m$. Intuisi di balik ini adalah bahwa struktur periodik dari operator eksponensiasi modular dikodekan dalam keadaan kuantum, dan QFT mengubah periodisitas ini menjadi puncak yang terukur dalam domain frekuensi.

Untuk pemahaman yang lebih mendalam tentang mengapa Circuit QFT digunakan dalam algoritma Shor, kita merujuk pembaca ke kursus Fundamentals of quantum algorithms. Kita sekarang siap menggunakan Circuit estimasi fase untuk pencarian orde.

Masalah pencarian orde

Untuk mendefinisikan masalah pencarian orde, kita mulai dengan beberapa konsep teori bilangan. Pertama, untuk setiap bilangan bulat positif $N$, definisikan himpunan $\mathbb{Z}_N$ sebagai $\mathbb{Z}_N = \{0, 1, 2, \dots, N-1\}.$ Semua operasi aritmetika di $\mathbb{Z}_N$ dilakukan modulo $N$. Khususnya, semua elemen $a \in \mathbb{Z}_n$ yang koprima dengan $N$ bersifat istimewa dan membentuk $\mathbb{Z}^*_N$ sebagai $\mathbb{Z}^*_N = \{ a \in \mathbb{Z}_N : \mathrm{gcd}(a, N)=1 \}.$ Untuk suatu elemen $a \in \mathbb{Z}^*_N$, bilangan bulat positif terkecil $r$ sedemikian sehingga $a^r \equiv 1 \; (\mathrm{mod} \; N)$ didefinisikan sebagai orde dari $a$ modulo $N$. Seperti yang akan kita lihat nanti, menemukan orde dari $a \in \mathbb{Z}^*_N$ akan memungkinkan kita memfaktorkan $N$. Untuk membangun Circuit pencarian orde dari Circuit estimasi fase, kita perlu dua pertimbangan. Pertama, kita perlu mendefinisikan uniter $U$ yang akan memungkinkan kita menemukan orde $r$, dan kedua, kita perlu mendefinisikan vektor eigen $\ket{\psi}$ dari $U$ untuk mempersiapkan keadaan awal Circuit estimasi fase.

Untuk menghubungkan masalah pencarian orde ke estimasi fase, kita mempertimbangkan operasi yang didefinisikan pada sistem yang keadaan klasiknya berkorespondensi dengan $\mathbb{Z}_N$, di mana kita mengalikan dengan elemen tetap $a \in \mathbb{Z}^*_N$. Khususnya, kita mendefinisikan operator perkalian $M_a$ sedemikian sehingga $M_a \ket{x} = \ket{ax \; (\mathrm{mod} \; N)}$ untuk setiap $x \in \mathbb{Z}_N$. Perlu dicatat bahwa secara implisit kita mengambil hasil perkalian modulo $N$ di dalam ket di ruas kanan persamaan. Analisis matematis menunjukkan bahwa $M_a$ adalah operator uniter. Lebih lanjut, ternyata $M_a$ memiliki pasangan vektor eigen dan nilai eigen yang memungkinkan kita menghubungkan orde $r$ dari $a$ ke masalah estimasi fase. Secara spesifik, untuk pilihan $j \in \{0, \dots, r-1\}$ mana pun, kita memiliki bahwa $\ket{\psi_j} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \omega^{-jk}_{r} \ket{a^k}$ adalah vektor eigen dari $M_a$ yang nilai eigennya berkorespondensi adalah $\omega^{j}_{r}$, di mana $\omega^{j}_{r} = e^{2 \pi i \frac{j}{r}}.$ Dari pengamatan, kita melihat bahwa pasangan vektor eigen/nilai eigen yang nyaman adalah keadaan $\ket{\psi_1}$ dengan $\omega^{1}_{r} = e^{2 \pi i \frac{1}{r}}$. Oleh karena itu, jika kita bisa menemukan vektor eigen $\ket{\psi_1}$, kita bisa mengestimasi fase $\theta=1/r$ dengan Circuit kuantum kita dan dengan demikian mendapatkan estimasi orde $r$. Namun, hal itu tidak mudah dilakukan, dan kita perlu mempertimbangkan alternatif lain.

Mari kita pertimbangkan apa yang akan dihasilkan Circuit jika kita mempersiapkan keadaan komputasi $\ket{1}$ sebagai keadaan awal. Ini bukan keadaan eigen dari $M_a$, tetapi merupakan superposisi seragam dari keadaan-keadaan eigen yang baru saja kita deskripsikan. Dengan kata lain, relasi berikut berlaku. $\ket{1} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \ket{\psi_k}$ Implikasi dari persamaan di atas adalah bahwa jika kita menetapkan keadaan awal ke $\ket{1}$, kita akan memperoleh hasil pengukuran yang persis sama seolah-olah kita telah memilih $k \in \{ 0, \dots, r-1\}$ secara seragam acak dan menggunakan $\ket{\psi_k}$ sebagai vektor eigen dalam Circuit estimasi fase. Dengan kata lain, pengukuran pada $m$ Qubit teratas menghasilkan aproksimasi $y / 2^m$ dari nilai $k / r$ di mana $k \in \{ 0, \dots, r-1\}$ dipilih secara seragam acak. Ini memungkinkan kita mempelajari $r$ dengan tingkat keyakinan yang tinggi setelah beberapa eksekusi independen, yang merupakan tujuan kita.

Operator eksponensiasi modular

Sejauh ini, kita menghubungkan masalah estimasi fase ke masalah pencarian orde dengan mendefinisikan $U = M_a$ dan $\ket{\psi} = \ket{1}$ dalam Circuit kuantum kita. Oleh karena itu, bahan terakhir yang tersisa adalah menemukan cara efisien untuk mendefinisikan eksponen modular dari $M_a$ sebagai $M_a^k$ untuk $k = 1, 2, 4, \dots, 2^{m-1}$. Untuk melakukan komputasi ini, kita menemukan bahwa untuk pangkat $k$ mana pun yang kita pilih, kita dapat membuat Circuit untuk $M_a^k$ bukan dengan mengiterasi $k$ kali Circuit untuk $M_a$, melainkan dengan menghitung $b = a^k \; \mathrm{mod} \; N$ dan kemudian menggunakan Circuit untuk $M_b$. Karena kita hanya membutuhkan pangkat yang merupakan pangkat dua itu sendiri, kita dapat melakukan ini secara efisien secara klasik menggunakan pengkuadratan iteratif.

Langkah 2: Mengoptimalkan masalah untuk eksekusi pada hardware kuantum

Contoh spesifik dengan $N = 15$ dan $a=2$

Kita bisa berhenti sejenak di sini untuk mendiskusikan contoh spesifik dan membangun Circuit pencarian orde untuk $N=15$. Perhatikan bahwa kemungkinan $a \in \mathbb{Z}_N^*$ yang non-trivial untuk $N=15$ adalah $a \in \{2, 4, 7, 8, 11, 13, 14 \}$. Untuk contoh ini, kita pilih $a=2$. Kita akan membangun operator $M_2$ dan operator eksponensiasi modular $M_2^k$. Aksi dari $M_2$ pada keadaan basis komputasi adalah sebagai berikut. $M_2 \ket{0} = \ket{0} \quad M_2 \ket{5} = \ket{10} \quad M_2 \ket{10} = \ket{5}$ $M_2 \ket{1} = \ket{2} \quad M_2 \ket{6} = \ket{12} \quad M_2 \ket{11} = \ket{7}$ $M_2 \ket{2} = \ket{4} \quad M_2 \ket{7} = \ket{14} \quad M_2 \ket{12} = \ket{9}$ $M_2 \ket{3} = \ket{6} \quad M_2 \ket{8} = \ket{1} \quad M_2 \ket{13} = \ket{11}$ $M_2 \ket{4} = \ket{8} \quad M_2 \ket{9} = \ket{3} \quad M_2 \ket{14} = \ket{13}$ Dari pengamatan, kita bisa melihat bahwa keadaan basis diacak, sehingga kita memiliki matriks permutasi. Kita dapat membangun operasi ini pada empat Qubit dengan Gate swap. Di bawah ini, kita membangun operasi $M_2$ dan controlled-$M_2$.

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Gate yang bekerja pada lebih dari dua Qubit akan didekomposisi lebih lanjut menjadi Gate dua Qubit.

circ.decompose(reps=2).draw(output="mpl", fold=-1)

Sekarang kita perlu membangun operator eksponensiasi modular. Untuk mendapatkan presisi yang cukup dalam estimasi fase, kita akan menggunakan delapan Qubit untuk pengukuran estimasi. Oleh karena itu, kita perlu membangun $M_b$ dengan $b = a^{2^k} \; (\mathrm{mod} \; N)$ untuk setiap $k = 0, 1, \dots, 7$.

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Seperti yang bisa kita lihat dari daftar nilai $b$, selain $M_2$ yang sebelumnya kita bangun, kita juga perlu membangun $M_4$ dan $M_1$. Perhatikan bahwa $M_1$ bekerja secara trivial pada keadaan basis komputasi, sehingga ini hanyalah operator identitas.

$M_4$ bekerja pada keadaan basis komputasi sebagai berikut. $M_4 \ket{0} = \ket{0} \quad M_4 \ket{5} = \ket{5} \quad M_4 \ket{10} = \ket{10}$ $M_4 \ket{1} = \ket{4} \quad M_4 \ket{6} = \ket{9} \quad M_4 \ket{11} = \ket{14}$ $M_4 \ket{2} = \ket{8} \quad M_4 \ket{7} = \ket{13} \quad M_4 \ket{12} = \ket{3}$ $M_4 \ket{3} = \ket{12} \quad M_4 \ket{8} = \ket{2} \quad M_4 \ket{13} = \ket{7}$ $M_4 \ket{4} = \ket{1} \quad M_4 \ket{9} = \ket{6} \quad M_4 \ket{14} = \ket{11}$

Oleh karena itu, permutasi ini dapat dibangun dengan operasi swap berikut.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Gate yang bekerja pada lebih dari dua Qubit akan didekomposisi lebih lanjut menjadi Gate dua Qubit.

circ.decompose(reps=2).draw(output="mpl", fold=-1)

Kita melihat bahwa operator $M_b$ untuk $b \in \mathbb{Z}^*_N$ tertentu adalah operasi permutasi. Karena ukuran masalah permutasi yang relatif kecil di sini, karena $N=15$ hanya membutuhkan empat Qubit, kita bisa mensintesis operasi ini langsung dengan Gate SWAP secara inspeksi. Secara umum, ini mungkin bukan pendekatan yang skalabel. Sebagai gantinya, kita mungkin perlu membangun matriks permutasi secara eksplisit, dan menggunakan kelas UnitaryGate dari Qiskit serta metode transpilasi untuk mensintesis matriks permutasi ini. Namun, hal ini dapat menghasilkan Circuit yang jauh lebih dalam. Contohnya sebagai berikut.

def mod_mult_gate(b, N):
    """
    Modular multiplication gate from permutation matrix.
    """
    if gcd(b, N) > 1:
        print(f"Error: gcd({b},{N}) > 1")
    else:
        n = floor(log(N - 1, 2)) + 1
        U = np.full((2**n, 2**n), 0)
        for x in range(N):
            U[b * x % N][x] = 1
        for x in range(N, 2**n):
            U[x][x] = 1
        G = UnitaryGate(U)
        G.name = f"M_{b}"
        return G

# Let's build M2 using the permutation matrix definition
M2_other = mod_mult_gate(2, 15)

# Add it to a circuit
circ = QuantumCircuit(4)
circ.compose(M2_other, inplace=True)
circ = circ.decompose()

# Transpile the circuit and get the depth
coupling_map = CouplingMap.from_line(4)
pm = generate_preset_pass_manager(coupling_map=coupling_map)
transpiled_circ = pm.run(circ)

print(f"qubits: {circ.num_qubits}")
print(
    f"2q-depth: {transpiled_circ.depth(lambda x: x.operation.num_qubits==2)}"
)
print(f"2q-size: {transpiled_circ.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circ.count_ops()}")
transpiled_circ.decompose().draw(
    output="mpl", fold=-1, style="clifford", idle_wires=False
)

qubits: 4
2q-depth: 94
2q-size: 96
Operator counts: OrderedDict({'cx': 45, 'swap': 32, 'u': 24, 'u1': 7, 'u3': 4, 'unitary': 3, 'circuit-335': 1, 'circuit-338': 1, 'circuit-341': 1, 'circuit-344': 1, 'circuit-347': 1, 'circuit-350': 1, 'circuit-353': 1, 'circuit-356': 1, 'circuit-359': 1, 'circuit-362': 1, 'circuit-365': 1, 'circuit-368': 1, 'circuit-371': 1, 'circuit-374': 1, 'circuit-377': 1, 'circuit-380': 1})

Mari kita bandingkan jumlah ini dengan kedalaman Circuit yang telah dikompilasi dari implementasi manual Gate $M_2$ kita.

# Get the M2 operator from our manual construction
M2 = M2mod15()

# Add it to a circuit
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ = circ.decompose(reps=3)

# Transpile the circuit and get the depth
coupling_map = CouplingMap.from_line(4)
pm = generate_preset_pass_manager(coupling_map=coupling_map)
transpiled_circ = pm.run(circ)

print(f"qubits: {circ.num_qubits}")
print(
    f"2q-depth: {transpiled_circ.depth(lambda x: x.operation.num_qubits==2)}"
)
print(f"2q-size: {transpiled_circ.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circ.count_ops()}")
transpiled_circ.draw(
    output="mpl", fold=-1, style="clifford", idle_wires=False
)

qubits: 4
2q-depth: 9
2q-size: 9
Operator counts: OrderedDict({'cx': 9})

Seperti yang bisa kita lihat, pendekatan matriks permutasi menghasilkan Circuit yang jauh lebih dalam bahkan untuk satu Gate $M_2$ saja dibandingkan implementasi manual kita. Oleh karena itu, kita akan melanjutkan dengan implementasi operasi $M_b$ sebelumnya. Sekarang, kita siap membangun Circuit pencarian orde lengkap menggunakan operator eksponensiasi modular terkontrol yang telah kita definisikan sebelumnya. Dalam kode berikut, kita juga mengimpor Circuit QFT dari pustaka Circuit Qiskit, yang menggunakan Gate Hadamard pada setiap Qubit, serangkaian Gate controlled-U1 (atau Z, tergantung fasenya), dan lapisan Gate swap.

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFT(num_control, inverse=True), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

Perhatikan bahwa kita menghilangkan operasi eksponensiasi modular terkontrol dari Qubit kontrol yang tersisa karena $M_1$ adalah operator identitas. Perhatikan bahwa nantinya dalam tutorial ini, kita akan menjalankan Circuit ini pada Backend ibm_marrakesh. Untuk melakukan ini, kita mentranspilasi Circuit sesuai Backend spesifik ini dan melaporkan kedalaman Circuit serta jumlah Gate.

service = QiskitRuntimeService()
backend = service.backend("ibm_marrakesh")
pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(
    f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}"
)
print(
    f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}"
)
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(
    output="mpl", fold=-1, style="clifford", idle_wires=False
)

2q-depth: 187
2q-size: 260
Operator counts: OrderedDict({'sx': 521, 'rz': 354, 'cz': 260, 'measure': 8, 'x': 4})

Langkah 3: Eksekusi menggunakan Qiskit primitives

Pertama, kita bahas apa yang secara teoritis akan kita dapatkan jika menjalankan Circuit ini di simulator ideal. Di bawah ini ada sekumpulan hasil simulasi dari Circuit di atas menggunakan 1024 shots. Seperti terlihat, kita mendapatkan distribusi yang kira-kira seragam di empat bitstring pada control qubit.

# Obtained from the simulator
counts = {"00000000": 264, "01000000": 268, "10000000": 249, "11000000": 243}

plot_histogram(counts)

Dengan mengukur control qubit, kita mendapatkan estimasi fase delapan-bit dari operator $M_a$. Kita bisa mengonversi representasi biner ini ke desimal untuk menemukan fase yang terukur. Seperti terlihat dari histogram di atas, empat bitstring berbeda diukur, dan masing-masing berkorespondensi dengan nilai fase sebagai berikut.

# Rows to be displayed in table
rows = []
# Corresponding phase of each bitstring
measured_phases = []

for output in counts:
    decimal = int(output, 2)  # Convert bitstring to decimal
    phase = decimal / (2**num_control)  # Find corresponding eigenvalue
    measured_phases.append(phase)
    # Add these values to the rows in our table:
    rows.append(
        [
            f"{output}(bin) = {decimal:>3}(dec)",
            f"{decimal}/{2 ** num_control} = {phase:.2f}",
        ]
    )

# Print the rows in a table
headers = ["Register Output", "Phase"]
df = pd.DataFrame(rows, columns=headers)
print(df)

Register Output           Phase
0  00000000(bin) =   0(dec)    0/256 = 0.00
1  01000000(bin) =  64(dec)   64/256 = 0.25
2  10000000(bin) = 128(dec)  128/256 = 0.50
3  11000000(bin) = 192(dec)  192/256 = 0.75

Ingat bahwa setiap fase yang terukur berkorespondensi dengan $\theta = k / r$ di mana $k$ diambil secara acak merata dari $\{0, 1, \dots, r-1 \}$. Oleh karena itu, kita bisa menggunakan algoritma continued fractions untuk mencoba menemukan $k$ dan orde $r$. Python sudah memiliki fungsionalitas ini secara bawaan. Kita bisa menggunakan modul fractions untuk mengubah float menjadi objek Fraction, misalnya:

Fraction(0.666)

Fraction(5998794703657501, 9007199254740992)

Karena ini menghasilkan pecahan yang mengembalikan hasil secara tepat (dalam kasus ini, 0.6660000...), hasilnya bisa jadi rumit seperti di atas. Kita bisa menggunakan metode .limit_denominator() untuk mendapatkan pecahan yang paling mendekati float kita, dengan penyebut di bawah nilai tertentu:

# Get fraction that most closely resembles 0.666
# with denominator < 15
Fraction(0.666).limit_denominator(15)

Fraction(2, 3)

Ini jauh lebih rapi. Orde (r) harus lebih kecil dari N, jadi kita akan menetapkan penyebut maksimum menjadi 15:

# Rows to be displayed in a table
rows = []

for phase in measured_phases:
    frac = Fraction(phase).limit_denominator(15)
    rows.append(
        [phase, f"{frac.numerator}/{frac.denominator}", frac.denominator]
    )

# Print the rows in a table
headers = ["Phase", "Fraction", "Guess for r"]
df = pd.DataFrame(rows, columns=headers)
print(df)

Phase Fraction  Guess for r
0   0.00      0/1            1
1   0.25      1/4            4
2   0.50      1/2            2
3   0.75      3/4            4

Kita bisa melihat bahwa dua dari nilai eigen yang terukur memberi kita hasil yang benar: $r=4$, dan kita bisa melihat bahwa algoritma Shor untuk order finding punya kemungkinan gagal. Hasil yang buruk ini terjadi karena $k = 0$, atau karena $k$ dan $r$ tidak koprima — dan alih-alih mendapatkan $r$, kita mendapatkan faktor dari $r$. Solusi paling mudah adalah dengan mengulangi eksperimen sampai kita mendapatkan hasil $r$ yang memuaskan. Sejauh ini, kita mengimplementasikan masalah order finding untuk $N=15$ dengan $a=2$ menggunakan Circuit estimasi fase di simulator. Langkah terakhir dari algoritma Shor adalah menghubungkan masalah order finding dengan masalah faktorisasi bilangan bulat. Bagian terakhir dari algoritma ini murni klasikal dan bisa diselesaikan di komputer klasik setelah pengukuran fase diperoleh dari komputer kuantum. Oleh karena itu, kita menunda bagian terakhir algoritma sampai setelah kita mendemonstrasikan cara menjalankan Circuit order finding di hardware nyata.

Eksekusi di hardware

Sekarang kita bisa menjalankan Circuit order finding yang sebelumnya sudah kita transpile untuk ibm_marrakesh. Di sini kita beralih ke dynamical decoupling (DD) untuk penekanan error, dan gate twirling untuk mitigasi error. DD melibatkan penerapan serangkaian pulsa kontrol yang waktunya tepat pada perangkat kuantum, secara efektif merata-ratakan interaksi lingkungan yang tidak diinginkan dan dekoherensi. Gate twirling, di sisi lain, mengacak Gate kuantum tertentu untuk mengubah coherent error menjadi Pauli error, yang terakumulasi secara linear bukan kuadratik. Kedua teknik ini sering digabungkan untuk meningkatkan koherensi dan fidelitas komputasi kuantum.

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Seperti terlihat, kita mendapatkan bitstring yang sama dengan jumlah tertinggi. Karena hardware kuantum memiliki noise, ada sedikit kebocoran ke bitstring lain yang bisa kita saring secara statistik.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

{'00000000': 58, '01000000': 41, '11000000': 42, '10000000': 40}

Langkah 4: Pasca-proses dan kembalikan hasil dalam format klasikal yang diinginkan

Faktorisasi Bilangan Bulat

Sejauh ini, kita membahas cara mengimplementasikan masalah order finding menggunakan Circuit estimasi fase. Sekarang, kita hubungkan masalah order finding dengan faktorisasi bilangan bulat, yang melengkapi algoritma Shor. Perlu diingat bahwa bagian algoritma ini bersifat klasikal. Kita sekarang mendemonstrasikan ini menggunakan contoh $N = 15$ dan $a = 2$. Ingat bahwa fase yang kita ukur adalah $k / r$, di mana $a^r \; (\textrm{mod} \; N) = 1$ dan $k$ adalah bilangan bulat acak antara $0$ dan $r - 1$. Dari persamaan ini, kita punya $(a^r - 1) \; (\textrm{mod} \; N) = 0,$ yang berarti $N$ harus membagi $a^r-1$. Jika $r$ juga genap, maka kita bisa menulis $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$ Jika $r$ tidak genap, kita tidak bisa melanjutkan dan harus mencoba lagi dengan nilai $a$ yang berbeda; jika tidak, ada probabilitas tinggi bahwa greatest common divisor dari $N$ dan salah satu dari $a^{r/2}-1$, atau $a^{r/2}+1$ adalah faktor sejati dari $N$.

Karena beberapa eksekusi algoritma akan gagal secara statistik, kita akan mengulang algoritma ini sampai setidaknya satu faktor dari $N$ ditemukan. Sel di bawah mengulang algoritma sampai setidaknya satu faktor dari $N=15$ ditemukan. Kita akan menggunakan hasil eksekusi hardware di atas untuk menebak fase dan faktor yang berkorespondensi di setiap iterasi.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.25
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Diskusi

Karya terkait

Di bagian ini, kita membahas karya-karya penting lainnya yang telah mendemonstrasikan algoritma Shor di hardware nyata.

Karya seminal [3] dari IBM® mendemonstrasikan algoritma Shor untuk pertama kalinya, memfaktorkan angka 15 menjadi faktor prima 3 dan 5 menggunakan komputer kuantum nuclear magnetic resonance (NMR) tujuh-Qubit. Eksperimen lain [4] memfaktorkan 15 menggunakan qubit fotonik. Dengan memanfaatkan satu Qubit yang didaur ulang berkali-kali dan mengenkode register kerja dalam keadaan dimensi lebih tinggi, para peneliti mengurangi jumlah Qubit yang dibutuhkan menjadi sepertiga dari protokol standar, menggunakan algoritma yang dikompilasi dua-foton. Makalah penting dalam demonstrasi algoritma Shor adalah [5], yang menggunakan teknik iterative phase estimation Kitaev [8] untuk mengurangi kebutuhan Qubit dari algoritma. Para penulis menggunakan tujuh control qubit dan empat cache qubit, bersama dengan implementasi modular multiplier. Namun, implementasi ini memerlukan pengukuran mid-circuit dengan operasi feed-forward dan daur ulang Qubit dengan operasi reset. Demonstrasi ini dilakukan pada komputer kuantum ion-trap.

Karya yang lebih baru [6] berfokus pada pemfaktoran 15, 21, dan 35 di hardware IBM Quantum®. Mirip dengan karya sebelumnya, para peneliti menggunakan versi kompilasi dari algoritma yang menggunakan semi-classical quantum Fourier transform seperti yang diusulkan Kitaev untuk meminimalkan jumlah Qubit fisik dan Gate. Karya paling baru [7] juga melakukan demonstrasi proof-of-concept untuk memfaktorkan bilangan bulat 21. Demonstrasi ini juga melibatkan penggunaan versi kompilasi dari rutinitas quantum phase estimation, dan membangun di atas demonstrasi sebelumnya oleh [4]. Para penulis melampaui karya tersebut dengan menggunakan konfigurasi approximate Toffoli gate dengan residual phase shift. Algoritma ini diimplementasikan di prosesor IBM quantum hanya menggunakan lima Qubit, dan keberadaan entanglement antara control qubit dan register qubit berhasil diverifikasi.

Skalabilitas algoritma

Perlu dicatat bahwa enkripsi RSA biasanya melibatkan ukuran kunci sekitar 2048 hingga 4096 bit. Mencoba memfaktorkan angka 2048-bit dengan algoritma Shor akan menghasilkan Circuit kuantum dengan jutaan Qubit, termasuk overhead koreksi error dan kedalaman Circuit sekitar satu miliar, yang melampaui batas hardware kuantum saat ini untuk dieksekusi. Oleh karena itu, algoritma Shor akan memerlukan metode konstruksi Circuit yang dioptimalkan atau koreksi error kuantum yang andal agar praktis layak untuk membobol sistem kriptografi modern. Kami merujuk Anda ke [9] untuk diskusi lebih rinci tentang estimasi sumber daya untuk algoritma Shor.

Tantangan

Selamat telah menyelesaikan tutorial ini! Sekarang adalah waktu yang tepat untuk menguji pemahaman Anda. Bisakah Anda mencoba membangun Circuit untuk memfaktorkan 21? Anda bisa memilih $a$ sesuai pilihan Anda sendiri. Anda perlu menentukan akurasi bit dari algoritma untuk memilih jumlah Qubit, dan Anda perlu merancang operator modular exponentiation $M_a$. Kami mendorong Anda untuk mencoba sendiri, lalu membaca tentang metodologi yang ditunjukkan di Fig. 9 dari [6] dan Fig. 2 dari [7].

def M_a_mod21():
    """
    M_a (mod 21)
    """

    # Your code here
    pass

Referensi

1. Shor, Peter W. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer." SIAM review 41.2 (1999): 303-332.
2. IBM Quantum Fundamentals of Quantum Algorithms course by Dr. John Watrous.
3. Vandersypen, Lieven MK, et al. "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance." Nature 414.6866 (2001): 883-887.
4. Martin-Lopez, Enrique, et al. "Experimental realization of Shor's quantum factoring algorithm using qubit recycling." Nature photonics 6.11 (2012): 773-776.
5. Monz, Thomas, et al. "Realization of a scalable Shor algorithm." Science 351.6277 (2016): 1068-1070.
6. Amico, Mirko, Zain H. Saleem, and Muir Kumph. "Experimental study of Shor's factoring algorithm using the IBM Q Experience." Physical Review A 100.1 (2019): 012305.
7. Skosana, Unathi, and Mark Tame. "Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors." Scientific reports 11.1 (2021): 16599.
8. Kitaev, A. Yu. "Quantum measurements and the Abelian stabilizer problem." arXiv preprint quant-ph/9511026 (1995).
9. Gidney, Craig, and Martin Ekerå. "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits." Quantum 5 (2021): 433.