Algoritma Shor

Anggaran penggunaan: Tiga saat pada pemproses Eagle r3 (NOTA: Ini adalah anggaran sahaja. Masa jalan anda mungkin berbeza.)

Hasil pembelajaran

Selepas melalui tutorial ini, pengguna seharusnya memahami:

• Latar belakang matematik algoritma Shor untuk pemfaktoran integer
• Cara menjalankan contoh algoritma ini pada perkakasan

Prasyarat

Kami mencadangkan agar pengguna biasa dengan topik berikut sebelum melalui tutorial ini:

• Asas algoritma kuantum.
• Anggaran fasa dan pemfaktoran. Kami membincangkan sebahagian bahan ini dalam tutorial ini.

Latar belakang

Algoritma Shor, yang dibangunkan oleh Peter Shor pada tahun 1994, ialah algoritma kuantum yang revolusioner untuk memfaktorkan integer dalam masa polinomial. Kepentingannya terletak pada keupayaannya memfaktorkan integer besar dengan jauh lebih pantas secara eksponen berbanding mana-mana algoritma klasik yang diketahui, mengancam keselamatan sistem kriptografi yang digunakan secara meluas seperti RSA, yang bergantung pada kesukaran memfaktorkan nombor besar. Dengan menyelesaikan masalah ini secara cekap pada komputer kuantum yang cukup berkuasa, algoritma Shor boleh merevolusikan bidang seperti kriptografi, keselamatan siber, dan matematik pengkomputeran, menegaskan kuasa transformatif pengkomputeran kuantum.

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

Pertama, kita takrifkan masalah pencarian perintah dan bina Circuit yang berkaitan daripada protokol anggaran fasa kuantum. Seterusnya, kita jalankan Circuit pencarian perintah pada perkakasan sebenar menggunakan Circuit dengan kedalaman terpendek yang boleh kita transpilkan. Bahagian terakhir melengkapkan algoritma Shor dengan menghubungkan masalah pencarian perintah kepada pemfaktoran integer.

Kita akhiri tutorial ini dengan perbincangan mengenai demonstrasi lain algoritma Shor pada perkakasan sebenar, menumpukan pada implementasi generik dan yang disesuaikan untuk memfaktorkan integer tertentu seperti 15 dan 21. Nota: Tutorial ini lebih menumpukan pada implementasi dan demonstrasi Circuit yang berkaitan dengan algoritma Shor. Untuk sumber pendidikan yang lebih mendalam mengenai bahan ini, rujuk kursus Asas algoritma kuantum oleh Dr. John Watrous, dan makalah dalam bahagian Rujukan.

Keperluan

Sebelum memulakan tutorial ini, pastikan anda telah memasang perkara berikut:

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

Persediaan

# 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: Petakan input klasik kepada masalah kuantum

Algoritma Shor untuk pemfaktoran integer menggunakan masalah pertengahan yang dikenali sebagai masalah pencarian perintah. Dalam bahagian ini, kita tunjukkan cara menyelesaikan masalah pencarian perintah menggunakan anggaran fasa kuantum.

Masalah anggaran fasa

Dalam masalah anggaran fasa, kita diberi keadaan kuantum $\ket{\psi}$ bagi $n$ qubit, bersama litar kuantum uniter yang bertindak pada $n$ qubit. Kita dijanjikan bahawa $\ket{\psi}$ ialah eigenvector bagi matriks uniter $U$ yang menggambarkan tindakan Circuit itu, dan matlamat kita ialah mengira atau menganggarkan nilai eigen $\lambda = e^{2 \pi i \theta}$ yang berpadanan dengan $\ket{\psi}$. Dengan kata lain, Circuit itu perlu mengeluarkan anggaran kepada nombor $\theta \in [0, 1)$ yang memenuhi $U \ket{\psi}= e^{2 \pi i \theta} \ket{\psi}.$ Matlamat Circuit anggaran fasa ialah menganggarkan $\theta$ dalam $m$ bit. Secara matematik, kita ingin mencari $y$ supaya $\theta \approx y / 2^m$, di mana $y \in {0, 1, 2, \dots, 2^{m-1}}$. Imej berikut menunjukkan Circuit kuantum yang menganggarkan $y$ dalam $m$ bit dengan membuat pengukuran pada $m$ qubit. Dalam Circuit di atas, $m$ qubit teratas dimulakan dalam keadaan $\ket{0^m}$, dan $n$ qubit di bawah dimulakan dalam $\ket{\psi}$, yang dijanjikan sebagai eigenvector bagi $U$. Bahan pertama dalam Circuit anggaran fasa ialah operasi uniter terkawalan yang bertanggungjawab melaksanakan phase kickback kepada qubit kawalan yang sepadan. Uniter terkawalan ini dipangkatkan mengikut kedudukan qubit kawalan, daripada bit paling tidak signifikan kepada bit paling signifikan. Oleh sebab $\ket{\psi}$ ialah eigenvector bagi $U$, keadaan $n$ qubit bawah tidak terjejas oleh operasi ini, tetapi maklumat fasa nilai eigen merambat ke $m$ qubit teratas. Ternyata bahawa selepas operasi phase kickback melalui uniter terkawalan, semua keadaan yang mungkin bagi $m$ qubit teratas adalah ortonormal antara satu sama lain bagi setiap eigenvector $\ket{\psi}$ bagi uniter $U$. Oleh itu, keadaan-keadaan ini boleh dibezakan dengan sempurna, dan kita boleh memutar asas yang dibentuknya kembali ke asas pengkomputeran untuk membuat pengukuran. Analisis matematik menunjukkan bahawa matriks putaran ini sepadan dengan jelmaan Fourier kuantum songsang (QFT) dalam ruang Hilbert berdimensi $2^m$. Intuisi di sebalik ini ialah struktur berkala bagi pengendali pemangkatan modular dikodkan dalam keadaan kuantum, dan QFT menukar kekala ini kepada puncak yang boleh diukur dalam domain frekuensi.

Untuk pemahaman yang lebih mendalam tentang sebab Circuit QFT digunakan dalam algoritma Shor, kami merujuk pembaca kepada kursus Asas algoritma kuantum. Kita kini bersedia menggunakan Circuit anggaran fasa untuk pencarian perintah.

Masalah pencarian perintah

Untuk mentakrifkan masalah pencarian perintah, kita mulakan dengan beberapa konsep teori nombor. Pertama, bagi mana-mana integer positif $N$ yang diberi, takrifkan set $\mathbb{Z}_N$ sebagai $\mathbb{Z}_N = \{0, 1, 2, \dots, N-1\}.$ Semua operasi aritmetik dalam $\mathbb{Z}_N$ dilaksanakan modulo $N$. Khususnya, semua elemen $a \in \mathbb{Z}_n$ yang koprosa dengan $N$ adalah istimewa dan membentuk $\mathbb{Z}^*_N$ sebagai $\mathbb{Z}^*_N = \{ a \in \mathbb{Z}_N : \mathrm{gcd}(a, N)=1 \}.$ Bagi elemen $a \in \mathbb{Z}^*_N$, integer positif terkecil $r$ supaya $a^r \equiv 1 \; (\mathrm{mod} \; N)$ ditakrifkan sebagai perintah bagi $a$ modulo $N$. Seperti yang akan kita lihat kemudian, mencari perintah bagi $a \in \mathbb{Z}^*_N$ akan membolehkan kita memfaktorkan $N$. Untuk membina Circuit pencarian perintah daripada Circuit anggaran fasa, kita memerlukan dua pertimbangan. Pertama, kita perlu mentakrifkan uniter $U$ yang akan membolehkan kita mencari perintah $r$, dan kedua, kita perlu mentakrifkan eigenvector $\ket{\psi}$ bagi $U$ untuk menyediakan keadaan awal Circuit anggaran fasa.

Untuk menghubungkan masalah pencarian perintah kepada anggaran fasa, kita pertimbangkan operasi yang ditakrifkan pada sistem yang keadaan klasiknya sepadan dengan $\mathbb{Z}_N$, di mana kita darab dengan elemen tetap $a \in \mathbb{Z}^*_N$. Khususnya, kita takrifkan pengendali pendaraban $M_a$ supaya $M_a \ket{x} = \ket{ax \; (\mathrm{mod} \; N)}$ bagi setiap $x \in \mathbb{Z}_N$. Perhatikan bahawa secara tersirat kita mengambil hasil darab modulo $N$ di dalam ket pada sebelah kanan persamaan. Analisis matematik menunjukkan bahawa $M_a$ ialah pengendali uniter. Tambahan pula, $M_a$ mempunyai pasangan eigenvector dan nilai eigen yang membolehkan kita menghubungkan perintah $r$ bagi $a$ kepada masalah anggaran fasa. Khususnya, bagi mana-mana pilihan $j \in \{0, \dots, r-1\}$, kita dapati bahawa $\ket{\psi_j} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \omega^{-jk}_{r} \ket{a^k}$ ialah eigenvector bagi $M_a$ yang nilai eigennya sepadan ialah $\omega^{j}_{r}$, di mana $\omega^{j}_{r} = e^{2 \pi i \frac{j}{r}}.$ Dengan pemerhatian, kita nampak bahawa pasangan eigenvector/nilai eigen yang mudah ialah keadaan $\ket{\psi_1}$ dengan $\omega^{1}_{r} = e^{2 \pi i \frac{1}{r}}$. Oleh itu, jika kita boleh mencari eigenvector $\ket{\psi_1}$, kita boleh menganggarkan fasa $\theta=1/r$ dengan Circuit kuantum kita dan seterusnya mendapat anggaran perintah $r$. Namun, ini tidaklah mudah dilakukan, dan kita perlu mempertimbangkan alternatif lain.

Mari kita pertimbangkan apa yang akan dihasilkan oleh Circuit jika kita menyediakan keadaan pengkomputeran $\ket{1}$ sebagai keadaan awal. Ini bukanlah eigenstate bagi $M_a$, tetapi ia ialah superposisi seragam bagi eigenstate yang baru kita huraikan di atas. Dengan kata lain, hubungan berikut berlaku. $\ket{1} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \ket{\psi_k}$ Implikasi persamaan di atas ialah jika kita tetapkan keadaan awal kepada $\ket{1}$, kita akan mendapat tepat hasil pengukuran yang sama seolah-olah kita telah memilih $k \in \{ 0, \dots, r-1\}$ secara seragam rawak dan menggunakan $\ket{\psi_k}$ sebagai eigenvector dalam Circuit anggaran fasa. Dengan kata lain, pengukuran $m$ qubit teratas menghasilkan anggaran $y / 2^m$ kepada nilai $k / r$ di mana $k \in \{ 0, \dots, r-1\}$ dipilih secara seragam rawak. Ini membolehkan kita mengetahui $r$ dengan keyakinan yang tinggi selepas beberapa larian bebas, yang merupakan matlamat kita.

Pengendali pemangkatan modular

Setakat ini, kita telah menghubungkan masalah anggaran fasa kepada masalah pencarian perintah dengan mentakrifkan $U = M_a$ dan $\ket{\psi} = \ket{1}$ dalam Circuit kuantum kita. Oleh itu, bahan terakhir yang tinggal ialah mencari cara yang cekap untuk mentakrifkan eksponen modular bagi $M_a$ sebagai $M_a^k$ untuk $k = 1, 2, 4, \dots, 2^{m-1}$. Untuk melaksanakan pengiraan ini, kita dapati bahawa bagi sebarang kuasa $k$ yang kita pilih, kita boleh mencipta Circuit untuk $M_a^k$ bukan dengan mengulang $k$ kali Circuit untuk $M_a$, tetapi sebaliknya dengan mengira $b = a^k \; \mathrm{mod} \; N$ dan kemudian menggunakan Circuit untuk $M_b$. Oleh sebab kita hanya memerlukan kuasa yang merupakan kuasa 2 itu sendiri, kita boleh melakukan ini dengan cekap secara klasik menggunakan kuasa dua berulang.

Langkah 2: Optimumkan masalah untuk pelaksanaan perkakasan kuantum

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

Kita boleh berhenti sebentar di sini untuk membincangkan contoh khusus dan membina Circuit pencarian perintah untuk $N=15$. Perhatikan bahawa nilai $a \in \mathbb{Z}_N^*$ yang tidak trivial yang mungkin untuk $N=15$ ialah $a \in \{2, 4, 7, 8, 11, 13, 14 \}$. Untuk contoh ini, kita pilih $a=2$. Kita akan membina pengendali $M_2$ dan pengendali pemangkatan modular $M_2^k$. Tindakan $M_2$ pada keadaan asas pengkomputeran adalah seperti 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}$ Dengan pemerhatian, kita dapat lihat bahawa keadaan asas ditukar ganti, jadi kita mempunyai matriks permutasi. Kita boleh membina operasi ini pada empat qubit dengan gate swap. Di bawah, kita bina operasi $M_2$ dan $M_2$ terkawalan.

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 bertindak pada lebih daripada dua qubit akan didekomposkan lagi kepada gate dua qubit.

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

Kini kita perlu membina pengendali pemangkatan modular. Untuk mendapatkan ketepatan yang mencukupi dalam anggaran fasa, kita akan menggunakan lapan qubit untuk pengukuran anggaran. Oleh itu, kita perlu membina $M_b$ dengan $b = a^{2^k} \; (\mathrm{mod} \; N)$ bagi 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 dapat kita lihat daripada senarai nilai $b$, selain $M_2$ yang telah kita bina sebelum ini, kita juga perlu membina $M_4$ dan $M_1$. Perhatikan bahawa $M_1$ bertindak secara trivial pada keadaan asas pengkomputeran, jadi ia hanyalah pengendali identiti.

$M_4$ bertindak pada keadaan asas pengkomputeran seperti 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 itu, permutasi ini boleh dibina 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 bertindak pada lebih daripada dua qubit akan didekomposkan lagi kepada gate dua qubit.

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

Kita telah lihat bahawa pengendali $M_b$ bagi $b \in \mathbb{Z}^*_N$ yang diberikan adalah operasi permutasi. Disebabkan saiz masalah permutasi yang agak kecil di sini, oleh kerana $N=15$ hanya memerlukan empat qubit, kita dapat mensintesis operasi ini terus dengan gate SWAP melalui pemeriksaan. Secara umum, ini mungkin bukan pendekatan yang berskala. Sebaliknya, kita mungkin perlu membina matriks permutasi secara eksplisit, dan menggunakan kelas UnitaryGate Qiskit dan kaedah transpilasi untuk mensintesis matriks permutasi ini. Namun, ini boleh menghasilkan Circuit yang jauh lebih dalam. Contoh berikut menunjukkannya.

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 kiraan ini dengan kedalaman Circuit yang dikompil bagi implementasi manual kita bagi gate $M_2$.

# 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 dapat kita lihat, pendekatan matriks permutasi menghasilkan Circuit yang jauh lebih dalam walaupun untuk satu gate $M_2$ berbanding implementasi manual kita. Oleh itu, kita akan teruskan dengan implementasi operasi $M_b$ yang sebelumnya. Kini, kita bersedia untuk membina Circuit pencarian perintah penuh menggunakan pengendali pemangkatan modular terkawalan yang telah kita takrifkan sebelum ini. Dalam kod berikut, kita juga mengimport Circuit QFT daripada pustaka Circuit Qiskit, yang menggunakan gate Hadamard pada setiap qubit, satu siri gate controlled-U1 (atau Z, bergantung pada fasa), 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 bahawa kita telah menghilangkan operasi pemangkatan modular terkawalan daripada qubit kawalan yang tinggal kerana $M_1$ ialah pengendali identiti. Perhatikan bahawa kemudian dalam tutorial ini, kita akan menjalankan Circuit ini pada Backend ibm_marrakesh. Untuk melakukan ini, kita transpilkan Circuit mengikut Backend khusus ini dan laporkan kedalaman Circuit serta kiraan 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: Laksanakan menggunakan primitif Qiskit

Pertama, kita bincangkan apa yang kita akan dapat secara teorinya jika kita jalankan litar ini pada simulator yang ideal. Di bawah, kita ada satu set keputusan simulasi litar di atas menggunakan 1024 shot. Seperti yang dapat kita lihat, kita mendapat taburan yang lebih kurang seragam merentasi empat bitstring pada qubit kawalan.

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

plot_histogram(counts)

Dengan mengukur qubit kawalan, kita memperoleh anggaran fasa lapan-bit bagi pengendali $M_a$. Kita boleh menukar perwakilan binari ini kepada perpuluhan untuk mencari fasa yang diukur. Seperti yang dapat kita lihat daripada histogram di atas, empat bitstring berbeza telah diukur, dan setiap satunya sepadan dengan nilai fasa seperti 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 bahawa mana-mana fasa yang diukur sepadan dengan $\theta = k / r$ di mana $k$ disampel secara rawak seragam daripada $\{0, 1, \dots, r-1 \}$. Oleh itu, kita boleh menggunakan algoritma pecahan berterusan untuk cuba mencari $k$ dan peringkat $r$. Python ada fungsi ini terbina dalam. Kita boleh menggunakan modul fractions untuk menukar float kepada objek Fraction, contohnya:

Fraction(0.666)

Fraction(5998794703657501, 9007199254740992)

Memandangkan ini memberikan pecahan yang mengembalikan hasil dengan tepat (dalam kes ini, 0.6660000...), ini boleh menghasilkan keputusan yang janggal seperti di atas. Kita boleh menggunakan kaedah .limit_denominator() untuk mendapatkan pecahan yang paling hampir menyerupai 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 kemas. Peringkat (r) mestilah kurang daripada N, jadi kita akan tetapkan penyebut maksimum kepada 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 dapat lihat bahawa dua daripada nilai eigen yang diukur memberikan kita hasil yang betul: $r=4$, dan kita dapat lihat bahawa algoritma Shor untuk mencari peringkat ada kemungkinan gagal. Keputusan yang tidak baik ini adalah kerana $k = 0$, atau kerana $k$ dan $r$ tidak koprim — dan bukannya $r$, kita diberi faktor $r$. Penyelesaian paling mudah untuk ini ialah dengan mengulangi eksperimen sahaja sehingga kita mendapat hasil yang memuaskan untuk $r$. Setakat ini, kita melaksanakan masalah pencarian peringkat untuk $N=15$ dengan $a=2$ menggunakan litar anggaran fasa pada simulator. Langkah terakhir algoritma Shor ialah mengaitkan masalah pencarian peringkat dengan masalah pemfaktoran integer. Bahagian terakhir algoritma ini adalah sepenuhnya klasik dan boleh diselesaikan pada komputer klasik selepas pengukuran fasa diperoleh daripada komputer kuantum. Oleh itu, kita tangguhkan bahagian terakhir algoritma ini sehingga selepas kita tunjukkan cara kita boleh menjalankan litar pencarian peringkat pada perkakasan sebenar.

Jalankan pada perkakasan

Sekarang kita boleh menjalankan litar pencarian peringkat yang sebelum ini kita transpil untuk ibm_marrakesh. Di sini kita beralih kepada dynamical decoupling (DD) untuk penyekatan ralat, dan gate twirling untuk tujuan pengurangan ralat. DD melibatkan penerapan jujukan denyutan kawalan yang tepat masanya pada peranti kuantum, yang secara efektif merata-rata interaksi persekitaran yang tidak diingini dan penyahkoheranan. Gate twirling pula merawakkan gate kuantum tertentu untuk mengubah ralat koheren kepada ralat Pauli, yang terkumpul secara linear berbanding kuadratik. Kedua-dua teknik ini sering digabungkan untuk meningkatkan koheranan dan kesetiaan pengiraan 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

# Assign tags before executing
sampler.options.environment.job_tags = ["TUT_SA"]

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 yang dapat kita lihat, kita memperoleh bitstring yang sama dengan bilangan terbanyak. Memandangkan perkakasan kuantum ada hingar, terdapat sedikit kebocoran kepada bitstring lain, yang boleh kita tapis 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: Proses selepas pengiraan dan kembalikan hasil dalam format klasik yang dikehendaki

Pemfaktoran Integer

Setakat ini, kita bincangkan cara kita boleh melaksanakan masalah pencarian peringkat menggunakan litar anggaran fasa. Sekarang, kita hubungkan masalah pencarian peringkat dengan pemfaktoran integer, yang melengkapkan algoritma Shor. Perhatikan bahawa bahagian algoritma ini adalah klasik. Kita kini tunjukkan ini menggunakan contoh $N = 15$ dan $a = 2$. Ingat bahawa fasa yang kita ukur ialah $k / r$, di mana $a^r \; (\textrm{mod} \; N) = 1$ dan $k$ ialah integer rawak antara $0$ dan $r - 1$. Daripada persamaan ini, kita ada $(a^r - 1) \; (\textrm{mod} \; N) = 0,$ yang bermaksud $N$ mesti membahagi $a^r-1$. Jika $r$ juga genap, maka kita boleh tulis $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$ Jika $r$ tidak genap, kita tidak boleh pergi lebih jauh dan mesti cuba semula dengan nilai $a$ yang berbeza; jika tidak, ada kebarangkalian tinggi bahawa pembahagi sepunya terbesar bagi $N$ dan sama ada $a^{r/2}-1$, atau $a^{r/2}+1$ adalah faktor sebenar $N$.

Memandangkan sesetengah jalankan algoritma ini akan gagal secara statistik, kita akan ulangi algoritma ini sehingga sekurang-kurangnya satu faktor $N$ ditemui. Sel di bawah mengulangi algoritma sehingga sekurang-kurangnya satu faktor $N=15$ ditemui. Kita akan gunakan keputusan jalankan perkakasan di atas untuk meneka fasa dan faktor yang sepadan dalam setiap ulangan.

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 ***

Perbincangan

Kerja berkaitan

Dalam bahagian ini, kita bincangkan kerja-kerja pencapaian penting lain yang telah menunjukkan algoritma Shor pada perkakasan sebenar.

Kerja seminal [3] daripada IBM® menunjukkan algoritma Shor buat pertama kalinya, memfaktorkan nombor 15 kepada faktor prima 3 dan 5 menggunakan komputer kuantum resonans magnetik nuklear (NMR) tujuh qubit. Eksperimen lain [4] memfaktorkan 15 menggunakan qubit fotonik. Dengan menggunakan satu qubit yang dikitar semula beberapa kali dan mengekod daftar kerja dalam keadaan berdimensi lebih tinggi, para penyelidik mengurangkan bilangan qubit yang diperlukan kepada satu pertiga daripada protokol standard, menggunakan algoritma terkompil dua foton. Satu makalah penting dalam demonstrasi algoritma Shor ialah [5], yang menggunakan teknik anggaran fasa berulang Kitaev [8] untuk mengurangkan keperluan qubit algoritma. Para pengarang menggunakan tujuh qubit kawalan dan empat qubit cache, bersama-sama dengan pelaksanaan pengganda modular. Walau bagaimanapun, pelaksanaan ini memerlukan pengukuran pertengahan litar dengan operasi suap-hadapan dan pengitaran semula qubit dengan operasi tetapan semula. Demonstrasi ini dilakukan pada komputer kuantum perangkap ion.

Kerja terkini [6] memfokuskan pada pemfaktoran 15, 21, dan 35 pada perkakasan IBM Quantum®. Sama seperti kerja sebelumnya, para penyelidik menggunakan versi terkompil algoritma yang menggunakan transformasi Fourier kuantum semi-klasik seperti yang dicadangkan oleh Kitaev untuk meminimumkan bilangan qubit fizikal dan gate. Kerja paling terkini [7] juga melakukan demonstrasi bukti konsep untuk memfaktorkan integer 21. Demonstrasi ini juga melibatkan penggunaan versi terkompil rutin anggaran fasa kuantum, dan dibina atas demonstrasi sebelumnya oleh [4]. Para pengarang melampaui kerja ini dengan menggunakan konfigurasi gate Toffoli penghampiran dengan anjakan fasa sisa. Algoritma ini dilaksanakan pada pemproses kuantum IBM menggunakan hanya lima qubit, dan kehadiran keterjalin antara qubit kawalan dan daftar berjaya disahkan.

Penskalaan algoritma

Kita perhatikan bahawa penyulitan RSA biasanya melibatkan saiz kunci pada susunan 2048 hingga 4096 bit. Cuba memfaktorkan nombor 2048-bit dengan algoritma Shor akan menghasilkan litar kuantum dengan berjuta-juta qubit, termasuk overhed pembetulan ralat dan kedalaman litar pada susunan satu bilion, yang melebihi had perkakasan kuantum semasa untuk dilaksanakan. Oleh itu, algoritma Shor memerlukan sama ada kaedah pembinaan litar yang dioptimumkan atau pembetulan ralat kuantum yang kukuh untuk menjadi praktikal bagi memecahkan sistem kriptografi moden. Kami merujuk anda kepada [9] untuk perbincangan lebih terperinci mengenai anggaran sumber untuk algoritma Shor.

Cabaran

Tahniah kerana menyelesaikan tutorial ini! Sekarang adalah masa yang baik untuk menguji kefahaman anda. Bolehkah anda cuba membina litar untuk memfaktorkan 21? Anda boleh pilih $a$ mengikut pilihan sendiri. Anda perlu menentukan ketepatan bit algoritma untuk memilih bilangan qubit, dan anda perlu mereka bentuk pengendali pemangkatan modular $M_a$. Kami menggalakkan anda untuk mencuba sendiri, kemudian baca tentang metodologi yang ditunjukkan dalam Rajah 9 daripada [6] dan Rajah 2 daripada [7].

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

    # Your code here
    pass

Rujukan

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.