Kapitel 2 : Quantencomputing
Um Berechnungen durchzuführen, ist Quantencomputing eine Art von Computing, das sich die kollektiven Eigenschaften von Quantenzuständen wie Überlagerung, Interferenz und Verschränkung zunutze macht. Quantencomputer sind die elektronischen Geräte, die in der Lage sind, Quantenberechnungen durchzuführen. Eines der Teilgebiete, das unter das Dach der Quanteninformationswissenschaft fällt, ist die Erforschung des Quantencomputings.
Das Quantenschaltungsmodell, die Quanten-Turing-Maschine, der adiabatische Quantencomputer, der Einweg-Quantencomputer und eine Vielzahl von quantenzellulären Automaten sind einige der verschiedenen Arten von Quantencomputern (auch als Quantencomputersysteme bekannt). Die Quantenschaltung, die auf dem Quantenbit basiert, auch "Qubit" genannt, das in gewisser Weise mit dem im herkömmlichen Rechnen verwendeten Bit vergleichbar ist, ist das Modell, das am häufigsten verwendet wird. Ein Qubit kann in einem Quantenzustand von eins oder null existieren, oder es kann in einer Überlagerung beider Zustände gleichzeitig existieren. Wenn sie jedoch gemessen wird, ist sie entweder 0 oder 1, und die Wahrscheinlichkeit eines der beiden Ereignisse hängt vom Quantenzustand des Qubits kurz vor der Messung ab.
Um einen physikalischen Quantencomputer zu konstruieren, konzentrieren sich die Forscher auf die Entwicklung von Technologien wie Transmonen, Ionenfallen und topologischen Quantencomputern. Diese Technologien sind darauf ausgelegt, qualitativ hochwertige Qubits zu produzieren. Auf der anderen Seite kann jedes Problem, das von einem Quantencomputer gelöst werden kann, auch von einem herkömmlichen Computer gelöst werden, wenn genügend Zeit vorhanden ist, zumindest in der Theorie. Anders ausgedrückt: Der Church-Turing-These folgen Quantencomputer. Dies deutet darauf hin, dass Quantencomputer zwar keine zusätzlichen Vorteile gegenüber klassischen Computern in Bezug auf die Berechenbarkeit bieten, Quantenalgorithmen für spezifische Probleme jedoch eine deutlich geringere Zeitkomplexität aufweisen als entsprechende bekannte klassische Algorithmen. Und das, obwohl Quantencomputer keine zusätzlichen Vorteile bieten. Insbesondere wird angenommen, dass Quantencomputer einige Probleme schnell lösen können, die kein herkömmlicher Computer in einem denkbaren Zeitraum lösen könnte. Diese Errungenschaft ist als "Quantenüberlegenheit" bekannt und etwas, das kein klassischer Computer leisten könnte. Im Kontext von Quantencomputern untersucht das Forschungsgebiet der Quantenkomplexitätstheorie den Schwierigkeitsgrad, den Fragestellungen für Quantencomputer mit sich bringen.
Im Jahr 1980 schlug der Wissenschaftler Paul Benioff ein quantenmechanisches Modell der Turing-Maschine vor, das als Beginn des Quantencomputings gilt.
Das am weitesten verbreitete Modell des Quantencomputings stellt den Prozess des Rechnens so dar, dass er aus einem Netzwerk von Quantenlogikgattern besteht.
Ein Speicher, der aus Informationsbits besteht, hat mögliche Zustände.
Ein Vektor, der alle Speicherzustände darstellt, hat also Einträge (einen für jeden Zustand).
Dieser Vektor wird als Wahrscheinlichkeitsvektor angesehen, da er die Tatsache widerspiegelt, dass der Speicher höchstwahrscheinlich in einem bestimmten Zustand entdeckt wird.
Nach traditioneller Auffassung hätte nur einer der Einträge den Wert eins (was bedeutet, dass es eine hundertprozentige Wahrscheinlichkeit gibt, sich in diesem Zustand zu befinden), während die anderen Einträge alle einen Wert von Null hätten.
Das Konzept der Wahrscheinlichkeitsvektoren kann auf das der Dichteoperatoren in der Quantenmechanik angewendet werden. In den meisten Fällen wird der Quantenzustandsvektor-Formalismus zuerst vorgestellt, weil er theoretisch einfacher ist und auch, weil er anstelle des Dichtematrix-Formalismus für reine Zustände verwendet werden kann, der in Situationen anwendbar ist, in denen das gesamte Quantensystem bekannt ist.
Beginnen wir mit einem grundlegenden Speicher, der nur ein Bit enthält. Dieser Speicher kann sich entweder im Nullzustand oder im Ein-Zustand befinden. Dies sind die beiden möglichen Zustände. Wir können die Dirac-Notation verwenden, um den Zustand dieses Speichers auszudrücken, um sicherzustellen, dass
Ein Quantenspeicher kann dann in einer beliebigen Quantenüberlagerung der beiden klassischen Zustände und gefunden werden:
Die Koeffizienten und sind komplexe Zahlen.
Es wird angegeben, dass in den Quantenspeicher Informationen im Wert von einem Qubit eingebettet sind.
Der Zustand ist selbst kein Wahrscheinlichkeitsvektor, sondern kann über eine Messoperation mit einem Wahrscheinlichkeitsvektoren verbunden werden.
Wenn der Quantenspeicher gemessen wird, um zu bestimmen, ob der Zustand oder ist (dies wird als rechnerische Basismessung bezeichnet), würde der Nullzustand mit Wahrscheinlichkeit und der eine Zustand mit Wahrscheinlichkeit beobachtet werden.
Die Zahlen und werden als Wahrscheinlichkeitsamplituden bezeichnet.
Der Zustand dieses Ein-Qubit-Quantenspeichers kann durch die Anwendung von Quantenlogikgattern modifiziert werden, was vergleichbar mit der Art und Weise ist, wie der Zustand eines herkömmlichen Speichers mit Hilfe klassischer Logikgatter geändert werden kann. Das NOT-Gatter, das als Matrix dargestellt werden kann, ist ein wesentliches Gatter sowohl für die konventionelle als auch für die Quantenverarbeitung.
Mathematisch kann die Modellierung der Anwendung eines solchen Logikgatters auf einen Quantenzustandsvektor durch Matrixmultiplikation erfolgen.
Also und .
Auf zwei wichtige Arten kann die Mathematik von Einzel-Qubit-Gattern erweitert werden, um mit Multi-Qubit-Quantenspeichern zu arbeiten. Dies eröffnet neue Möglichkeiten für den Bereich des Quantencomputings. Eine Technik hierfür besteht darin, ein Qubit nach dem Zufallsprinzip auszuwählen und dann das ausgewählte Gate auf das Qubit anzuwenden, das Sie ändern möchten, während der Rest des Speichers unberührt bleibt. Es besteht auch die Möglichkeit, das Gate nur unter der Bedingung auf sein Ziel anzuwenden, dass sich ein anderer Teil des Speichers bereits im erforderlichen Zustand befindet. Eine weitere Abbildung kann verwendet werden, um diese beiden Optionen zu vergleichen und gegenüberzustellen. Im Folgenden sind die Zustände aufgeführt, die in einem Quantenspeicher mit zwei Qubits gespeichert werden können:
Im Folgenden finden Sie eine Matrix, die zur Darstellung des CNOT-Gatters verwendet werden kann, das verwendet werden kann:
Als direktes Ergebnis dieser Definition unter Verwendung mathematischer Begriffe, , , und .
Anders ausgedrückt: Das CNOT wendet ein NOT-Gatter ( von vor) auf das zweite Qubit an, wenn und nur wenn sich das erste Qubit im Zustand befindet.
Wenn das erste Qubit ist, wird an keinem der Qubits eine Änderung vorgenommen.
Kurz gesagt, kann ein Quantencomputer als ein Netzwerk konzipiert werden, das aus Quantenlogikgattern und Messungen besteht. Dennoch kann jede Messung bis zum Abschluss der Quantenberechnung verschoben werden; Diese Verschiebung kann jedoch mit einem Rechenaufwand verbunden sein, weshalb die Mehrzahl der Quantenschaltkreise ein Netzwerk darstellt, das ausschließlich aus Quantenlogikgattern besteht und keine Messungen enthält.
Jede Berechnung, die Quantenmechanik verwendet (was in der vorangegangenen Formalisierung eine beliebige unitäre Matrix über Qubits ist) kann als ein Netzwerk von Quantenlogikgattern aus einer relativ kleinen Familie von Gattern dargestellt werden.
Ein universelles Gate-Set bezieht sich auf eine bestimmte Gate-Familie nach eigener Wahl, die diese Konstruktion ermöglicht, da ein Computer, der in der Lage ist, solche Schaltkreise zu betreiben, als universeller Quantencomputer angesehen wird.
Ein solcher Satz verfügt häufig über alle Einzel-Qubit-Gatter zusätzlich zu dem oben beschriebenen CNOT-Gatter.
Dies deutet darauf hin, dass jedes Quantencomputing durchgeführt werden kann, indem eine Reihe von Gattern ausgeführt wird, die auf einem einzelnen Qubit in Verbindung mit Gattern arbeiten, die auf CNOT-Qubits arbeiten.
Trotz der Tatsache, dass diese Gattermenge kein Ende hat, ist es gemäß dem Satz von Solovay-Kitaev möglich, sie durch eine endliche Gattermenge zu ersetzen.
Das Modell der Quantenschaltkreise ist oft der Ort, an dem Forscher ihre Bemühungen konzentrieren, wenn sie versuchen, bei der Suche nach Quantenalgorithmen voranzukommen. Es gibt jedoch Ausnahmen, wie z. B. den quantenadiabatischen Algorithmus. Quantenalgorithmen können im Allgemeinen in mehrere Kategorien eingeteilt werden, basierend auf der Art der Beschleunigung, die sie im Vergleich zu ihren herkömmlichen Gegenstücken erzeugen. Bestimmte Orakelprobleme, wie das Simon-Problem und das Bernstein-Vazirani-Problem, führen zu beweisbaren Beschleunigungen; Dies ist jedoch im Quantenabfragemodell der Fall, bei dem es sich um ein eingeschränktes Modell handelt, bei dem untere Grenzen viel einfacher zu beweisen sind. Dies führt jedoch nicht unbedingt zu einer Beschleunigung bei praktischen Problemen. Das Simon-Problem und das Bernstein-Vazirani-Problem sind Beispiele für solche Probleme.
Andere Probleme, wie die Simulation quantenphysikalischer Prozesse aus der Chemie und Festkörperphysik, die Approximation bestimmter Jones-Polynome und der Quantenalgorithmus für lineare Gleichungssysteme, haben allesamt Quantenalgorithmen, die superpolynomiale Beschleunigungen zu liefern scheinen und BQP-vollständig sind. Zu diesen Problemen gehören: Aufgrund der Tatsache, dass diese Probleme BQP-vollständig sind, würde die Existenz einer...
