Shor sim Algorithmus

Verbruchsschätzig: Drüü Sekunde uf emene Eagle r3-Prozessor (ACHTIG: Das isch nume e Schätzig. Dyni Loufzyt chan anders sy.)

Shor sim Algorithmus, vom Peter Shor im Johr 1994 entwicklet, isch en bahnbrechende Quantealgorithmus fürs Faktorisiere vo Zahle i polynomialere Zyt. Syni Bedütig lyt drinn, dass er grossi Zahle exponentiell schnäller faktorisiere chan als alli bekannte klassische Algorithme, und demit d'Sicherheit vo wyt verbreite Kryptosysteem wie RSA bedroht, wo druf basiere, dass es schwierig isch, grossi Zahle z'faktorisiere. Indem er das Problem uf emene gnueg starke Quantecomputer effizient löst, chönnt Shor sim Algorithmus Gebiet wie Kryptografie, Cybersicherheit und Berächnigsmathematik revolutioniere, und demit d'transformativi Chraft vo de Quanteberechni g unterstryche.

Das Tutorial zeigt Shor sim Algorithmus, indem mir d'15 uf emene Quantecomputer faktorisiere.

Zerscht definiere mir s'Orni gsfindi gsproblem und konstruiere entsprechendi Schaltchreis us em Quantephasenischätzigsprotokoll. Als nöchschts lönd mir d'Ornigsfindi gsschaltchreis uf echter Hardware mit de chürzeste Schaltchreis, wo mir transpiliere chönd. Dr letschti Abschnitt vervollständigt Shor sim Algorithmus, indem mir s'Ornigsfindi gsproblem mit de ganzzahlige Faktorisierig verbinde.

Mir schliesse s'Tutorial mit enere Diskussion über anderi Demonstratione vom Shor sim Algorithmus uf echter Hardware ab, wo sech sowohl uf allgemeini Implementatione als au uf selli konzentriere, wo uf s'Faktorisiere vo spezielle Zahle wie 15 und 21 zuegeschnitte sind. Achtig: Das Tutorial konzentriert sech me uf d'Implementazioon und Demonstrazioon vo de Schaltchreis für Shor sim Algorithmus. Für e vertiefti pädagogischi Ressource über s'Material lueg bitte i Fundamentals of quantum algorithms Kurs vom Dr. John Watrous, und d'Papers im Referenze-Abschnitt.

Vorussetzige

Bevor du mit em Tutorial aafangsch, lueg, dass du s'Folgende installiert hesch:

Qiskit SDK v2.0 oder neuer, mit Visualisierig Unterstützig
Qiskit Runtime v0.40 oder neuer (pip install qiskit-ibm-runtime)

Yrichtig

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

Schritt 1: Klassischi Ygabe uf es Quanteproblem abbilde

Hintergrund

Shor sim Algorithmus für ganzzahligi Faktorisierig nutzt es Zwüscheproblem, wo als Ornigsfindi gsproblem bekannt isch. I dem Abschnitt zeige mir, wie mir s'Ornigsfindi gsproblem mit Quantephasenischätzig löse.

Phasenischätzi gsproblem

Bim Phasenischätzi gsproblem überchöme mir en Quantezuestand $\ket{\psi}$ vo $n$ Qubits, zäme mit emene unitäre Quanteschaltchreis, wo uf $n$ Qubits schafft. Üs wird verspro che, dass $\ket{\psi}$ en Eigevektor vo de unitäre Matrix $U$ isch, wo d'Wurkig vom Schaltchreis beschrybt, und üses Ziel isch es, de Eigewärt $\lambda = e^{2 \pi i \theta}$ z'berechne oder abzschätze, zu dem $\ket{\psi}$ ghört. Mit andere Wort, dr Schaltchreis söll e Annäherig a d'Zahl $\theta \in [0, 1)$ usgäh, wo $U \ket{\psi}= e^{2 \pi i \theta} \ket{\psi}$ erfüllt. S'Ziel vom Phasenischätzi gsschaltchreis isch es, $\theta$ i $m$ Bits abzschätze. Mathematisch gredt wönd mir $y$ finde, so dass $\theta \approx y / 2^m$ , wo $y \in {0, 1, 2, \dots, 2^{m-1}}$ . S'folgendi Bild zeigt de Quanteschaltchreis, wo $y$ i $m$ Bits abschätzt, indem er e Messig uf $m$ Qubits macht. Quantum phase estimation circuit Im Schaltchreis obe wärde d'oberschte $m$ Qubits im $\ket{0^m}$ -Zuestand initialisiert, und d'unterste $n$ Qubits im $\ket{\psi}$ , wo verspro che wird, en Eigevektor vo $U$ z'sy. D'erscht Zueta t im Phasenischätzi gsschaltchreis sind d'kontrollierte unitäre Operatore, wo derfür verantwortli ch sind, en Phasekickback uf ihrem entsprechende Kontroll-Qubit durezfüere. Die kontrollierte Unitäre wärde potenziert gmäss de Position vom Kontroll-Qubit, vom mindescht signifikante Bit bis zum meischt signifikante Bit. Wyl $\ket{\psi}$ en Eigevektor vo $U$ isch, blybt dr Zuestand vo de unterste $n$ Qubits vo dere Operazioon unberüehrt, aber d'Phaseninformazioon vom Eigewärt breitet sech zu de oberschte $m$ Qubits uus. Es stellt sech use, dass nach em Phasekickback über kontrollierti Unitäri alli mögliche Zueständ vo de oberschte $m$ Qubits orthonormal zuenand sind für jede Eigevektor $\ket{\psi}$ vom unitäre $U$ . Darum sind die Zueständ perfekt unterscheidbar, und mir chönd d'Basis, wo si bilde, zrugg i d'Berächnigsbasis rotiere, zum e Messig z'mache. E mathematischi Analysi zeigt, dass die Rotazioonsmartix de inverse Quantefouriertransformazioon (QFT) im $2^m$ -dimensionale Hilbert-Ruum entspricht. D'Intuizioon dehinder isch, dass d'periodischi Struktur vo de modulare Potenzierigsoperatore im Quantezuestand kodiert isch, und d'QFT wandlet die Periodizität i messbare Spitze im Freque nzbereich um.

Für es vertiefts Verständnis drüber, warum dr QFT-Schaltchreis im Shor sim Algorithmus bruucht wird, verwyse mir de Läser uf de Fundamentals of quantum algorithms Kurs. Mir sind jetz parat, de Phasenischätzi gsschaltchreis fürs Ornigsfinde z'bruche.

Ornigsfindi gsproblem

Zum s'Ornigsfindi gsproblem z'definiere, fange mir mit es paar zahletheor etische Konzept aa. Zerscht definiere mir für jedi positivi Ganzzahl $N$ d'Mängi $\mathbb{Z}_N$ als $\mathbb{Z}_N = \{0, 1, 2, \dots, N-1\}.$ Alli arithmetische Operazioone i $\mathbb{Z}_N$ wärde modulo $N$ duregfüehrt. Bsunders sind alli Elemänt $a \in \mathbb{Z}_n$ , wo teilerfrämd mit $N$ sind, speziell und bilde $\mathbb{Z}^*_N$ als $\mathbb{Z}^*_N = \{ a \in \mathbb{Z}_N : \mathrm{gcd}(a, N)=1 \}.$ Für es Elemänt $a \in \mathbb{Z}^*_N$ wird d'chlynscht positivi Ganzzahl $r$ so, dass $a^r \equiv 1 \; (\mathrm{mod} \; N)$ als d'Ornig vo $a$ modulo $N$ definiert. Wie mir später gsehnd, lönd üs s'Finde vo de Ornig vo emene $a \in \mathbb{Z}^*_N$ $N$ faktorisiere. Zum de Ornigsfindi gsschaltchreis us em Phasenischätzi gsschaltchreis z'konstruiere, bruche mir zwei Überlegige. Zerscht müesse mir s'unitäri $U$ definiere, wo üs erlaubt, d'Ornig $r$ z'finde, und zweitens müesse mir en Eigevektor $\ket{\psi}$ vo $U$ definiere, zum de Aafangszuestand vom Phasenischätzi gsschaltchreis vorzberäite.

Zum s'Ornigsfindi gsproblem mit de Phasenischätzig z'verbinde, betrachte mir d'Operazioon, wo uf emene System definiert isch, wo dyni klassische Zueständ $\mathbb{Z}_N$ entspräche, wo mir mit emene feste Elemänt $a \in \mathbb{Z}^*_N$ multipliziere. Bsunders definiere mir dä Multiplikazioons-Operator $M_a$ so, dass $M_a \ket{x} = \ket{ax \; (\mathrm{mod} \; N)}$ für jedes $x \in \mathbb{Z}_N$ . Lueg, dass es implizit isch, dass mir s'Produkt modulo $N$ innerhalb vom Ket uf de rächte Syte vo de Glychig näme. E mathematischi Analysi zeigt, dass $M_a$ en unitäre Operator isch. Wyters stellt sech use, dass $M_a$ Eigevektor- und Eigewärtpaar het, wo üs erlaubet, d'Ornig $r$ vo $a$ mit em Phasenischätzi gsproblem z'verbinde. Speziell, für jedi Wahl vo $j \in \{0, \dots, r-1\}$ händ mir, dass $\ket{\psi_j} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \omega^{-jk}_{r} \ket{a^k}$ en Eigevektor vo $M_a$ isch, wo dä entsprechend Eigewärt $\omega^{j}_{r}$ isch, wo $\omega^{j}_{r} = e^{2 \pi i \frac{j}{r}}.$ Dur Beob achtig gsehnd mir, dass es bequems Eigevektor/Eigewärt-Paar dr Zuestand $\ket{\psi_1}$ mit $\omega^{1}_{r} = e^{2 \pi i \frac{1}{r}}$ isch. Darum, wänn mir de Eigevektor $\ket{\psi_1}$ chönnte finde, chönnte mir d'Phase $\theta=1/r$ mit üsem Quanteschaltchreis abschätze und demit e Abschätzig vo de Ornig $r$ übercho. Aber das isch nöd eifach, und mir müesse e Alternativ betrachte.

Lönd üs überlegge, was dr Schaltchreis usgäh wurd, wänn mir de Berächni gszuestand $\ket{1}$ als Aafangszuestand vorbereite. Das isch kei Eigezuestand vo $M_a$ , aber es isch d'glychförmi g Überlagerig vo de obe beschriebene Eigezueständ. Mit andere Wort, d'folgendi Beziehi g gilt. $\ket{1} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \ket{\psi_k}$ D'Bedüti g vo de obige Glychig isch, dass wänn mir de Aafangszuestand uf $\ket{1}$ setze, überchöme mir genau s'glychi Messresultat, wie wänn mir $k \in \{ 0, \dots, r-1\}$ glychförmi g zufällig gwählt hätte und $\ket{\psi_k}$ als Eigevektor im Phasenischätzi gsschaltchreis bruucht hätte. Mit andere Wort, e Messig vo de oberschte $m$ Qubits git e Annäherig $y / 2^m$ a de Wärt $k / r$ , wo $k \in \{ 0, \dots, r-1\}$ glychförmi g zufällig gwählt wird. Das erlaubt üs, $r$ mit emene hohe Grad a Sicherheit nach mehrere unabhängige Durchlöif z'lehre, was üses Ziel isch gsi.

Modulari Potenzierigsoperatore

Bis jetz händ mir s'Phasenischätzi gsproblem mit em Ornigsfindi gsproblem verbunde, indem mir $U = M_a$ und $\ket{\psi} = \ket{1}$ i üsem Quanteschaltchreis definiert händ. Darum isch d'letscht verblibeni Zueta t, en effizienti Wäg z'finde, zum modulari Exponente vo $M_a$ als $M_a^k$ für $k = 1, 2, 4, \dots, 2^{m-1}$ z'definiere. Zum die Berächni g durezfüere, stelle mir fescht, dass für jedi Potänz $k$ , wo mir wähle, chönd mir en Schaltchreis für $M_a^k$ nöd erstelle, indem mir $k$ mal de Schaltchreis für $M_a$ iteriere, sundern indem mir $b = a^k \; \mathrm{mod} \; N$ berächne und dänn de Schaltchreis für $M_b$ bruche. Wyl mir nume d'Potänze bruche, wo sälber Potänze vo 2 sind, chönd mir das klassisch effizient mache, indem mir iterativs Quadriere bruche.

Schritt 2: Problem fürs Quantehardware-Usfüehrig optimiere

Speziells Byspil mit $N = 15$ und $a=2$

Mir chönd hie pausiere, zum es speziells Byspil z'diskutiere und de Ornigsfindi gsschaltchreis für $N=15$ z'konstruiere. Lueg, dass möglichi nöd-triviali $a \in \mathbb{Z}_N^*$ für $N=15$ sind $a \in \{2, 4, 7, 8, 11, 13, 14 \}$ . Für das Byspil wähle mir $a=2$ . Mir wärde de $M_2$ -Operator und d'modulare Potenzierigsoperatore $M_2^k$ konstruiere. D'Wurkig vo $M_2$ uf d'Berächni gsbasi szueständ isch wie folgt. $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}$ Dur Beobachti g chönd mir gseh, dass d'Basiszueständ gmischt wärde, also händ mir e Permutazioonsmartix. Mir chönd die Operazioon uf vier Qubits mit Swap-Gates konstruiere. Une konstruiere mir de $M_2$ und d'kontrollierte- $M_2$ Operatore.

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)

Output of the previous code cell

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)

Output of the previous code cell

Gates, wo uf meh als zwei Qubits schaffed, wärde wyter i zwei-Qubit-Gates zerleit.

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

Output of the previous code cell

Jetz müesse mir d'modulare Potenzierigsoperatore konstruiere. Zum gnueg Präzision i de Phasenischätzi g z'übercho, wärde mir acht Qubits für d'Abschätzigsmessig bruche. Darum müesse mir $M_b$ mit $b = a^{2^k} \; (\mathrm{mod} \; N)$ für jedes $k = 0, 1, \dots, 7$ konstruiere.

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]

Wie mir us de Lischt vo $b$ -Wärt gsehn d chönd, bruche mir näbe $M_2$ , wo mir vorher konstruiert händ, au $M_4$ und $M_1$ . Lueg, dass $M_1$ trivial uf d'Berächni gsbasi szueständ wurkt, also isch es eifach dr Identitätsoperator.

$M_4$ wurkt uf d'Berächni gsbasi szueständ wie folgt. $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}$

Darum cha die Permutazioon mit de folgendi Swap-Operazioon konstruiert wärde.

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)

Output of the previous code cell

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)

Output of the previous code cell

Gates, wo uf meh als zwei Qubits schaffed, wärde wyter i zwei-Qubit-Gates zerleit.

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

Output of the previous code cell

Mir händ gseh, dass $M_b$ -Operatore für es gehs $b \in \mathbb{Z}^*_N$ Permutazioonsoperatore sind. Wäge de relativ chline Gröss i vom Permutazioonsprobl em, wo mir hie händ, wyl $N=15$ nume vier Qubits bruucht, händ mir die Operazioone direkt mit SWAP-Gates dur Inspekzioon chöne synthesiere. Im Allgemeine chönnt das nöd skalierbar sy. Stattdesse chönnte mir d'Permutazioonsmarti x explizit konstruiere und Qiskits UnitaryGate-Klass und Transpilierigs-Methode bruche, zum die Permutazioonsmarti x z'synthesiere. Aber das cha zu signifikant tiefere Schaltchreis füehre. Es Byspil folgt.

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})

Output of the previous code cell

Lönd üs die Zahle mit de kompilierten Schaltchreistiefe vo üsere manuelle Implementazioon vom $M_2$ -Gate verglyche.

# 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})

Output of the previous code cell

Wie mir gsehn d chönd, het dr Permutazioonsmarti x-Aasatz zu emene signifikant tiefe Schaltchreis gfüehrt, sogar für en einzelne $M_2$ -Gate, vergliche mit üsere manuelle Implementazioon. Darum wärde mir mit üsere vorherige Implementazioon vo de $M_b$ -Operazioone wyterma che. Jetz sind mir parat, de vollständig Ornigsfindi gsschaltchreis mit üsere vorher definierten kontrollierten modulare Potenzierigsoperatore z'konstruiere. Im folgende Code importiere mir au de QFT-Schaltchreis us de Qiskit Circuit-Bibliothek, wo Hadamard-Gates uf jedem Qubit bruucht, e Reihe vo kontrollierte U1- (oder Z-, je nach Phase) Gates und e Laag vo Swap-Gates.

# 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)

Output of the previous code cell

Lueg, dass mir d'kontrollierte modulare Potenzierigsoperazioone vo de verblibene Kontroll-Qubits wägglaa händ, wyl $M_1$ dr Identitätsoperator isch. Lueg, dass mir später i däm Tutorial dä Schaltchreis uf em ibm_marrakesh-Backend laafe wärde. Defür transpiliere mir de Schaltchreis für dä spezielle Backend und berichte d'Schaltchreistiefe und Gate-Zahle.

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})

Output of the previous code cell

Schritt 3: Mit Qiskit-Primitiv usfüehre

Zerscht diskutiere mir, was mir theoretisch überchöme würde, wänn mir dä Schaltchreis uf emene ideale Simulator laafe tä. Une händ mir es Set vo Simulazioonsresultaten vom obe Schaltchreis mit 1024 Shots. Wie mir gsehn d chönd, überchöme mir e ungefähr glychförmi gi Verteilig über vier Bitstrings über d'Kontroll-Qubits.

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

plot_histogram(counts)

Output of the previous code cell

Indem mir d'Kontroll-Qubits mässe, überchöme mir e acht-Bit-Phasenischätzi g vom $M_a$ -Operator. Mir chönd die binäri Darstellig i dezimal umwandle, zum d'gmässeni Phase z'finde. Wie mir im obe Histogramm gsehn d chönd, sind vier verschiedeni Bitstrings gmässe worde, und jedes vo ihne entspricht emene Phasewärt wie folgt.

# 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
00000000(bin) =   0(dec)    0/256 = 0.00
01000000(bin) =  64(dec)   64/256 = 0.25
10000000(bin) = 128(dec)  128/256 = 0.50
11000000(bin) = 192(dec)  192/256 = 0.75

Dänk dra, dass jedi gmässeni Phase $\theta = k / r$ entspricht, wo $k$ glychförmi g zufällig us $\{0, 1, \dots, r-1 \}$ gsamplet wird. Darum chönd mir de Kettebruch-Algorithmus bruche, zum z'versuche, $k$ und d'Ornig $r$ z'finde. Python het die Funktionalität yybaut. Mir chönd s'fractions-Modul bruche, zum en Float i es Fraction-Objekt umzwandle, zum Byspil:

Fraction(0.666)

Fraction(5998794703657501, 9007199254740992)

Wyl das Brüüch git, wo s'Resultat genau zrugggänd (i däm Fall 0.6660000...), cha das verrussti Resultat wie das obe gäh. Mir chönd d'.limit_denominator()-Methode bruche, zum de Bruch z'übercho, wo üsem Float am nöchste chunt, mit emene Nänner ünger emene bestimmte Wärt:

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

Fraction(2, 3)

Das isch vill schöner. D'Ornig (r) mues chlyner als N sy, also setze mir de maximali Nänner uf 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.00      0/1            1
 0.25      1/4            4
 0.50      1/2            2
 0.75      3/4            4

Mir chönd gseh, dass zwei vo de gmässene Eigewärt üs s'korräkti Resultat glifferet händ: $r=4$ , und mir chönd gseh, dass Shor sim Algorithmus fürs Ornigsfinde e Chans het z'versage. Die schläächte Resultat chömed drüs, dass $k = 0$ , oder wyl $k$ und $r$ nöd teilerfrämd sind - und statt $r$ überchöme mir en Faktor vo $r$ . D'eifachsti Lösig derför isch eifach, s'Experiment z'widerholen, bis mir es zfridenstell ends Resultat für $r$ überchöme. Bis jetz händ mir s'Ornigsfindi gsproblem für $N=15$ mit $a=2$ mit emene Phasenischätzi gsschaltchreis uf emene Simulator implementiert. Dr letscht Schritt vo Shor sim Algorithmus wird sy, s'Ornigsfindi gsproblem zum ganzzahlige Faktorisierigsproblem z'verknüpfe. Dä letscht Teil vom Algorithmus isch rein klassisch und cha uf emene klassische Computer glöst wärde, nachdem d'Phasemässige vo emene Quantecomputer usgäh worde sind. Darum verschüebe mir dä letscht Teil vom Algorithmus, bis mir demonstriert händ, wie mir de Ornigsfindi gsschaltchreis uf echter Hardware laafe chönd.

Hardware-Usfüehrige

Jetz chönd mir de Ornigsfindi gsschaltchreis laafe, wo mir vorher für ibm_marrakesh transpiliert händ. Hie wände mir üs a Dynamischi Entkopplig (DD) für Fähler-Unterdrückig und Gate-Twirling für Fähler-Mittering-Zwäck. DD involviert s'Aawände vo Reihefol ge vo präzis zytlich festgelegte Kontroll-Pulse uf es Quantegerät, was effektiv unerwünschtigi Umgäbigs-Interakzioone und Dekohärenz usmittlet. Gate-Twirling, uf de andere Syte, randomisiert spezielli Quantegates, zum kohärenti Fähler i Pauli-Fähler umzwandle, wo linear statt quadratisch wachsed. Beidi Technike wärde oft kombiniert, zum d'Kohärenz und Treui vo Quanteberächnige z'verbessere.

# 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))

Output of the previous code cell

Wie mir gsehn d chönd, händ mir di glyche Bitstrings mit de höchschte Zahle übercho. Wyl Quantehardware Rusche het, gits es bitzeli Leckage zu andere Bitstrings, wo mir statistisch filtere chönd.

# 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}

Schritt 4: Nachbearbeitig und Resultat im gwünschte klassische Format usgäh

Ganzzahligi Faktorisierig

Bis jetz händ mir diskutiert, wie mir s'Ornigsfindi gsproblem mit emene Phasenischätzi gsschaltchreis implementiere chönd. Jetz verknüpfe mir s'Ornigsfindi gsproblem mit de ganzzahlige Faktorisierig, was Shor sim Algorithmus vervollständigt. Lueg, dass dä Teil vom Algorithmus klassisch isch. Mir demonstriere das jetz mit üsem Byspil vo $N = 15$ und $a = 2$ . Dänk dra, dass d'Phase, wo mir gmässe händ, $k / r$ isch, wo $a^r \; (\textrm{mod} \; N) = 1$ und $k$ e zufälligi Ganzzahl zwüsche $0$ und $r - 1$ isch. Us dere Glychig händ mir $(a^r - 1) \; (\textrm{mod} \; N) = 0,$ was bedütet, $N$ mues $a^r-1$ teile. Wänn $r$ au grad isch, dänn chönd mir schryybe $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$ Wänn $r$ nöd grad isch, chönd mir nöd wyterga und müesse s'nomol mit emene andere Wärt für $a$ versuche; süscht gits e hohi Wahrschynlichk eit, dass dr grössti gemeinsam Teiler vo $N$ und entweder $a^{r/2}-1$ oder $a^{r/2}+1$ en echte Faktor vo $N$ isch.

Wyl es paar Usfüehrige vom Algorithmus statistisch versage wärde, wärde mir dä Algorithmus widerholen, bis mindeschtens ei Faktor vo $N$ gfunge isch. D'Zälle une widerholt de Algorithmus, bis mindeschtens ei Faktor vo $N=15$ gfunge isch. Mir wärde d'Resultat vo de Hardware-Usfüehrig obe bruche, zum d'Phase und dä entsprechend Faktor i jeder Iteration abzschätze.

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

Diskussion

I däm Abschnitt diskutiere mir anderi Meilenschtei-Arbete, wo Shor sim Algorithmus uf echter Hardware demonstriert händ.

D'wegwysendi Arbet [3] vo IBM® het Shor sim Algorithmus s'erscht Mal demonstriert, indem si d'Zahl 15 i ihri Primfaktore 3 und 5 faktorisiert het mit emene siibe-Qubit Nuclear Magnetic Resonance (NMR) Quantecomputer. Es anders Experiment [4] het d'15 mit photonische Qubits faktorisiert. Indem d'Forscher es einzels Qubit mehrmals widderbruucht händ und s'Werk-Register i höher-dimensionale Zueständ kodiert händ, händ si d'nötigi Azahl Qubits uf es Drittel vo däm im Standard-Protokoll reduziert, mit emene zwei-Photon-kompilierten Algorithmus. Es signifikants Paper i de Demonstrazioon vo Shor sim Algorithmus isch [5], wo Kitaevs iterativi Phasenischätzi gstechnik [8] bruucht, zum d'Qubit-Aforderig vom Algorithmus z'reduziere. Autore händ siibe Kontroll-Qubits und vier Cache-Qubits bruucht, zäme mit de Implementazioon vo modulare Multiplizierer. Die Implementazioon erforderet aber Mässige während em Durchlauf mit Feed-Forward-Operazioone und Qubit-Widderbruuch mit Reset-Operazioone. Die Demonstrazioon isch uf emene Ion-Trap-Quantecomputer gmacht worde.

Neugeri Arbet [6] het sech druf konzentriert, 15, 21 und 35 uf IBM Quantum® Hardware z'faktorisiere. Ähnlich wie vorigeri Arbet händ d'Forscher e kompilierti Version vom Algorithmus bruucht, wo e semi-klassischi Quantefouriertransformazioon, wie vom Kitaev vorgeschlage, bruucht het, zum d'Azahl vo physische Qubits und Gates z'minimiere. Es allerneugschts Wärch [7] het au es Proof-of-Concept-Demonstrazioon fürs Faktorisiere vo de ganzzahlige 21 duregfüehrt. Die Demonstrazioon het au d'Bruuch vo enere kompilierten Version vo de Quantephasenischätzi gsroutine involviert und het uf de vorigeri Demonstrazioon vo [4] ufbaut. Autore sind über das Wärch usegange, indem si e Konfigurazioon vo ungefähre Toffoli-Gates mit verblibende Phaseverschiebige bruucht händ. Dr Algorithmus isch uf IBM-Quanteprozessore mit nume föif Qubits implementiert worde, und d'Awesenheit vo Verschränkig zwüsche de Kontroll- und Register-Qubits isch erfolgrich verifiziert worde.

Skalierig vom Algorithmus

Mir merke, dass RSA-Verschlüsselig typisch Schlüssel-Grösse i de Ordnig vo 2048 bis 4096 Bits involviert. Wänn mir versuche, e 2048-Bit-Zahl mit Shor sim Algorithmus z'faktorisiere, resultiert das i emene Quanteschaltchreis mit Millione vo Qubits, inklusive Fählerkorrektur-Overhead und enere Schaltchreistiefe i de Ordnig vo enere Milliarde, was über d'Gränze vo aktueller Quantehardware usegaht. Darum wird Shor sim Algorithmus entweder optimierti Schaltchreiskonstruk zioons-Methode oder robuscht Quantefählerkorrektur bruche, zum praktisch verwendbar fürs Bräche vo moderne kryptografische Systeem z'sy. Mir verwyset di uf [9] für e detaillierti Diskussion über Ressourceschätzig für Shor sim Algorithmus.

Ufgab

Gratulier fürs Abschliesse vom Tutorial! Jetz isch e gueti Zyt, dys Verständnis z'teste. Chönnts du versuche, de Schaltchreis fürs Faktorisiere vo 21 z'konstruiere? Du chasch es $a$ vo dynere eigene Wahl uswähle. Du muesch über d'Bit-Genauigkeit vom Algorithmus entscheide, zum d'Azahl Qubits z'wähle, und du muesch d'modulare Potenzierigsoperatore $M_a$ entwärfe. Mir ermuetige di, das sälber uuszprobiere, und dänn über d'Methodologie z'läse, wo i Fig. 9 vo [6] und Fig. 2 vo [7] zeigt wird.

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

    # Your code here
    pass

Referenze

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

Vorussetzige​

Yrichtig​

Schritt 1: Klassischi Ygabe uf es Quanteproblem abbilde​

Hintergrund​

Phasenischätzi gsproblem​

Ornigsfindi gsproblem​

Modulari Potenzierigsoperatore​

Schritt 2: Problem fürs Quantehardware-Usfüehrig optimiere​

Speziells Byspil mit N=15N = 15N=15 und a=2a=2a=2​

Schritt 3: Mit Qiskit-Primitiv usfüehre​

Hardware-Usfüehrige​

Schritt 4: Nachbearbeitig und Resultat im gwünschte klassische Format usgäh​

Ganzzahligi Faktorisierig​

Diskussion​

Verwandti Arbet​

Skalierig vom Algorithmus​

Ufgab​

Referenze​

Vorussetzige

Yrichtig

Schritt 1: Klassischi Ygabe uf es Quanteproblem abbilde

Hintergrund

Phasenischätzi gsproblem

Ornigsfindi gsproblem

Modulari Potenzierigsoperatore

Schritt 2: Problem fürs Quantehardware-Usfüehrig optimiere

Speziells Byspil mit $N = 15$ und $a=2$

Schritt 3: Mit Qiskit-Primitiv usfüehre

Hardware-Usfüehrige

Schritt 4: Nachbearbeitig und Resultat im gwünschte klassische Format usgäh

Ganzzahligi Faktorisierig

Diskussion

Verwandti Arbet

Skalierig vom Algorithmus

Ufgab

Referenze