.svg)
Wissenschaftliche Quantenalgorithmen automatisch ausführbar machen
Quantenmodellierungskonstrukte und starke Synthesefähigkeiten schließen die Lücke zwischen den Absichten der Entwickler von Quantenalgorithmen, wie sie in akademischen Arbeiten veröffentlicht werden, und den tatsächlichen Implementierungen, die auf Quantencomputern, Simulatoren und Ressourcenschätzern ausgeführt werden können
Einführung
Quantenalgorithmen waren in den letzten dreißig Jahren weitgehend ein akademisches Unterfangen. Theoretiker haben wohldefinierte und bewährte Algorithmen veröffentlicht und sie in einer soliden wissenschaftlichen Sprache beschrieben. Diese Beschreibung umfasst Abbildungen, Beschriftungen, Texte, Gleichungen und andere Hilfsmittel, die den Wissenschaftlern zur Verfügung stehen, um die Korrektheit ihrer Arbeit formal zu beschreiben und zu beweisen. Leider beruht eine solche Beschreibung auf dem gegenseitigen Verständnis zwischen Wissenschaftlern und basiert auf einer formalen wissenschaftlichen Sprache. Diese Sprache ist nicht formal genug, um von Compilern verstanden zu werden und eine auf einem Quantencomputer ausführbare Beschreibung des Quantenalgorithmus zu erzeugen.
In diesem Beitrag stellen wir neue Modellierungskonstrukte und Redewendungen vor, die sich aus einer gründlichen Durchsicht vieler Quantenalgorithmen und Implementierungen ergeben, die im Laufe der Jahre veröffentlicht wurden. Selbst bei so singulären Algorithmen wie dem von Shor, Grover oder HHL - die alle relativ einfach angegeben werden können, wenn man von der internen Struktur abstrahiert - ergibt sich eine Fülle von Komplexitäten, wenn man die nächste Ebene von Details betrachtet - die modulare Potenzierung in Shors Algorithmus, das Orakel in Grovers Algorithmus und die Form der linearen Gleichungen in HHLs Algorithmus. Im Folgenden werden wir uns am Beispiel des Shor-Algorithmus orientieren, da er für jeden, der einen Einführungskurs in Quantenalgorithmen belegt, am einfachsten zu verstehen ist. Mithilfe von Microsofts Azure Quantum Resource Estimator zeigen wir, dass für die Ausführung des Shor-Algorithmus mit vier modularen Additionen 354.562 physische Qubits erforderlich sind, und wir ermitteln die spezifische Anzahl der benötigten Gatter. In diesem Beispiel zeigen wir nur die Modellierungskonstrukte, die wir in einem breiten Spektrum von Quantenalgorithmen für relevant halten.
Der Gesamtverdienst unserer Methode wird dadurch bestimmt, wie sehr das Modell dem Quantenschaltkreis ähnelt, wie er vom Konstrukteur, z. B. in einer wissenschaftlichen Arbeit, beschrieben wurde, und durch die Fähigkeit des Modells, alle formalen Anforderungen des Schaltkreises eindeutig zu erfassen.
Die Modellierungskonstrukte sowie die Synthese-Engine, die in der Lage ist, das Modell formal zu verstehen und eine konkrete, optimierte Quantenschaltkreis-Implementierung zu erzeugen, wurden alle in die Classiq-Plattform für den Entwurf von Quantenalgorithmen implementiert, so dass zum ersten Mal die Möglichkeit besteht, komplexe Quantenalgorithmen vom Gedanken bis zur Ausführung zu erstellen. Die von der Classiq-Plattform erstellten Quantenalgorithmen (z. B. Implementierungen des Shor-Algorithmus) sind bei weitem die komplexesten und umfangreichsten Quantenalgorithmen, die je erstellt wurden.
Implementierung des Shor'schen Algorithmus
Wir gehen auf die wichtigsten Konzepte und Werkzeuge ein, die in der grafischen Modellierung von Classiq verwendet werden, um eine Schaltung zu erzeugen, die den Shor-Algorithmus zur Faktorisierung einer durch n Bits dargestellten Zahl N implementiert. Die Schaltung folgt der Implementierung von Beauregard(https://arxiv.org/pdf/quant-ph/0205095 [1]) und benötigt 4n+2 Qubits. Der Unterschied zwischen den beiden Schaltkreisen besteht darin, dass der Originalschaltkreis von Beauregard den endgültigen inversen QFT-Schaltkreis auf einem einzelnen Qubit implementiert, indem er ein einzelnes Qubit 2n-mal misst und neu präpariert (und daher 2n+3 Qubits benötigt), während in unserer Implementierung die "reguläre" QFT auf 2n Qubits verwendet wird.
Die Schaltung implementiert den Quanten-Teil von Shors Algorithmus. Erinnern Sie sich daran, dass in Shors Algorithmus, um einen Faktor einer gegebenen n-Qubit-Zahl N zu finden, eine Zufallszahl a ausgewählt wird, die kleiner als N ist, und gcd(a,N) berechnet wird, wobei gcd den größten gemeinsamen Nenner bezeichnet. Wenn gcd(a,N) >1 ist, sind wir fertig - gcd(a,N) ist ein Faktor von N. Wenn nicht, führen wir den Quanten-Teil des Algorithmus durch - dessen Hauptteil die Berechnung von $|a^xmodN\rangle$ ist (dem Quanten-Teil folgt eine zusätzliche klassische Nachbearbeitung des gemessenen Ergebnisses).
Um eine solche Schaltung für ein beliebiges n zu konstruieren, muss man in der Lage sein, die Schaltung hierarchisch auszudrücken, angefangen bei den grundlegenden Quantenbausteinen auf der untersten Ebene (die Quantenbausteine sind grundlegende Gatter und Funktionen, die von der Synthese-Engine erkannt werden) bis hin zur gesamten Schaltung auf der obersten Ebene. Darüber hinaus muss man in der Lage sein, mit Registern statt mit einzelnen Qubits zu arbeiten, d. h. Gatter auf Register anzuwenden und gleichzeitig die Möglichkeit zu behalten, Register zu zerschneiden und Gatter auf ausgewählte Qubits anzuwenden. Die Werkzeuge, die eine solche Modellierung eines Schaltkreises ermöglichen, werden in jeder der Haupthierarchien/Schichten des Schaltkreises demonstriert, nämlich:
- Ein modularer Addierer im Fourier-Raum, der aus Basisgattern (hauptsächlich phasengesteuerte, phasengesteuerte und doppelt phasengesteuerte Gatter) und QFT aufgebaut ist.
- Modulare Multiplikation, die aus n modularen Addierern besteht.
- Modulare Potenzierung, konstruiert aus n modularen Multiplikationsschaltungen.
Die gesteuerte modulare Addierer-Schaltung
Beim modularen Addierer wird die Zahl a zu einem (n+1) Qubit-Quantenregister (dem b-Register ) addiert. Der Eingangszustand des Registers ist, wenn das höchstwertige Bit (MSB) von b den Wert Null hat. Dieses Qubit wird als Überlaufbit verwendet. Außerdem enthält die Schaltung zwei Steuerbits und ein Hilfsbit, das am Eingang und am Ausgang Null ist. Der modulare Addierer ist in der folgenden Schaltung dargestellt. Der dicke schwarze Balken unterscheidet zwischen dem Addierer (Balken auf der rechten Seite) und seiner Umkehrung, die die Subtraktion implementiert (Balken auf der linken Seite):
Bei c1=c2=1 funktioniert die Schaltung wie folgt (bei anderen Werten von ci werden die gesteuerten Vorgänge nicht aktiviert und die übrigen Vorgänge heben sich auf).
o Teilschaltkreis A: Addiert a zum (n+1) Qubit-Register b mit $\Phi(b)$.
o Sub-circuit B: Subtracts N from a+b and then adds N again if N < a+b – this is done by checking the MSB of a+b-N.
$$|1,1,\Phi (b),0\rangle \rightarrow |1,1,\Phi (b+a),0\rangle$$
Man beachte, dass sich das b-Register zu diesem Zeitpunkt im Zustand (a+b)mod N befindet, aber im Allgemeinen mit dem Hilfsquantum verschränkt ist.
o Teilschaltkreis C: Setzt das letzte/unterste Hilfsqubit auf $|0\rangle$ zurück (und entkoppelt es vom b-Register), indem es a vom Register subtrahiert, das höchstwertige Bit des b-Registers prüft (und gegebenenfalls das Hilfsbit umkehrt) und a wieder zum Register addiert.
Der Betrieb der gesamten Schaltung bei den "legalen" Eingangszuständen (bei denen das MSB von b Null ist) ist erforderlich:
$$|1,1,\Phi (b),0\rangle \rightarrow |1,1,\Phi ((b+a) mod N),0\rangle .$$
Der Hauptbaustein des modularen Addierers ist eine Addierschaltung (in der Fourier-Basis), die die Zahl a (kleiner als N) zu einem (n+1) Qubit-Quantenregister addiert, sowie deren Inverse (mit und ohne Steuerung). Der (ungesteuerte) Addierer ist ausschließlich aus Ein-Qubit-Phasentoren aufgebaut (hier - $|\Phi(b)\rangle = QFT|b\rangle $):
Die Zahl a ist hier "klassisch" in dem Sinne, dass sie nicht von einem Quantenregister getragen wird, sondern in den Phasen kodiert ist. In unserer Plattform wird der Addierer einfach durch das Kaskadenmodellierungswerkzeug realisiert, mit dem eine Operation vertikal dupliziert wird: Sie wird auf alle Qubits in einem Register angewendet, wie unten gezeigt (der Grund, warum es Kaskade und nicht z.B. forall heißt, wird später deutlich).
Der Eingang und der Ausgang oben sind W-Qubit-Register mit W, einem Parameter, der von oben in der Hierarchie festgelegt wird, und die Kaskadenanweisung wendet das Ein-Qubit-Phasentor auf jedes Qubit im Register an. Jedem der Qubits wird eine andere Phase zugeführt. Diese Phasen werden vom Benutzer als Teil der Modellierung in die Schaltung eingeführt. Die formalen Anschlussnamen der Gatter sind target_in und target_out.
Ein weiterer Baustein, der in der modularen Addierer-Teilschaltung (Abb. 1) verwendet wird, ist der kontrollierte und doppelt kontrollierte Addierer, bei dem die Phasengatter durch Gatter mit kontrollierter Phase (CPhase) ersetzt werden. Bei diesem Gatter steuert ein einzelnes Qubit die Phasen der Ziel-Qubits. Um ein Gatter wiederholt auf dasselbe Register anzuwenden, verwenden wir die Anweisung instances. Bei der Implementierung des gesteuerten Addierers werden die Phasen jedoch sequentiell in alle Qubits im Zielregister eingeführt, weshalb man sowohl Kaskade (Wiederholung auf Qubits) als auch Instanzen (Wiederholung von Gattern) zusammen verwenden muss.
Das einzelne Qubit im Steuerregister nimmt an allen W CPhase-Gattern der Sequenz teil, während jedes der W Qubits im Zielregister an genau einem Gatter teilnimmt.
Das gesamte Schema für die modulare Addiererschaltung aus Abb. 1 ist unten dargestellt. Beachten Sie, wie sehr diese Schaltung der akademischen Zeichnung in Abb. 1 ähnelt. Der Hauptunterschied besteht natürlich darin, dass diese Schaltung vollständig ausführbar ist und durch die Synthese-Engine bis zur besten konkreten Implementierung optimiert werden kann.
Die Schaltung besteht aus fünf Addierern (einschließlich kontrollierter und inverser Addierer) und zwei "twoQFT"-Funktionen, die die beiden Konstruktionen in der obigen Schaltung implementieren, indem sie das MSB-Qubit im b-Register überprüfen und das Hilfs-Qubit bei Bedarf invertieren (jede dieser Konstruktionen umfasst zwei QFT-Funktionen, die das b-Register in den Fourier-Raum und aus diesem heraus führen). Diese Namenskonvention wird in Abb. 5 demonstriert und in der nachfolgenden Legende erläutert.
Die gesteuerte modulare Multiplikatorschaltung
Die Schaltung, die die modulare Multiplikation implementiert, kann aus der n-maligen Wiederholung der Funktion des modularen Addierers, wie unten gezeigt, aufgebaut werden:
Man beachte, dass in Abb. 6 die Steuerung des $\Phi$ADD(2j )mod N nicht vollständig "legal" ist (obwohl sie in [1] grafisch gut definiert ist wie die Schaltung in Abb. 1), da die Steuerung nicht auf alle Gatter innerhalb der $\Phi$ADD(2j )mod N-Teilschaltung angewendet wird und die korrekte gesteuerte Entwicklung nur für "legale" Eingänge erhalten wird, bei denen das Überlaufbit 0 ist.
Die gesamte Operation der n modularen Addierer wird im Fourier-Raum durchgeführt, daher sind zusätzliche QFT und inverse QFT in und aus dem Fourier-Raum erforderlich. Diese Schaltung kann mit dem grafischen Modellierer wie unten gezeigt einfach implementiert werden:
Man beachte, dass die modulare Additionsschaltung (Abb. 5) zwei Ein-Qubit-Register als Steuerung erhält, während auf der oberen Multiplikationsschicht (Abb. 7) das c2-Register n Qubits enthält, die dann auf der unteren modularen Additionsschicht kaskadiert werden.
Die modulare Potenzierung wird implementiert, indem die modulare Multiplikation 2n-mal für verschiedene Potenzen von a wiederholt wird. In der Schaltung für die modulare Multiplikation befindet sich das Register b anfangs im Zustand 0, und um es in jeder der 2n modularen Multiplikationen wiederzuverwenden, sollte es auf 0 zurückgesetzt werden. Dies kann durch einen kontrollierten Tausch zwischen den Registern b und x und die anschließende Anwendung der inversen modularen Multiplikation für den inversen Wert der geeigneten Potenz von a geschehen.
Modulare Potenzierung
Die modulare Potenzierung wird durchgeführt, indem die Zahl 1 in das Register b eingegeben wird, ein oberes 2n-Qubit-Register vorbereitet wird (durch eine Hadamard-Transformation) und das Paar der obigen modularen Multiplikationskonstruktion direkt 2n-mal angewendet wird - durch Kaskadierung des oberen 2n-Qubit-Registers, so dass jedes Qubit im Register die geeignete modulare Multiplikationsoperation steuert, und durch Anwendung einer inversen QFT auf das oberste Register (das Ergebnis des Quantenteils wird durch Messung dieses Registers erhalten). Der gesamte Shor-Algorithmus, dessen wichtigster Modellierungsteil die modulare Potenzierung ist, ist in Abb. 8 dargestellt.
Synthese
Die Synthese-Engine, die das oben beschriebene Modell als Input nimmt und eine optimale Implementierungsschaltung erzeugt, die dem Funktionsmodell entspricht, ist nicht Gegenstand dieses Berichts. Wir erwähnen hier nur, dass es für jeden Funktionsblock im Modell viele funktional äquivalente Implementierungen gibt (z. B. die Kompromisse zwischen der Anzahl der Hilfsqubits, die den Block implementieren, seiner Tiefe, der Anzahl der 2-Qubit-Gatter, die er enthält, und seiner Gesamtgenauigkeit). Die Aufgabe der Synthese-Engine ist es, die beste Implementierung für den Gesamtschaltkreis unter Berücksichtigung eines Budgets von Qubits, Tiefe, Laufzeit, Gesamttreue, algorithmischer Genauigkeit und Gesamtziel zu finden. Wir weisen auch darauf hin, dass die Optimierung auf dieser funktionalen Ebene viel leistungsfähiger ist als die Optimierung auf der Transpilerebene, da der Transpiler die Low-Level-Semantik der Schaltung intakt halten muss - im Gegensatz zur Erhaltung nur der funktionalen Semantik der Schaltung, wenn er Zugriff auf diese Semantik hat. Eine endgültige Implementierung des Algorithmus von Shor ist in Abb. 9 dargestellt.
Ressourcenabschätzung für eine fehlertolerante Realisierung der Shor'schen Schaltung
Schaltungen, die die modulare Potenzierung und den Shor-Algorithmus implementieren, wie die obige Implementierung, erfordern erhebliche Ressourcen in Bezug auf die Anzahl der Gatter und die Tiefe der Schaltung. Folglich würde eine Realisierung solcher Schaltungen zwangsläufig die Verwendung von Fehlerkorrekturcodes erfordern, was die erforderlichen Ressourcen um Größenordnungen erhöhen würde.
Ein kürzlich verfügbares Tool zur Ressourcenabschätzung für die fehlertolerante Implementierung von Quantenalgorithmen - der Azure Quantum Resource Estimator - wurde auf die obige Schaltung angewandt und ermöglicht einen Vergleich zwischen den Ressourcen, die für die "normale" verrauschte Implementierung der Schaltung und die fehlertolerante Implementierung benötigt werden. Für diese Analyse wurde ein Oberflächencode verwendet.
Erforderliche Ressourcen für die reguläre Durchführung
Unsere Implementierung der Beauregard-Schaltung [1] erfordert 4n+2 Qubits. Die Schaltung umfasst 4n2 modulare Addierer-Teilschaltungen (einschließlich der inversen Schaltungen). Jeder modulare Addierer enthält n+1 Phasengatter, n+1 cPhasengatter, 3(n+1) ccPhasengatter und zusätzlich 4 QFT-Funktionen (und inverse QFT-Funktionen). Da jede QFT n(n+1)/2 cPhasen-Gatter und n Hadamard-Gatter enthält, umfasst die gesamte Schaltung:
o $O(n^4)$ cPhasen-Gatter
o $O(n^3)$ ccPhasen-, Phasen- und Hadamard-Tore
o $O(n^2)$ ccx, cx und x Gatter.
Azure Resource Estimator Ergebnisse für n=4
Mit Hilfe der grafischen Modellierungs- und Synthese-Engine Classiq wurde die Shor-Implementierung für n=4 (mit insgesamt 18 Qubits) im QIR-Format erstellt. Die Schaltung umfasste die folgenden Phasengatter:
o 3. 244 C-Phasen-Tore
o 920 ccPhasen-Tore
o 320 Phasentore.
Azure Resource Estimator wurde auf die Schaltung mit Standardargumenten angewendet - unter der Annahme einer Fehlerrate von 0,001 für Ein- und Zwei-Qubit-Gatter sowie T-Gatter und Ein-Qubit-Messungen. Der erforderliche Gesamtfehler der Schaltung (Gesamtfehlerbudget) betrug 0,33.
Um dieses Fehlerbudget einzuhalten, beträgt nach dem Ressourcenschätzer der erforderliche Oberflächencodeabstand d=13 und die erforderliche Fehlerrate für logische Qubits $5,1 * 10^{-9}$. Zusätzlich werden 25 T-State-Fabriken (die parallel arbeiten) benötigt. Die erforderliche Fehlerrate für die T-Zustände beträgt $1,35 * 10^{-7}$.
Die Anzahl der physischen Qubits für ein logisches Qubit ist gegeben durch 2d2 = 338. Die Gesamtzahl der logischen Qubits in einer fehlertoleranten Schaltung beträgt 16 562 (ein planares Layout der ursprünglichen Schaltung erfordert 49 Qubits, die jeweils 338 physische Qubits benötigen). Diese Qubits tragen die Informationen während der gesamten Berechnung. Darüber hinaus werden viele weitere Qubits für die Erzeugung und Destillation von T-Zuständen durch die T-Fabriken benötigt. Diese T-Zustände werden immer dann verwendet, wenn ein T-Gate in der fehlertoleranten Schaltung eingesetzt wird (d. h. die T-Zustände interagieren mit den Qubits der logischen Schaltung und verschränken sich mit ihnen, um dann gemessen zu werden, um sie von den Qubits der logischen Schaltung zu entkoppeln). Um T-Zustände mit der erforderlichen Fehlerrate zu destillieren, sind 13.520 physikalische Qubits pro T-Zustand erforderlich. Somit beträgt die Gesamtzahl der für die T-Zustände erforderlichen physikalischen Qubits 338.000.
Die Gesamtzahl der physikalischen Qubits (T-Zustands-Qubits + Schaltkreis-Qubits) beträgt 354.562. Beachten Sie, dass die T-State-Qubits während der Anwendung der Schaltung viele Male wiederverwendet werden.
Ein wichtiger Punkt, der sich aus den Ergebnissen des Ressourcenschätzers ergibt, ist, dass eine fehlertolerante Schaltung 50.471 einzelne Qubit-Drehungen enthalten würde, die von den verschiedenen Phasengattern (einschließlich cphase und ccphase) in der ursprünglichen Schaltung ausgehen. Diese einzelnen Qubit-Rotationen würden fast alle T-Zustände verbrauchen, die für die gesamte Schaltung erforderlich sind. Diese Ergebnisse legen nahe, dass es vorteilhaft wäre, die Anzahl der verschiedenen Phasengatter in der Schaltung zu reduzieren. Dies kann z. B. durch die Verwendung der approximativen QFT-Funktionen (anstelle der exakten QFT) in der Schaltung erreicht werden. Alternativ könnte auch eine andere Implementierung des Shor-Algorithmus, die nicht auf der Addition in der Fourier-Basis, sondern auf anderen Arten von Adder-Schaltungen basiert, von Vorteil sein.
Zusammenfassung
Wir haben gezeigt, wie akademische Beschreibungen von Quantenalgorithmen nahtlos auf formale Weise modelliert werden können, wobei die Struktur und Denkweise des wissenschaftlich dargestellten Algorithmus beibehalten wird. In diesem Beitrag haben wir zwei wichtige Modellierungskonstrukte diskutiert, die in den meisten Quantenalgorithmen allgegenwärtig sind: Kaskade und Instanzen. Wir haben festgestellt, dass eine Reihe von etwa zehn solcher Konstrukte, die alle einfach zu verstehen sind, fast jeden bisher veröffentlichten Algorithmus abdecken. Mit solchen Modellierungskonstrukten können wir die Lücke zwischen der wissenschaftlichen Darstellung von Algorithmen und der tatsächlichen Ausführung auf Hardware und Simulatoren schließen, indem wir algorithmische Werkzeuge wie Synthesizer zum Aufbau konkreter Schaltungen aus dem Quantenalgorithmusmodell mit Ressourcenschätzern wie dem kürzlich vorgestellten Microsoft-Tool verbinden.
Quantenmodellierungskonstrukte und starke Synthesefähigkeiten schließen die Lücke zwischen den Absichten der Entwickler von Quantenalgorithmen, wie sie in akademischen Arbeiten veröffentlicht werden, und den tatsächlichen Implementierungen, die auf Quantencomputern, Simulatoren und Ressourcenschätzern ausgeführt werden können
Einführung
Quantenalgorithmen waren in den letzten dreißig Jahren weitgehend ein akademisches Unterfangen. Theoretiker haben wohldefinierte und bewährte Algorithmen veröffentlicht und sie in einer soliden wissenschaftlichen Sprache beschrieben. Diese Beschreibung umfasst Abbildungen, Beschriftungen, Texte, Gleichungen und andere Hilfsmittel, die den Wissenschaftlern zur Verfügung stehen, um die Korrektheit ihrer Arbeit formal zu beschreiben und zu beweisen. Leider beruht eine solche Beschreibung auf dem gegenseitigen Verständnis zwischen Wissenschaftlern und basiert auf einer formalen wissenschaftlichen Sprache. Diese Sprache ist nicht formal genug, um von Compilern verstanden zu werden und eine auf einem Quantencomputer ausführbare Beschreibung des Quantenalgorithmus zu erzeugen.
In diesem Beitrag stellen wir neue Modellierungskonstrukte und Redewendungen vor, die sich aus einer gründlichen Durchsicht vieler Quantenalgorithmen und Implementierungen ergeben, die im Laufe der Jahre veröffentlicht wurden. Selbst bei so singulären Algorithmen wie dem von Shor, Grover oder HHL - die alle relativ einfach angegeben werden können, wenn man von der internen Struktur abstrahiert - ergibt sich eine Fülle von Komplexitäten, wenn man die nächste Ebene von Details betrachtet - die modulare Potenzierung in Shors Algorithmus, das Orakel in Grovers Algorithmus und die Form der linearen Gleichungen in HHLs Algorithmus. Im Folgenden werden wir uns am Beispiel des Shor-Algorithmus orientieren, da er für jeden, der einen Einführungskurs in Quantenalgorithmen belegt, am einfachsten zu verstehen ist. Mithilfe von Microsofts Azure Quantum Resource Estimator zeigen wir, dass für die Ausführung des Shor-Algorithmus mit vier modularen Additionen 354.562 physische Qubits erforderlich sind, und wir ermitteln die spezifische Anzahl der benötigten Gatter. In diesem Beispiel zeigen wir nur die Modellierungskonstrukte, die wir in einem breiten Spektrum von Quantenalgorithmen für relevant halten.
Der Gesamtverdienst unserer Methode wird dadurch bestimmt, wie sehr das Modell dem Quantenschaltkreis ähnelt, wie er vom Konstrukteur, z. B. in einer wissenschaftlichen Arbeit, beschrieben wurde, und durch die Fähigkeit des Modells, alle formalen Anforderungen des Schaltkreises eindeutig zu erfassen.
Die Modellierungskonstrukte sowie die Synthese-Engine, die in der Lage ist, das Modell formal zu verstehen und eine konkrete, optimierte Quantenschaltkreis-Implementierung zu erzeugen, wurden alle in die Classiq-Plattform für den Entwurf von Quantenalgorithmen implementiert, so dass zum ersten Mal die Möglichkeit besteht, komplexe Quantenalgorithmen vom Gedanken bis zur Ausführung zu erstellen. Die von der Classiq-Plattform erstellten Quantenalgorithmen (z. B. Implementierungen des Shor-Algorithmus) sind bei weitem die komplexesten und umfangreichsten Quantenalgorithmen, die je erstellt wurden.
Implementierung des Shor'schen Algorithmus
Wir gehen auf die wichtigsten Konzepte und Werkzeuge ein, die in der grafischen Modellierung von Classiq verwendet werden, um eine Schaltung zu erzeugen, die den Shor-Algorithmus zur Faktorisierung einer durch n Bits dargestellten Zahl N implementiert. Die Schaltung folgt der Implementierung von Beauregard(https://arxiv.org/pdf/quant-ph/0205095 [1]) und benötigt 4n+2 Qubits. Der Unterschied zwischen den beiden Schaltkreisen besteht darin, dass der Originalschaltkreis von Beauregard den endgültigen inversen QFT-Schaltkreis auf einem einzelnen Qubit implementiert, indem er ein einzelnes Qubit 2n-mal misst und neu präpariert (und daher 2n+3 Qubits benötigt), während in unserer Implementierung die "reguläre" QFT auf 2n Qubits verwendet wird.
Die Schaltung implementiert den Quanten-Teil von Shors Algorithmus. Erinnern Sie sich daran, dass in Shors Algorithmus, um einen Faktor einer gegebenen n-Qubit-Zahl N zu finden, eine Zufallszahl a ausgewählt wird, die kleiner als N ist, und gcd(a,N) berechnet wird, wobei gcd den größten gemeinsamen Nenner bezeichnet. Wenn gcd(a,N) >1 ist, sind wir fertig - gcd(a,N) ist ein Faktor von N. Wenn nicht, führen wir den Quanten-Teil des Algorithmus durch - dessen Hauptteil die Berechnung von $|a^xmodN\rangle$ ist (dem Quanten-Teil folgt eine zusätzliche klassische Nachbearbeitung des gemessenen Ergebnisses).
Um eine solche Schaltung für ein beliebiges n zu konstruieren, muss man in der Lage sein, die Schaltung hierarchisch auszudrücken, angefangen bei den grundlegenden Quantenbausteinen auf der untersten Ebene (die Quantenbausteine sind grundlegende Gatter und Funktionen, die von der Synthese-Engine erkannt werden) bis hin zur gesamten Schaltung auf der obersten Ebene. Darüber hinaus muss man in der Lage sein, mit Registern statt mit einzelnen Qubits zu arbeiten, d. h. Gatter auf Register anzuwenden und gleichzeitig die Möglichkeit zu behalten, Register zu zerschneiden und Gatter auf ausgewählte Qubits anzuwenden. Die Werkzeuge, die eine solche Modellierung eines Schaltkreises ermöglichen, werden in jeder der Haupthierarchien/Schichten des Schaltkreises demonstriert, nämlich:
- Ein modularer Addierer im Fourier-Raum, der aus Basisgattern (hauptsächlich phasengesteuerte, phasengesteuerte und doppelt phasengesteuerte Gatter) und QFT aufgebaut ist.
- Modulare Multiplikation, die aus n modularen Addierern besteht.
- Modulare Potenzierung, konstruiert aus n modularen Multiplikationsschaltungen.
Die gesteuerte modulare Addierer-Schaltung
Beim modularen Addierer wird die Zahl a zu einem (n+1) Qubit-Quantenregister (dem b-Register ) addiert. Der Eingangszustand des Registers ist, wenn das höchstwertige Bit (MSB) von b den Wert Null hat. Dieses Qubit wird als Überlaufbit verwendet. Außerdem enthält die Schaltung zwei Steuerbits und ein Hilfsbit, das am Eingang und am Ausgang Null ist. Der modulare Addierer ist in der folgenden Schaltung dargestellt. Der dicke schwarze Balken unterscheidet zwischen dem Addierer (Balken auf der rechten Seite) und seiner Umkehrung, die die Subtraktion implementiert (Balken auf der linken Seite):
Bei c1=c2=1 funktioniert die Schaltung wie folgt (bei anderen Werten von ci werden die gesteuerten Vorgänge nicht aktiviert und die übrigen Vorgänge heben sich auf).
o Teilschaltkreis A: Addiert a zum (n+1) Qubit-Register b mit $\Phi(b)$.
o Sub-circuit B: Subtracts N from a+b and then adds N again if N < a+b – this is done by checking the MSB of a+b-N.
$$|1,1,\Phi (b),0\rangle \rightarrow |1,1,\Phi (b+a),0\rangle$$
Man beachte, dass sich das b-Register zu diesem Zeitpunkt im Zustand (a+b)mod N befindet, aber im Allgemeinen mit dem Hilfsquantum verschränkt ist.
o Teilschaltkreis C: Setzt das letzte/unterste Hilfsqubit auf $|0\rangle$ zurück (und entkoppelt es vom b-Register), indem es a vom Register subtrahiert, das höchstwertige Bit des b-Registers prüft (und gegebenenfalls das Hilfsbit umkehrt) und a wieder zum Register addiert.
Der Betrieb der gesamten Schaltung bei den "legalen" Eingangszuständen (bei denen das MSB von b Null ist) ist erforderlich:
$$|1,1,\Phi (b),0\rangle \rightarrow |1,1,\Phi ((b+a) mod N),0\rangle .$$
Der Hauptbaustein des modularen Addierers ist eine Addierschaltung (in der Fourier-Basis), die die Zahl a (kleiner als N) zu einem (n+1) Qubit-Quantenregister addiert, sowie deren Inverse (mit und ohne Steuerung). Der (ungesteuerte) Addierer ist ausschließlich aus Ein-Qubit-Phasentoren aufgebaut (hier - $|\Phi(b)\rangle = QFT|b\rangle $):
Die Zahl a ist hier "klassisch" in dem Sinne, dass sie nicht von einem Quantenregister getragen wird, sondern in den Phasen kodiert ist. In unserer Plattform wird der Addierer einfach durch das Kaskadenmodellierungswerkzeug realisiert, mit dem eine Operation vertikal dupliziert wird: Sie wird auf alle Qubits in einem Register angewendet, wie unten gezeigt (der Grund, warum es Kaskade und nicht z.B. forall heißt, wird später deutlich).
Der Eingang und der Ausgang oben sind W-Qubit-Register mit W, einem Parameter, der von oben in der Hierarchie festgelegt wird, und die Kaskadenanweisung wendet das Ein-Qubit-Phasentor auf jedes Qubit im Register an. Jedem der Qubits wird eine andere Phase zugeführt. Diese Phasen werden vom Benutzer als Teil der Modellierung in die Schaltung eingeführt. Die formalen Anschlussnamen der Gatter sind target_in und target_out.
Ein weiterer Baustein, der in der modularen Addierer-Teilschaltung (Abb. 1) verwendet wird, ist der kontrollierte und doppelt kontrollierte Addierer, bei dem die Phasengatter durch Gatter mit kontrollierter Phase (CPhase) ersetzt werden. Bei diesem Gatter steuert ein einzelnes Qubit die Phasen der Ziel-Qubits. Um ein Gatter wiederholt auf dasselbe Register anzuwenden, verwenden wir die Anweisung instances. Bei der Implementierung des gesteuerten Addierers werden die Phasen jedoch sequentiell in alle Qubits im Zielregister eingeführt, weshalb man sowohl Kaskade (Wiederholung auf Qubits) als auch Instanzen (Wiederholung von Gattern) zusammen verwenden muss.
Das einzelne Qubit im Steuerregister nimmt an allen W CPhase-Gattern der Sequenz teil, während jedes der W Qubits im Zielregister an genau einem Gatter teilnimmt.
Das gesamte Schema für die modulare Addiererschaltung aus Abb. 1 ist unten dargestellt. Beachten Sie, wie sehr diese Schaltung der akademischen Zeichnung in Abb. 1 ähnelt. Der Hauptunterschied besteht natürlich darin, dass diese Schaltung vollständig ausführbar ist und durch die Synthese-Engine bis zur besten konkreten Implementierung optimiert werden kann.
Die Schaltung besteht aus fünf Addierern (einschließlich kontrollierter und inverser Addierer) und zwei "twoQFT"-Funktionen, die die beiden Konstruktionen in der obigen Schaltung implementieren, indem sie das MSB-Qubit im b-Register überprüfen und das Hilfs-Qubit bei Bedarf invertieren (jede dieser Konstruktionen umfasst zwei QFT-Funktionen, die das b-Register in den Fourier-Raum und aus diesem heraus führen). Diese Namenskonvention wird in Abb. 5 demonstriert und in der nachfolgenden Legende erläutert.
Die gesteuerte modulare Multiplikatorschaltung
Die Schaltung, die die modulare Multiplikation implementiert, kann aus der n-maligen Wiederholung der Funktion des modularen Addierers, wie unten gezeigt, aufgebaut werden:
Man beachte, dass in Abb. 6 die Steuerung des $\Phi$ADD(2j )mod N nicht vollständig "legal" ist (obwohl sie in [1] grafisch gut definiert ist wie die Schaltung in Abb. 1), da die Steuerung nicht auf alle Gatter innerhalb der $\Phi$ADD(2j )mod N-Teilschaltung angewendet wird und die korrekte gesteuerte Entwicklung nur für "legale" Eingänge erhalten wird, bei denen das Überlaufbit 0 ist.
Die gesamte Operation der n modularen Addierer wird im Fourier-Raum durchgeführt, daher sind zusätzliche QFT und inverse QFT in und aus dem Fourier-Raum erforderlich. Diese Schaltung kann mit dem grafischen Modellierer wie unten gezeigt einfach implementiert werden:
Man beachte, dass die modulare Additionsschaltung (Abb. 5) zwei Ein-Qubit-Register als Steuerung erhält, während auf der oberen Multiplikationsschicht (Abb. 7) das c2-Register n Qubits enthält, die dann auf der unteren modularen Additionsschicht kaskadiert werden.
Die modulare Potenzierung wird implementiert, indem die modulare Multiplikation 2n-mal für verschiedene Potenzen von a wiederholt wird. In der Schaltung für die modulare Multiplikation befindet sich das Register b anfangs im Zustand 0, und um es in jeder der 2n modularen Multiplikationen wiederzuverwenden, sollte es auf 0 zurückgesetzt werden. Dies kann durch einen kontrollierten Tausch zwischen den Registern b und x und die anschließende Anwendung der inversen modularen Multiplikation für den inversen Wert der geeigneten Potenz von a geschehen.
Modulare Potenzierung
Die modulare Potenzierung wird durchgeführt, indem die Zahl 1 in das Register b eingegeben wird, ein oberes 2n-Qubit-Register vorbereitet wird (durch eine Hadamard-Transformation) und das Paar der obigen modularen Multiplikationskonstruktion direkt 2n-mal angewendet wird - durch Kaskadierung des oberen 2n-Qubit-Registers, so dass jedes Qubit im Register die geeignete modulare Multiplikationsoperation steuert, und durch Anwendung einer inversen QFT auf das oberste Register (das Ergebnis des Quantenteils wird durch Messung dieses Registers erhalten). Der gesamte Shor-Algorithmus, dessen wichtigster Modellierungsteil die modulare Potenzierung ist, ist in Abb. 8 dargestellt.
Synthese
Die Synthese-Engine, die das oben beschriebene Modell als Input nimmt und eine optimale Implementierungsschaltung erzeugt, die dem Funktionsmodell entspricht, ist nicht Gegenstand dieses Berichts. Wir erwähnen hier nur, dass es für jeden Funktionsblock im Modell viele funktional äquivalente Implementierungen gibt (z. B. die Kompromisse zwischen der Anzahl der Hilfsqubits, die den Block implementieren, seiner Tiefe, der Anzahl der 2-Qubit-Gatter, die er enthält, und seiner Gesamtgenauigkeit). Die Aufgabe der Synthese-Engine ist es, die beste Implementierung für den Gesamtschaltkreis unter Berücksichtigung eines Budgets von Qubits, Tiefe, Laufzeit, Gesamttreue, algorithmischer Genauigkeit und Gesamtziel zu finden. Wir weisen auch darauf hin, dass die Optimierung auf dieser funktionalen Ebene viel leistungsfähiger ist als die Optimierung auf der Transpilerebene, da der Transpiler die Low-Level-Semantik der Schaltung intakt halten muss - im Gegensatz zur Erhaltung nur der funktionalen Semantik der Schaltung, wenn er Zugriff auf diese Semantik hat. Eine endgültige Implementierung des Algorithmus von Shor ist in Abb. 9 dargestellt.
Ressourcenabschätzung für eine fehlertolerante Realisierung der Shor'schen Schaltung
Schaltungen, die die modulare Potenzierung und den Shor-Algorithmus implementieren, wie die obige Implementierung, erfordern erhebliche Ressourcen in Bezug auf die Anzahl der Gatter und die Tiefe der Schaltung. Folglich würde eine Realisierung solcher Schaltungen zwangsläufig die Verwendung von Fehlerkorrekturcodes erfordern, was die erforderlichen Ressourcen um Größenordnungen erhöhen würde.
Ein kürzlich verfügbares Tool zur Ressourcenabschätzung für die fehlertolerante Implementierung von Quantenalgorithmen - der Azure Quantum Resource Estimator - wurde auf die obige Schaltung angewandt und ermöglicht einen Vergleich zwischen den Ressourcen, die für die "normale" verrauschte Implementierung der Schaltung und die fehlertolerante Implementierung benötigt werden. Für diese Analyse wurde ein Oberflächencode verwendet.
Erforderliche Ressourcen für die reguläre Durchführung
Unsere Implementierung der Beauregard-Schaltung [1] erfordert 4n+2 Qubits. Die Schaltung umfasst 4n2 modulare Addierer-Teilschaltungen (einschließlich der inversen Schaltungen). Jeder modulare Addierer enthält n+1 Phasengatter, n+1 cPhasengatter, 3(n+1) ccPhasengatter und zusätzlich 4 QFT-Funktionen (und inverse QFT-Funktionen). Da jede QFT n(n+1)/2 cPhasen-Gatter und n Hadamard-Gatter enthält, umfasst die gesamte Schaltung:
o $O(n^4)$ cPhasen-Gatter
o $O(n^3)$ ccPhasen-, Phasen- und Hadamard-Tore
o $O(n^2)$ ccx, cx und x Gatter.
Azure Resource Estimator Ergebnisse für n=4
Mit Hilfe der grafischen Modellierungs- und Synthese-Engine Classiq wurde die Shor-Implementierung für n=4 (mit insgesamt 18 Qubits) im QIR-Format erstellt. Die Schaltung umfasste die folgenden Phasengatter:
o 3. 244 C-Phasen-Tore
o 920 ccPhasen-Tore
o 320 Phasentore.
Azure Resource Estimator wurde auf die Schaltung mit Standardargumenten angewendet - unter der Annahme einer Fehlerrate von 0,001 für Ein- und Zwei-Qubit-Gatter sowie T-Gatter und Ein-Qubit-Messungen. Der erforderliche Gesamtfehler der Schaltung (Gesamtfehlerbudget) betrug 0,33.
Um dieses Fehlerbudget einzuhalten, beträgt nach dem Ressourcenschätzer der erforderliche Oberflächencodeabstand d=13 und die erforderliche Fehlerrate für logische Qubits $5,1 * 10^{-9}$. Zusätzlich werden 25 T-State-Fabriken (die parallel arbeiten) benötigt. Die erforderliche Fehlerrate für die T-Zustände beträgt $1,35 * 10^{-7}$.
Die Anzahl der physischen Qubits für ein logisches Qubit ist gegeben durch 2d2 = 338. Die Gesamtzahl der logischen Qubits in einer fehlertoleranten Schaltung beträgt 16 562 (ein planares Layout der ursprünglichen Schaltung erfordert 49 Qubits, die jeweils 338 physische Qubits benötigen). Diese Qubits tragen die Informationen während der gesamten Berechnung. Darüber hinaus werden viele weitere Qubits für die Erzeugung und Destillation von T-Zuständen durch die T-Fabriken benötigt. Diese T-Zustände werden immer dann verwendet, wenn ein T-Gate in der fehlertoleranten Schaltung eingesetzt wird (d. h. die T-Zustände interagieren mit den Qubits der logischen Schaltung und verschränken sich mit ihnen, um dann gemessen zu werden, um sie von den Qubits der logischen Schaltung zu entkoppeln). Um T-Zustände mit der erforderlichen Fehlerrate zu destillieren, sind 13.520 physikalische Qubits pro T-Zustand erforderlich. Somit beträgt die Gesamtzahl der für die T-Zustände erforderlichen physikalischen Qubits 338.000.
Die Gesamtzahl der physikalischen Qubits (T-Zustands-Qubits + Schaltkreis-Qubits) beträgt 354.562. Beachten Sie, dass die T-State-Qubits während der Anwendung der Schaltung viele Male wiederverwendet werden.
Ein wichtiger Punkt, der sich aus den Ergebnissen des Ressourcenschätzers ergibt, ist, dass eine fehlertolerante Schaltung 50.471 einzelne Qubit-Drehungen enthalten würde, die von den verschiedenen Phasengattern (einschließlich cphase und ccphase) in der ursprünglichen Schaltung ausgehen. Diese einzelnen Qubit-Rotationen würden fast alle T-Zustände verbrauchen, die für die gesamte Schaltung erforderlich sind. Diese Ergebnisse legen nahe, dass es vorteilhaft wäre, die Anzahl der verschiedenen Phasengatter in der Schaltung zu reduzieren. Dies kann z. B. durch die Verwendung der approximativen QFT-Funktionen (anstelle der exakten QFT) in der Schaltung erreicht werden. Alternativ könnte auch eine andere Implementierung des Shor-Algorithmus, die nicht auf der Addition in der Fourier-Basis, sondern auf anderen Arten von Adder-Schaltungen basiert, von Vorteil sein.
Zusammenfassung
Wir haben gezeigt, wie akademische Beschreibungen von Quantenalgorithmen nahtlos auf formale Weise modelliert werden können, wobei die Struktur und Denkweise des wissenschaftlich dargestellten Algorithmus beibehalten wird. In diesem Beitrag haben wir zwei wichtige Modellierungskonstrukte diskutiert, die in den meisten Quantenalgorithmen allgegenwärtig sind: Kaskade und Instanzen. Wir haben festgestellt, dass eine Reihe von etwa zehn solcher Konstrukte, die alle einfach zu verstehen sind, fast jeden bisher veröffentlichten Algorithmus abdecken. Mit solchen Modellierungskonstrukten können wir die Lücke zwischen der wissenschaftlichen Darstellung von Algorithmen und der tatsächlichen Ausführung auf Hardware und Simulatoren schließen, indem wir algorithmische Werkzeuge wie Synthesizer zum Aufbau konkreter Schaltungen aus dem Quantenalgorithmusmodell mit Ressourcenschätzern wie dem kürzlich vorgestellten Microsoft-Tool verbinden.
Über "Der Podcast des Qubit-Typen"
Der Podcast wird von The Qubit Guy (Yuval Boger, unser Chief Marketing Officer) moderiert. In ihm diskutieren Vordenker der Quanteninformatik über geschäftliche und technische Fragen, die das Ökosystem der Quanteninformatik betreffen. Unsere Gäste geben interessante Einblicke in Quantencomputer-Software und -Algorithmen, Quantencomputer-Hardware, Schlüsselanwendungen für Quantencomputer, Marktstudien der Quantenindustrie und vieles mehr.
Wenn Sie einen Gast für den Podcast vorschlagen möchten, kontaktieren Sie uns bitte .
