„Ich denke, ich kann mit Sicherheit sagen, dass niemand die Quantenmechanik versteht.“ – Richard Feynman
Das Thema Quantencomputing hat Technikautoren und Journalisten schon immer fasziniert. Sein Rechenpotenzial und seine Komplexität verliehen ihm eine gewisse mystische Aura. Allzu oft beschreiben Leitartikel und Infografiken ausführlich die verschiedenen Perspektiven dieser Branche, gehen dabei aber kaum auf ihre praktische Anwendung ein: Dies kann den weniger aufmerksamen Leser irreführen.
Populärwissenschaftliche Artikel lassen Beschreibungen von Quantensystemen aus und machen Aussagen wie:
Ein normales Bit kann eine 1 oder eine 0 sein, aber ein Qubit kann gleichzeitig eine 1 und eine 0 sein.
Wenn Sie großes Glück haben (wobei ich mir nicht sicher bin), wird Ihnen Folgendes gesagt:
Das Qubit befindet sich in einer Überlagerung zwischen „1“ und „0“.
Keine dieser Erklärungen erscheint plausibel, da wir versuchen, ein quantenmechanisches Phänomen mithilfe einer Sprache zu formulieren, die in einer sehr traditionellen Welt entwickelt wurde. Um die Prinzipien des Quantencomputings klar zu erklären, ist es notwendig, eine andere Sprache zu verwenden – die mathematische.
In diesem Tutorial behandle ich die mathematischen Werkzeuge, die zum Modellieren und Verstehen von Quantencomputersystemen erforderlich sind, und erkläre, wie man die Logik des Quantencomputers veranschaulicht und anwendet. Darüber hinaus werde ich ein Beispiel für einen Quantenalgorithmus geben und Ihnen erklären, welche Vorteile er gegenüber einem herkömmlichen Computer hat.
Ich werde mein Bestes tun, um dies alles in klarer Sprache zu erklären, hoffe aber dennoch, dass die Leser dieses Artikels ein grundlegendes Verständnis der linearen Algebra und der digitalen Logik haben (lineare Algebra wird behandelt). , über digitale Logik - ).
Lassen Sie uns zunächst die Prinzipien der digitalen Logik durchgehen. Es basiert auf der Verwendung elektrischer Schaltkreise zur Durchführung von Berechnungen. Um unsere Beschreibung abstrakter zu gestalten, vereinfachen wir den Zustand des elektrischen Kabels auf „1“ oder „0“, was den Zuständen „ein“ oder „aus“ entspricht. Indem wir Transistoren in einer bestimmten Reihenfolge anordnen, erstellen wir sogenannte Logikelemente, die einen oder mehrere Eingangssignalwerte annehmen und diese basierend auf bestimmten Regeln der Booleschen Logik in ein Ausgangssignal umwandeln.
Gängige Logikgatter und ihre Zustandstabellen
Basierend auf den Ketten solcher Grundelemente können komplexere Elemente erstellt werden, und basierend auf den Ketten komplexerer Elemente können wir letztendlich mit einem hohen Abstraktionsgrad erwarten, ein Analogon des Zentralprozessors zu erhalten.
Wie ich bereits erwähnt habe, brauchen wir eine Möglichkeit, digitale Logik mathematisch darzustellen. Lassen Sie uns zunächst die traditionelle mathematische Logik einführen. Mithilfe der linearen Algebra lassen sich die klassischen Bits mit den Werten „1“ und „0“ als zwei Spaltenvektoren darstellen:
wo die Zahlen auf der linken Seite sind Vektor. Indem wir unsere Bits auf diese Weise darstellen, können wir mithilfe von Vektortransformationen logische Operationen an den Bits modellieren. Bitte beachten Sie: Obwohl die Verwendung von zwei Bits in Logikgattern viele Operationen ausführen kann (UND, NICHT, XOR usw.), können bei Verwendung eines Bits nur vier Operationen ausgeführt werden: Identitätsumwandlung, Negation, Berechnung der Konstante „0“ und Berechnung der Konstante „1“. Bei einer Identitätsumwandlung bleibt das Bit unverändert, bei einer Negation ändert sich der Bitwert ins Gegenteil (von „0“ nach „1“ oder von „1“ nach „0“) und die Berechnung der Konstante „1“ oder „0“ setzt das Bit unabhängig von seinem vorherigen Wert auf „1“ oder „0“.
| Identitätsschutz | Identitätstransformation |
| die Negierung | Verweigerung |
| Konstante-0 | Berechnung der Konstante „0“ |
| Konstante-1 | Berechnung der Konstante „1“ |
Basierend auf unserer vorgeschlagenen neuen Darstellung eines Bits ist es recht einfach, mithilfe einer Vektortransformation Operationen am entsprechenden Bit durchzuführen:
Bevor wir weitermachen, werfen wir einen Blick auf das Konzept , was einfach bedeutet, dass es zur Gewährleistung der Reversibilität einer Operation oder eines Logikelements notwendig ist, eine Liste von Eingangssignalwerten basierend auf den Ausgangssignalen und den Namen der verwendeten Operationen zu bestimmen. Daraus können wir schließen, dass die Identitätstransformation und Negation reversibel sind, die Operationen zur Berechnung der Konstanten „1“ und „0“ jedoch nicht. Dank an In der Quantenmechanik nutzen Quantencomputer ausschließlich reversible Operationen, daher konzentrieren wir uns darauf. Als nächstes wandeln wir irreversible Elemente in reversible Elemente um, damit sie von einem Quantencomputer verwendet werden können.
Mit Einzelne Bits können durch viele Bits dargestellt werden:
Nachdem wir nun fast alle notwendigen mathematischen Konzepte kennen, kommen wir zu unserem ersten Quantenlogikgatter. Dies ist der Betreiber oder kontrolliertes Nicht (NOT), was im Reversible- und Quantencomputing von großer Bedeutung ist. Das CNOT-Element gilt für zwei Bits und gibt zwei Bits zurück. Das erste Bit wird als „Kontroll“-Bit bezeichnet, das zweite als „Kontroll“-Bit. Wenn das Steuerbit auf „1“ gesetzt ist, ändert das Steuerbit seinen Wert; Ist das Steuerbit auf „0“ gesetzt, wird das Steuerbit nicht verändert.
Dieser Operator kann als folgender Transformationsvektor dargestellt werden:
Um alles zu demonstrieren, was wir bisher behandelt haben, zeige ich Ihnen, wie Sie das CNOT-Element für mehrere Bits verwenden:
Um das bereits Gesagte zusammenzufassen: Im ersten Beispiel zerlegen wir |10⟩ in Teile seines Tensorprodukts und verwenden die CNOT-Matrix, um einen neuen entsprechenden Zustand des Produkts zu erhalten; Wir faktorisieren es dann gemäß der zuvor angegebenen Tabelle der CNOT-Werte auf |11⟩.
Wir haben uns also an alle mathematischen Regeln erinnert, die uns helfen werden, traditionelles Rechnen und gewöhnliche Bits zu verstehen, und können endlich zum modernen Quantencomputing und den Qubits übergehen.
Wenn Sie bis hierhin gelesen haben, habe ich eine gute Nachricht für Sie: Qubits lassen sich leicht mathematisch ausdrücken. Wenn ein klassisches Bit (cbit) auf |1⟩ oder |0⟩ gesetzt werden kann, befindet sich das Qubit im Allgemeinen einfach in Überlagerung und kann vor der Messung sowohl |0⟩ als auch |1⟩ sein. Nach der Messung fällt es in |0⟩ oder |1⟩ zusammen. Mit anderen Worten, ein Qubit kann als lineare Kombination von |0⟩ und |1⟩ gemäß der folgenden Formel dargestellt werden:
wo ein₀ и a₁ stellen jeweils die Amplituden |0⟩ und |1⟩ dar. Diese kann man sich als „Quantenwahrscheinlichkeiten“ vorstellen, die die Wahrscheinlichkeit darstellen, dass ein Qubit nach der Messung in einen der Zustände kollabiert, da in der Quantenmechanik ein überlagertes Objekt nach seiner Fixierung in einen der Zustände kollabiert. Erweitern wir diesen Ausdruck und erhalten wir Folgendes:
Um meine Erklärung zu vereinfachen, verwende ich in diesem Artikel diese Darstellung.
Für dieses Qubit besteht die Möglichkeit, dass es auf den Wert zusammenbricht ein₀ nach der Messung ist gleich |a₀|² und die Möglichkeit eines Zusammenbruchs auf den Wert a₁ ist gleich |a₁|². Zum Beispiel für das folgende Qubit:
Die Wahrscheinlichkeit, in „1“ zu kollabieren, ist gleich |1/ √2|² oder ½, also 50/50.
Da sich im klassischen System alle Wahrscheinlichkeiten zu Eins addieren müssen (für eine vollständige Wahrscheinlichkeitsverteilung), können wir daraus schließen, dass sich die Quadrate der Absolutwerte der Amplituden |0⟩ und |1⟩ zu Eins addieren müssen. Basierend auf diesen Informationen können wir die folgende Gleichung formulieren:
Wenn Sie sich mit Trigonometrie auskennen, werden Sie feststellen, dass diese Gleichung dem Satz des Pythagoras (a²+b²=c²) entspricht, das heißt, wir können die möglichen Zustände des Qubits grafisch als Punkte auf dem Einheitskreis darstellen, nämlich:
Logische Operatoren und Elemente werden auf Qubits auf die gleiche Weise angewendet wie bei klassischen Bits – basierend auf einer Matrixtransformation. Alle bisher bekannten invertierbaren Matrixoperatoren, insbesondere CNOT, können für die Arbeit mit Qubits verwendet werden. Mit solchen Matrixoperatoren können Sie jede Amplitude des Qubits verwenden, ohne es zu messen und zu reduzieren. Lassen Sie mich Ihnen ein Beispiel für die Verwendung des Negationsoperators für ein Qubit geben:
Bevor wir fortfahren, möchte ich Sie an die Amplitudenwerte erinnern a₀ und a₁ sind tatsächlich , sodass der Zustand eines Qubits am genauesten auf eine dreidimensionale Einheitskugel abgebildet werden kann, auch bekannt als :
Um die Erklärung zu vereinfachen, beschränken wir uns hier jedoch auf reelle Zahlen.
Es scheint an der Zeit, einige logische Elemente zu diskutieren, die nur im Kontext des Quantencomputings Sinn machen.
Einer der wichtigsten Operatoren ist das „Hadamard-Element“: Es nimmt ein Bit in einen „0“- oder „1“-Zustand und versetzt es in die entsprechende Überlagerung mit einer 50-prozentigen Chance, in einen „1“ oder „0“-Zustand zu kollabieren. nach der Messung.
Beachten Sie, dass sich unten rechts im Hadamard-Operator eine negative Zahl befindet. Dies liegt daran, dass das Ergebnis der Anwendung des Operators vom Wert des Eingangssignals abhängt: - |1⟩ oder |0⟩, und daher ist die Berechnung umkehrbar.
Ein weiterer wichtiger Punkt des Hadamard-Elements ist seine Invertibilität, was bedeutet, dass es ein Qubit in der entsprechenden Überlagerung annehmen und in |0⟩ oder |1⟩ umwandeln kann.
Dies ist sehr wichtig, da es uns die Möglichkeit gibt, von einem Quantenzustand zu transformieren, ohne den Zustand des Qubits zu bestimmen – und dementsprechend ohne es zusammenbrechen zu lassen. Somit können wir Quantencomputing auf der Grundlage eines deterministischen statt eines probabilistischen Prinzips strukturieren.
Quantenoperatoren, die nur reelle Zahlen enthalten, sind ihr eigenes Gegenteil, daher können wir das Ergebnis der Anwendung des Operators auf ein Qubit als Transformation innerhalb des Einheitskreises in Form einer Zustandsmaschine darstellen:
Somit wird das Qubit, dessen Zustand im obigen Diagramm dargestellt ist, nach Anwendung der Hadamard-Operation in den durch den entsprechenden Pfeil angezeigten Zustand umgewandelt. Ebenso können wir eine andere Zustandsmaschine konstruieren, die die Transformation eines Qubits mithilfe des oben gezeigten Negationsoperators (auch bekannt als Pauli-Negationsoperator oder Bitinversion) veranschaulicht, wie unten gezeigt:
Um komplexere Operationen an unserem Qubit durchzuführen, können wir mehrere Operatoren verketten oder Elemente mehrfach anwenden. Beispiel einer seriellen Transformation basierend auf выглядит следующим образом:
Das heißt, wenn wir mit Bit |0⟩ beginnen, eine Bitinversion anwenden und dann eine Hadamard-Operation, dann eine weitere Bitinversion und erneut eine Hadamard-Operation, gefolgt von einer abschließenden Bitinvertierung, erhalten wir am Ende den durch on gegebenen Vektor die rechte Seite der Kette. Indem wir verschiedene Zustandsmaschinen übereinander legen, können wir bei |0⟩ beginnen und die farbigen Pfeile verfolgen, die den einzelnen Transformationen entsprechen, um zu verstehen, wie das Ganze funktioniert.
Da wir so weit gekommen sind, ist es an der Zeit, eine der Arten von Quantenalgorithmen zu betrachten, nämlich – und zeigen seine Vorteile gegenüber einem klassischen Computer. Es ist erwähnenswert, dass der Deutsch-Jozsa-Algorithmus vollständig deterministisch ist, das heißt, er liefert in 100 % der Fälle die richtige Antwort (im Gegensatz zu vielen anderen Quantenalgorithmen, die auf der probabilistischen Definition von Qubits basieren).
Stellen wir uns vor, dass Sie eine Blackbox haben, die eine Funktion/einen Operator für ein Bit enthält (denken Sie daran: Mit einem Bit können nur vier Operationen ausgeführt werden: Identitätsumwandlung, Negation, Auswertung der Konstante „0“ und Auswertung der Konstante „1“. "). Was genau ist die Funktion, die in der Box ausgeführt wird? Sie wissen nicht, welche, aber Sie können beliebig viele Varianten von Eingabewerten durchgehen und die Ausgabeergebnisse auswerten.
Wie viele Ein- und Ausgänge müssten Sie durch die Blackbox laufen lassen, um herauszufinden, welche Funktion verwendet wird? Denken Sie eine Sekunde darüber nach.
Bei einem klassischen Computer müssen Sie zwei Abfragen durchführen, um die zu verwendende Funktion zu bestimmen. Wenn beispielsweise der Eingang „2“ einen Ausgang „1“ erzeugt, wird deutlich, dass entweder die Funktion zur Berechnung der Konstante „0“ oder die Negationsfunktion verwendet wird, wonach Sie den Wert des Eingangssignals ändern müssen auf „0“ und sehen Sie, was am Ausgang passiert.
Im Falle eines Quantencomputers sind ebenfalls zwei Abfragen erforderlich, da Sie weiterhin zwei unterschiedliche Ausgabewerte benötigen, um die Funktion, die auf den Eingabewert angewendet werden soll, genau zu definieren. Wenn man die Frage jedoch ein wenig umformuliert, stellt sich heraus, dass Quantencomputer immer noch einen gravierenden Vorteil haben: Wenn man wissen wollte, ob die verwendete Funktion konstant oder variabel ist, wären Quantencomputer im Vorteil.
Die in der Box verwendete Funktion ist variabel, wenn unterschiedliche Werte des Eingangssignals unterschiedliche Ergebnisse am Ausgang erzeugen (z. B. Identitätsumwandlung und Bitinvertierung) und wenn sich der Ausgangswert unabhängig vom Eingangswert nicht ändert, dann Funktion ist konstant (zum Beispiel die Berechnung einer Konstante „1“ oder die Berechnung der Konstante „0“).
Mithilfe eines Quantenalgorithmus können Sie anhand nur einer Abfrage bestimmen, ob eine Funktion in einer Blackbox konstant oder variabel ist. Doch bevor wir uns im Detail damit befassen, wie das geht, müssen wir einen Weg finden, jede dieser Funktionen auf einem Quantencomputer zu strukturieren. Da jeder Quantenoperator invertierbar sein muss, stehen wir sofort vor einem Problem: Die Funktionen zur Berechnung der Konstanten „1“ und „0“ sind es nicht.
Eine im Quantencomputing häufig verwendete Lösung besteht darin, ein zusätzliches Ausgabe-Qubit hinzuzufügen, das den von der Funktion empfangenen Eingabewert zurückgibt.
| Vorher: | Nachher: |
|
|
|
Auf diese Weise können wir den Eingabewert ausschließlich anhand des Ausgabewerts bestimmen und die Funktion wird invertierbar. Aufgrund der Struktur von Quantenschaltungen ist ein zusätzliches Eingangsbit erforderlich. Um die entsprechenden Operatoren zu entwickeln, gehen wir davon aus, dass das zusätzliche Eingabe-Qubit auf |0⟩ gesetzt ist.
Sehen wir uns anhand derselben Quantenschaltungsdarstellung, die wir zuvor verwendet haben, an, wie jedes der vier Elemente (Identitätstransformation, Negation, Auswertung der Konstante „0“ und Auswertung der Konstante „1“) mithilfe von Quantenoperatoren implementiert werden kann.
So können Sie beispielsweise die Funktion zur Berechnung der Konstante „0“ implementieren:
Berechnung der Konstante „0“:
Hier brauchen wir überhaupt keine Operatoren. Das erste Eingabe-Qubit (von dem wir angenommen haben, dass es |0⟩ ist) kehrt mit demselben Wert zurück, und der zweite Eingabewert gibt sich selbst zurück – wie üblich.
Bei der Funktion zur Berechnung der Konstante „1“ ist die Situation etwas anders:
Berechnung der Konstante „1“:
Da wir davon ausgegangen sind, dass das erste Eingangs-Qubit immer auf |0⟩ gesetzt ist, führt die Anwendung des Bitinversionsoperators dazu, dass am Ausgang immer eine Eins erzeugt wird. Und wie üblich gibt das zweite Qubit am Ausgang seinen eigenen Wert aus.
Bei der Zuordnung des Identitätstransformationsoperators wird die Aufgabe immer komplizierter. So geht's:
Identische Transformation:
Das hier verwendete Symbol bezeichnet das CNOT-Element: Die obere Zeile bezeichnet das Steuerbit und die untere Zeile bezeichnet das Steuerbit. Ich möchte Sie daran erinnern, dass sich bei Verwendung des CNOT-Operators der Wert des Steuerbits ändert, wenn das Steuerbit gleich |1⟩ ist, aber unverändert bleibt, wenn das Steuerbit gleich |0⟩ ist. Da wir davon ausgegangen sind, dass der Wert der oberen Zeile immer gleich |0⟩ ist, wird ihr Wert immer der unteren Zeile zugewiesen.
Ähnlich verfahren wir mit dem Negationsoperator:
Negation:
Wir invertieren einfach das Bit am Ende der Ausgabezeile.
Nachdem wir nun dieses vorläufige Verständnis geklärt haben, schauen wir uns die spezifischen Vorteile eines Quantencomputers gegenüber einem herkömmlichen Computer an, wenn es darum geht, die Konstanz oder Variabilität einer in einer Blackbox versteckten Funktion mit nur einer Abfrage zu bestimmen.
Um dieses Problem mithilfe von Quantencomputern in einer einzigen Anfrage zu lösen, ist es notwendig, die Eingabe-Qubits in eine Überlagerung zu bringen, bevor sie an die Funktion übergeben werden, wie unten gezeigt:
Das Hadamard-Element wird erneut auf das Ergebnis der Funktion angewendet, um die Qubits aus der Überlagerung zu lösen und den Algorithmus deterministisch zu machen. Wir starten das System im Zustand |00⟩ und erhalten aus Gründen, die ich gleich erläutern werde, das Ergebnis |11⟩, wenn die angewendete Funktion konstant ist. Wenn die Funktion innerhalb der Blackbox variabel ist, gibt das System nach der Messung das Ergebnis |01⟩ zurück.
Um den Rest des Artikels zu verstehen, schauen wir uns die Abbildung an, die ich zuvor gezeigt habe:
Durch die Verwendung des Bitinversionsoperators und die anschließende Anwendung des Hadamard-Elements auf beide Eingabewerte gleich |0⟩ stellen wir sicher, dass sie wie folgt in die gleiche Überlagerung von |0⟩ und |1⟩ übersetzt werden:
Am Beispiel der Übergabe dieses Werts an eine Black-Box-Funktion lässt sich leicht zeigen, dass beide Konstantwertfunktionen |11⟩ ausgeben.
Berechnung der Konstante „0“:
Ebenso sehen wir, dass die Funktion zur Berechnung der Konstante „1“ auch |11⟩ als Ausgabe erzeugt, also:
Berechnung der Konstante „1“:
Beachten Sie, dass die Ausgabe |1⟩ sein wird, da -1² = 1.
Mit dem gleichen Prinzip können wir beweisen, dass wir bei Verwendung beider Variablenfunktionen immer |01⟩ am Ausgang erhalten (vorausgesetzt, wir verwenden die gleiche Methode), obwohl alles etwas komplizierter ist.
Identische Transformation:
Da es sich bei CNOT um einen Zwei-Qubit-Operator handelt, kann er nicht als einfache Zustandsmaschine dargestellt werden. Daher müssen zwei Ausgangssignale definiert werden, die auf dem Tensorprodukt beider Eingangs-Qubits und der Multiplikation mit der CNOT-Matrix basieren, wie zuvor beschrieben:
Mit dieser Methode können wir auch bestätigen, dass der Ausgabewert |01⟩ empfangen wird, wenn die Negationsfunktion in der Blackbox versteckt ist:
Negation:
Damit haben wir gerade eine Situation demonstriert, in der ein Quantencomputer deutlich effizienter ist als ein herkömmlicher Computer.
Was kommt als nächstes?
Ich schlage vor, dass wir hier enden. Wir haben schon einen tollen Job gemacht. Wenn Sie alles verstanden haben, was ich behandelt habe, haben Sie meiner Meinung nach jetzt ein gutes Verständnis für die Grundlagen des Quantencomputings und der Quantenlogik und wissen, warum Quantenalgorithmen in bestimmten Situationen effizienter sein können als herkömmliches Computing.
Meine Beschreibung kann kaum als vollwertiger Leitfaden für Quantencomputer und Algorithmen bezeichnet werden – vielmehr handelt es sich um eine kurze Einführung in Mathematik und Notation, die darauf abzielt, die von populärwissenschaftlichen Quellen aufgedrängten Vorstellungen der Leser über das Thema zu zerstreuen (im Ernst, viele können es wirklich nicht verstehen). die Situation!). Ich hatte keine Zeit, viele wichtige Themen anzusprechen, wie zum Beispiel , Komplexität der Amplitudenwerte |0⟩ und |1⟩ und die Funktionsweise verschiedener Quantenlogikelemente während der Transformation durch die Bloch-Kugel.
Wenn Sie Ihr Wissen über Quantencomputer systematisieren und strukturieren möchten, stark Ich empfehle Ihnen zu lesen Emma Strubel: Trotz der Fülle an mathematischen Formeln geht dieses Buch viel ausführlicher auf Quantenalgorithmen ein.
Source: habr.com