Shor singe Algorithmus

Schätzung för de Verbrauch: Drei Sekonge op enem Eagle r3-Prozessor (OPJEPASS: Dat es bloß en Schätzung. Ding Laufzick künnt andersch sin.)

Shor singe Algorithmus, vum Peter Shor em Johr 1994 entwikkelt, es ene revolutionäre Quantealgorithmus för et Faktorisiere vun Zahle en polynomiale Zick. Singe Bedütung litt dodren, dat hä jruße Zahle exponentiell flotter faktorisiere kann wie all bekannte klassische Algorithme, un domet de Secherheit vun wiet verbreidete Kryptosysteme wie RSA bedroht, de drop basiere, dat et schwierich es, jruße Zahle ze faktorisiere. Indämm hä dat Problem op enem kräftige jenoch Quantecomputer effizient löst, künnt Shor singe Algorithmus Beräijer wie Kryptografie, Cybersecherheit un Berechnungsmathematik revolutioniere, un domet de transformative Kraft vun de Quanteberechnung ongerstresse.

Dat Tutorial zeich Shor singe Algorithmus, indämm mer de 15 op enem Quantecomputer faktorisiert.

Zuerst definiere mer et Ordinungsfingungsproblem un konstruiere entsprechende Schaltkreise us däm Quante-Phasenabschätzungsprotokoll. Als nächstes laache mer de Ordinungsfingungsschaltkreise op echte Hardware met de körzeste Schaltkreise, de mer transpiliere künne. Dr letzte Avschnitt komplettiert Shor singe Algorithmus, indämm mer et Ordinungsfingungsproblem met dr ganzzahlige Faktorisierung verbenge.

Mer schl ieße dat Tutorial met ener Diskussion övver ander Demonstratione vun Shor singem Algorithmus op echter Hardware av, de sisch suwohl op allgemeine Implementieronge wie och op söllige konzentriert, de op et Faktorisiere vun speziellen Zahle wie 15 un 21 zogeschnedde sin. Opjepass: Dat Tutorial konzentriert sisch mih op de Implementierung un Demonstration vun de Schaltkreise för Shor singe Algorithmus. För en detaillierte pädagogische Ress ource övver et Material, luurt ens en däm Fundamentals of quantum algorithms Kurs vum Dr. John Watrous, un de Papers em Referenze-Avschnitt.

Vorussetzunge

Bevör de met däm Tutorial aanfängst, pass op, dat de dat Folgend installiert häs:

• Qiskit SDK v2.0 oder neuer, met Visualisierung Ongerstötzung
• Qiskit Runtime v0.40 oder neuer (pip install qiskit-ibm-runtime)

Opsetze

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

Schrett 1: Klassische Engave op e Quanteproblem afbilde

Hengerjrund

Shor singe Algorithmus för ganzzahlige Faktorisierung nötzt e Zweschenproblem, dat als Ordinungsfingungsproblem bekannt es. En däm Avschnett zeije mer, wie mer et Ordinungsfingungsproblem met Quante-Phasenabschätzung löse.

Phasenabschätzungsproblem

Bim Phasenabschätzungsproblem krije mer ene Quantezustand $\ket{\psi}$ vun $n$ Qubits, zessamme met enem unitäre Quanteschaltkreis, dä op $n$ Qubits werkt. Uns weed versprocke, dat $\ket{\psi}$ en Eigenvektor vun dr unitäre Matrix $U$ es, de de Werking vum Schaltkreis beschrievt, un uns Ziel es et, dä Eigenwert $\lambda = e^{2 \pi i \theta}$ ze berechne oder affenschätze, zo däm $\ket{\psi}$ jehürt. Met andere Wööter, dä Schaltkreis soll en Annäherung an de Zahl $\theta \in [0, 1)$ usjavve, de $U \ket{\psi}= e^{2 \pi i \theta} \ket{\psi}$ erföllt. Dat Ziel vum Phasenabschätzungsschaltkreis es et, $\theta$ en $m$ Bits affenschätze. Mathematisch jesproche welle mer $y$ finge, esu dat $\theta \approx y / 2^m$, wo $y \in {0, 1, 2, \dots, 2^{m-1}}$. Dat folgende Beld zeich dä Quanteschaltkreis, dä $y$ en $m$ Bits affeschätzt, indämm hä en Messong op $m$ Qubits määt. Em Schaltkreis dovve wäde de ov erste $m$ Qubits em $\ket{0^m}$-Zustand initialisiert, un de ungere $n$ Qubits em $\ket{\psi}$, däm versprocke weed, ene Eigenvektor vun $U$ ze sin. Dat erste Ingredient em Phasenabschätzungsschaltkreis sin de kontrollierten unitäre Operatore, de doför verantwortlisch sin, ene Phasen-Kickback op ihrm entsprechende Kontroll-Qubit dörchzefüre. Dise kontrollierten Unitäre wäde potenziert jemäß dr Position vum Kontroll-Qubit, vum minnste signifikante Bit bes zum beträglichste signifikante Bit. Weil $\ket{\psi}$ ene Eigenvektor vun $U$ es, blievt dä Zustand vun de ungere $n$ Qubits vun diser Operation unberöhrt, ävver de Phaseninformation vum Eigenwert breit sisch noh de ov erste $m$ Qubits us. Et stellt sisch erus, dat noh däm Phasen-Kickback övver kontrollierte Unitäre all müjjelesche Zustäng vun de ov erste $m$ Qubits orthonormal zo enander sin för jedde Eigenvektor $\ket{\psi}$ vun däm unitäre $U$. Doher sin dise Zustäng perfekt ongerscheidbar, un mer künne de Basis, de se bilde, zerök en de Rechenb asis rotiere, öm en Messong ze maache. En mathematische Analyse zeich, dat dise Rotationsmatrix dr inverse Quante-Fourier-Transformation (QFT) em $2^m$-dimensionale Hilbert-Raum entspreecht. De Intuition dodahinger es, dat de periodische Struktur vun de modulare Potenzierungsoperatore em Quantezustand kodiert es, un de QFT wandelt dise Periodizität en messbare Spitze em Frequenzberäisch öm.

För en diefere Verständnis dodrövver, woröm dä QFT-Schaltkreis en Shor singem Algorithmus benotzt weed, verwies mer däm Leser op dä Fundamentals of quantum algorithms Kurs. Mer sin jetz parat, dä Phasenabschätzungsschaltkreis för Ordinungsfingung ze benotze.

Ordinungsfingungsproblem

Öm et Ordinungsfingungsproblem ze definiere, fange mer met e paar Zahletheoretische Konzepte aan. Zuerst definiere mer för jede positive Ganzzahl $N$ de Meng $\mathbb{Z}_N$ als $\mathbb{Z}_N = \{0, 1, 2, \dots, N-1\}.$ All arithmetische Operatore en $\mathbb{Z}_N$ wäde modulo $N$ dörchjeföhrt. Besonders sin all Elemente $a \in \mathbb{Z}_n$, de teilerfremd met $N$ sin, speziell un bilde $\mathbb{Z}^*_N$ als $\mathbb{Z}^*_N = \{ a \in \mathbb{Z}_N : \mathrm{gcd}(a, N)=1 \}.$ För en Element $a \in \mathbb{Z}^*_N$ weed de kleinste positive Ganzzahl $r$ esu, dat $a^r \equiv 1 \; (\mathrm{mod} \; N)$ als de Ordinung vun $a$ modulo $N$ definiert. Wie mer später sin wäde, löss uns et Finge vun dr Ordinung vun enem $a \in \mathbb{Z}^*_N$ $N$ faktorisiere. Öm dä Ordinungsfingungsschaltkreis us däm Phasenabschätzungsschaltkreis ze konstruiere, bruche mer zwei Övverlegonge. Zuerst mösse mer dat unitäre $U$ definiere, dat uns et erlaubt, de Ordinung $r$ ze finge, un zweitens mösse mer ene Eigenvektor $\ket{\psi}$ vun $U$ definiere, öm dä Aafangszustand vum Phasenabschätzungsschaltkreis vörzebereide.

Öm et Ordinungsfingungsproblem met dr Phasenabschätzung ze verbenge, betrachte mer de Operation, de op enem System definiert es, desse klassische Zustäng $\mathbb{Z}_N$ entspreche, wo mer met enem feste Element $a \in \mathbb{Z}^*_N$ multipliziere. Besonders definiere mer dise Multiplikationsoperator $M_a$ esu, dat $M_a \ket{x} = \ket{ax \; (\mathrm{mod} \; N)}$ för jeddes $x \in \mathbb{Z}_N$. Pass op, dat et implizit es, dat mer et Produkt modulo $N$ ennerhalb vum Ket op dr rächte Sigg vun dr Gleichung nemme. En mathematische Analyse zeich, dat $M_a$ en unitäre Operator es. Wiggerhin stellt sisch erus, dat $M_a$ Eigenvektor- un Eigenwertepaare hät, de uns erlaubt, de Ordinung $r$ vun $a$ met däm Phasenabschätzungsproblem ze verbenge. Speziell, för jede Wahl vun $j \in \{0, \dots, r-1\}$ han mer, dat $\ket{\psi_j} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \omega^{-jk}_{r} \ket{a^k}$ en Eigenvektor vun $M_a$ es, desse entsprechende Eigenwert $\omega^{j}_{r}$ es, wo $\omega^{j}_{r} = e^{2 \pi i \frac{j}{r}}.$ Dörch Beovachtung sin mer, dat en bequeme Eigenvektor/Eigenwert-Paar dä Zustand $\ket{\psi_1}$ met $\omega^{1}_{r} = e^{2 \pi i \frac{1}{r}}$ es. Doher, wann mer dä Eigenvektor $\ket{\psi_1}$ finge künnte, künnte mer de Phase $\theta=1/r$ met unserem Quanteschaltkreis affenschätze un domet en Affenschätzung vun dr Ordinung $r$ krije. Ävver dat es nit einfach, un mer mösse en Alternative betrachte.

Losse mer övverlääje, wat dä Schaltkreis erusjävve däät, wann mer dä Rechenzustand $\ket{1}$ als Aafangszustand vörbereide. Dat es kein Eigenzustand vun $M_a$, ävver et es de gleichförmige Övverlagerung vun de ove beschrievene Eigenzustäng. Met andere Wööter, de folgende Beziehung jelt. $\ket{1} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \ket{\psi_k}$ De Bedeitung vun dr ove Gleichung es, dat wann mer dä Aafangszustand op $\ket{1}$ setze, krije mer jenau dat selvige Messungsresultat, wie wann mer $k \in \{ 0, \dots, r-1\}$ gleichförmich zofällisch jewählt hätte un $\ket{\psi_k}$ als Eigenvektor em Phasenabschätzungsschaltkreis benotzt hätte. Met andere Wööter, en Messong vun de ov erste $m$ Qubits erjevt en Annäherung $y / 2^m$ aan dä Wert $k / r$, wo $k \in \{ 0, \dots, r-1\}$ gleichförmich zofällisch jewählt weed. Dat erlaubt uns, $r$ met ener huhe Wahrscheinlichkeit noh mehrere onavhängige Durchlöf ze lähre, wat uns Ziel wohr.

Modulare Potenzierungsoperatore

Bes jetz han mer et Phasenabschätzungsproblem met däm Ordinungsfingungsproblem verbonge, indämm mer $U = M_a$ un $\ket{\psi} = \ket{1}$ en unserem Quanteschaltkreis definiert han. Doher es dat letzte verblievene Ingredient, en effiziente Wääch ze finge, öm modulare Exponentialfunktione vun $M_a$ als $M_a^k$ för $k = 1, 2, 4, \dots, 2^{m-1}$ ze definiere. Öm dise Berechnung dörchzefüre, stelle mer fest, dat för jede Potenz $k$, de mer wähle, künne mer ene Schaltkreis för $M_a^k$ nit erstelle, indämm mer $k$ Mol dä Schaltkreis för $M_a$ iteriere, sondern indämm mer $b = a^k \; \mathrm{mod} \; N$ berechne un dann dä Schaltkreis för $M_b$ benotze. Weil mer bloß de Potenzen bruche, de sälver Potenzen vun 2 sin, künne mer dat klassisch effizient maache, indämm mer iteratives Quadriere benotze.

Schrett 2: Problem för Quante-Hardware-Usiröhrung optimiere

Spezielles Beispell met $N = 15$ un $a=2$

Mer künne he pausiere, öm en spezielles Beispell ze diskutiere un dä Ordinungsfingungsschaltkreis för $N=15$ ze konstruiere. Pass op, dat müjjeliche nit-triviale $a \in \mathbb{Z}_N^*$ för $N=15$ sin $a \in \{2, 4, 7, 8, 11, 13, 14 \}$. För dat Beispell wähle mer $a=2$. Mer wäde dä $M_2$-Operator un de modulare Potenzierungsoperatore $M_2^k$ konstruiere. De Werking vun $M_2$ op de Rechenbasisz ustäng es wie folgich. $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}$ Dörch Beovachtung künne mer sin, dat de Basiszustäng jemescht wäde, also han mer en Permutationsmatrix. Mer künne dise Operation op vier Qubits met Swap-Gates konstruiere. Unge konstruiere mer dä $M_2$ un de 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)

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)

Gates, de op mih wie zwei Qubits werke, wäde wigger en zwei-Qubit-Gates zerlääch.

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

Jetz mösse mer de modulare Potenzierungsoperatore konstruiere. Öm jenoch Präzision en dr Phasenabschätzung ze krije, wäde mer aat Qubits för de Affenschätzungsmessong benotze. Doher mösse mer $M_b$ met $b = a^{2^k} \; (\mathrm{mod} \; N)$ för jeddes $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 mer us dr Leß vun $b$-Werte sin künne, bruche mer nävven $M_2$, dat mer vörher konstruiert han, och $M_4$ un $M_1$. Pass op, dat $M_1$ trivial op de Rechenbasisz ustäng werkt, also es et einfach dä Identitätsoperator.

$M_4$ werkt op de Rechenbasisz ustäng wie folgich. $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}$

Doher kann dise Permutation met dr folgende Swap-Operation konstruiert wäde.

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)

Gates, de op mih wie zwei Qubits werke, wäde wigger en zwei-Qubit-Gates zerlääch.

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

Mer han jesinn, dat $M_b$-Operatore för en jävve $b \in \mathbb{Z}^*_N$ Permutationsoperatore sin. Wääje dr relativ kleine Jrüß vum Permutationsproblem, dat mer he han, weil $N=15$ bloß vier Qubits bruch, künnte mer dise Operatore direkt met SWAP-Gates dörch Inspek tion synthesiere. Em Allgemeine künnt dat nit skalierbar sin. Stattdesse künnte mer de Permutationsmatrix explizit konstruiere un Qiskits UnitaryGate-Klass un Transpilationsmethod e benotze, öm dise Permutationsmatrix ze synthesiere. Ävver dat kann zu signifikant tiefere Schaltkreise föhre. E Beispell folgich.

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

Losse uns dise Zahle met dr kompilierten Schaltkreisdiefe vun unser manuelle Implementierung vum $M_2$-Gate vergliche.

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

Wie mer sin künne, hät dä Permutationsmatrix-Aansat zo enem signifikant diefe Schaltkreis jeföhrt, selvs för en einzelne $M_2$-Gate, verglische met unser manuelle Implementierung. Doher wäde mer met unser vörherige Implementierung vun de $M_b$-Operatore wiggermaache. Jetz sin mer parat, dä vollständige Ordinungsfingungsschaltkreis met unsere vörher definierten kontrollierten modulare Potenzierungsoperatore ze konstruiere. Em folgende Code importiere mer och dä QFT-Schaltkreis us dr Qiskit Circuit-Bibliothek, dä Hadamard-Gates op jedem Qubit benotzt, en Reih vun kontrollierten U1- (oder Z-, jenohch vun dr Phase) Gates un en Laach vun 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)

Pass op, dat mer de kontrollierten modulare Potenzierungsoperatore vun de verblievene Kontroll-Qubits wächjelosse han, weil $M_1$ dä Identitätsoperator es. Pass op, dat mer später en däm Tutorial dise Schaltkreis op dä ibm_marrakesh-Backend laache wäde. Doför transpiliere mer dä Schaltkreis för dise spezielle Backend un berichte de Schaltkreisdiefe un Gate-Zahle.

service = QiskitRuntimeService()
backend = service.backend("ibm_marrakish")
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})

Schrett 3: Met Qiskit-Primitive usiröhre

Zuerst diskutiere mer, wat mer theoretisch usjavve däte, wann mer dise Schaltkreis op enem ideale Simulator laache däte. Unge han mer e Set vun Simulationsresultate vum ove Schaltkreis met 1024 Shots. Wie mer sin künne, krije mer en ungefähr gleichförmige Verdeilu ng övver vier Bitstrings övver de Kontroll-Qubits.

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

plot_histogram(counts)

Indämm mer de Kontroll-Qubits messe, krije mer en aat-Bit-Phasenabschätzung vum $M_a$-Operator. Mer künne dise binäre Dorstelloung en dezimal ömwandele, öm de jemessene Phase ze finge. Wie mer em ove Histogramm sin künne, wore vier verschiddene Bitstrings jemesse, un jedde vun ihne entspreecht enem Phasewert wie folgich.

# 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

Denk dran, dat jede jemessene Phase $\theta = k / r$ entspreecht, wo $k$ gleichförmich zofällisch us $\{0, 1, \dots, r-1 \}$ jesampelt weed. Doher künne mer dä Kettenbrochalgorithmus benotze, öm ze versöke, $k$ un de Ordinung $r$ ze finge. Python hät dise Funktionalität enjebaaut. Mer künne et fractions-Modul benotze, öm en Float en en Fraction-Objekt ömzewandele, för Beispell:

Fraction(0.666)

Fraction(5998794703657501, 9007199254740992)

Weil dat Brööch erjevt, de et Resultat jenau zoröckjävve (en däm Fall 0.6660000...), kann dat knotzije Resultate wie dat ove jävve. Mer künne de .limit_denominator()-Method e benotze, öm dä Broch ze krije, dä unserem Float am nächste kütt, met enem Nenner ongerm bestemmte Wert:

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

Fraction(2, 3)

Dat es vell schüner. De Ordinung (r) möss kleiner wie N sin, also setze mer dä maximale Nenner op 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

Mer künne sin, dat zwei vun de jemessene Eigenwerte uns et korräkte Resultat jeliffert han: $r=4$, un mer künne sin, dat Shor singe Algorithmus för Ordinungsfingung en Chance hät ze versage. Dise schlä chte Resultate kumme dodrövver, dat $k = 0$, oder weil $k$ un $r$ nit teilerfremd sin - un statt $r$ krije mer ene Faktor vun $r$. De einfachste Lösung dodröm es einfach, et Experiment ze widderhuhle, bes mer e zufriedestellend Resultat för $r$ krije. Bes jetz han mer et Ordinungsfingungsproblem för $N=15$ met $a=2$ met enem Phasenabschätzungsschaltkreis op enem Simulator implementiert. Dä letzte Schrett vun Shor singem Algorithmus weed sin, et Ordinungsfingungsproblem zo däm ganzzahlige Faktorisierungsproblem ze setze. Dise letzte Deel vum Algorithmus es rein klassisch un kann op enem klassische Computer jelöst wäde, nohdem de Phasemessonge vun enem Quantecomputer usjavve wore sin. Doher verschievve mer dä letzte Deel vum Algorithmus, bes mer demonstriert han, wie mer dä Ordinungsfingungsschaltkreis op echter Hardware laache künne.

Hardware-Usirührunge

Jetz künne mer dä Ordinungsfingungsschaltkreis laache, dä mer vörher för ibm_marrakesh transpiliert han. He wende mer uns aan Dynamisch Entkoppelung (DD) för Fehleröggerdrückung un Gate-Twirling för Fehlermildierungszwecke. DD involviert et Aawende vun Reihfolge vun präzis zeitlich jevastjelegte Kontrollpulse op en Quantejät, wat effektiv onerwünschte Ömjevungsinteraktione un Dekohärenz mittelt. Gate-Twirling, op dr andere Sigg, randomisiert speziell Quantegates, öm kohärente Fehler en Pauli-Fehler ömzewandele, de linear, nit quadratisch wachse. Beide Technike wäde off kombiniert, öm de Kohärenz un Fidel ität vun Quanteberechnunge ze 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))

Wie mer sin künne, han mer de selvige Bitstrings met dä hüchste Zahle usjavve krääje. Weil Quantehardware Rausche hät, jitt et e besje Lekkage zu andere Bitstrings, de mer statistisch filtriere künne.

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

Schrett 4: Nohbeärbeide un Resultat em jewünschte klassische Format usjavve

Ganzzahlige Faktorisierung

Bes jetz han mer diskutiert, wie mer et Ordinungsfingungsproblem met enem Phasenabschätzungsschaltkreis implementiere künne. Jetz verbenge mer et Ordinungsfingungsproblem met dr ganzzahlige Faktorisierung, wat Shor singe Algorithmus komplettiert. Pass op, dat dise Deel vum Algorithmus klassisch es. Mer demonstriere dat jetz met unserem Beispell vun $N = 15$ un $a = 2$. Denk dran, dat de Phase, de mer jemesse han, $k / r$ es, wo $a^r \; (\textrm{mod} \; N) = 1$ un $k$ en zofällije Ganzzahl zweschent $0$ un $r - 1$ es. Us diser Gleichung han mer $(a^r - 1) \; (\textrm{mod} \; N) = 0,$ wat bedeut, $N$ möss $a^r-1$ deile. Wann $r$ och jeräät es, dann künne mer schrieve $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$ Wann $r$ nit jeräät es, künne mer nit wigger jon un mösse et nochens met enem andere Wert för $a$ versöke; sonst jitt et en huhe Wahrscheinlichkeit, dat dä jrüßte jemeinsame Deiler vun $N$ un entweder $a^{r/2}-1$ oder $a^{r/2}+1$ ene echte Faktor vun $N$ es.

Weil e paar Usirührunge vum Algorithmus statistisch versage wäde, wäde mer dise Algorithmus widderhuhle, bes mindestens eine Faktor vun $N$ jefunge es. De Zell unge widderhuult dä Algorithmus, bes mindestens eine Faktor vun $N=15$ jefunge es. Mer wäde de Resultate vun dr Hardware-Usiröhrung ove benotze, öm de Phase un dä entsprechende Faktor en jeder Iteration affenschä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

Verwandte Ärbet

En däm Avschnett diskutiere mer ander Meilensteinärbet, dat Shor singe Algorithmus op echter Hardware demonstriert hät.

Dat seminal e Wärk [3] vun IBM® hät Shor singe Algorithmus för et erste Mol demonstriert, indämm et de Zahl 15 en sing Primfaktore 3 un 5 faktorisiert hät met enem sibbe-Qubit Nuclear Magnetic Resonance (NMR) Quantecomputer. En ander Experiment [4] hät de 15 met photonische Qubits faktorisiert. Indämm de Forsche e einzich Qubit mehrmals widderbenotzt han un et Wärkregister en hüher-dimensionale Zustäng kodiert han, han se de erforderliche Anzahl Qubits op en Dridde vun däm em Standardprotokoll reduziert, met enem zwei-Photon-kompilierten Algorithmus. E signifikantes Paper en dr Demonstration vun Shor singem Algorithmus es [5], dat Kitaevs iterative Phasenabschätzungstechnik [8] benotzt, öm de Qubit-Aaforderung vum Algorithmus ze reduziere. Autore han sibbe Kontroll-Qubits un vier Cache-Qubits benotzt, zessamme met dr Implementierung vun modulare Multipliziere. Dise Implementierung erfordert ävver Messunge während däm Durchlauf met Feed-Forward-Operatore un Qubit-Widderbenotzung met Reset-Operatore. Dise Demonstration woch op enem Ion-Trap-Quantecomputer jedonn.

Mih rezente Ärbet [6] hät sisch drop konzentriert, 15, 21 un 35 op IBM Quantum® Hardware ze faktorisiere. Ähnlisch wie vörherisch Ärbet han de Forsche en kompilierte Version vum Algorithmus benotzt, de en semi-klassische Quante-Fourier-Transformation jewäät hät, wie vum Kitaev vörjeschlaahn, öm de Anzahl vun physische Qubits un Gates ze minimiere. E allerrecentes Wärk [7] hät och en Proof-of-Concept-Demonstration för et Faktorisiere vun dr ganzzahligen 21 dörchjeföhrt. Dise Demonstration hät och de Notzung vun ener kompilierten Version vun dr Quante-Phasenabschätzungsroutine involved un hät op dr vörherijje Demonstration vun [4] opjebaaut. Autore sin övver dat Wärk erusjejonge, indämm se en Konfiguration vun ungefähr Toffoli-Gates met verblievene Phasverschiebonge benotzt han. Dä Algorithmus woch op IBM-Quanteprozessore met bloß fünf Qubits implementiert, un de Awesenheit vun Verschrängung zweschent de Kontroll- un Register-Qubits woch erfolgrisch verifiziert.

Skalierung vum Algorithmus

Mer passe op, dat RSA-Verschlösselung typisch Schlösselgrößen en dr Ordinung vun 2048 bes 4096 Bits involviert. Wann mer versöke, en 2048-Bit-Zahl met Shor singem Algorithmus ze faktorisiere, resultiert dat en enem Quanteschaltkreis met Millione vun Qubits, inklusive Fehlerkorrektur-Overhead un ener Schaltkreisdiefe en dr Ordinung vun ener Milliard, wat övver de Jrenze vun aktuelle Quantehardware erus jeiht. Doher weed Shor singe Algorithmus entweder optimierte Schaltkreiskonstruktionsmethod e oder robuste Quantefehlerkorrektur bruche, öm praktisch användbar för et Breche vun moderne kryptografische Systeme ze sin. Mer verwise dich op [9] för en detailliertere Diskussion övver Ressourceschätzung för Shor singe Algorithmus.

Ufjaav

Jratulatio för et Avschließe vum Tutorial! Jetz es en jode Zick, ding Verständnis ze teste. Künns de versöke, dä Schaltkreis för et Faktorisiere vun 21 ze konstruiere? De kanns en $a$ vun dingem eije Wahl jreife. Du möss övver de Bit-Jenauigkeit vum Algorithmus entscheide, öm de Anzahl Qubits ze wähle, un du möss de modulare Potenzierungsoperatore $M_a$ entwerfe. Mer ermutige dich, dat sälvs uszerobiere, un dann övver de Methodologie ze lässe, de en Fig. 9 vun [6] un Fig. 2 vun [7] jezeicht wäde.

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

    # Your code here
    pass

Referenze

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.