Shor sien Algorithmus

Bruuk-Inschattung: Dree Sekunnen op'n Eagle r3-Prozessor (ACHTUNG: Dit is bloots 'ne Inschattung. Dien Looptied kunn annoers sien.)

Shor sien Algorithmus, vun Peter Shor in't Johr 1994 ontwikkelt, is'n bahnbrekend Quantenalgorithmus för't Faktoriseren vun Tahlen in polynomialer Tied. Sien Bedüden liggt dor in, dat he grote Tahlen exponentiell gauer faktoriseren kann as all bekannten klassischen Algorithmen, un dormit de Sekerheit vun wiet verbreiten Kryptosystemen as RSA bedroht, de dorup beruhrt, dat't swoor is, grote Tahlen to faktoriseren. Indeem he dit Problem op'n stark noog Quantencomputer effizient löst, kunn Shor sien Algorithmus Fäller as Kryptografie, Cybersicherheit un Bereken-Mathematik revolutioneern, un dormit de transformative Kraft vun de Quantenberekening ünnerstrieken.

Dit Tutorial wiest Shor sien Algorithmus, indeem wi de 15 op'n Quantencomputer faktoriseert.

Toeerst defini eert wi dat Ordnungsfinn-Problem un konstrueert passliche Schaltkreisen ut dat Quantenpha sen-Inschattungsprotokoll. As nächstes laat wi de Ordnungsfinn-Schaltkreisen op echte Hardware mit de körtesten Schaltkreisen, de wi transpileren künnt. De leste Afsnitt kompleteert Shor sien Algorithmus, indeem wi dat Ordnungsfinn-Problem mit de heeltahlige Faktoriseerung verbinnt.

Wi slüüt dat Tutorial af mit'ne Diskuschoon över anner Demonstratschonen vun Shor sien Algorithmus op echte Hardware, de sik sowohl op algemene Implementatschonen as ok op de konzentr eert, de op't Faktoriseren vun spezielle Tahlen as 15 un 21 tosneden sünd. Achtung: Dit Tutorial konzentreert sik mehr op de Implementatschoon un Demonstratschoon vun de Schaltkreisen för Shor sien Algorithmus. För'n deeperen pädagogischen Ressource över dat Material, kiek mol in de Fundamentals of quantum algorithms Kurs vun Dr. John Watrous, un de Papers in de Referenzen-Afsnitt.

Vöruttset tungen

Bevör du mit dit Tutorial anfangst, kiek to, dat du dat Folgende installeert hest:

• Qiskit SDK v2.0 oder neeger, mit Visualiseerung Ünnerstüttung
• Qiskit Runtime v0.40 oder neeger (pip install qiskit-ibm-runtime)

Opsetten

# 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

Schritt 1: Klassische Ingaben op'n Quantenproblem afbilden

Achtergrund

Shor sien Algorithmus för heeltahlige Faktoriseerung nützt'n Twüschenproblem, dat as Ordnungsfinn-Problem bekannt is. In dissen Afsnitt wiesen wi, wo wi dat Ordnungsfinn-Problem mit Quantenphasen-Inschattung lösen doot.

Phasen-Inschattungsproblem

Bi't Phasen-Inschattungsproblem kriegt wi'n Quantentostand $\ket{\psi}$ vun $n$ Qubits, tohoop mit'n unitären Quantenschaltkreis, de op $n$ Qubits warkt. Wi warrt tosakkt, dat $\ket{\psi}$ 'n Eigenvektor vun de unitäre Matrix $U$ is, de de Warkung vun Schaltkreis beschrifft, un us Teel is't, de Eigenwert $\lambda = e^{2 \pi i \theta}$ to berekenen oder intrüden, to den $\ket{\psi}$ höört. Mit anner Wöör, de Schaltkreis schall'ne Annäherung an de Tahl $\theta \in [0, 1)$ utgeben, de $U \ket{\psi}= e^{2 \pi i \theta} \ket{\psi}$ erfüllt. Dat Teel vun Phasen-Inschattungsschaltkreis is't, $\theta$ in $m$ Bits intrüden. Mathematisch spraken willt wi $y$ finnen, so dat $\theta \approx y / 2^m$, wo $y \in {0, 1, 2, \dots, 2^{m-1}}$. Dat folgende Bild wiest de Quantenschaltkreis, de $y$ in $m$ Bits inschattet, indeem he'ne Meeten op $m$ Qubits maakt. In Schaltkreis boven warrt de böversten $m$ Qubits in de $\ket{0^m}$-Tostand initialiseer t, un de ünnersten $n$ Qubits in $\ket{\psi}$, den tosakkt warrt, 'n Eigenvektor vun $U$ to sien. Dat eerste Ingredient in Phasen-Inschattungsschaltkreis sünd de kontrolleerten unitären Operatoren, de dofür verantwoordlik sünd, 'n Phasen-Kickback op ehr passenden Kontroll-Qubit dörtofören. Disse kontrolleerten Unitären warrt potentseert na de Positschoon vun Kontroll-Qubit, vun dat minst signifikante Bit bet to dat meest signifikante Bit. Wieldat $\ket{\psi}$ 'n Eigenvektor vun $U$ is, blifft de Tostand vun de ünnersten $n$ Qubits vun disse Operatschoon unrührt, aver de Phaseninformatschoon vun Eigenwert breet sik na de böversten $m$ Qubits ut. Dat stellt sik rut, dat na de Phasen-Kickback över kontrolleerte Unitären all möglichen Tostänn vun de böversten $m$ Qubits orthonormal to nanner sünd för elken Eigenvektor $\ket{\psi}$ vun dat unitäre $U$. Dorüm sünd disse Tostänn perfekt ünnersche edbaar, un wi künnt de Basis, de se billt, torüch in de Reken-Basis dreihen, üm'ne Meeten to maken. 'Ne mathematische Analyse wiest, dat disse Rotaschoons-Matrix de inverse Quantenfourier-Transformatschoon (QFT) in $2^m$-dimensionalen Hilbert-Ruum entspricht. De Intuitschoon dor achter is, dat de periodische Struktur vun de modularen Potenzerungs-Operatoren in Quantentostand kodeert is, un de QFT wandelt disse Periodizität in meetbare Spieten in Frequenzberik üm.

För'n deeper Verstahn dorvun, worüm de QFT-Schaltkreis in Shor sien Algorithmus bruukt warrt, verwiest wi de Leser op de Fundamentals of quantum algorithms Kurs. Wi sünd nu proot, de Phasen-Inschattungsschaltkreis för Ordnungsfinn to bruken.

Ordnungsfinn-Problem

Üm dat Ordnungsfinn-Problem to definiern, fangt wi mit'n paar tahlentheoretische Konzepten an. Toeerst definiern wi för elke positieve Heeltahl $N$ de Meng $\mathbb{Z}_N$ as $\mathbb{Z}_N = \{0, 1, 2, \dots, N-1\}.$ All arithmetischen Operatschonen in $\mathbb{Z}_N$ warrt modulo $N$ dörtofö hrt. Besünners sünd all Elementen $a \in \mathbb{Z}_n$, de teelerfree mit $N$ sünd, speziell un billt $\mathbb{Z}^*_N$ as $\mathbb{Z}^*_N = \{ a \in \mathbb{Z}_N : \mathrm{gcd}(a, N)=1 \}.$ För'n Element $a \in \mathbb{Z}^*_N$ warrt de lüttste positieve Heeltahl $r$ so, dat $a^r \equiv 1 \; (\mathrm{mod} \; N)$ as de Ordnung vun $a$ modulo $N$ defineert. As wi later sehn warrt, lett us dat Finnen vun de Ordnung vun'n $a \in \mathbb{Z}^*_N$ $N$ faktoriseren. Üm de Ordnungsfinn-Schaltkreis ut de Phasen-Inschattungsschaltkreis to konstruern, bruukt wi twee Övverlegungen. Toeerst mööt wi dat unitäre $U$ definiern, dat us dat erlövt, de Ordnung $r$ to finnen, un tweedens mööt wi'n Eigenvektor $\ket{\psi}$ vun $U$ definiern, üm de Anfangstostand vun Phasen-Inschattungsschaltkreis vörtobereien.

Üm dat Ordnungsfinn-Problem mit de Phasen-Inschattung to verbinnen, bekiekt wi de Operatschoon, de op'n System defineert is, wodenn klassische Tostänn $\mathbb{Z}_N$ entsprekt, wo wi mit'n faste Element $a \in \mathbb{Z}^*_N$ multiplizeert. Besünners definiern wi dissen Multiplikatschoons-Operator $M_a$ so, dat $M_a \ket{x} = \ket{ax \; (\mathrm{mod} \; N)}$ för elke $x \in \mathbb{Z}_N$. Kiek to, dat't implizit is, dat wi dat Produkt modulo $N$ binnen vun Ket op de rechte Sied vun de Gliekung neemt. 'Ne mathematische Analyse wiest, dat $M_a$ 'n unitärer Operator is. Wiederdeen stellt sik rut, dat $M_a$ Eigenvektor- un Eigenweertpaaren hett, de us erlövt, de Ordnung $r$ vun $a$ mit dat Phasen-Inschattungsproblem to verbinnen. Speziell, för elke Wahl vun $j \in \{0, \dots, r-1\}$ hebbt wi, dat $\ket{\psi_j} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \omega^{-jk}_{r} \ket{a^k}$ 'n Eigenvektor vun $M_a$ is, wodenn passenden Eigenwert $\omega^{j}_{r}$ is, wo $\omega^{j}_{r} = e^{2 \pi i \frac{j}{r}}.$ Dörch Beövachtung seht wi, dat'n bequeem Eigenvektor/Eigenweer t-Paar de Tostand $\ket{\psi_1}$ mit $\omega^{1}_{r} = e^{2 \pi i \frac{1}{r}}$ is. Dorüm, wenn wi de Eigenvektor $\ket{\psi_1}$ finnen künnt, künnt wi de Phase $\theta=1/r$ mit usen Quantenschaltkreis inschatten un dormit'ne Inschattung vun de Ordnung $r$ kriegen. Aver dat is nich eenfach, un wi mööt'ne Alternative bekieken.

Laat us övverleggen, wat de Schaltkreis rutgeven dee, wenn wi de Rekentostand $\ket{1}$ as Anfangstostand vörbereit. Dat is keen Eigentostand vun $M_a$, aver dat is de gliekeförmige Övverlagrung vun de boven beschrevenen Eigentostänn. Mit anner Wöör, de folgende Betreken gellt. $\ket{1} = \frac{1}{\sqrt{r}} \sum^{r-1}_{k=0} \ket{\psi_k}$ De Bedüden vun de boven Gliekung is, dat wenn wi de Anfangstostand op $\ket{1}$ sett, kriegt wi jüst dat sülvige Meetresultaat, as wenn wi $k \in \{ 0, \dots, r-1\}$ gliekeförmig tofällig wählt harrn un $\ket{\psi_k}$ as Eigenvektor in Phasen-Inschattungsschaltkreis bruukt harrn. Mit anner Wöör, 'ne Meeten vun de böversten $m$ Qubits gifft'ne Annäherung $y / 2^m$ an de Weert $k / r$, wo $k \in \{ 0, \dots, r-1\}$ gliekeförmig tofällig wählt warrt. Dat erlövt us, $r$ mit'n hogen Grad vun Sekerheit na mehrere unafhängige Dörgäng to lehrn, wat us Teel weer.

Modulare Potenzerungs-Operatoren

Bet nu hebbt wi dat Phasen-Inschattungsproblem mit dat Ordnungsfinn-Problem verbunnen, indeem wi $U = M_a$ un $\ket{\psi} = \ket{1}$ in usen Quantenschaltkreis defineert hebbt. Dorüm is dat leste verblevene Ingredient, 'n effiziente Weg to finnen, üm modulare Exponenten vun $M_a$ as $M_a^k$ för $k = 1, 2, 4, \dots, 2^{m-1}$ to definiern. Üm disse Berekening dörtofören, findt wi, dat för elke Potenz $k$, de wi wählt, künnt wi'n Schaltkreis för $M_a^k$ nich maaken, indeem wi $k$ Mal de Schaltkreis för $M_a$ itereart, sünnern indeem wi $b = a^k \; \mathrm{mod} \; N$ bereekent un denn de Schaltkreis för $M_b$ bruukt. Wieldat wi bloots de Potenzen bruukt, de sülvst Potenzen vun 2 sünd, künnt wi dat klassisch effizient maken, indeem wi iteratives Quadrern bruukt.

Schritt 2: Problem för Quantenhardware-Utföhrung optimern

Speziell Bispill mit $N = 15$ un $a=2$

Wi künnt hier'n Ogenblick pausern, üm'n speziell Bispill to diskuteern un de Ordnungsfinn-Schaltkreis för $N=15$ to konstruern. Kiek to, dat mögliche nich-triviale $a \in \mathbb{Z}_N^*$ för $N=15$ sünd $a \in \{2, 4, 7, 8, 11, 13, 14 \}$. För dit Bispill wählt wi $a=2$. Wi warrt de $M_2$-Operator un de modularen Potenzerungs-Operatoren $M_2^k$ konstruern. De Warkung vun $M_2$ op de Reken-Basistostänn is as 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}$ Dörch Beövachtung künnt wi sehn, dat de Basistostänn dörnannersmieten warrt, also hebbt wi'ne Permutatschoons-Matrix. Wi künnt disse Operatschoon op veer Qubits mit Swap-Gates konstruern. Ünnen konstruern wi de $M_2$ un de kontrolleerten-$M_2$ Operatoren.

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 mehr as twee Qubits warkt, warrt wieder in twee-Qubit-Gates toleggd.

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

Nu mööt wi de modularen Potenzerungs-Operatoren konstruern. Üm noog Präzischoon in de Phasen-Inschattung to kriegen, warrt wi acht Qubits för de Inschattungs-Meeten bruken. Dorüm mööt wi $M_b$ mit $b = a^{2^k} \; (\mathrm{mod} \; N)$ för elke $k = 0, 1, \dots, 7$ konstruern.

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]

As wi ut de List vun $b$-Weerten sehn künnt, bruukt wi neven $M_2$, dat wi vördem konstruert hebbt, ok $M_4$ un $M_1$. Kiek to, dat $M_1$ trivial op de Reken-Basistostänn warkt, also is't eenfach de Identitäts-Operator.

$M_4$ warkt op de Reken-Basistostänn as 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}$

Dorüm kann disse Permutatschoon mit de folgende Swap-Operatschoon konstruert warrn.

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 mehr as twee Qubits warkt, warrt wieder in twee-Qubit-Gates toleggd.

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

Wi hebbt sehn, dat $M_b$-Operatoren för'n geven $b \in \mathbb{Z}^*_N$ Permutatschoons-Operatoren sünd. Wegen de relativ lütte Gröött vun Permutatschoons-Problem, dat wi hier hebbt, wieldat $N=15$ bloots veer Qubits bruukt, künnt wi disse Operatschonen direkt mit SWAP-Gates dörch Inspektschoon syntheseern. Im Algemeinen kunn dat nich skaleerbar sien. Stattdessen künnt wi de Permutatschoons-Matrix explizit konstruern un Qiskits UnitaryGate-Klass un Transpileer-Methoden bruken, üm disse Permutatschoons-Matrix to syntheseern. Aver dat kann to signifikant deeper Schaltkreisen föhrn. 'N Bispill 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})

Laat us disse Tahlen mit de kompileerten Schaltkreis-Deepde vun use manuelle Implementatschoon vun $M_2$-Gate verglieken.

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

As wi sehn künnt, hett de Permutatschoons-Matrix-Ansat to'n signifikant depen Schaltkreis föhrt, selvst för'n enk elen $M_2$-Gate, verglieken mit use manuelle Implementatschoon. Dorüm warrt wi mit use vörige Implementatschoon vun de $M_b$-Operatschonen wiedermaken. Nu sünd wi proot, de vollständige Ordnungsfinn-Schaltkreis mit use vördem defineerten kontrolleerten modularen Potenzerungs-Operatoren to konstruern. In folgende Code importeert wi ok de QFT-Schaltkreis ut de Qiskit Circuit-Bibliotheek, de Hadamard-Gates op elke Qubit bruukt, 'ne Reeg vun kontrolleerten U1- (oder Z-, na de Phase) Gates un'ne Laag 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)

Kiek to, dat wi de kontrolleerten modularen Potenzerungs-Operatschonen vun de verblevenen Kontroll-Qubits weglaten hebbt, wieldat $M_1$ de Identitäts-Operator is. Kiek to, dat wi later in dit Tutorial dissen Schaltkreis op de ibm_marrakesh-Backend laaten warrt. Doför transpileert wi de Schaltkreis för dissen speziellen Backend un berichtet de Schaltkreis-Deepde un Gate-Tahlen.

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

Schritt 3: Mit Qiskit-Primitiven utföhrn

Toeerst diskuteert wi, wat wi theoretisch rutkriegen deen, wenn wi dissen Schaltkreis op'n idealen Simulator laaten deen. Ünnen hebbt wi'n Set vun Simulatschoons-Resultaten vun boven Schaltkreis mit 1024 Shots. As wi sehn künnt, kriegt wi'ne ungefähr gliekeförmige Verdeelung över veer Bitstrings över de Kontroll-Qubits.

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

plot_histogram(counts)

Indeem wi de Kontroll-Qubits meet, kriegt wi'ne acht-Bit-Phasen-Inschattung vun $M_a$-Operator. Wi künnt disse binäre Dorstellen in dezimal ümwanneln, üm de meetene Phase to finnen. As wi in boven Histogramm sehn künnt, sünd veer verscheden Bitstrings meeten, un elke vun ehr entspricht'n Phasen-Weert as 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
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 elke meetene Phase $\theta = k / r$ entspricht, wo $k$ gliekeförmig tofällig ut $\{0, 1, \dots, r-1 \}$ sampelt warrt. Dorüm künnt wi de Kettenbrock-Algorithmus bruken, üm to versöken, $k$ un de Ordnung $r$ to finnen. Python hett disse Funktschoon inbuut. Wi künnt dat fractions-Modul bruken, üm'n Float in'n Fraction-Objekt ümtowannel n, to'n Bispill:

Fraction(0.666)

Fraction(5998794703657501, 9007199254740992)

Wieldat dat Bröök gifft, de dat Resultaat jüst torüchgifft (in dissen Fall 0.6660000...), kann dat knotige Resultaten as dat boven geven. Wi künnt de .limit_denominator()-Methode bruken, üm de Brock to kriegen, de usen Float an nächsten liggt, mit'n Nenner ünner'n bestimmten Weert:

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

Fraction(2, 3)

Dat is veel schöner. De Ordnung (r) mutt lütter as N sien, also sett wi de 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

Wi künnt sehn, dat twee vun de meetenen Eigenweerten us dat korrekte Resultaat levern hebbt: $r=4$, un wi künnt sehn, dat Shor sien Algorithmus för Ordnungsfinn'ne Chance hett to missglücken. Disse slächten Resultaten koomt dorut, dat $k = 0$, oder wieldat $k$ un $r$ nich teelerfree sünd - un statt $r$ kriegt wi'n Faktor vun $r$. De eenfachste Lösung dorvun is eenfach, dat Experiment to wedderholen, bet wi'n tofredenstellend Resultaat för $r$ kriegt. Bet nu hebbt wi dat Ordnungsfinn-Problem för $N=15$ mit $a=2$ mit'n Phasen-Inschattungsschaltkreis op'n Simulator implementeert. De leste Schritt vun Shor sien Algorithmus warrt sien, dat Ordnungsfinn-Problem to dat heeltahlige Faktoriseer-Problem to verknüppen. Disse leste Deel vun Algorithmus is rein klassisch un kann op'n klassischen Computer löst warrn, nahdem de Phasen-Meetungen vun'n Quantencomputer rutgeven sünd. Dorüm verschuuft wi de leste Deel vun Algorithmus, bet wi demonstreert hebbt, wo wi de Ordnungsfinn-Schaltkreis op echte Hardware laaten künnt.

Hardware-Utföhrungen

Nu künnt wi de Ordnungsfinn-Schaltkreis laaten, de wi vördem för ibm_marrakesh transpileert hebbt. Hier wennt wi us an Dynamische Entkopplung (DD) för Fehler-Ünnerdrückung un Gate-Twirling för Fehler-Minnern-Twecken. DD involviert dat Anwennen vun Reegfolgen vun präzis tiedelik fastleggten Kontroll-Pulsen op'n Quantenapparat, wat effektiv unerwünschte Ümgevungs-Interaktschonen un Dekohärenz middelt. Gate-Twirling, op de anner Sied, randomi seert speziell Quantengates, üm kohärente Fehler in Pauli-Fehler ümtowanneln, de linear, nich quadratisch, wussen doot. Beide Technieken warrt oft kombineert, üm de Kohärenz un Treue vun Quantenberekeningen to verbetern.

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

As wi sehn künnt, hebbt wi de sülvigen Bitstrings mit de högsten Tahlen rutkregen. Wieldat Quantenhardware Ruschen hett, gifft dat'n beten Leckage to anner Bitstrings, de wi statistisch filtern künnt.

# 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: Nabearbeiden un Resultaat in wünschten klassischen Formaat rutgeven

Heeltahlige Faktoriseerung

Bet nu hebbt wi diskuteert, wo wi dat Ordnungsfinn-Problem mit'n Phasen-Inschattungsschaltkreis implementeern künnt. Nu verknüppt wi dat Ordnungsfinn-Problem mit de heeltahlige Faktoriseerung, wat Shor sien Algorithmus kompleteert. Kiek to, dat disse Deel vun Algorithmus klassisch is. Wi demonstreert dat nu mit us Bispill vun $N = 15$ un $a = 2$. Denk dran, dat de Phase, de wi meeten hebbt, $k / r$ is, wo $a^r \; (\textrm{mod} \; N) = 1$ un $k$ 'ne tofällige Heeltahl twüschen $0$ un $r - 1$ is. Ut disse Gliekung hebbt wi $(a^r - 1) \; (\textrm{mod} \; N) = 0,$ wat bedüdt, $N$ mutt $a^r-1$ deeln. Wenn $r$ ok geraad is, denn künnt wi schrieven $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$ Wenn $r$ nich geraad is, künnt wi nich wieder gahn un mööt dat wedder mit'n annern Weert för $a$ versöken; süs gifft dat'ne hoge Wahrschienlichkeit, dat de gröteste gemeensame Deeler vun $N$ un entweder $a^{r/2}-1$ oder $a^{r/2}+1$ 'n echten Faktor vun $N$ is.

Wieldat'n paar Utföhrungen vun Algorithmus statistisch missglücken warrt, warrt wi dissen Algorithmus wedderholen, bet minnstens een Faktor vun $N$ funnen is. De Zell ünnen wedderhoolt de Algorithmus, bet minnstens een Faktor vun $N=15$ funnen is. Wi warrt de Resultaten vun de Hardware-Utföhrung boven bruken, üm de Phase un de passenden Faktor in elke Iteratschoon intorüden.

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

Diskuschoon

Verwante Arbeit

In dissen Afsnitt diskuteert wi anner Meilensteen-Arbeiten, de Shor sien Algorithmus op echte Hardware demonstreert hebbt.

Dat bahnbrekende Wark [3] vun IBM® hett Shor sien Algorithmus to't eerste Mal demonstreert, indeem dat de Tahl 15 in ehr Primfaktoren 3 un 5 faktoriseert hett mit'n söven-Qubit Nuclear Magnetic Resonance (NMR) Quantencomputer. 'N anner Experiment [4] hett de 15 mit photonische Qubits faktoriseert. Indeem de Forschers een enkel Qubit mehrmals wedderbruukt hebbt un dat Wark-Register in höger-dimensionale Tostänn kodeert hebbt, hebbt se de nödige Antahl Qubits op een Drittel vun dat in Standard-Protokoll reduz eert, mit'n twee-Photon-kompileerten Algorithmus. 'N signifikant Paper in de Demonstratschoon vun Shor sien Algorithmus is [5], dat Kitaevs iterative Phasen-Inschattungs-Technik [8] bruukt, üm de Qubit-Anförderung vun Algorithmus to reduzern. Autoren hebbt söven Kontroll-Qubits un veer Cache-Qubits bruukt, tohoop mit de Implementatschoon vun modulare Multiplizierers. Disse Implementatschoon erfordert aver Meetungen binnen dat Dörlopen mit Feed-Forward-Operatschonen un Qubit-Wedderbruuk mit Reset-Operatschonen. Disse Demonstratschoon weer op'n Ion-Trap-Quantencomputer daan.

Neegere Arbeit [6] hett sik dorop konzentr eert, 15, 21 un 35 op IBM Quantum® Hardware to faktorisern. Ähnlik as vörige Arbeit hebbt de Forschers'ne kompileerte Version vun Algorithmus bruukt, de'ne semi-klassische Quantenfourier-Transformatschoon, as vun Kitaev vörschlagen, bruukt hett, üm de Antahl vun physische Qubits un Gates to minimern. 'N allerneegstes Wark [7] hett ok'n Proof-of-Concept-Demonstratschoon för dat Faktorisern vun de heeltahlige 21 dörtofö hrt. Disse Demonstratschoon hett ok de Bruuk vun'ne kompileerte Version vun de Quantenphasen-Inschattungs-Routine involveert un hett op de vörige Demonstratschoon vun [4] opbuut. Autoren sünd över dat Wark rutgahn, indeem se'ne Konfigu ratschoon vun ungefähr Toffoli-Gates mit restliche Phasen-Verschuven bruukt hebbt. De Algorithmus weer op IBM-Quantenprozessoren mit bloots föfv Qubits implementeert, un de Anwesenheit vun Verstrickung twüschen de Kontroll- un Register-Qubits weer erfolgriek verifizeert.

Skaleerung vun Algorithmus

Wi markt, dat RSA-Verschlötung typisch Slötel-Gröötten in de Ordenung vun 2048 bet 4096 Bits involveert. Wenn wi versökt, 'ne 2048-Bit-Tahl mit Shor sien Algorithmus to faktorisern, resulteert dat in'n Quantenschaltkreis mit Millionen vun Qubits, inklusive Fehlerkorrektur-Overhead un'ne Schaltkreis-Deepde in de Ordenung vun'ne Milliard, wat över de Grenzen vun aktuelle Quantenhardware rutgeiht. Dorüm warrt Shor sien Algorithmus entweder optimeerde Schaltkreis-Konstruktschoons-Methoden oder robuste Quantenfehler-Korrektur bruken, üm praktisch bruukbar för dat Breken vun moderne kryptografische Systemen to sien. Wi verwiest di op [9] för'ne detailleertere Diskuschoon över Ressourcen-Inschattung för Shor sien Algorithmus.

Opgaav

Gratuleer för dat Afsluuten vun Tutorial! Nu is'ne gode Tied, dien Verstahn to testen. Kunnst du versöken, de Schaltkreis för dat Faktorisern vun 21 to konstruern? Du kannst'n $a$ vun diene egene Wahl utköhrn. Du muttst över de Bit-Genauigkeit vun Algorithmus entscheden, üm de Antahl Qubits to wähln, un du muttst de modularen Potenzerungs-Operatoren $M_a$ entwarpn. Wi muddigt di an, dat sülvst uttoprobern, un denn över de Methodologien to lesen, de in Fig. 9 vun [6] un Fig. 2 vun [7] wiest warrt.

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

    # Your code here
    pass

Referenzen

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.