Ein Quantencomputer bzw. Quantenrechner ist
ein Computer, dessen Funktion auf den Gesetzen der Quantenmechanik
beruht. Im Unterschied zum Digitalrechner arbeitet er nicht auf der
Basis der Gesetze der klassischen Physik bzw. Informatik, sondern auf
der Basis quantenmechanischer Zustände, was wesentlich über die Regeln
der klassischen Theorien hinausgeht (siehe zum Beispiel die Bellsche
Ungleichung). Die Verarbeitung dieser Zustände erfolgt nach
quantenmechanischen Prinzipien. Hierbei sind vor allem 1. das Superpositionsprinzip (d. h. die
quantenmechanische Kohärenz, analog zu den Kohärenzeffekten, siehe z. B.
Holographie, in der sonst inkohärenten Optik) und 2. die sog. Quantenverschränkung (s. u.) von besonderer Bedeutung.
Theoretische Studien legen nahe, dass unter
Ausnutzung dieser Effekte bestimmte Probleme der Informatik, z. B. die
Suche in extrem großen Datenbanken (siehe Grover-Algorithmus) und die
Produktzerlegung extrem langer Zahlen (siehe Shor-Algorithmus)
wesentlich effizienter gelöst werden können als mit klassischen
Computern. Dies würde das mathematische Problem, das die Basis für die
Sicherheit weit verbreiteter kryptographischer Verfahren darstellt,
leicht lösbar und diese damit unbrauchbar machen. Der Quantencomputer ist gegenwärtig noch ein
überwiegend theoretisches Konzept. Es existiert aber schon jetzt eine
Vielzahl von Vorschlägen, wie ein Quantencomputer realisiert werden
könnte, und in kleinem Maßstab wurden einige dieser Konzepte im Labor
erprobt und es wurden Quantencomputer mit wenigen Qubits realisiert; der
Zeitpunkt einer tatsächlichen Anwendung und praktischem Nutzen ist
jedoch unklar.
Inhaltsverzeichnis [Verbergen] · 1 Qubits · 2 Quantenregister, Verschränkung · 3 Quantengatter · 4 Einweg-Quantencomputer · 5 Adiabatische Quantencomputer · 6 Physikalische Realisierung o 6.1 Relaxation o 6.2 Dekohärenz · 7 Berechenbarkeits- und Komplexitätstheorie
o 7.1 Berechenbarkeit o 7.2 Komplexität · 8 Algorithmen für Quantencomputer · 9 Architektur für Quantencomputer · 10 Forschung · 11 Weblinks · 12 Literatur · 13 Einzelnachweise und Fußnoten
Qubits
→ Hauptartikel: Qubit
Zur Definition des Begriffes Qubit: Beim Quantencomputing arbeitet man mit
allgemeinen Zuständen, die in bestimmter Weise durch Überlagerung der
beiden farbig gekennzeichneten Basiszustände entstehen, wogegen beim
klassischen Computing nur die Basiszustände selbst auftreten. In einem klassischen Computer wird sämtliche
Information in Bits dargestellt. Physikalisch wird ein Bit dadurch
realisiert, dass ein Spannungspotential entweder oberhalb eines
bestimmten Pegels liegt oder unterhalb. Auch in einem Quantencomputer wird Information
in der Regel binär dargestellt. Dazu bedient man sich eines
physikalischen Systems mit zwei Basiszuständen eines zweidimensionalen
komplexen Raums, wie er in der Quantenmechanik auftritt. Ein
Basiszustand repräsentiert den quantenmechanischen Zustandsvektor , der
andere den Zustandsvektor . Dabei benutzt man die in der Quantenphysik
gebräuchliche Dirac-Notation. Bei diesen Zwei-Niveau-Systemen der
Quantenmechanik kann es sich z. B. um den Spin eines Elektrons handeln,
der entweder nach oben oder nach unten zeigt. Andere Implementierungen
nutzen das Energieniveau in Atomen oder Molekülen oder die Flussrichtung
eines Stroms in einem ringförmigen Supraleiter. Die Bezeichnung Qubit soll den
quantenmechanischen Charakter der auf diese Weise dargestellten Bits
betonen und leitet sich aus Quanten-Bit ab. Eine wichtige Eigenschaft quantenmechanischer
Zustandsvektoren ist in diesem Zusammenhang, dass diese eine
Überlagerung anderer Zustände sein können. Dies wird auch Superposition
genannt. Im konkreten Fall bedeutet dies, dass ein Qubit nicht entweder
oder sein muss, wie dies für die Bits des klassischen Computers der Fall
ist. Vielmehr ergibt sich der Zustand eines Qubits in dem oben erwähnten
zweidimensionalen komplexen Raum allgemein zu
, wobei wie in der kohärenten Optik beliebige
Überlagerungszustände zugelassen sind. Der Unterschied zwischen
klassischem und quantenmechanischem Computing ist also analog dem
zwischen inkohärenter bzw. kohärenter Optik (im ersten Fall werden
Intensitäten addiert, im zweiten direkt die Feldamplituden, wie etwa in
der Holographie). Hierbei sind und beliebige komplexe Zahlen.
Zur Normierung fordert man aber ohne Beschränkung der Allgemeinheit noch
. Die Betragsquadrate der komplexen Zahlen und geben die
Wahrscheinlichkeit dafür an, als Resultat einer Messung am Zustand den
Wert 0 bzw. 1 zu erhalten. Beispielsweise ist also die
Wahrscheinlichkeit, eine 0 zu messen. Man darf dieses probabilistische
Verhalten allerdings nicht so interpretieren, dass sich das Qubit mit
einer bestimmten Wahrscheinlichkeit im Zustand und mit einer anderen
Wahrscheinlichkeit im Zustand befindet, während andere Zustände nicht
zugelassen sind. Ein solches ausschließendes Verhalten könnte man auch
mit einem klassischen Computer erzielen, der einen Zufallsgenerator
verwendet, um beim Auftreten von überlagerten Zuständen zu entscheiden,
ob er mit 0 oder 1 weiterrechnet. In der theoretischen Physik kommt ein
entsprechendes ausschließendes Verhalten in der sog. Statistischen
Physik vor, die also im Gegensatz zur Quantenmechanik inkohärent ist. Bei Berücksichtigung der kohärenten
Überlagerung erhält man dagegen allgemein
wobei den Realteil der komplexen Zahl
bedeutet, die konjugiert-komplexe Zahl zu ist und das quantenmechanische
Skalarprodukt der betreffenden Zustände ist. [1] Quantenregister, Verschränkung[Bearbeiten |
Quelltext bearbeiten] Wie beim klassischen Computer auch, fasst man
mehrere Qubits zu Quanten-Registern zusammen. Der Zustand eines Qubit-Registers
ist dann gemäß den Gesetzen der Vielteilchen-Quantenmechanik ein Zustand
aus einem -dimensionalen Hilbert-Raum. Eine mögliche Basis dieses
Vektorraums ist die Produktbasis über der Basis . Für ein Register aus
zwei Qubits erhielte man demnach die Basis . Auch der Zustand des
Registers kann eine beliebige Superposition dieser Basiszustände sein,
also bei N Qubits von der Form , mit beliebigen komplexen Zahlen und der
üblichen Dualbasis. Auch Summen bzw. Differenzen solcher Terme sind
erlaubt, während bei klassischen Computern nur die Basiszustände selbst
vorkommen, d. h. nur aus den Ziffern 0 bzw. 1 zusammengesetzte
Vorfaktoren. Eine wichtige Eigenschaft des
Quanten-Registers ist, dass dessen Zustände nicht stets aus den
Zuständen unabhängiger Qubits zusammengesetzt werden können:
Beispielsweise kann man den Zustand nicht in ein Produkt aus einem
Zustand für das erste und einem Zustand für das zweite Qubit zerlegen. Man nennt einen derartigen Zustand daher auch
verschränkt (in der englischsprachigen Literatur spricht man von
entanglement). Das Gleiche gilt auch für den von verschiedenen Zustand
.[2] Die Eigenschaft der Verschränkung gibt auch
einen Hinweis darauf, dass Quantencomputer mächtiger als klassische
Computer sein könnten, d. h. dass sie prinzipiell bestimmte Probleme
wesentlich schneller lösen können, als dies mit klassischen Computern
möglich ist: Um den Zustand eines klassischen -Bit Registers
darzustellen, benötigt man Bits an Information. Der Zustand des
Quanten-Registers ist aber ein Vektor aus einem -dimensionalen
Vektorraum, so dass man zu dessen Darstellung komplexwertige
Koeffizienten angeben muss. Hier ist wesentlich, dass bei großem die
Zahl viel größer ist als selbst. Das Superpositionsprinzip wird oft so
dargestellt, dass ein Quantencomputer in einem Quantenregister aus
Qubits gleichzeitig alle Zahlen von 0 bis speichern könnte. Diese
Vorstellung ist irreführend. Da eine am Register vorgenommene Messung
stets genau einen der Basiszustände auswählt, lässt sich unter Anwendung
des so genannten Holevo-Theorems zeigen, dass der maximale zugängliche
Informationsgehalt eines einzelnen unverschränkten Qubits wie im
klassischen Fall genau ein Bit beträgt.[3][4] Es ist dennoch korrekt,
dass das Superpositionsprinzip eine Parallelität in den Rechnungen
erlaubt, die wesentlich über das hinausgeht, was in einem klassischen
Parallelrechner passiert. Bei der Vorstellung einiger
Quanten-Algorithmen wird darauf näher eingegangen.
