Quantencomputer

Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Hierbei spielen Superposition und Verschränkung die Hauptrolle. Es konnte gezeigt werden, dass unter Ausnutzung dieser Effekte bestimmte Probleme der Informatik wesentlich effizienter gelöst werden können, als dies mit klassischen Computern möglich ist.

Zum jetzigen Zeitpunkt ist der Quantencomputer noch ein theoretisches Konzept. Es existiert eine Vielzahl von Vorschlägen, wie ein Quantencomputer realisiert werden könnte. Im kleinen Maßstab wurden bereits einige dieser Konzepte im Labor erprobt, von einer tatsächlichen Anwendung ist man allerdings noch weit entfernt. Sowohl die physikalischen Methoden als auch das fundamentale Verständnis der Quantenmechanik müssen im Hinblick auf einen praktisch nutzbaren Quantencomputer verfeinert werden.

Die Funktionsweise eines Quantencomputers beruht im Wesentlichen darauf, dass sowohl die Darstellung von Information als auch deren Verarbeitung auf einem Weg geschieht, bei welchem die Gesetze der Quantenmechanik eine fundamentale Rolle spielen. Für eine konkrete Realisierung dieses Prinzips gibt es eine Vielzahl unterschiedlicher Vorschläge, die in einem späteren Abschnitt beleuchtet werden.

In einem klassischen Computer wird sämtliche Information in Bits dargestellt. Physikalisch wird ein Bit dadurch realisiert, dass entweder Strom fließt (Wert 1) oder nicht (Wert 0).

Auch in einem Quantencomputer wird Information in der Regel binär dargestellt. Dazu bedient man sich eines physikalischen Systems mit zwei Zuständen. Ein Zustand repräsentiert dann die 0, einer die 1. In Anlehnung an die in der Quantenphysik gebräuchliche Dirac-Notation schreibt man ${\displaystyle |0\rangle }${\displaystyle |0\rangle } und ${\displaystyle |1\rangle }${\displaystyle |1\rangle } für diese Zustände. Bei diesen Zwei-Niveau-Systemen kann es sich z.B. um den Spin eines Elektrons handeln, der entweder nach oben oder nach unten zeigt. Weitere Möglichkeiten sind Energieniveaus 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 Quantum Bit ab. Eine wichtige Eigenschaft quantenmechanischer Zustände ist in diesem Zusammenhang, dass ein solcher Zustand eine Überlagerung anderer Zustände sein kann. Dies wird auch Superposition genannt. Im konkreten Fall bedeutet dies, dass ein Qubit nicht entweder ${\displaystyle |0\rangle }${\displaystyle |0\rangle } oder ${\displaystyle |1\rangle }${\displaystyle |1\rangle } sein muss, wie dies für die Bits des klassischen Computers der Fall ist. Vielmehr ergibt sich der Zustand eines Qubits zu

${\displaystyle \Psi =c_{0}|0\rangle +c_{1}|1\rangle .}${\displaystyle \Psi =c_{0}|0\rangle +c_{1}|1\rangle .}

Dabei sind ${\displaystyle c_{0}}${\displaystyle c_{0}} und ${\displaystyle c_{1}}${\displaystyle c_{1}} komplexe Zahlen. Zur Normierung fordert man noch ${\displaystyle |c_{0}|^{2}+|c_{1}|^{2}=1}${\displaystyle |c_{0}|^{2}+|c_{1}|^{2}=1}. In der gebräuchlichen Interpretation der Quantenmechanik geben diese komplexen Zahlen die Wahrscheinlichkeit dafür an, bei einer Messung des Qubits den Wert 0 oder 1 zu messen. Die Wahrscheinlichkeit, eine 0 zu messen, ist ${\displaystyle P(0)=|c_{0}|^{2}}${\displaystyle P(0)=|c_{0}|^{2}}. Man darf dieses probabilistische Verhalten allerdings nicht so interpretieren, dass das Qubit mit einer bestimmten Wahrscheinlichkeit im Zustand ${\displaystyle |0\rangle }${\displaystyle |0\rangle } und mit einer anderen Wahrscheinlichkeit im Zustand ${\displaystyle |1\rangle }${\displaystyle |1\rangle } ist. Dieses 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 weiter rechnet. Vertiefende Erläuterungen hierzu finden sich im Artikel zur Superposition.

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 dem ${\displaystyle 2^{N}}${\displaystyle 2^{N}}-dimensionalen Hilbert-Raum. Eine mögliche Basis dieses Vektorraums ist die Produktbasis über der Basis ${\displaystyle |0\rangle ,|1\rangle }${\displaystyle |0\rangle ,|1\rangle }. Für ein Register aus zwei Qubits erhielte man demnach die Basis ${\displaystyle |00\rangle ,|01\rangle ,|10\rangle ,|11\rangle }${\displaystyle |00\rangle ,|01\rangle ,|10\rangle ,|11\rangle }. Auch der Zustand des Registers kann eine Superposition dieser Basiszustände sein.

Eine wichtige Eigenschaft des Quanten-Registers ist, dass dessen Zustände nicht zwangsläufig aus den Zuständen unabhängiger einzelner Qubits zusammen gesetzt werden können: Den Zustand ${\displaystyle \Psi ={\frac {1}{\sqrt {2}}}(|00\rangle +|11\rangle )}${\displaystyle \Psi ={\frac {1}{\sqrt {2}}}(|00\rangle +|11\rangle )} kann man 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änkten Zustand.

Diese Eigenschaft gibt auch einen Hinweis darauf, dass Quantencomputer mächtiger als klassische Computer sein könnten: Um den Zustand eines klassischen ${\displaystyle N}${\displaystyle N}-Bit Registers darzustellen, benötigt man ${\displaystyle N}${\displaystyle N} Bits an Information. Der Zustand des Quanten-Registers ist aber ein Vektor aus einem ${\displaystyle 2^{N}}${\displaystyle 2^{N}}-dimensionalen Vektorraum, so dass man zu dessen Darstellung ${\displaystyle 2^{N}}${\displaystyle 2^{N}} komplexwertige Koeffizienten angeben muss.

Das Superpositionsprinzip wird oft so verstanden, dass ein Quantencomputer in einem ${\displaystyle N}${\displaystyle N}-Qubit Register gleichzeitig alle ${\displaystyle 2^{N}}${\displaystyle 2^{N}} Zahlen von 0 bis ${\displaystyle 2^{N}-1}${\displaystyle 2^{N}-1} 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 zeigen, dass der Informationsgehalt eines Qubits wie im klassischen Fall genau ein Bit beträgt. Es ist dennoch korrekt, dass das Superpositionsprinzip eine gewisse Parallelität in den Rechnungen erlaubt. Bei der Vorstellung einiger Quanten-Algorithmen wird darauf näher eingegangen werden.

Hauptartikel Quantengatter

Beim klassischen Computer werden durch Logikgatter (engl. Gates) elementare Operationen auf den Bits durchgeführt. Mehrere Gatter werden zu einem Schaltnetz verbunden, dass dann komplexe Operationen wie das Addieren zweier Binärzahlen durchführen kann. Die Gatter werden dabei durch physikalische Bauelemente wie Transistoren realisiert und die Information als elektrisches Signal durch diese Bauelemente geleitet.

Berechnungen auf einem Quantencomputer laufen grundsätzlich anders ab: Ein Quantengatter (engl. Quantum Gate) ist kein technischer Baustein, sondern stellt eine elementare physikalische Manipulation eines oder mehrerer Qubits dar. Wie genau so eine Manipulation aussieht, hängt von der tatsächlichen physikalischen Natur des Qubits ab. So lässt sich der Spin eines Elektrons durch eingestrahlte Magnetfelder beeinflussen, der Anregungszustand eines Atoms durch Laserpulse. Obwohl also ein Quantengatter kein elektronischer Baustein sondern eine im Verlauf der Zeit auf das Quanten-Register angewendete Aktion ist, beschreibt man Quanten-Algorithmen mit Hilfe von Schaltplänen, vgl. hierzu den Artikel Liste der Quantengatter.

Formal gesprochen ist ein Quantengatter eine unitäre Operation ${\displaystyle U}${\displaystyle U}, welche auf den Zustand des Quanten-Registers wirkt:

${\displaystyle \Psi \rightarrow U\cdot \Psi .}${\displaystyle \Psi \rightarrow U\cdot \Psi .}

Ein Quantengatter kann daher als unitäre Matrix geschrieben werden. Ein Gatter, welches den Zustand eines Qubits umdreht (negiert), entspräche der Matrix

${\displaystyle U={\begin{pmatrix}0&1\1円&0\end{pmatrix}}.}${\displaystyle U={\begin{pmatrix}0&1\1円&0\end{pmatrix}}.}

Ein Quanten-Schaltkreis besteht nun aus mehreren Quantengattern, die in fester zeitlicher Abfolge auf das Quantenregister angwendet werden. Beispiele hierfür sind die Quanten-Fouriertransformation oder der Shor-Algorithmus. Mathematisch ist auch ein Quanten-Schaltkreis eine unitäre Transformation, deren Matrix einfach das Produkt der Matrizen der einzelnen Quantengatter ist.

Das bisher beschriebene Konzept ist zunächst abstrakt und allgemein gültig. Aus Sicht der Informatik ist die Behandlung von Quantencomputer daher bereits recht weit fortgeschritten. Will man einen konkret nutzbaren Quantencomputer bauen, muss man natürliche die physikalischen Einschränkungen beachten, die im Folgenden beschrieben werden.

Überlässt man ein System sich selbst, neigt es dazu, einen Zustand mit möglichst niedriger Energie einzunehmen. Dies führt dazu, dass ein Qubit aus dem Zustand ${\displaystyle |1\rangle }${\displaystyle |1\rangle } nach einer gewissen Zeit mit einer bestimmten Wahrscheinlichkeit in den Zustand ${\displaystyle |0\rangle }${\displaystyle |0\rangle } gesprungen ist. Diesen Prozess nennt man Relaxation. Die Relaxationszeit ${\displaystyle T_{1}}${\displaystyle T_{1}} ist dabei exponentialverteilt.

Mit Dekohärenz ist der Verlust der Superpositionseigenschaften eines Quantenzustands gemeint. Durch den Einfluss der Umgebung entwickelt sich aus dem Superpositionszustand ${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )} entweder der Zustand ${\displaystyle |0\rangle }${\displaystyle |0\rangle } oder der Zustand ${\displaystyle |1\rangle }${\displaystyle |1\rangle }. Dann verhält sich das Qubit nur noch wie ein klassisches Bit. Die Dekohärenzzeit ${\displaystyle T_{2}}${\displaystyle T_{2}} ist in der Regel ebenfalls exponentialverteilt und typischerweise viel kleiner als die Relaxationszeit. Während die Relaxation auch für klassische Computer ein Problem darstellt (so könnten sich Magnete auf der Festplattet spontan umpolen), ist die Dekohärenz ein rein quantenmechanisches Phänomen.

Die Verlässlichkeit von Quantencomputern kann durch die so genannte Quantenfehlerkorrektur erhöht werden.

Der wohl berühmteste Algorithmus für Quantencomputer ist der Shor-Algorithmus zur Faktorisierung von Zahlen. Seine Bedeutung beruht auf der Tatsache, dass die Sicherheit der weit verbreiteten asymmetrischen Verschlüsselungsverfahren wie RSA darauf basieren, dass keine effizienten Algorithmen zur Faktorisierung großer Zahlen bekannt sind.

Ein weiterer sehr nützlicher Algorithmus ist der Grover-Algorithmus zum effizienten Suchen in einem unsortierten Array. Ein gewöhnlicher Computer muss sich bei ${\displaystyle n}${\displaystyle n} Einträgen im schlimmsten Fall alle Einträge ansehen (d. h. vergleichen), klassisch ist dieses Problem also in Zeit ${\displaystyle \Theta (n)}${\displaystyle \Theta (n)} lösbar. Auf einem Quantencomputer kann man dies mit dem Grover-Algorithmus in lediglich ${\displaystyle {\mathcal {O}}({\sqrt {n}})}${\displaystyle {\mathcal {O}}({\sqrt {n}})} Operationen erledigen. Diese Schranke ist scharf, das heißt, kein Quantenalgorithmus kann dieses Problem in (asymptotisch) weniger Operationen lösen. Daraus folgt, dass im allgemeinen kein exponentieller Geschwindigkeitsvorteil bei Verwendung von Quantenalgorithmen zu erwarten ist.

In beiden Fällen handelt es sich um probabilistische Algorithmen, d.h. der Algorithmus führt nur mit einer gewissen Wahrscheinlichkeit zum Ziel. Bei mehrfacher Wiederholung wird allerdings die Wahrscheinlichkeit, ohne korrektes Ergebnis zu bleiben, verschwindend gering.

Quantencomputer mit einer sehr geringen Anzahl Qubits sind bereits realisiert worden und haben z. B. den Shor-Algorithmus erfolgreich ausgeführt (hierbei wurde die Zahl 15 in ihre Primfaktoren 3 und 5 zerlegt).

Im November 2005 gelang es Prof. Rainer Blatt am Institut für Experimentalphysik der Universität Innsbruck erstmals, ein QuByte zu erzeugen. Die Verschränkung aller acht Qubits musste durch 650.000 Messungen nachgewiesen werden und dauerte 10 Stunden.

Die kanadische Firma D-Wave Systems hat in Kalifornien am 14. Februar 2007 nach eigenen Angaben den ersten Quantenprozessor mit 16 Qubits vorgestellt.^[1] Bei der Vorstellung wurde ein Sudoku-Rätsel gelöst und ein Terminplan erstellt. Eine 512-Qubit Version soll in einem Jahr vorliegen. Das Gerät mit dem Namen Orion war bei der Vorstellung über einen vernetzten Monitor erreichbar, also selbst nicht anwesend. Es ist zweifelhaft, ob es sich bei dem vorgestellten System tatsächlich um einen QC gehandelt hat. Im Vorfeld angekündigte wissenschaftliche Veröffentlichungen seitens D-Wave Systems stehen noch aus. Die Firma hat auch seit der angeblichen Präsentation keine weiteren Pressemeldungen mehr herausgegeben.

Von einem Quantencomputer mit einer großen Anzahl Qubits ist man aber noch weit entfernt. Hauptprobleme beim Bau von Quantencomputern zur Lösung komplexer Probleme sind die Dekohärenz, die den Quantenzustand durch Kopplung an die Umgebung stört, sowie die Skalierbarkeit, also die Frage, wie man ein System mit einer großen Zahl von Qubits realisieren kann. Einzelne Qubits wurden bereits mit einer Vielzahl verschiedener Technologien realisiert, u. a. mit Ionenfallen, Kernspinresonanz, Supraleiter-Strukturen (Josephson-Kontakte oder SQUIDs), einzelnen Photonen oder Quantenpunkten. Es ist noch nicht abzusehen, welche dieser Technologien sich letztendlich durchsetzen wird.

Eine weitere Art, den Quantencomputer weniger fehleranfällig zu machen, wäre der topologische Quantencomputer, welcher mit Hilfe von mit Anyonen gebildeten Quantenknoten arbeiten soll. Daran arbeitet z.B. die Firma Microsoft in ihrem Project Q.

Feed-Forward macht Quantencomputer deterministisch.

Das Problem der Zufälligkeit kann elegant umgangen werden indem man schnell genug die Art der Messung des nächsten Photons so anpasst, dass der Fehler kompensiert wird (Error Correction). Man adaptiert dadurch sozusagen „in Echt-Zeit" die Software des Computers; das Problem der Zufälligkeit wird ausgeschaltet. Diese schnelle Adaptierung der späteren Messungen erfordert so genanntes „aktives Feed-Forward" (Vorwärtskopplung), das natürlich aufgrund der Geschwindigkeit der Photonen sehr schnell sein muss. Dies haben Anton Zeilinger und sein Wiener Quantencomputer-Team entwickelt.

Nicht zu verwechseln mit Quantencomputern ist die Quantenschlüsselverteilung, bzw. Quantenkryptografie.

• Quanteninformatik
• Quanteninformation
• Qubit
• Quantenverschränkung
• Quantenteleportation
• David Deutsch
• Richard Feynman
• DNA-Computer
• QNN (quantum neural network)
• BQP
• Quantenkryptografie

libquantum

C-Bibliothek zur Simulation von Quantencomputern

• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge 2000, ISBN 0-521-63503-9
• Matthias Homeister: Quantum Computing verstehen. Vieweg, Wiesbaden 2005, ISBN 3-528-05921-4
• J.B. Waldner: Nanocomputers and Swarm Intelligence, ISTE, S.150-S.159, ISBN 1847040020.
• Wolfgang Tittel u.a.: Quantenkryptographie in: Physikalische Blätter 55 (6) 1999, S. 25
• Dagmar Bruß: Quanteninformation. Fischer Taschenbuch Verlag, Frankfurt am Main 2003, ISBN 3-596-15563-0
• Einsteins unverhofftes Erbe. Quanteninformationstechnologie. 2005

  Broschüre des Bundesministeriums für Bildung und Forschung

1. ↑ Wolfgang Richter: Rechenwunder, bitte warten , in: Financial Times Deutschland vom 14. Februar 2007.

• Quantensprung für verschränkte Atome - Forscher erzielen Erfolg auf dem langen Weg zum Quantencomputer - Bericht über einen Artikel im Wissenschaftsmagazin Nature (Bd. 438, S. 639 und 643, 2005)
• Erstes "Quantenbyte" erzeugt (Pressebericht der Österreichischen Akademie der Wissenschaften)

Weitere Seiten in englischer Sprache:

• Howstuffworks "How Quantum Computers Work" - Eine englische Beschreibung von Quantencomputern
• QCL - A Programming Language for Quantum Computers (QCL - eine Programmiersprache für Quantencomputer)
• Quantum Computing ("Stanford Encyclopedia of Philosophy" inkl. Literaturangaben)

Vorlage:Link FA

• Quanteninformatik
• Rechnerarchitektur