"Ich glaube, ich kann mit Sicherheit sagen, dass niemand die Quantenmechanik versteht", so Richard Feynman
Das Thema Quantencomputing hat seit jeher technische Redakteure und Journalisten angezogen. Ihr Rechenpotential und ihre Komplexität gaben ihr eine Art mystischen Schein. Zu oft beschreiben thematische Artikel und Infografiken ausführlich alle möglichen Perspektiven für diese Branche, ohne dabei die praktischen Aspekte zu berühren: Dies kann einen nicht allzu aufmerksamen Leser irreführen.
In populärwissenschaftlichen Artikeln werden Beschreibungen von Quantensystemen weggelassen und Aussagen wie:
Ein reguläres Bit kann gleich "1" oder "0" sein, aber ein Qubit kann gleichzeitig gleich "1" und "0" sein.Wenn Sie sehr viel Glück haben (von dem ich nicht sicher bin), dann werden sie Ihnen sagen, dass:
Das Qubit liegt in einer Überlagerung zwischen "1" und "0".Keine dieser Erklärungen erscheint plausibel, da wir versuchen, ein quantenmechanisches Phänomen mit Sprachwerkzeugen zu formulieren, die in einer sehr traditionellen Welt geschaffen wurden. Um die Prinzipien des Quantencomputers klar zu erklären, muss eine andere Sprache verwendet werden - mathematisch.
In diesem Handbuch werde ich über die mathematischen Werkzeuge sprechen, die zum Modellieren und Verstehen von Quantencomputersystemen erforderlich sind, und darüber, wie die Logik des Quantencomputers veranschaulicht und angewendet werden kann. Außerdem werde ich ein Beispiel für einen Quantenalgorithmus geben und erläutern, was sein Vorteil gegenüber einem herkömmlichen Computer ist.
Ich werde mein Bestes tun, um in einer verständlichen Sprache darüber zu sprechen, aber ich hoffe trotzdem, dass die Leser dieses Artikels grundlegende Ideen zur linearen Algebra und zur digitalen Logik haben (lineare Algebra wird
hier beschrieben, digitale Logik ist
hier ).
Lassen Sie uns zunächst die Prinzipien der digitalen Logik durchgehen. Es basiert auf der Verwendung elektrischer Schaltkreise für Berechnungen. Um unsere Beschreibung abstrakter zu gestalten, vereinfachen wir den Zustand der Leitung auf „1“ oder „0“, was den Zuständen „Ein“ oder „Aus“ entspricht. Nachdem wir Transistoren in einer bestimmten Reihenfolge aufgebaut haben, werden wir die sogenannten Logikelemente erstellen, die einen oder mehrere Werte der Eingangssignale nehmen und sie basierend auf bestimmten Regeln der Booleschen Logik in ein Ausgangssignal umwandeln.
Gemeinsame Logikelemente und Statustabellen
Auf der Grundlage von Ketten solcher Grundelemente können Sie komplexere Elemente erstellen, und auf der Grundlage von Ketten komplexerer Elemente können wir uns letztendlich darauf verlassen, ein Analogon des Zentralprozessors mit einem hohen Grad an Abstraktheit zu erhalten.
Wie ich bereits erwähnt habe, müssen wir die digitale Logik mathematisch abbilden können. Lassen Sie uns zunächst die traditionelle mathematische Logik einführen. Mit der linearen Algebra können klassische Bits mit den Werten "1" und "0" als zwei Spaltenvektoren dargestellt werden:
wo die Zahlen auf der linken Seite die
Dirac- Vektornotation sind. Indem wir unsere Bits auf diese Weise darstellen, können wir logische Operationen an Bits unter Verwendung von Vektortransformationen modellieren. Bitte beachten Sie: Trotz der Tatsache, dass Sie bei Verwendung von zwei Bits in Logikelementen viele Operationen ausführen können („AND“ (AND), „Not“ (NOT), „Exclude Or“ (XOR) usw.), wenn Sie eines verwenden Bits ist es möglich, nur vier Operationen durchzuführen: Identitätsumwandlung, Negation, Berechnung der Konstante "0" und Berechnung der Konstante "1". Während der identischen Umwandlung bleibt das Bit unverändert, wenn es negiert wird, wird der Bitwert umgekehrt (von "0" auf "1" oder von "1" auf "0"), und die Berechnung der Konstante "1" oder "0" setzt das Bit auf "1". oder "0" unabhängig von seinem vorherigen Wert.
Basierend auf unserer neuen Darstellung eines Bits ist es recht einfach, Operationen mit dem entsprechenden Bit unter Verwendung der Vektortransformation durchzuführen:
Bevor wir fortfahren, schauen wir uns das Konzept des
reversiblen Rechnens an , das nur impliziert, dass zur Gewährleistung der Reversibilität einer Operation oder eines logischen Elements eine Liste von Eingangssignalwerten basierend auf den Ausgangssignalen und den Namen der verwendeten Operationen erstellt werden muss. Somit können wir schließen, dass die Identitätstransformation und die Negation reversibel sind, die Operation zum Berechnen der Konstanten "1" und "0" jedoch nicht. Aufgrund der
Einheitlichkeit der Quantenmechanik verwenden Quantencomputer ausschließlich reversible Operationen, weshalb wir uns auf diese konzentrieren werden. Als nächstes werden wir die irreversiblen Elemente in reversible Elemente umwandeln, um sicherzustellen, dass sie von einem Quantencomputer verwendet werden können.
Mit dem
Tensorprodukt einzelner Bits können viele Bits dargestellt werden:
Nachdem wir fast alle notwendigen mathematischen Konzepte haben, werden wir zu unserem ersten quantenlogischen Element übergehen. Dies ist der
CNOT- Operator oder das gesteuerte „NOT“ (NOT), das für das reversible und das Quantencomputing von großer Bedeutung ist. Das CNOT-Element wird auf zwei Bits angewendet und gibt zwei Bits zurück. Das erste Bit wird als "Steuerung" und das zweite - "Steuerung" zugewiesen. Wenn das Steuerbit auf "1" gesetzt ist, ändert das Steuerbit seinen Wert. Wenn das Steuerbit auf „0“ gesetzt ist, ändert sich das Steuerbit nicht.
Dieser Operator kann als folgender Transformationsvektor dargestellt werden:
Um alles zu demonstrieren, was wir bereits behandelt haben, zeige ich Ihnen, wie Sie das CNOT-Element in Bezug auf viele Bits verwenden:
Wir fassen zusammen, was bereits gesagt wurde: Im ersten Beispiel zerlegen wir | 10⟩ in Teile seines Tensorprodukts und verwenden die CNOT-Matrix, um einen neuen entsprechenden Zustand des Produkts zu erhalten; dann faktorisieren wir es gemäß der zuvor angegebenen CNOT-Wertetabelle auf | 11⟩.
Wir haben uns also an alle mathematischen Regeln erinnert, die uns helfen werden, mit traditionellen Berechnungen und gewöhnlichen Bits umzugehen, und schließlich können wir zu modernen Quantencomputern und Qubits übergehen.
Wenn Sie bis zu diesem Punkt lesen, dann habe ich eine gute Nachricht für Sie: Qubits können leicht mathematisch ausgedrückt werden. Wenn das klassische Bit (cbit) auf | 1⟩ oder | 0⟩ gesetzt werden kann, ist das Qubit im Allgemeinen einfach in Überlagerung und kann vor der Messung gleich | 0⟩ und | 1⟩ sein. Nach der Messung kollabiert es bei | 0⟩ oder | 1⟩. Mit anderen Worten kann ein Qubit als eine lineare Kombination von | 0⟩ und | 1⟩ gemäß der folgenden Formel dargestellt werden:
wobei
a₀ und
a₁ jeweils die Amplituden | 0⟩ und | 1⟩ darstellen. Sie können als „Quantenwahrscheinlichkeiten“ betrachtet werden, die die Wahrscheinlichkeit eines Zusammenbruchs eines Qubits in einen der Zustände nach seiner Messung darstellen, da in der Quantenmechanik ein überlagertes Objekt nach der Fixierung in einen der Zustände zusammenbricht. Erweitern Sie diesen Ausdruck und erhalten Sie Folgendes:
Um meine Erklärung zu vereinfachen, werde ich genau diesen Begriff in diesem Artikel verwenden.
Für dieses Qubit beträgt die
Kollapswahrscheinlichkeit zu
a measurement nach der Messung |
a ₀ | ², und die Wahrscheinlichkeit eines Zusammenbruchs in a₁ ist gleich |
a & sub1; | ². Zum Beispiel für das folgende Qubit:
die Wahrscheinlichkeit eines Zusammenbruchs in "1" ist | 1 / √2 | ² oder ½, dh 50/50.
Da im klassischen System alle Wahrscheinlichkeiten in der Summe eine Einheit ergeben müssen (für eine vollständige Wahrscheinlichkeitsverteilung), können wir schließen, dass die Quadrate der Absolutwerte der Amplituden | 0⟩ und | 1⟩ eins ergeben müssen. Basierend auf diesen Informationen können wir die folgende Gleichung aufstellen:
Wenn Sie mit der Trigonometrie vertraut sind, werden Sie feststellen, dass diese Gleichung dem Satz des Pythagoras entspricht (a² + b² = c²), dh wir können die möglichen Zustände des Qubits in Form von Punkten auf dem Einheitskreis grafisch darstellen, und zwar:
Logische Operatoren und Elemente werden sowohl auf Qubits als auch auf klassische Bits angewendet - basierend auf Matrixtransformation. Alle bisher bekannten reversiblen Matrixoperatoren, insbesondere CNOT, können für die Arbeit mit Qubits verwendet werden. Solche Matrixoperatoren ermöglichen es, jede der Amplituden eines Qubits zu verwenden, ohne es zu messen und zu kollabieren. Lassen Sie mich ein Beispiel für die Verwendung des Negationsoperators für Qubit geben:
Bevor wir fortfahren, erinnere ich mich, dass die Amplituden
a a und a₁ tatsächlich
komplexe Zahlen sind , so dass der Qubit-Zustand auf einer dreidimensionalen Einheitskugel, auch als
Bloch-Kugel bekannt, am genauesten angezeigt werden kann:
Um die Erklärung zu vereinfachen, beschränken wir uns hier jedoch auf reelle Zahlen.
Es scheint an der Zeit zu sein, einige logische Elemente zu diskutieren, die ausschließlich im Kontext des Quantencomputers sinnvoll sind.
Einer der wichtigsten Operatoren ist das „Hadamard-Element“: Es nimmt ein Bit in den Zustand „0“ oder „1“ und versetzt es in die entsprechende Überlagerung mit einer Wahrscheinlichkeit von 50%, dass es nach der Messung auf „1“ oder „0“ reduziert wird.
Beachten Sie, dass sich rechts unten im Hadamard-Operator eine negative Zahl befindet. Dies ist darauf zurückzuführen, dass das Ergebnis der Verwendung des Operators vom Wert des Eingangssignals abhängt: - | 1⟩ oder | 0⟩, und daher ist die Berechnung umkehrbar.
Ein weiterer wichtiger Punkt im Zusammenhang mit dem Hadamard-Element ist seine Reversibilität, dh es kann ein Qubit in der entsprechenden Überlagerung aufnehmen und in | 0⟩ oder | 1⟩ umwandeln.
Dies ist sehr wichtig, da es uns ermöglicht, von einem Quantenzustand zu transformieren, ohne den Zustand des Qubits zu bestimmen - und dementsprechend, ohne es zu kollabieren. Wir können Quantencomputing also eher auf der Grundlage eines deterministischen als eines probabilistischen Prinzips strukturieren.
Quantenoperatoren, die ausschließlich reelle Zahlen enthalten, sind das Gegenteil, sodass wir das Ergebnis der Anwendung des Operators auf ein Qubit als Transformation innerhalb des Einheitskreises in Form einer Zustandsmaschine darstellen können:
Somit wird das Qubit, dessen Zustand in dem obigen Diagramm gezeigt ist, nach Anwenden der Hadamard-Operation in den durch den entsprechenden Pfeil angezeigten Zustand umgewandelt. In ähnlicher Weise können wir eine weitere Zustandsmaschine konstruieren, die die Transformation eines Qubits mit dem oben gezeigten Negationsoperator (auch bekannt als Pauli-Negationsoperator oder Bitinversion) wie folgt veranschaulicht:
Um komplexere Operationen mit unserem Qubit auszuführen, können Sie eine Kette von vielen Operatoren verwenden oder Elemente mehrfach anwenden. Ein Beispiel für eine serielle Transformation basierend auf der
Darstellung einer Quantenkette ist wie folgt:
Das heißt, wenn wir mit dem Bit | 0⟩ beginnen, wenden wir die Inverse des Bits an und dann die Hadamard-Operation, dann eine weitere Bitinversion und erneut die Hadamard-Operation, wonach wir die letzte Bitinversion erhalten, den Vektor auf der rechten Seite der Kette. Durch Übereinanderlegen verschiedener Zustandsautomaten können wir mit | 0⟩ beginnen und die farbigen Pfeile verfolgen, die jeder der Transformationen entsprechen, um zu verstehen, wie dies alles funktioniert.
Da wir so weit gegangen sind, ist es an der Zeit, einen der Typen von Quantenalgorithmen zu betrachten, nämlich
den Deutsch-Joji-Algorithmus , und seinen Vorteil gegenüber einem klassischen Computer zu demonstrieren. Es ist erwähnenswert, dass der Deutsch-Yogi-Algorithmus vollständig deterministisch ist, dh in 100% der Fälle die richtige Antwort zurückgibt (im Gegensatz zu vielen anderen Quantenalgorithmen, die auf der probabilistischen Bestimmung von Qubits basieren).
Stellen wir uns vor, Sie haben eine Blackbox, die eine Funktion / einen Operator für ein Bit enthält (denken Sie daran, dass bei Verwendung eines Bits nur vier Operationen möglich sind: Identisch transformieren, negieren, die Konstante „0“ berechnen und die Konstante „1“ berechnen). Welche Funktion wird in einer Box ausgeführt? Sie wissen nicht, welche, Sie können jedoch beliebig viele Varianten von Eingabewerten aussortieren und die Ergebnisse am Ausgang auswerten.
Wie viele Eingangs- und Ausgangssignale müssen durch die Blackbox geleitet werden, 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 verwendete Funktion zu bestimmen. Wenn Sie beispielsweise "1" eingeben und am Ausgang "0" erhalten, wird klar, dass entweder die Funktion zur Berechnung der Konstante "0" oder die Negationsfunktion verwendet wird. Danach müssen Sie den Wert des Eingangssignals auf "0" ändern und sehen, was passiert am Ausgang.
Bei einem Quantencomputer benötigen Sie außerdem zwei Abfragen, da Sie immer noch zwei verschiedene Ausgabewerte benötigen, um die genaue Funktion zu bestimmen, die für den Eingabewert gilt. Wenn wir die Frage jedoch ein wenig umformulieren, stellt sich heraus, dass Quantencomputer immer noch einen gravierenden Vorteil haben: Wenn Sie herausfinden möchten, ob die verwendete Funktion konstant oder variabel ist, liegt die Überlegenheit auf der Seite der Quantencomputer.
Die in der Box verwendete Funktion ist eine Variable. Wenn unterschiedliche Werte des Eingangssignals am Ausgang unterschiedliche Ergebnisse liefern (z. B. identische Umwandlung und Invertierung eines Bits) und sich der Ausgangswert unabhängig vom Eingangswert nicht ändert, ist die Funktion konstant (z. B. Berechnung der Konstante) "1" oder die Berechnung der Konstante "0").
Mithilfe des Quantenalgorithmus können Sie anhand einer einzigen Anforderung feststellen, ob eine Funktion in einer Blackbox konstant oder variabel ist. Bevor wir dies jedoch im Detail untersuchen, müssen wir einen Weg finden, mit dem wir jede dieser Funktionen auf einem Quantencomputer strukturieren können. Da beliebige Quantenoperatoren invertierbar sein müssen, stoßen wir sofort auf ein Problem: Die Funktionen zur Berechnung der Konstanten "1" und "0" sind es nicht.
Beim Quantencomputing wird häufig die folgende Lösung verwendet: Ein zusätzliches Ausgangs-Qubit wird hinzugefügt, das einen beliebigen Wert des von der Funktion empfangenen Eingangssignals zurückgibt.
Somit können wir die Eingangswerte nur auf der Grundlage des am Ausgang erhaltenen Wertes bestimmen, und die Funktion wird invertierbar. Die Struktur der Quantenschaltungen erfordert ein zusätzliches Eingangsbit. Um die entsprechenden Operatoren zu entwickeln, nehmen wir an, dass das zusätzliche Eingangs-Qubit auf | 0⟩ gesetzt ist.
Anhand derselben Darstellung der Quantenkette, die wir zuvor verwendet haben, wird gezeigt, wie jedes der vier Elemente (Identitätstransformation, Negation, Berechnung der Konstante „0“ und Berechnung der Konstante „1“) mithilfe von Quantenoperatoren implementiert werden kann.
Beispielsweise können Sie die Funktion zur Berechnung der Konstante „0“ implementieren:
Berechnung der Konstante "0":Hier brauchen wir überhaupt keine Operatoren. Das erste eingegebene Qubit (das wir gleich | 0⟩ genommen haben) gibt den gleichen Wert zurück, und der zweite Eingabewert gibt sich selbst zurück - wie üblich.
Bei der Funktion zur Berechnung der Konstante „1“ sieht die Situation etwas anders aus:
Berechnung der Konstante "1":Da wir angenommen haben, dass das erste Eingangs-Qubit aufgrund der Anwendung des Bitinversionsoperators immer auf | 0⟩ gesetzt ist, gibt es am Ausgang immer eins. Und wie immer gibt das zweite Qubit am Ausgang einen eigenen Wert aus.
Wenn der Identitätsumwandlungsoperator angezeigt wird, wird die Aufgabe immer komplizierter. So geht's:
Identitätstransformation:Das hier verwendete Symbol kennzeichnet das CNOT-Element: Die obere Zeile kennzeichnet das Steuerbit und die untere Zeile kennzeichnet das Steuerbit. Lassen Sie mich daran erinnern, dass sich bei Verwendung des CNOT-Operators der Wert des Steuerbits ändert, wenn das Steuerbit | 1⟩ ist, aber unverändert bleibt, wenn das Steuerbit | 0⟩ ist. Da wir angenommen haben, dass der Wert der oberen Zeile immer gleich | 0⟩ ist, wird sein Wert immer der unteren Zeile zugewiesen.
Ebenso verhalten wir uns mit dem Negationsoperator:
Ablehnung:Wir invertieren einfach das Bit am Ende der Ausgangsleitung.
Nachdem wir die vorläufige Darstellung herausgefunden haben, wollen wir uns die spezifischen Vorteile eines Quantencomputers gegenüber einem herkömmlichen Computer ansehen, wenn es darum geht, die Konstanz oder Variabilität einer in einer Blackbox verborgenen Funktion mit nur einer Abfrage zu bestimmen.
Um dieses Problem mithilfe von Quantencomputing in einer einzelnen Anforderung zu lösen, müssen die eingegebenen Qubits in eine Überlagerung übersetzt werden, bevor sie in die Funktion übertragen werden.
Das Hadamard-Element wird erneut auf das Ergebnis der Verwendung der Funktion angewendet, um Qubits aus der Überlagerung abzuleiten und den Algorithmus deterministisch zu machen. Wir starten das System im Zustand | 00⟩ und erhalten aus den Gründen, über die ich jetzt sprechen werde, das Ergebnis | 11⟩, wenn die verwendete Funktion konstant ist. Wenn die Funktion in der Blackbox variabel ist, gibt das System nach der Messung das Ergebnis | 01⟩ zurück.
Um den Rest des Artikels zu behandeln, wenden wir uns der Abbildung zu, die ich zuvor gezeigt habe:
Unter Verwendung des Bitinversionsoperators und anschließender Anwendung des Hadamard-Elements auf beide Eingabewerte gleich | 0⟩ stellen wir sicher, dass sie in dieselbe Überlagerung | 0 | und | 1⟩ übersetzt werden, und zwar:
Am Beispiel der Übertragung dieses Wertes einer Funktion in eine Blackbox lässt sich leicht demonstrieren, dass beide Funktionen eines konstanten Wertes | 11⟩ an den Ausgang liefern.
Berechnung der Konstante "0":, , «1» |11⟩, :
«1»:: |1⟩, -1² = 1.
, |01⟩ ( ), .
:CNOT , , CNOT :
|01⟩, :
:, , , .
Was kommt als nächstes
. . , , , , , .
— , , , - (, !). — ,
, |0⟩ |1⟩ .
,
« » (An Introduction to Quantum Algorithms) : , .