{ "cells": [ { "cell_type": "markdown", "id": "e72c9e73-98e1-49ae-bc3c-511954eeb15c", "metadata": { "tags": [ "remove_cell" ] }, "source": [ "---\n", "title: \"Shor-Algorithmus\"\n", "description: \"Dieses Tutorial konzentriert sich darauf, Shors Algorithmus anhand der Faktorisierung von 15 auf einem Quantencomputer zu demonstrieren.\"\n", "---\n", "\n", "{/* cspell:ignore textrm */}\n", "\n", "\n", "\n", "# Shor-Algorithmus\n", "\n", "*Geschätzte Nutzungsdauer: Drei Sekunden auf einem Eagle r3 Prozessor (HINWEIS: Dies ist nur eine Schätzung. Ihre Laufzeit kann variieren.)*\n", "\n", "\n", "\n", "## Lernziele\n", "\n", "* Die mathematischen Grundlagen von Shors Algorithmus zur Faktorisierung von ganzen Zahlen\n", "* So führen Sie eine Beispielinstanz dieses Algorithmus auf Hardware aus\n", "\n", "\n", "\n", "## Voraussetzungen\n", "\n", "* [Grundlagen von Quantenalgorithmen](/learning/courses/fundamentals-of-quantum-algorithms).\n", "* [Phasenschätzung und Faktorisierung](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction). Einiges davon behandeln wir in diesem Tutorial.\n", "\n", "\n", "\n", "## Hintergrund\n", "\n", "[Der Shor-Algorithmus](https://epubs.siam.org/doi/abs/10.1137/S0036144598347011), der 1994 von Peter Shor entwickelt wurde, ist ein bahnbrechender Quantenalgorithmus zur Faktorisierung von ganzen Zahlen in polynominaler Zeit. Seine Bedeutung liegt darin, dass er große ganze Zahlen exponentiell schneller zerlegen kann als jeder bekannte klassische Algorithmus, was die Sicherheit weit verbreiteter kryptografischer Systeme wie RSA gefährdet, die auf der Schwierigkeit der Faktorisierung großer Zahlen beruhen. Durch die effiziente Lösung dieses Problems auf einem ausreichend leistungsfähigen Quantencomputer könnte Shors Algorithmus Bereiche wie Kryptografie, Cybersicherheit und angewandte Mathematik revolutionieren und damit die transformative Kraft der Quantencomputer unterstreichen.\n", "\n", "In diesem Tutorium geht es um die Demonstration des Shor-Algorithmus, indem 15 auf einem Quantencomputer faktorisiert wird.\n", "\n", "Zunächst definieren wir das Problem der Ordnungsfindung und konstruieren entsprechende Schaltungen aus dem Quantenphasenschätzungsprotokoll. Als Nächstes führen wir die Ordnungsfindungsschaltungen auf echter Hardware aus, wobei wir Schaltungen mit der kürzesten Tiefe verwenden, die wir übertragen können. Der letzte Abschnitt vervollständigt den Algorithmus von Shor, indem er das Problem der Ordnungsfindung mit der ganzzahligen Faktorisierung verbindet.\n", "\n", "Wir beenden das Tutorial mit einer Diskussion über andere Demonstrationen des Shor-Algorithmus auf realer Hardware, wobei wir uns sowohl auf allgemeine Implementierungen als auch auf solche konzentrieren, die auf die Faktorisierung bestimmter ganzer Zahlen wie 15 und 21 zugeschnitten sind.\n", "\n" ] }, { "cell_type": "markdown", "id": "22f3a6f3-0ba5-4826-a4f3-9dcc62f51c70", "metadata": {}, "source": [ "Hinweis: Dieses Tutorial konzentriert sich mehr auf die Implementierung und Demonstration der Schaltungen zum Shor-Algorithmus. Ausführliche Informationen zu diesem Thema finden Sie im Kurs [Grundlagen der Quantenalgorithmen](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction) von Dr. John Watrous und in den Unterlagen im Abschnitt [Referenzen](#references).\n", "\n" ] }, { "cell_type": "markdown", "id": "b41b8639-ff72-4cd5-8bd3-3c16c01bedc0", "metadata": {}, "source": [ "\n", "\n", "### Anforderungen\n", "\n", "Vergewissern Sie sich vor Beginn dieses Tutorials, dass Sie die folgenden Komponenten installiert haben:\n", "\n", "* Qiskit SDK v2.0 oder später, mit [Visual](/docs/api/qiskit/visualization) isierungsunterstützung\n", "* Qiskit Runtime v0.40 oder später (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "93dcb213-ddcd-4329-8bcb-7c61fa298ee5", "metadata": {}, "source": [ "\n", "\n", "### Einrichtung\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "0860914d-cf1f-4bee-907d-3c442cd92cc6", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import pandas as pd\n", "from fractions import Fraction\n", "from math import floor, gcd, log\n", "\n", "from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister\n", "from qiskit.circuit.library import QFT, UnitaryGate\n", "from qiskit.transpiler import CouplingMap, generate_preset_pass_manager\n", "from qiskit.visualization import plot_histogram\n", "\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler" ] }, { "cell_type": "markdown", "id": "a28eeaa5-2da0-4b6b-8877-547a86fbcd76", "metadata": {}, "source": [ "\n", "\n", "## Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen\n", "\n" ] }, { "cell_type": "markdown", "id": "c09ec908-51ba-4ea3-bc84-142e8f8002bf", "metadata": {}, "source": [ "Shors Algorithmus zur ganzzahligen Faktorisierung verwendet ein Zwischenproblem, das als *Ordnungsfindungsproblem* bekannt ist. In diesem Abschnitt wird gezeigt, wie das Problem der Auftragsfindung mit Hilfe der *Quantenphasenschätzung* gelöst werden kann.\n", "\n" ] }, { "cell_type": "markdown", "id": "e1aa8e70-a760-43ca-bcf2-def23d49ba36", "metadata": {}, "source": [ "\n", "\n", "### Phasenschätzungsproblem\n", "\n", "Beim Phasenschätzungsproblem erhalten wir einen Quantenzustand $\\ket{\\psi}$ mit $n$ Qubits sowie eine unitäre Quantenschaltung, die auf $n$ Qubits wirkt. Man hat uns versprochen, dass $\\ket{\\psi}$ ein Eigenvektor der Einheitsmatrix $U$ ist, die die Wirkung der Schaltung beschreibt, und unser Ziel ist es, den Eigenwert $\\lambda = e^{2 \\pi i \\theta}$, dem $\\ket{\\psi}$ entspricht, zu berechnen oder zu approximieren. Mit anderen Worten, die Schaltung sollte eine Annäherung an die Zahl $\\theta \\in [0, 1)$ ausgeben, die zufriedenstellend ist $U \\ket{\\psi}= e^{2 \\pi i \\theta} \\ket{\\psi}.$ Das Ziel der Phasenschätzungsschaltung ist die Annäherung an $\\theta$ in $m$ Bits. Mathematisch ausgedrückt, möchten wir $y$ so finden, dass $\\theta \\approx y / 2^m$, wobei $y \\in {0, 1, 2, \\dots, 2^{m-1}}$. Das folgende Bild zeigt die Quantenschaltung, die $y$ in $m$ Bits schätzt, indem sie eine Messung an $m$ Qubits durchführt.\n", "\n" ] }, { "cell_type": "markdown", "id": "7ae92a5f-55b4-4597-be58-fe47b450dc39", "metadata": {}, "source": [ "![Quanten-Phasenschätzungsschaltung](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/phase-estimation-procedure.svg)\n", "\n" ] }, { "cell_type": "markdown", "id": "c527ff28-8038-44fc-8d62-1c9dda2b600e", "metadata": {}, "source": [ "In der obigen Schaltung werden die oberen $m$ Qubits im Zustand $\\ket{0^m}$ und die unteren $n$ Qubits im Zustand $\\ket{\\psi}$ initiiert, der ein Eigenvektor von $U$ sein soll. Der erste Bestandteil der Phasenschätzungsschaltung sind die Controlled-Unitary-Operationen, die für die Durchführung eines *Phasenrückstoßes* zu ihrem entsprechenden Kontroll-Qubit verantwortlich sind. Diese kontrollierten Einheiten werden entsprechend der Position des Kontrollbits potenziert, vom niedrigstwertigen Bit bis zum höchstwertigen Bit. Da $\\ket{\\psi}$ ein Eigenvektor von $U$ ist, wird der Zustand der unteren $n$ Qubits durch diese Operation nicht beeinflusst, aber die Phaseninformation des Eigenwerts breitet sich auf die oberen $m$ Qubits aus.\n", "\n" ] }, { "cell_type": "markdown", "id": "40b4a6e3-6f46-4971-8054-4a7ae9dd535e", "metadata": {}, "source": [ "Es stellt sich heraus, dass nach der Phasenrückkopplungsoperation über kontrollierte Unitarien alle möglichen Zustände der oberen $m$ Qubits für jeden Eigenvektor $\\ket{\\psi}$ der Unitarie $U$ orthonormal zueinander sind. Daher sind diese Zustände perfekt unterscheidbar, und wir können die Basis, die sie bilden, zurück zur Berechnungsbasis drehen, um eine Messung durchzuführen. Eine mathematische Analyse zeigt, dass diese Rotationsmatrix der inversen Quanten-Fourier-Transformation (QFT) im $2^m$ -dimensionalen Hilbert-Raum entspricht. Die Intuition dahinter ist, dass die periodische Struktur der modularen Potenzierungsoperatoren im Quantenzustand kodiert ist und die QFT diese Periodizität in messbare Spitzen im Frequenzbereich umwandelt.\n", "\n", "Für ein tiefergehendes Verständnis, warum der QFT-Schaltkreis in Shors Algorithmus verwendet wird, verweisen wir den Leser auf den Kurs [Grundlagen der Quantenalgorithmen](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction).\n", "\n" ] }, { "cell_type": "markdown", "id": "acfa31d3-7980-42ad-b418-77a24d16513a", "metadata": {}, "source": [ "Wir sind nun bereit, die Phasenschätzungsschaltung für die Auftragsfindung zu verwenden.\n", "\n" ] }, { "cell_type": "markdown", "id": "535674d6-cc8a-45f5-9fc7-f5fd3053f4c4", "metadata": {}, "source": [ "\n", "\n", "### Problem bei der Bestellung\n", "\n", "Um das Problem der Ordnungsfindung zu definieren, beginnen wir mit einigen zahlentheoretischen Konzepten. Zunächst wird für eine beliebige positive ganze Zahl $N$ die Menge $\\mathbb{Z}_N$ definiert als $\\mathbb{Z}_N = \\{0, 1, 2, \\dots, N-1\\}.$ Alle arithmetischen Operationen in $\\mathbb{Z}_N$ werden modulo $N$ durchgeführt. Insbesondere sind alle Elemente $a \\in \\mathbb{Z}_n$, die mit $N$ koprim sind, speziell und bilden $\\mathbb{Z}^*_N$ als $\\mathbb{Z}^*_N = \\{ a \\in \\mathbb{Z}_N : \\mathrm{gcd}(a, N)=1 \\}.$ Für ein Element $a \\in \\mathbb{Z}^*_N$ ist die kleinste positive ganze Zahl $r$ so definiert, dass $a^r \\equiv 1 \\; (\\mathrm{mod} \\; N)$ als die *Ordnung* von $a$ modulo $N$ definiert ist. Wie wir später sehen werden, können wir durch die Bestimmung der Ordnung von $a \\in \\mathbb{Z}^*_N$ den Faktor $N$ bestimmen.\n", "\n" ] }, { "cell_type": "markdown", "id": "6de4cbed-6591-40da-a994-2ff139c9f064", "metadata": {}, "source": [ "Um die Schaltung zur Auftragsfindung aus der Schaltung zur Phasenschätzung zu konstruieren, sind zwei Überlegungen erforderlich. Erstens müssen wir die unitäre $U$ definieren, die es uns ermöglicht, die Ordnung $r$ zu finden, und zweitens müssen wir einen Eigenvektor $\\ket{\\psi}$ von $U$ definieren, um den Anfangszustand der Phasenschätzungsschaltung vorzubereiten.\n", "\n", "Um das Problem der Ordnungsfindung mit der Phasenabschätzung zu verbinden, betrachten wir die Operation, die für ein System definiert ist, dessen klassische Zustände $\\mathbb{Z}_N$ entsprechen, wobei wir mit einem festen Element $a \\in \\mathbb{Z}^*_N$ multiplizieren. Insbesondere definieren wir diesen Multiplikationsoperator $M_a$ so, dass $M_a \\ket{x} = \\ket{ax \\; (\\mathrm{mod} \\; N)}$ für jedes $x \\in \\mathbb{Z}_N$. Man beachte, dass es implizit ist, dass wir das Produkt modulo $N$ innerhalb des ket auf der rechten Seite der Gleichung nehmen. Eine mathematische Analyse zeigt, dass $M_a$ ein unitärer Operator ist. Außerdem stellt sich heraus, dass $M_a$ Eigenvektor- und Eigenwertpaare hat, die es uns ermöglichen, die Ordnung $r$ von $a$ mit dem Problem der Phasenschätzung zu verbinden. Konkret bedeutet dies, dass für jede Wahl von $j \\in \\{0, \\dots, r-1\\}$ $\\ket{\\psi_j} = \\frac{1}{\\sqrt{r}} \\sum^{r-1}_{k=0} \\omega^{-jk}_{r} \\ket{a^k}$ ein Eigenvektor von $M_a$ ist, dessen entsprechender Eigenwert $\\omega^{j}_{r}$ ist, wobei $\\omega^{j}_{r} = e^{2 \\pi i \\frac{j}{r}}.$\n", "\n" ] }, { "cell_type": "markdown", "id": "57942d8d-b2fc-4863-bfdd-f99aa941e0c0", "metadata": {}, "source": [ "Durch Beobachtung sehen wir, dass ein geeignetes Eigenvektor/Eigenwert-Paar der Zustand $\\ket{\\psi_1}$ mit $\\omega^{1}_{r} = e^{2 \\pi i \\frac{1}{r}}$ ist. Wenn wir also den Eigenvektor $\\ket{\\psi_1}$ finden könnten, könnten wir die Phase $\\theta=1/r$ mit unserer Quantenschaltung abschätzen und so eine Schätzung der Ordnung $r$ erhalten. Das ist jedoch nicht einfach, und wir müssen eine Alternative in Betracht ziehen.\n", "\n", "Betrachten wir, was die Schaltung ergeben würde, wenn wir den Berechnungszustand $\\ket{1}$ als Ausgangszustand vorbereiten. Dabei handelt es sich nicht um einen Eigenzustand von $M_a$, sondern um die gleichmäßige Überlagerung der oben beschriebenen Eigenzustände. Mit anderen Worten: Es gilt die folgende Beziehung. $\\ket{1} = \\frac{1}{\\sqrt{r}} \\sum^{r-1}_{k=0} \\ket{\\psi_k}$ Die obige Gleichung besagt, dass wir, wenn wir den Anfangszustand auf $\\ket{1}$ setzen, genau dasselbe Messergebnis erhalten, als wenn wir $k \\in \\{ 0, \\dots, r-1\\}$ zufällig gewählt und $\\ket{\\psi_k}$ als Eigenvektor in der Phasenschätzungsschaltung verwendet hätten. Mit anderen Worten: Eine Messung der obersten $m$ Qubits ergibt eine Annäherung $y / 2^m$ an den Wert $k / r$, wobei $k \\in \\{ 0, \\dots, r-1\\}$ gleichmäßig zufällig gewählt wird. Dies ermöglicht es uns, $r$ nach mehreren unabhängigen Durchläufen mit einem hohen Maß an Vertrauen zu lernen, was unser Ziel war.\n", "\n" ] }, { "cell_type": "markdown", "id": "c037fd9d-2ad6-4258-a11d-bd91944e7f01", "metadata": {}, "source": [ "\n", "\n", "### Modulare Exponentialoperatoren\n", "\n", "Bisher haben wir das Phasenschätzungsproblem mit dem Ordnungsfindungsproblem verknüpft, indem wir $U = M_a$ und $\\ket{\\psi} = \\ket{1}$ in unserer Quantenschaltung definiert haben. Daher besteht die letzte verbleibende Zutat darin, einen effizienten Weg zu finden, um modulare Exponentiale von $M_a$ als $M_a^k$ für $k = 1, 2, 4, \\dots, 2^{m-1}$ zu definieren. Um diese Berechnung durchzuführen, stellen wir fest, dass wir für jede Potenz $k$, die wir wählen, eine Schaltung für $M_a^k$ erstellen können, nicht indem wir $k$ mal die Schaltung für $M_a$ iterieren, sondern indem wir $b = a^k \\; \\mathrm{mod} \\; N$ berechnen und dann die Schaltung für $M_b$ verwenden. Da wir nur die Potenzen benötigen, die selbst Potenzen von 2 sind, können wir dies klassisch effizient mit Hilfe der iterativen Quadrierung tun.\n", "\n" ] }, { "cell_type": "markdown", "id": "09d93ee7-ab42-43a8-a44f-ad303c9407c7", "metadata": {}, "source": [ "\n", "\n", "## Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware\n", "\n" ] }, { "cell_type": "markdown", "id": "80d39ec2-715f-4014-9dbc-37db001528b1", "metadata": {}, "source": [ "\n", "\n", "### Konkretes Beispiel mit $N = 15$ und $a=2$\n", "\n", "Wir können hier innehalten, um ein konkretes Beispiel zu besprechen und die Schaltung zur Auftragsfindung für $N=15$ zu konstruieren. Beachten Sie, dass mögliche nicht-triviale $a \\in \\mathbb{Z}_N^*$ für $N=15$ $a \\in \\{2, 4, 7, 8, 11, 13, 14 \\}$ sind. Für dieses Beispiel wählen wir $a=2$. Wir werden den Operator $M_2$ und die modularen Potenzierungsoperatoren $M_2^k$ konstruieren.\n", "\n" ] }, { "cell_type": "markdown", "id": "5fcd0c79-0c62-42f1-b6fa-c0f4c58e1994", "metadata": {}, "source": [ "Die Aktion von $M_2$ auf die Berechnungsbasiszustände ist 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}$ Durch Beobachtung können wir sehen, dass die Basiszustände gemischt werden, so dass wir eine Permutationsmatrix haben. Wir können diese Operation auf vier Qubits mit Swap-Gates durchführen. Im Folgenden werden die Operationen $M_2$ und die kontrollierte $M_2$ beschrieben.\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "ec5d416b-7fc9-43f3-b291-e0edc8ad195f", "metadata": {}, "outputs": [], "source": [ "def M2mod15():\n", " \"\"\"\n", " M2 (mod 15)\n", " \"\"\"\n", " b = 2\n", " U = QuantumCircuit(4)\n", "\n", " U.swap(2, 3)\n", " U.swap(1, 2)\n", " U.swap(0, 1)\n", "\n", " U = U.to_gate()\n", " U.name = f\"M_{b}\"\n", "\n", " return U" ] }, { "cell_type": "code", "execution_count": 3, "id": "0a8885f1-91d4-40bd-912d-dc5eea05f5bd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Get the M2 operator\n", "M2 = M2mod15()\n", "\n", "# Add it to a circuit and plot\n", "circ = QuantumCircuit(4)\n", "circ.compose(M2, inplace=True)\n", "circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)" ] }, { "cell_type": "code", "execution_count": 4, "id": "d0ae7456-053a-4389-8653-a1c9c8ff757c", "metadata": {}, "outputs": [], "source": [ "def controlled_M2mod15():\n", " \"\"\"\n", " Controlled M2 (mod 15)\n", " \"\"\"\n", " b = 2\n", " U = QuantumCircuit(4)\n", "\n", " U.swap(2, 3)\n", " U.swap(1, 2)\n", " U.swap(0, 1)\n", "\n", " U = U.to_gate()\n", " U.name = f\"M_{b}\"\n", " c_U = U.control()\n", "\n", " return c_U" ] }, { "cell_type": "code", "execution_count": 5, "id": "ab7fe331-2f9e-47ca-ba3b-f5d67992062a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Get the controlled-M2 operator\n", "controlled_M2 = controlled_M2mod15()\n", "\n", "# Add it to a circuit and plot\n", "circ = QuantumCircuit(5)\n", "circ.compose(controlled_M2, inplace=True)\n", "circ.decompose(reps=1).draw(output=\"mpl\", fold=-1)" ] }, { "cell_type": "markdown", "id": "139b6d31-33d0-49ea-82b1-5bb50b5b6c9e", "metadata": {}, "source": [ "Gatter, die auf mehr als zwei Qubits wirken, werden weiter in Zwei-Qubit-Gatter zerlegt.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "13b4841d-a4ac-46bd-b4d0-d111b3017189", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)" ] }, { "cell_type": "markdown", "id": "e361cc09-e357-4ba7-950b-9fa83898fa88", "metadata": {}, "source": [ "Nun müssen wir die modularen Potenzierungsoperatoren konstruieren. Um eine ausreichende Genauigkeit bei der Phasenschätzung zu erreichen, werden wir acht Qubits für die Schätzungsmessung verwenden. Daher müssen wir $M_b$ mit $b = a^{2^k} \\; (\\mathrm{mod} \\; N)$ für jedes $k = 0, 1, \\dots, 7$ konstruieren.\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "72d989c8-ef62-44d7-887c-5fa13db818e9", "metadata": {}, "outputs": [], "source": [ "def a2kmodN(a, k, N):\n", " \"\"\"Compute a^{2^k} (mod N) by repeated squaring\"\"\"\n", " for _ in range(k):\n", " a = int(np.mod(a**2, N))\n", " return a" ] }, { "cell_type": "code", "execution_count": 8, "id": "69fa8c9f-4107-4339-96db-c6f950a71261", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 4, 1, 1, 1, 1, 1, 1]\n" ] } ], "source": [ "k_list = range(8)\n", "b_list = [a2kmodN(2, k, 15) for k in k_list]\n", "\n", "print(b_list)" ] }, { "cell_type": "markdown", "id": "e28ed7e5-f7ca-4b7b-b875-f14c5229588c", "metadata": {}, "source": [ "Wie wir aus der Liste der $b$ Werte ersehen können, müssen wir zusätzlich zu $M_2$, das wir zuvor konstruiert haben, auch $M_4$ und $M_1$ erstellen. Beachten Sie, dass $M_1$ trivial auf die Zustände der Berechnungsbasis wirkt, es ist also einfach der Identitätsoperator.\n", "\n", "$M_4$ wirkt sich wie folgt auf die Berechnungsgrundlagen aus. $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}$\n", "\n", "Daher kann diese Permutation mit der folgenden Vertauschungsoperation konstruiert werden.\n", "\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "4f3a5fe4-5449-4869-ae94-6fdefd6765f0", "metadata": {}, "outputs": [], "source": [ "def M4mod15():\n", " \"\"\"\n", " M4 (mod 15)\n", " \"\"\"\n", " b = 4\n", " U = QuantumCircuit(4)\n", "\n", " U.swap(1, 3)\n", " U.swap(0, 2)\n", "\n", " U = U.to_gate()\n", " U.name = f\"M_{b}\"\n", "\n", " return U" ] }, { "cell_type": "code", "execution_count": 10, "id": "be041e3d-28b1-453e-983e-184c2366aeb9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Get the M4 operator\n", "M4 = M4mod15()\n", "\n", "# Add it to a circuit and plot\n", "circ = QuantumCircuit(4)\n", "circ.compose(M4, inplace=True)\n", "circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)" ] }, { "cell_type": "code", "execution_count": 11, "id": "0efb7000-7d13-4b73-95d4-f9f747ec5119", "metadata": {}, "outputs": [], "source": [ "def controlled_M4mod15():\n", " \"\"\"\n", " Controlled M4 (mod 15)\n", " \"\"\"\n", " b = 4\n", " U = QuantumCircuit(4)\n", "\n", " U.swap(1, 3)\n", " U.swap(0, 2)\n", "\n", " U = U.to_gate()\n", " U.name = f\"M_{b}\"\n", " c_U = U.control()\n", "\n", " return c_U" ] }, { "cell_type": "code", "execution_count": 12, "id": "8d943b00-a502-4157-8a0d-13fb1f55e705", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Get the controlled-M4 operator\n", "controlled_M4 = controlled_M4mod15()\n", "\n", "# Add it to a circuit and plot\n", "circ = QuantumCircuit(5)\n", "circ.compose(controlled_M4, inplace=True)\n", "circ.decompose(reps=1).draw(output=\"mpl\", fold=-1)" ] }, { "cell_type": "markdown", "id": "7d2a4f30-afb1-49fc-abbb-b9070b58fe8d", "metadata": {}, "source": [ "Gatter, die auf mehr als zwei Qubits wirken, werden weiter in Zwei-Qubit-Gatter zerlegt.\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "68399eef-5e55-4c95-a8a4-c8efaebd34b9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)" ] }, { "cell_type": "markdown", "id": "1f12fb24-257b-4b12-b7c5-e01b975e3216", "metadata": {}, "source": [ "Wir haben gesehen, dass $M_b$ Operatoren für eine gegebene $b \\in \\mathbb{Z}^*_N$ Permutationsoperationen sind. Aufgrund der relativ geringen Größe des Permutationsproblems, das wir hier haben, da $N=15$ nur vier Qubits benötigt, konnten wir diese Operationen direkt mit `SWAP` Gattern durch Inspektion synthetisieren. Im Allgemeinen ist dieser Ansatz nicht unbedingt skalierbar. Stattdessen müssen wir die Permutationsmatrix explizit konstruieren und die `UnitaryGate` Klasse und die Transpilationsmethoden von Qiskit verwenden, um diese Permutationsmatrix zu synthetisieren. Dies kann jedoch zu deutlich tieferen Schaltungen führen. Es folgt ein Beispiel.\n", "\n" ] }, { "cell_type": "code", "execution_count": 14, "id": "33a328b8-11d8-4b0c-a277-5d76b2c07c5e", "metadata": {}, "outputs": [], "source": [ "def mod_mult_gate(b, N):\n", " \"\"\"\n", " Modular multiplication gate from permutation matrix.\n", " \"\"\"\n", " if gcd(b, N) > 1:\n", " print(f\"Error: gcd({b},{N}) > 1\")\n", " else:\n", " n = floor(log(N - 1, 2)) + 1\n", " U = np.full((2**n, 2**n), 0)\n", " for x in range(N):\n", " U[b * x % N][x] = 1\n", " for x in range(N, 2**n):\n", " U[x][x] = 1\n", " G = UnitaryGate(U)\n", " G.name = f\"M_{b}\"\n", " return G" ] }, { "cell_type": "code", "execution_count": 15, "id": "c184f6dd-9f80-4487-ac0b-0dd94170b0f0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "qubits: 4\n", "2q-depth: 94\n", "2q-size: 96\n", "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})\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Let's build M2 using the permutation matrix definition\n", "M2_other = mod_mult_gate(2, 15)\n", "\n", "# Add it to a circuit\n", "circ = QuantumCircuit(4)\n", "circ.compose(M2_other, inplace=True)\n", "circ = circ.decompose()\n", "\n", "# Transpile the circuit and get the depth\n", "coupling_map = CouplingMap.from_line(4)\n", "pm = generate_preset_pass_manager(coupling_map=coupling_map)\n", "transpiled_circ = pm.run(circ)\n", "\n", "print(f\"qubits: {circ.num_qubits}\")\n", "print(\n", " f\"2q-depth: {transpiled_circ.depth(lambda x: x.operation.num_qubits==2)}\"\n", ")\n", "print(f\"2q-size: {transpiled_circ.size(lambda x: x.operation.num_qubits==2)}\")\n", "print(f\"Operator counts: {transpiled_circ.count_ops()}\")\n", "transpiled_circ.decompose().draw(\n", " output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False\n", ")" ] }, { "cell_type": "markdown", "id": "fe8caaf6-4bb6-4d27-8177-71f1b530556d", "metadata": {}, "source": [ "Vergleichen wir diese Werte mit der kompilierten Schaltungstiefe unserer manuellen Implementierung des Gatters $M_2$.\n", "\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "0235c931-0adb-4972-9fce-32a0341822bf", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "qubits: 4\n", "2q-depth: 9\n", "2q-size: 9\n", "Operator counts: OrderedDict({'cx': 9})\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Get the M2 operator from our manual construction\n", "M2 = M2mod15()\n", "\n", "# Add it to a circuit\n", "circ = QuantumCircuit(4)\n", "circ.compose(M2, inplace=True)\n", "circ = circ.decompose(reps=3)\n", "\n", "# Transpile the circuit and get the depth\n", "coupling_map = CouplingMap.from_line(4)\n", "pm = generate_preset_pass_manager(coupling_map=coupling_map)\n", "transpiled_circ = pm.run(circ)\n", "\n", "print(f\"qubits: {circ.num_qubits}\")\n", "print(\n", " f\"2q-depth: {transpiled_circ.depth(lambda x: x.operation.num_qubits==2)}\"\n", ")\n", "print(f\"2q-size: {transpiled_circ.size(lambda x: x.operation.num_qubits==2)}\")\n", "print(f\"Operator counts: {transpiled_circ.count_ops()}\")\n", "transpiled_circ.draw(\n", " output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False\n", ")" ] }, { "cell_type": "markdown", "id": "c3f0f349-a26c-4176-aa9d-407e17184b91", "metadata": {}, "source": [ "Wie wir sehen können, führte der Permutationsmatrix-Ansatz zu einer deutlich tieferen Schaltung selbst für ein einzelnes $M_2$ -Gatter im Vergleich zu unserer manuellen Implementierung. Daher werden wir mit der bisherigen Umsetzung der $M_b$ fortfahren.\n", "\n" ] }, { "cell_type": "markdown", "id": "0dafd632-797b-402c-a88a-821a62c7265a", "metadata": {}, "source": [ "Nun sind wir bereit, die vollständige Schaltung zur Ordnungsfindung zu konstruieren, indem wir unsere zuvor definierten Operatoren zur kontrollierten modularen Potenzierung verwenden. Im folgenden Code importieren wir auch die [QFT-Schaltung](/docs/api/qiskit/qiskit.circuit.library.QFT) aus der Qiskit Circuit-Bibliothek, die Hadamard-Gatter auf jedem Qubit, eine Reihe von controlled-U1 (oder Z, je nach Phase) Gattern und eine Schicht von Swap-Gattern verwendet.\n", "\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "0e854aed-c11b-494c-8c80-adeb8eb0e8fe", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Order finding problem for N = 15 with a = 2\n", "N = 15\n", "a = 2\n", "\n", "# Number of qubits\n", "num_target = floor(log(N - 1, 2)) + 1 # for modular exponentiation operators\n", "num_control = 2 * num_target # for enough precision of estimation\n", "\n", "# List of M_b operators in order\n", "k_list = range(num_control)\n", "b_list = [a2kmodN(2, k, 15) for k in k_list]\n", "\n", "# Initialize the circuit\n", "control = QuantumRegister(num_control, name=\"C\")\n", "target = QuantumRegister(num_target, name=\"T\")\n", "output = ClassicalRegister(num_control, name=\"out\")\n", "circuit = QuantumCircuit(control, target, output)\n", "\n", "# Initialize the target register to the state |1>\n", "circuit.x(num_control)\n", "\n", "# Add the Hadamard gates and controlled versions of the\n", "# multiplication gates\n", "for k, qubit in enumerate(control):\n", " circuit.h(k)\n", " b = b_list[k]\n", " if b == 2:\n", " circuit.compose(\n", " M2mod15().control(), qubits=[qubit] + list(target), inplace=True\n", " )\n", " elif b == 4:\n", " circuit.compose(\n", " M4mod15().control(), qubits=[qubit] + list(target), inplace=True\n", " )\n", " else:\n", " continue # M1 is the identity operator\n", "\n", "# Apply the inverse QFT to the control register\n", "circuit.compose(QFT(num_control, inverse=True), qubits=control, inplace=True)\n", "\n", "# Measure the control register\n", "circuit.measure(control, output)\n", "\n", "circuit.draw(\"mpl\", fold=-1)" ] }, { "cell_type": "markdown", "id": "78cf31ef-b2e7-4256-996a-5f89500efb52", "metadata": {}, "source": [ "Man beachte, dass wir die kontrollierten modularen Potenzierungsoperationen für die verbleibenden Kontroll-Qubits weggelassen haben, da $M_1$ der Identitätsoperator ist.\n", "\n" ] }, { "cell_type": "markdown", "id": "792a5cb7-2ac0-4964-b747-2780193a0401", "metadata": {}, "source": [ "Beachten Sie, dass wir diese Schaltung später in diesem Lernprogramm auf dem `ibm_marrakesh` backend ausführen werden. Zu diesem Zweck transpilieren wir die Schaltung entsprechend diesem spezifischen Backend und melden die Schaltungstiefe und die Anzahl der Gatter.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "95925dd5-7ba9-4746-b96e-ba50400fa5ac", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2q-depth: 187\n", "2q-size: 260\n", "Operator counts: OrderedDict({'sx': 521, 'rz': 354, 'cz': 260, 'measure': 8, 'x': 4})\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "service = QiskitRuntimeService()\n", "backend = service.backend(\"ibm_marrakesh\")\n", "pm = generate_preset_pass_manager(optimization_level=2, backend=backend)\n", "\n", "transpiled_circuit = pm.run(circuit)\n", "\n", "print(\n", " f\"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}\"\n", ")\n", "print(\n", " f\"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}\"\n", ")\n", "print(f\"Operator counts: {transpiled_circuit.count_ops()}\")\n", "transpiled_circuit.draw(\n", " output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False\n", ")" ] }, { "cell_type": "markdown", "id": "f96a2a7e-0363-49d6-bc21-f0f207a84610", "metadata": {}, "source": [ "\n", "\n", "## Schritt 3: Mit „ Qiskit primitives “ ausführen\n", "\n" ] }, { "cell_type": "markdown", "id": "a3fd5248-11f2-40b6-857a-6efc25e31bdb", "metadata": {}, "source": [ "Zunächst erörtern wir, was wir theoretisch erhalten würden, wenn wir diese Schaltung auf einem idealen Simulator ausführen würden. Nachfolgend finden Sie eine Reihe von Simulationsergebnissen für die obige Schaltung mit 1024 Aufnahmen. Wie wir sehen können, erhalten wir eine annähernd gleichmäßige Verteilung über vier Bitstrings über die Kontroll-Qubits.\n", "\n" ] }, { "cell_type": "code", "execution_count": 19, "id": "c8720362-684f-4114-8abb-83d71d21c0df", "metadata": {}, "outputs": [], "source": [ "# Obtained from the simulator\n", "counts = {\"00000000\": 264, \"01000000\": 268, \"10000000\": 249, \"11000000\": 243}" ] }, { "cell_type": "code", "execution_count": 20, "id": "0d6d2702-02e4-47de-8f7e-0b256657ef0f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_histogram(counts)" ] }, { "cell_type": "markdown", "id": "5ddd6952-fb4d-447c-8781-968ca5bb88a3", "metadata": {}, "source": [ "Durch Messung der Kontroll-Qubits erhalten wir eine Acht-Bit-Phasenschätzung des $M_a$ -Operators. Wir können diese Binärdarstellung in Dezimalzahlen umwandeln, um die gemessene Phase zu ermitteln. Wie aus dem obigen Histogramm hervorgeht, wurden vier verschiedene Bitstrings gemessen, und jeder von ihnen entspricht einem Phasenwert wie folgt\n", "\n" ] }, { "cell_type": "code", "execution_count": 21, "id": "59ae21fc-e3d0-48e3-8cc6-dbce59c747ca", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " Register Output Phase\n", "0 00000000(bin) = 0(dec) 0/256 = 0.00\n", "1 01000000(bin) = 64(dec) 64/256 = 0.25\n", "2 10000000(bin) = 128(dec) 128/256 = 0.50\n", "3 11000000(bin) = 192(dec) 192/256 = 0.75\n" ] } ], "source": [ "# Rows to be displayed in table\n", "rows = []\n", "# Corresponding phase of each bitstring\n", "measured_phases = []\n", "\n", "for output in counts:\n", " decimal = int(output, 2) # Convert bitstring to decimal\n", " phase = decimal / (2**num_control) # Find corresponding eigenvalue\n", " measured_phases.append(phase)\n", " # Add these values to the rows in our table:\n", " rows.append(\n", " [\n", " f\"{output}(bin) = {decimal:>3}(dec)\",\n", " f\"{decimal}/{2 ** num_control} = {phase:.2f}\",\n", " ]\n", " )\n", "\n", "# Print the rows in a table\n", "headers = [\"Register Output\", \"Phase\"]\n", "df = pd.DataFrame(rows, columns=headers)\n", "print(df)" ] }, { "cell_type": "markdown", "id": "f0ca65bb-abb4-4f4b-bc32-4749f36e5780", "metadata": {}, "source": [ "Erinnern Sie sich, dass jede gemessene Phase $\\theta = k / r$ entspricht, wobei $k$ gleichmäßig zufällig aus $\\{0, 1, \\dots, r-1 \\}$ entnommen wird. Daher können wir den Algorithmus der fortgesetzten Brüche verwenden, um zu versuchen, $k$ und die Ordnung $r$ zu finden. Python hat diese Funktionalität eingebaut. Mit dem Modul `fractions` können wir z. B. einen Float in ein `Fraction` Objekt umwandeln:\n", "\n" ] }, { "cell_type": "code", "execution_count": 22, "id": "999f04bc-f912-465f-9cba-90d08bda3758", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Fraction(5998794703657501, 9007199254740992)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Fraction(0.666)" ] }, { "cell_type": "markdown", "id": "c5452b79-967f-4fe9-86d7-f9797987a8b5", "metadata": {}, "source": [ "Da dies Brüche ergibt, die genau das Ergebnis liefern (in diesem Fall `0.6660000...`), kann dies zu unschönen Ergebnissen wie dem obigen führen. Wir können die Methode `.limit_denominator()` verwenden, um den Bruch zu erhalten, der unserem Float am ähnlichsten ist und dessen Nenner unter einem bestimmten Wert liegt:\n", "\n" ] }, { "cell_type": "code", "execution_count": 23, "id": "1352aa9e-7c98-4862-8ac6-8d17fce61f3d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Fraction(2, 3)" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Get fraction that most closely resembles 0.666\n", "# with denominator < 15\n", "Fraction(0.666).limit_denominator(15)" ] }, { "cell_type": "markdown", "id": "ab1ce9d5-7a24-4717-a94b-576f8c940ec2", "metadata": {}, "source": [ "Das ist viel schöner. Die Ordnung (r) muss kleiner als N sein, also setzen wir den maximalen Nenner auf `15`:\n", "\n" ] }, { "cell_type": "code", "execution_count": 24, "id": "6c20bff2-29b7-45ea-b1ed-e802e0d1a0f9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " Phase Fraction Guess for r\n", "0 0.00 0/1 1\n", "1 0.25 1/4 4\n", "2 0.50 1/2 2\n", "3 0.75 3/4 4\n" ] } ], "source": [ "# Rows to be displayed in a table\n", "rows = []\n", "\n", "for phase in measured_phases:\n", " frac = Fraction(phase).limit_denominator(15)\n", " rows.append(\n", " [phase, f\"{frac.numerator}/{frac.denominator}\", frac.denominator]\n", " )\n", "\n", "# Print the rows in a table\n", "headers = [\"Phase\", \"Fraction\", \"Guess for r\"]\n", "df = pd.DataFrame(rows, columns=headers)\n", "print(df)" ] }, { "cell_type": "markdown", "id": "7590599a-bb21-4d9c-8a78-2ff406acc4af", "metadata": {}, "source": [ "Wir können sehen, dass zwei der gemessenen Eigenwerte das richtige Ergebnis liefern: $r=4$ und wir sehen, dass der Shor-Algorithmus zur Ordnungsfindung scheitern kann. Diese schlechten Ergebnisse liegen daran, dass $k = 0$ oder $k$ und $r$ nicht koprimiert sind - und wir statt $r$ einen Faktor von $r$ erhalten. Die einfachste Lösung hierfür ist, das Experiment einfach zu wiederholen, bis wir ein zufriedenstellendes Ergebnis für $r$ erhalten.\n", "\n" ] }, { "cell_type": "markdown", "id": "174b446c-ca09-4816-8983-33f61eaecfa6", "metadata": {}, "source": [ "Bisher haben wir das Problem der Ordnungsfindung für $N=15$ mit $a=2$ unter Verwendung der Phasenschätzungsschaltung auf einem Simulator implementiert. Der letzte Schritt des Shor-Algorithmus besteht darin, das Problem der Ordnungsfindung mit dem Problem der ganzzahligen Faktorisierung zu verbinden. Dieser letzte Teil des Algorithmus ist rein klassisch und kann auf einem klassischen Computer gelöst werden, nachdem die Phasenmessungen von einem Quantencomputer erhalten wurden. Daher verschieben wir den letzten Teil des Algorithmus, bis wir zeigen, wie wir die Schaltung zur Auftragsfindung auf echter Hardware ausführen können.\n", "\n" ] }, { "cell_type": "markdown", "id": "7c826de7-0caa-4337-826e-3e81024ce125", "metadata": {}, "source": [ "\n", "\n", "### Hardware läuft\n", "\n" ] }, { "cell_type": "markdown", "id": "a8d6d6a9-9494-4733-89a2-790ac8adf929", "metadata": {}, "source": [ "Jetzt können wir die Schaltung zur Auftragssuche ausführen, die wir zuvor für `ibm_marrakesh` umgesetzt haben. Hier wenden wir uns der [dynamischen Entkopplung](/docs/guides/error-mitigation-and-suppression-techniques#dynamical-decoupling) (DD) zur Fehlerunterdrückung und dem [Gate Twirling](/docs/guides/error-mitigation-and-suppression-techniques#pauli-twirling) zur Fehlerminderung zu. Bei der DD werden Sequenzen von genau getakteten Steuerimpulsen auf ein Quantengerät angewandt, wodurch unerwünschte Wechselwirkungen mit der Umgebung und Dekohärenz effektiv ausgemerzt werden. Beim Gate Twirling hingegen werden bestimmte Quantengatter randomisiert, um kohärente Fehler in Pauli-Fehler umzuwandeln, die sich nicht quadratisch, sondern linear akkumulieren. Beide Techniken werden häufig kombiniert, um die Kohärenz und Genauigkeit von Quantenberechnungen zu verbessern.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "af61f1de-be24-4fc6-b2bb-af6845163c3c", "metadata": {}, "outputs": [], "source": [ "# Sampler primitive to obtain the probability distribution\n", "sampler = Sampler(backend)\n", "\n", "# Turn on dynamical decoupling with sequence XpXm\n", "sampler.options.dynamical_decoupling.enable = True\n", "sampler.options.dynamical_decoupling.sequence_type = \"XpXm\"\n", "# Enable gate twirling\n", "sampler.options.twirling.enable_gates = True\n", "\n", "# Assign tags before executing\n", "sampler.options.environment.job_tags = [\"TUT_SA\"]\n", "\n", "pub = transpiled_circuit\n", "job = sampler.run([pub], shots=1024)" ] }, { "cell_type": "code", "execution_count": 25, "id": "e5f53a20-40a4-440f-a6ea-349c20efbc95", "metadata": {}, "outputs": [], "source": [ "result = job.result()[0]\n", "counts = result.data[\"out\"].get_counts()" ] }, { "cell_type": "code", "execution_count": 26, "id": "559d7030-1f67-44e8-afa7-6afc7a334677", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_histogram(counts, figsize=(35, 5))" ] }, { "cell_type": "markdown", "id": "3614aa7e-0410-4e9e-b33a-3caf407e086a", "metadata": {}, "source": [ "Wie wir sehen können, erhalten wir die gleichen Bitstrings mit den höchsten Werten. Da Quanten-Hardware mit Rauschen behaftet ist, gibt es ein gewisses Leck in anderen Bitstrings, das wir statistisch herausfiltern können.\n", "\n" ] }, { "cell_type": "code", "execution_count": 27, "id": "f9cf9a07-5251-47bc-9713-c802f8f1a37c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'00000000': 58, '01000000': 41, '11000000': 42, '10000000': 40}\n" ] } ], "source": [ "# Dictionary of bitstrings and their counts to keep\n", "counts_keep = {}\n", "# Threshold to filter\n", "threshold = np.max(list(counts.values())) / 2\n", "\n", "for key, value in counts.items():\n", " if value > threshold:\n", " counts_keep[key] = value\n", "\n", "print(counts_keep)" ] }, { "cell_type": "markdown", "id": "c32cca67-9c9d-4373-9a0a-3174e884dd91", "metadata": {}, "source": [ "\n", "\n", "## Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format\n", "\n" ] }, { "cell_type": "markdown", "id": "5a7b116b-02d0-47dc-8cab-e792ba36d868", "metadata": {}, "source": [ "\n", "\n", "### Ganzzahlige Faktorisierung\n", "\n" ] }, { "cell_type": "markdown", "id": "691df180-6ac3-49ac-ad4d-2d78348ceea7", "metadata": {}, "source": [ "Bisher haben wir erörtert, wie wir das Problem der Auftragsfindung mit Hilfe einer Phasenschätzungsschaltung lösen können. Nun verbinden wir das Problem der Ordnungsfindung mit der ganzzahligen Faktorisierung, was den Shor-Algorithmus vervollständigt. Beachten Sie, dass dieser Teil des Algorithmus klassisch ist.\n", "\n" ] }, { "cell_type": "markdown", "id": "fe3472a3-f8cd-4db9-8178-c025ccf2ec55", "metadata": {}, "source": [ "Wir demonstrieren dies nun am Beispiel von $N = 15$ und $a = 2$. Erinnern Sie sich, dass die von uns gemessene Phase $k / r$ ist, wobei $a^r \\; (\\textrm{mod} \\; N) = 1$ und $k$ eine zufällige ganze Zahl zwischen $0$ und $r - 1$ ist. Aus dieser Gleichung ergibt sich $(a^r - 1) \\; (\\textrm{mod} \\; N) = 0,$, was bedeutet, dass $N$ durch $a^r-1$ geteilt werden muss. Wenn $r$ ebenfalls gerade ist, können wir $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$ schreiben. Wenn $r$ nicht gerade ist, können wir nicht weitergehen und müssen es mit einem anderen Wert für $a$ erneut versuchen; andernfalls besteht eine hohe Wahrscheinlichkeit, dass der größte gemeinsame Teiler von $N$ und entweder $a^{r/2}-1$ oder $a^{r/2}+1$ ein richtiger Faktor von $N$ ist.\n", "\n", "Da einige Durchläufe des Algorithmus statistisch gesehen fehlschlagen werden, wiederholen wir diesen Algorithmus, bis mindestens ein Faktor von $N$ gefunden wird.\n", "\n" ] }, { "cell_type": "markdown", "id": "dda4ad11-ef2b-4bfb-ba3c-5cb1f5810871", "metadata": {}, "source": [ "In der Zelle darunter wird der Algorithmus wiederholt, bis mindestens ein Faktor von $N=15$ gefunden wird. Wir werden die Ergebnisse des obigen Hardware-Laufs verwenden, um die Phase und den entsprechenden Faktor in jeder Iteration zu erraten.\n", "\n" ] }, { "cell_type": "code", "execution_count": 28, "id": "5d67cd71-8651-4a10-a913-a5bdaa6d6b38", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "ATTEMPT 0:\n", "Phase: theta = 0.0\n", "Order of 2 modulo 15 estimated as: r = 1\n", "\n", "ATTEMPT 1:\n", "Phase: theta = 0.25\n", "Order of 2 modulo 15 estimated as: r = 4\n", "*** Non-trivial factor found: 3 ***\n" ] } ], "source": [ "a = 2\n", "N = 15\n", "\n", "FACTOR_FOUND = False\n", "num_attempt = 0\n", "\n", "while not FACTOR_FOUND:\n", " print(f\"\\nATTEMPT {num_attempt}:\")\n", " # Here, we get the bitstring by iterating over outcomes\n", " # of a previous hardware run with multiple shots.\n", " # Instead, we can also perform a single-shot measurement\n", " # here in the loop.\n", " bitstring = list(counts_keep.keys())[num_attempt]\n", " num_attempt += 1\n", " # Find the phase from measurement\n", " decimal = int(bitstring, 2)\n", " phase = decimal / (2**num_control) # phase = k / r\n", " print(f\"Phase: theta = {phase}\")\n", "\n", " # Guess the order from phase\n", " frac = Fraction(phase).limit_denominator(N)\n", " r = frac.denominator # order = r\n", " print(f\"Order of {a} modulo {N} estimated as: r = {r}\")\n", "\n", " if phase != 0:\n", " # Guesses for factors are gcd(a^{r / 2} ± 1, 15)\n", " if r % 2 == 0:\n", " x = pow(a, r // 2, N) - 1\n", " d = gcd(x, N)\n", " if d > 1:\n", " FACTOR_FOUND = True\n", " print(f\"*** Non-trivial factor found: {x} ***\")" ] }, { "cell_type": "markdown", "id": "00f31b56-e1a9-479e-8a82-bb708263f1a3", "metadata": {}, "source": [ "\n", "\n", "## Diskussion\n", "\n" ] }, { "cell_type": "markdown", "id": "69189c94-6e78-410d-a365-8649d4c69163", "metadata": {}, "source": [ "\n", "\n", "### Verwandte Arbeiten\n", "\n", "In diesem Abschnitt gehen wir auf andere wegweisende Arbeiten ein, die Shors Algorithmus auf echter Hardware demonstriert haben.\n", "\n", "In der bahnbrechenden Arbeit [\\[3\\]](#references) von IBM® wurde der Shor-Algorithmus zum ersten Mal demonstriert, indem die Zahl 15 mit Hilfe eines Quantencomputers mit sieben Quantenbits für kernmagnetische Resonanz (NMR) in ihre Primfaktoren 3 und 5 zerlegt wurde. In einem anderen Experiment [\\[4\\]](#references) wurden mit Hilfe photonischer Qubits 15 Faktoren berechnet. Durch den Einsatz eines einzigen Qubits, das mehrfach recycelt wird, und die Codierung des Arbeitsregisters in höherdimensionale Zustände konnten die Forscher die erforderliche Anzahl von Qubits auf ein Drittel der Anzahl im Standardprotokoll reduzieren, indem sie einen mit zwei Photonen kompilierten Algorithmus verwendeten. Eine wichtige Arbeit zur Demonstration des Shor-Algorithmus ist [\\[5\\]](#references), in der die iterative Phasenschätzung von Kitaev [\\[8\\]](#references) verwendet wird, um die Qubit-Anforderungen des Algorithmus zu reduzieren. Die Autoren verwendeten sieben Kontroll-Qubits und vier Cache-Qubits sowie modulare Multiplizierer. Diese Implementierung erfordert jedoch Messungen in der Mitte des Schaltkreises mit Feedforward-Operationen und Qubit-Recycling mit Reset-Operationen. Diese Demonstration wurde mit einem Ionenfallen-Quantencomputer durchgeführt.\n", "\n", "Neuere Arbeiten [\\[6\\]](#references) konzentrierten sich auf das Factoring von 15, 21 und 35 auf IBM Quantum® Hardware. Ähnlich wie bei früheren Arbeiten verwendeten die Forscher eine kompilierte Version des Algorithmus, die eine von Kitaev vorgeschlagene semiklassische Quanten-Fourier-Transformation einsetzt, um die Anzahl der physikalischen Qubits und Gatter zu minimieren. In einer neueren Arbeit [\\[7\\]](#references) wurde auch ein Proof-of-Concept für die Faktorisierung der ganzen Zahl 21 durchgeführt. Bei dieser Demonstration wurde auch eine kompilierte Version der Quantenphasenschätzungsroutine verwendet, die auf der vorherigen Demonstration von [\\[4\\]](#references) aufbaut. Die Autoren gingen über diese Arbeit hinaus, indem sie eine Konfiguration von annähernden Toffoli-Gattern mit Restphasenverschiebungen verwendeten. Der Algorithmus wurde auf IBM Quantenprozessoren mit nur fünf Qubits implementiert, und das Vorhandensein von Verschränkung zwischen den Kontroll- und Register-Qubits wurde erfolgreich verifiziert.\n", "\n" ] }, { "cell_type": "markdown", "id": "2dab9ac1-d3e4-4b4e-babe-472d69b026ab", "metadata": {}, "source": [ "\n", "\n", "### Skalierung des Algorithmus\n", "\n", "Wir weisen darauf hin, dass die RSA-Verschlüsselung normalerweise Schlüsselgrößen in der Größenordnung von 2048 bis 4096 Bit erfordert. Der Versuch, eine 2048-Bit-Zahl mit dem Shor-Algorithmus zu faktorisieren, führt zu einem Quantenschaltkreis mit Millionen von Qubits, einschließlich des Fehlerkorrektur-Overheads und einer Schaltungstiefe in der Größenordnung von einer Milliarde, was die Grenzen der derzeitigen Quanten-Hardware zur Ausführung überschreitet. Daher erfordert der Shor-Algorithmus entweder optimierte Schaltkreiskonstruktionsmethoden oder eine robuste Quantenfehlerkorrektur, um für das Brechen moderner kryptographischer Systeme praktisch brauchbar zu sein. Wir verweisen auf [\\[9\\]](#references) für eine ausführlichere Diskussion über die Ressourcenabschätzung für den Shor-Algorithmus.\n", "\n" ] }, { "cell_type": "markdown", "id": "cb53f62c-e560-43cf-a614-d31f266a569c", "metadata": {}, "source": [ "\n", "\n", "## Herausforderung\n", "\n", "Herzlichen Glückwunsch zur Fertigstellung des Tutorials! Jetzt ist ein guter Zeitpunkt, um Ihr Verständnis zu testen. Könnten Sie versuchen, den Schaltkreis für die Multiplikation von 21 zu konstruieren? Sie können eine $a$ Ihrer Wahl auswählen. Sie müssen über die Bitgenauigkeit des Algorithmus entscheiden, um die Anzahl der Qubits zu wählen, und Sie müssen die modularen Potenzierungsoperatoren $M_a$ entwerfen. Wir ermutigen Sie, dies selbst auszuprobieren, und lesen Sie dann über die in Abb. 9 von [\\[6\\]](#references) und Abb. 2 von [\\[7\\]](#references) gezeigten Methoden.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "09d347b8-51a4-4eb5-8422-76508f7ba1ad", "metadata": {}, "outputs": [], "source": [ "def M_a_mod21():\n", " \"\"\"\n", " M_a (mod 21)\n", " \"\"\"\n", "\n", " # Your code here\n", " pass" ] }, { "cell_type": "markdown", "id": "dc16f509-7441-4221-8113-e09b118397a0", "metadata": {}, "source": [ "\n", "\n", "## Referenzen\n", "\n", "1. Shor, Peter W. \"[Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer](https://epubs.siam.org/doi/abs/10.1137/S0036144598347011) \" SIAM review 41.2 (1999): 303-332.\n", "2. IBM Quantum Kurs [„Grundlagen der Quantenalgorithmen“](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction) von Dr. John Watrous.\n", "3. Vandersypen, Lieven MK, et al. \"[Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance](https://www.nature.com/articles/414883a) \" Nature 414.6866 (2001): 883-887.\n", "4. Martin-Lopez, Enrique, et al. \"[Experimentelle Realisierung von Shors Quantenfactoring-Algorithmus unter Verwendung von Qubit-Recycling](https://www.nature.com/articles/nphoton.2012.259) \" Nature Photonics 6.11 (2012): 773-776.\n", "5. Monz, Thomas, et al. \"[Realisierung eines skalierbaren Shor-Algorithmus](https://www.science.org/doi/full/10.1126/science.aad9480) \" Science 351.6277 (2016): 1068-1070.\n", "6. Amico, Mirko, Zain H. Saleem, und Muir Kumph. \"[Experimentelle Untersuchung des Shor'schen Factoring-Algorithmus mit Hilfe der IBM Q Experience](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.100.012305) \" Physical Review A 100.1 (2019): 012305.\n", "7. Skosana, Unathi, und Mark Tame. \"[Demonstration des Shor'schen Faktorisierungsalgorithmus für N=21 auf IBM Quantenprozessoren](https://www.nature.com/articles/s41598-021-95973-w) \" Wissenschaftliche Berichte 11.1 (2021): 16599.\n", "8. Kitaev, A. Yu. \"[Quantenmessungen und das Problem der abelschen Stabilisatoren](https://arxiv.org/abs/quant-ph/9511026) \" arXiv vorabdruck quant-ph/9511026 (1995).\n", "9. Gidney, Craig, und Martin Ekerå. \"[Wie man 2048 Bit RSA-Ganzzahlen in 8 Stunden mit 20 Millionen verrauschten Qubits faktorisiert](https://doi.org/10.22331/q-2021-04-15-433) \" Quantum 5 (2021): 433.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 3 }, "nbformat": 4, "nbformat_minor": 4 }