Buch „Programmieren von Quantencomputern. Grundlegende Algorithmen und Codebeispiele "

Hallo Bewohner! Quantencomputer haben eine neue Computerrevolution ausgelöst, und Sie haben jetzt eine große Chance, sich dem technologischen Durchbruch anzuschließen. Entwickler, Computergrafikspezialisten und angehende IT-Profis finden in diesem Buch die praktischen Informationen zum Quantencomputer, die Programmierer benötigen. Anstatt Theorie und Formeln zu studieren, konzentrieren Sie sich sofort auf bestimmte Probleme, die die einzigartigen Fähigkeiten der Quantentechnologie demonstrieren.



Eric Johnston, Nick Harrigan und Mercedes Gimeno-Segovia helfen bei der Entwicklung der erforderlichen Fähigkeiten und der Intuition sowie bei der Beherrschung der Werkzeuge, die zur Erstellung von Quantenanwendungen erforderlich sind. Sie werden verstehen, wozu Quantencomputer in der Lage sind und wie sie im wirklichen Leben angewendet werden können. Das Buch besteht aus drei Teilen: - Programmieren von QPU: Grundlegende Konzepte zum Programmieren von Quantenprozessoren, Ausführen von Operationen mit Qubits und Quantenteleportation. - QPU-Grundelemente: algorithmische Grundelemente und Methoden, Amplitudenverstärkung, Quanten-Fourier-Transformation und Phasenschätzung. - QPU üben: Lösen spezifischer Probleme mit QPU-Grundelementen, Quantensuchmethoden und Shors Zerlegungsalgorithmus.

Echte Daten

Vollständige QPU-Anwendungen sind so konzipiert, dass sie mit realen Daten ohne Training arbeiten. Die realen Daten sind nicht immer auf die grundlegenden Ganzzahlen beschränkt, auf die wir bisher gekommen sind. Daher lohnt sich die Frage, wie komplexere Daten in QPU dargestellt werden sollen, und gute Datenstrukturen können genauso wichtig sein wie gute Algorithmen. In diesem Kapitel werden wir versuchen, zwei Fragen zu beantworten, die zuvor umgangen wurden:

1. Wie werden komplexe Datentypen im QPU-Register dargestellt? Eine positive ganze Zahl kann in einfacher binärer Codierung dargestellt werden. Aber was ist mit irrationalen Zahlen oder sogar zusammengesetzten Datentypen wie Vektoren oder Matrizen? Diese Frage erhält eine neue Tiefe, wenn man bedenkt, dass Überlagerung und relative Phase neue Quantencodierungsoptionen für diese Datentypen bieten können.
2. , QPU? , WRITE . , QPU . , , , QPU , .

Beginnen wir mit der ersten Frage. Bei der Beschreibung von QPU-Darstellungen für Datentypen mit zunehmender Komplexität werden wir uns mit der Einführung vollwertiger Quantendatenstrukturen und dem Konzept des Quanten-Direktzugriffsspeichers (QRAM) befassen. Quantum RAM ist eine wichtige Ressource für viele praktische QPU-Anwendungen.



Das Material in den folgenden Kapiteln hängt stark von den in diesem Kapitel vorgestellten Datenstrukturen ab. Beispielsweise ist die sogenannte komplexe Amplitudencodierung, die für Vektordaten beschrieben wird, von zentraler Bedeutung für alle in Kapitel 13 vorgestellten Anwendungen des quantenmaschinellen Lernens.

Nicht-Zieldaten

Wie codiere ich nicht ganzzahlige numerische Daten im QPU-Register? Die beiden Standardmethoden zur Darstellung solcher Werte in Binärform sind Festkomma- und Gleitkomma-Darstellungen. Obwohl die Gleitkomma-Darstellung flexibler ist (und an den Wertebereich angepasst werden kann, der mit einer bestimmten Anzahl von Bits dargestellt werden muss), ist die Festkomma-Darstellung aufgrund des hohen Werts der Qubits und unseres Wunsches nach Einfachheit ein besserer Ausgangspunkt.



Festkommazahlen werden häufig in Q-Notation beschrieben (Q bedeutet in diesem Fall leider nicht "Quantum"). Dies hilft, die Unklarheit darüber zu beseitigen, wo die Bruchbits enden und die Ganzzahlbits beginnen. Die Notation Qn.m bezeichnet ein n-Bit-Register, dessen m Bits für den Bruchteil bestimmt sind (und daher enthalten die verbleibenden (n - m) den ganzzahligen Teil). Natürlich können Sie dieselbe Notation verwenden, um anzugeben, wie das QPU-Register zum Codieren einer Festkommazahl verwendet werden soll. Zum Beispiel in Abb. 9.1 zeigt ein Acht-Qubit-QPU-Register, das den Wert 3.640625 in der Festkomma-Darstellung Q8.6 codiert.



In dem angegebenen Beispiel kann die ausgewählte Zahl in einer Festpunktdarstellung genau codiert werden, da 3.640625 =Natürlich wird solches Glück nicht immer gefunden. Durch Erhöhen der Anzahl von Bits im ganzzahligen Teil eines Festkommaregisters wird der Bereich von ganzzahligen Werten erweitert, die durch dieses dargestellt werden können, während durch Erhöhen der Anzahl von Bits im gebrochenen Teil die Genauigkeit des gebrochenen Teils einer Zahl verbessert wird. Je mehr Qubits im Bruchteil enthalten sind, desto wahrscheinlicher ist es, dass eine Kombination die angegebene Zahl genau wiedergeben kann.





Obwohl wir in den folgenden Kapiteln kurz auf die Verwendung der Festpunktdarstellung eingehen werden, spielt sie eine äußerst wichtige Rolle beim Experimentieren mit realen Daten in kleinen QPU-Registern. Wenn Sie mit verschiedenen Codierungsmethoden arbeiten, müssen Sie sorgfältig überwachen, welche spezifische Codierung für Daten in einem bestimmten QPU-Register verwendet wurde, um den Status seiner Qubits korrekt zu interpretieren.

QRAM

QPU-Register können Darstellungen verschiedener numerischer Werte speichern, aber wie speichern Sie diese Werte in ihnen? Handinitialisierte Daten sind sehr schnell veraltet. Was wir wirklich brauchen, ist die Fähigkeit, Werte aus dem Speicher zu lesen und gespeicherte Werte an einer binären Adresse abzurufen. Der Programmierer arbeitet mit herkömmlichem Direktzugriffsspeicher unter Verwendung von zwei Registern: eines wird mit einer Speicheradresse initialisiert, und das andere bleibt nicht initialisiert. Der Direktzugriffsspeicher schreibt in das zweite Register Binärdaten, die an der durch das erste Register angegebenen Adresse gespeichert sind, wie in Fig. 1 gezeigt. 9.2.





Kann der herkömmliche Speicher zum Speichern der Werte verwendet werden, die zum Initialisieren der QPU-Register vorgesehen sind? Natürlich sieht die Idee attraktiv aus.



Wenn Sie das QPU-Register mit nur einem herkömmlichen Wert (Zweierkomplement, Festkomma oder einfache Binärcodierung) initialisieren möchten, ist RAM in Ordnung. Der gewünschte Wert wird einfach im Speicher gespeichert, und write () und read () werden zum Schreiben oder Lesen aus dem QPU-Register verwendet. Es ist dieser begrenzte Mechanismus, der bisher vom QCEngine-JavaScript-Code verwendet wurde, um mit QPU-Registern zu interagieren.



Beispielsweise ruft der Beispielcode in Listing 9.1, der ein Array a empfängt und die Operation a [2] + = 1; implementiert, implizit dieses Array von Werten aus dem RAM ab, um das QPU-Register zu initialisieren. Die Schaltung ist in Abb. 9.3.

Beispielcode

Dieses Beispiel kann online unter http://oreilly-qc.github.io?p=9-1 erstellt werden.

Listing 9.1. Verwenden von QPU zum Erhöhen der Anzahl im Speicher

var a = [4, 3, 5, 1];

qc.reset(3);
var qreg = qint.new(3, 'qreg');

qc.print(a);
increment(2, qreg);
qc.print(a);

function increment(index, qreg)
{
      qreg.write(a[index]);
      qreg.add(1);
      a[index] = qreg.read();
}

Es ist anzumerken, dass in diesem einfachen Fall nicht nur der herkömmliche RAM zum Speichern der Ganzzahl verwendet wird, sondern auch der herkömmliche Prozessor das Array indiziert, um die QPU des gewünschten Werts auszuwählen und zu übertragen.



Diese Verwendung von RAM ermöglicht zwar die Initialisierung der QPU-Register auf einfache Binärwerte, weist jedoch schwerwiegende Einschränkungen auf. Was ist, wenn Sie das QPU-Register mit der Überlagerung gespeicherter Werte initialisieren müssen? Angenommen, im RAM wird der Wert 3 (110) an der Adresse 0x01 und der Wert 5 (111) an der Adresse 0x11 gespeichert. Wie bereite ich das Eingangsregister in einer Überlagerung dieser beiden Werte vor?



Mit herkömmlichem RAM und der klobigen traditionellen write () -Operation funktioniert dies nicht. Quantenprozessoren benötigen, genau wie ihre Röhrenvorfahren, grundlegend neue Speichergeräte - Quantenprozessoren. Mit Meet Quantum Random Access Memory (QRAM) können Sie Daten auf Quantenebene lesen und schreiben. Es gibt bereits einige Ideen, wie QRAM physisch erstellt werden kann, aber es ist erwähnenswert, dass sich die Geschichte möglicherweise wiederholt und unglaublich leistungsstarke Quantenprozessoren erscheinen können, lange bevor es funktionsfähige Quantenspeicherhardware gibt.



Es lohnt sich, etwas genauer zu erklären, was QRAM tut. Wie ein herkömmlicher Speicher empfängt der QRAM zwei Register als Eingabe: das QPU-Adressregister für die Speicheradresse und das QPU-Ausgangsregister, das den an der angegebenen Adresse gespeicherten Wert zurückgibt. Für QRAM bestehen beide Register aus Qubits. Dies bedeutet, dass es im Adressregister möglich ist, eine Überlagerung von Speicherzellen einzustellen und damit eine Überlagerung der entsprechenden Werte im Ausgangsregister zu erhalten (Abb. 9.4).





QRAM ermöglicht also tatsächlich das Lesen der in Überlagerung gespeicherten Werte. Die genauen komplexen Amplituden der Überlagerung, die im Ausgangsregister erhalten werden sollen, werden durch die Überlagerung bestimmt, die im Adressregister bereitgestellt wird. In Abb. Abbildung 9.2 zeigt die Unterschiede, wenn dieselbe Inkrementierungsoperation in Listing 9.1 (Abbildung 9.5) ausgeführt wird, jedoch anstelle von QPU-Lese- / Schreiboperationen QRAM für den Zugriff auf die Daten verwendet wird. Der Buchstabe "A" bezeichnet das Register, in dem die QRAM-Adresse (oder Überlagerung) übertragen wird. Der Buchstabe "D" bezeichnet das Register, in dem QRAM die entsprechende Überlagerung gespeicherter Werte (Daten) zurückgibt.

Beispielcode

Dieses Beispiel kann online unter oreilly-qc.github.io?p=9-2 erstellt werden .

Listing 9.2. Verwenden von QPU zum Inkrementieren einer Zahl aus dem QRAM - Das Adressregister kann eine Überlagerung enthalten, wodurch das Ausgangsregister eine Überlagerung gespeicherter Werte enthält

var a = [4, 3, 5, 1];
var reg_qubits = 3;
qc.reset(2 + reg_qubits + qram_qubits());
var qreg = qint.new(3, 'qreg');
var addr = qint.new(2, 'addr');
var qram = qram_initialize(a, reg_qubits);

qreg.write(0);
addr.write(2);
addr.hadamard(0x1);

qram_load(addr, qreg);
qreg.add(1);

Diese Beschreibung von QRAM mag zu vage erscheinen - was ist Quantenspeicherhardware? In diesem Buch wird nicht beschrieben, wie QRAM in der Praxis erstellt wird (da beispielsweise die meisten C ++ - Bücher keine detaillierte Beschreibung der Funktionsweise des herkömmlichen Speichers enthalten). Codebeispiele wie das in Listing 9.2 werden mit einem vereinfachten Modell ausgeführt, das das Verhalten von QRAM nachahmt. Es gibt jedoch Prototypen von QRAM-Technologien.



Während der Quantenspeicher eine kritische Komponente jeder ernsthaften QPU sein wird, werden sich die Implementierungsdetails wahrscheinlich ändern, wie bei jedem Quantencomputer. Was uns wichtig ist, ist die Idee einer grundlegenden Ressource, die sich wie in Abb. 1 dargestellt verhält. 9.4 und die leistungsstarken Anwendungen, die darauf aufbauen können.

Mit dem verfügbaren Quantenspeicher können Sie komplexe Quantendatenstrukturen aufbauen. Von besonderem Interesse sind Strukturen, mit denen Sie Vektor- und Matrixdaten darstellen können.

Vektorkodierung

Angenommen, Sie möchten das QPU-Register initialisieren, um einen einfachen Vektor wie Gleichung 9.1 darzustellen.



Formel 9.1. Ein Beispiel eines Vektors zum Initialisieren des QPU-Registers.





Daten in dieser Form werden häufig in Anwendungen für quantenmaschinelles Lernen gefunden.

Die vielleicht naheliegendste Methode zum Codieren von Vektordaten besteht darin, jede Komponente als separates QPU-Register mit einer geeigneten binären Darstellung darzustellen. Wir werden diese (wahrscheinlich offensichtlichste) Methodenzustandscodierung für Vektoren nennen. Der Vektor aus dem obigen Beispiel kann in vier Zwei-Qubit-Registern codiert werden, wie in Fig. 1 gezeigt. 9.6.





Eines der Probleme bei der naiven Zustandscodierung besteht darin, dass Qubits verschwendet werden - die wertvollste Ressource einer QPU. Eines der Pluspunkte traditioneller zustandscodierter Vektoren ist jedoch, dass sie keinen Quantenspeicher benötigen. Die Vektorkomponenten können einfach im Standardspeicher gespeichert werden und ihre separaten Werte können verwendet werden, um die Vorbereitung jedes einzelnen QPU-Registers zu steuern. Dieser Vorteil liegt jedoch auch dem schwerwiegendsten Fehler bei der Codierung des Vektorzustands zugrunde: Das Speichern von Vektordaten auf diese traditionelle Weise verhindert, dass wir die nicht traditionellen Funktionen von QPUs nutzen können. Um die Leistung von QPU nutzen zu können, müssen Sie in der Lage sein, die relativen Phasen von Überlagerungen zu manipulieren. Dies ist nicht einfach.wenn jede Komponente eines Vektors Ihren Quantenprozessor tatsächlich als eine Sammlung traditioneller Binärregister behandelt!



Stattdessen müssen Sie auf die Quantenebene absteigen. Angenommen, die Vektorkomponenten werden in der Überlagerung der Amplituden eines QPU-Registers gespeichert. Da ein QPU-Register von n Qubits in einer Überlagerung mit 2n Amplituden existieren kann (und daher 2n Kreise für Experimente mit zirkulärer Aufzeichnung vorhanden sind), ist es möglich, die Codierung eines Vektors mit n Komponenten in einem QPU-Register mit Ceil (log (n)) Qubits darzustellen.



Für das Vektorbeispiel aus Formel 9.1 würde dieser Ansatz ein Zwei-Qubit-Register erfordern - die Idee besteht darin, ein geeignetes Quantenschema zum Codieren der Vektordaten in Abbildung 1 zu finden. 9.7.





Nennen wir diese einzigartige Quantenvektordatencodierung eine komplexe Amplitudencodierung. Es ist wichtig, die Unterschiede zwischen der komplexen Amplitudencodierung und der konventionelleren Zustandscodierung zu erkennen. Tabelle 9.1 vergleicht die beiden Codierungsmethoden für verschiedene Vektordaten. Das letzte Beispiel für die Zustandscodierung erfordert vier 7-kbit-Register, von denen jedes eine Festkomma-Darstellung von Q7.7 verwendet.



Tabelle 9.1. Unterschiede zwischen Vektordatencodierungsmethoden (komplexe Amplitudencodierung und Zustandscodierung)





Um Vektoren mit komplexer Amplitudencodierung in QCEngine zu erhalten, können Sie die praktische Funktion amplitude_encode () verwenden. Das Programm in Listing 9.3 verwendet einen Wertevektor und eine Referenz auf ein QPU-Register (das groß genug sein muss) und bereitet dieses Register vor, indem es eine komplexe Amplitudencodierung für den Vektor durchführt.

Beispielcode

Dieses Beispiel kann online unter oreilly-qc.github.io?p=9-3 erstellt werden .



Listing 9.3. Vorbereiten von Vektoren mit komplexer Amplitudencodierung in QCEngine

//     ,    
//   2
var vector = [-1.0, 1.0, 1.0, 5.0, 5.0, 6.0, 6.0, 6.0];

//        
//  
var num_qubits = Math.log2(vector.length);
qc.reset(num_qubits);
var amp_enc_reg = qint.new(num_qubits, 'amp_enc_reg');

//      amp_enc_reg
amplitude_encode(vector, amp_enc_reg);

In diesem Beispiel wird der Vektor einfach als JavaScript-Array übergeben, das im herkömmlichen Speicher gespeichert ist - obwohl wir angegeben haben, dass die komplexe Amplitudencodierung vom QRAM abhängt. Wie führt QCEngine eine komplexe Amplitudencodierung durch, wenn dem Programm nur der RAM Ihres Computers zur Verfügung steht? Während es möglich ist, ein komplexes Amplitudencodierungsschema ohne QRAM zu erzeugen, kann dies sicherlich nicht effizient durchgeführt werden. QCEngine bietet ein langsames, aber funktionsfähiges Modell dessen, was mit dem QRAM-Zugriff erreicht werden kann.

Einschränkungen der komplexen Amplitudencodierung

Die Idee hinter der komplexen Amplitudencodierung sieht auf den ersten Blick gut aus - sie verwendet weniger Qubits und bietet Quantenwerkzeuge für die Arbeit mit Vektordaten. In jeder Anwendung, die diesen Mechanismus verwendet, sind zwei wichtige Faktoren zu berücksichtigen.

Problem 1: Quantenergebnisse

Möglicherweise haben Sie bereits die erste dieser Einschränkungen bemerkt: Quantenüberlagerungen können von READ im Allgemeinen nicht gelesen werden. Wieder unser Hauptfeind! Wenn Sie die Vektorkomponenten über die Quantenüberlagerung verteilen, können sie nicht erneut gelesen werden. Dies verursacht natürlich keine besonderen Probleme beim Übertragen von Vektordaten an den Eingang eines anderen QPU-Programms aus dem Speicher. Sehr oft erzeugen QPU-Anwendungen, die komplexe AM-codierte Vektordaten am Eingang empfangen, auch komplexe AM-codierte Vektordaten am Ausgang.



Die Verwendung einer komplexen Amplitudencodierung schränkt daher unsere Fähigkeit, die Ausgabe von Anwendungen mit einer READ-Operation zu lesen, stark ein. Glücklicherweise ist es oft möglich, nützliche Informationen aus komplexen Amplitudencodierungsergebnissen zu extrahieren. Wie Sie in den folgenden Kapiteln sehen werden, können Sie die globalen Eigenschaften von auf diese Weise codierten Vektoren herausfinden, obwohl Sie die einzelnen Komponenten nicht erkennen können. Eine komplexe Amplitudencodierung ist jedoch kein Allheilmittel, und ihre erfolgreiche Anwendung erfordert Aufmerksamkeit und Einfallsreichtum.

Problem 2: die Anforderung, Vektoren zu normalisieren

Das zweite Problem, das mit der komplexen Amplitudencodierung verbunden ist, ist in der Tabelle versteckt. 9.1. Schauen Sie sich die komplexe Amplitudencodierung der ersten beiden Vektoren in der Tabelle genauer an: [0,1,2,3] und [6,1,1,4]. Können die komplexen Amplituden eines Zwei-Qubit-QPU-Registers die Werte [0,1,2,3] oder die Werte [6,1,1,4] annehmen? Leider gibt es keine. In den vorhergehenden Kapiteln haben wir normalerweise die Diskussion der Amplituden und relativen Phasen zugunsten einer intuitiveren Zirkularnotation umgangen. Dieser Ansatz war zwar intuitiver, schützte Sie jedoch vor einer wichtigen numerischen Regel für komplexe Amplituden: Die Quadrate der komplexen Amplituden eines Registers müssen sich zu 1 addieren. Diese als Normalisierung bezeichnete Anforderung ist sinnvoll, wenn Sie sich daran erinnern, dass die Quadrate der Amplituden im Register den Wahrscheinlichkeiten des Lesens entsprechen. unterschiedliche Ergebnisse.Da ein Ergebnis erhalten werden muss, sollten sich diese Wahrscheinlichkeiten (und folglich die Quadrate aller komplexen Amplituden) zu 1 addieren. Wenn eine bequeme Zirkularnotation verwendet wird, kann die Normalisierung leicht vergessen werden, sie legt jedoch eine wichtige Einschränkung für den Vektor fest Auf die Daten kann eine komplexe Amplitudencodierung angewendet werden. Die Gesetze der Physik erlauben es nicht, ein Register zu erstellen, das sich mit komplexen Amplituden [0,1,2,3] oder [6,1,1,4] überlagert.Überlagerung mit komplexen Amplituden [0,1,2,3] oder [6,1,1,4].Überlagerung mit komplexen Amplituden [0,1,2,3] oder [6,1,1,4].



Anwenden einer komplexen Amplitudencodierung auf zwei Problemvektoren aus Tabelle. 9.1 müssen Sie sie zuerst normalisieren, indem Sie jede Komponente durch die Summe der Quadrate aller Komponenten dividieren. Beispielsweise müssen Sie bei der komplexen Amplitudencodierung des Vektors [0,1,2,3] zunächst alle Komponenten durch 3,74 teilen, um einen normalisierten Vektor [0,00, 0,27, 0,53, 0,80] zu erhalten, der jetzt für die Codierung in komplexen Überlagerungsamplituden geeignet ist.



Hat die Normalisierung von Vektordaten unerwünschte Auswirkungen? Es sieht so aus, als hätten sich die Daten komplett geändert! Tatsächlich lässt die Normalisierung die meisten wichtigen Informationen unverändert (in der geometrischen Darstellung wird nur die Länge des Vektors skaliert, wobei die Richtung unverändert bleibt). Können wir davon ausgehen, dass die normalisierten Daten die Originaldaten vollständig ersetzen? Dies hängt von den Anforderungen der jeweiligen QPU-Anwendung ab, in der Sie sie verwenden möchten. Denken Sie daran, dass Sie den numerischen Wert des Normalisierungsfaktors bei Bedarf in einem anderen Register speichern können.

Komplexe Amplitudencodierung und zirkuläre Aufzeichnung

Wenn Sie anfangen, genauer über die numerischen Werte der komplexen Amplituden der Register nachzudenken, kann es hilfreich sein, sich daran zu erinnern, wie komplexe Amplituden in Zirkularschreibweise dargestellt werden, und eine mögliche Gefahr zu bemerken. Die gefüllten Bereiche in Zirkularnotation repräsentieren die Quadrate der Amplituden der komplexen Amplituden des Quantenzustands. In Situationen wie der Codierung komplexer Amplituden, in denen die komplexen Amplituden die Komponenten eines Vektors mit reellen Werten darstellen müssen, bedeutet dies, dass die gefüllten Bereiche durch das Quadrat der entsprechenden Komponente des Vektors und nicht durch die Komponente selbst bestimmt werden. In Abb. 9.8 zeigt, wie die Darstellung des Vektors [0,1,2,3] nach Normalisierung in Zirkularschreibweise richtig interpretiert wird.





Sie wissen jetzt genug über komplexe amplitudencodierte Vektoren, um die QPU-Anwendungen zu verstehen, die in diesem Buch vorgestellt werden. Für viele Anwendungen, insbesondere im Zusammenhang mit quantenmaschinellem Lernen, ist es jedoch erforderlich, einen Schritt weiter zu gehen und QPU zu verwenden, um nicht nur Vektoren, sondern auch ganze Datenmatrizen zu manipulieren. Wie codieren Sie zweidimensionale Arrays von Zahlen?



»Weitere Details zum Buch finden Sie auf der Website des Verlags.

» Inhaltsverzeichnis

» Auszug



für Einwohner 25% Rabatt auf den Gutschein - Programmierung



Nach Zahlung der Papierversion des Buches wird ein E-Book per E-Mail verschickt.