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 überwiegend 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 und auch Quantencomputer mit wenigen Qubits realisiert, 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.

Quantencomputer dienen nicht dazu, Quantenkryptographie durchzuführen. Hierbei handelt es sich um ein eigenes Teilgebiet der Quanteninformatik, auf welchem es bereits realisierte und kommerzialisierte Systeme gibt.

Weiteres empfehlenswertes Fachwissen

Was ist der richtige Weg, um die Wiederholbarkeit bei Waagen zu überprüfen?

Dauerhaft genaue Prüfgewichte dank 12 kostenloser Tipps

Wie kann man Pipetten schnell überprüfen?

Grundprinzip

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.

Qubits

  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, der andere die 1. In Anlehnung an die in der Quantenphysik gebräuchliche Dirac-Notation schreibt man und 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 oder sein muss, wie dies für die Bits des klassischen Computers der Fall ist. Vielmehr ergibt sich der Zustand eines Qubits zu

Dabei sind c₀ und c₁ komplexe Zahlen. Zur Normierung fordert man noch | c₀ | ² + | c₁ | ² = 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 P(0) = | c₀ | ². Man darf dieses probabilistische Verhalten allerdings nicht so interpretieren, dass das Qubit mit einer bestimmten Wahrscheinlichkeit im Zustand und mit einer anderen Wahrscheinlichkeit im Zustand 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.

Quantenregister

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 2^N-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 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 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 N-Bit Registers darzustellen, benötigt man N Bits an Information. Der Zustand des Quanten-Registers ist aber ein Vektor aus einem 2^N-dimensionalen Vektorraum, so dass man zu dessen Darstellung 2^N komplexwertige Koeffizienten angeben muss.

Das Superpositionsprinzip wird oft so verstanden, dass ein Quantencomputer in einem N-Qubit Register gleichzeitig alle 2^N Zahlen von 0 bis 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.

Quantum Gates

Hauptartikel Quantengatter

Beim klassischen Computer werden durch Logikgatter (engl. Gates) elementare Operationen auf den Bits durchgeführt. Mehrere Gatter werden zu einem Schaltnetz verbunden, das 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 U, die auf den Zustand des Quanten-Registers wirkt:

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

Ein Quanten-Schaltkreis besteht nun aus mehreren Quantengattern, die in fester zeitlicher Abfolge auf das Quantenregister angewendet 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.

Physikalische Realisierung

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 die natürlichen physikalischen Einschränkungen beachten, die im Folgenden beschrieben werden.

Fehler

Relaxation

Ü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 nach einer gewissen Zeit mit einer bestimmten Wahrscheinlichkeit in den Zustand gesprungen ist. Diesen Prozess nennt man Relaxation. Die Relaxationszeit T₁ ist dabei exponentialverteilt.

Dekohärenz

Mit Dekohärenz ist der Verlust der Superpositionseigenschaften eines Quantenzustands gemeint. Durch den Einfluss der Umgebung entwickelt sich aus dem Superpositionszustand entweder der Zustand oder der Zustand . Dann verhält sich das Qubit nur noch wie ein klassisches Bit. Die Dekohärenzzeit T₂ 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 sogenannte Quantenfehlerkorrektur erhöht werden.

Berechenbarkeits- und Komplexitätstheorie

Da formal festgelegt ist, wie ein Quantencomputer arbeitet, können die aus der theoretischen Informatik bekannten Begriffe wie Berechenbarkeit oder Komplexitätsklasse auch auf einen Quantencomputer übertragen werden. Man stellt dabei fest, dass ein Quantencomputer keine prinzipiell neuen Probleme lösen kann, einige Probleme allerdings schneller gelöst werden können.

Berechenbarkeit

Ein klassischer Computer kann einen Quantencomputer simulieren, da die Wirkung der Gates auf dem Quantenregister einer Matrix-Vektor-Multiplikation entspricht. Der klassische Computer muss nun einfach all diese Multiplikationen ausführen, um den Anfangs- in den Endzustand des Register zu überführen.

Direkte Konsequenz dieser Simulierbarkeit ist, dass alle Probleme, die auf einem Quantencomputer gelöst werden können, auch auf einem klassischen Computer gelöst werden können. Umgekehrt bedeutet dies, dass Probleme wie das Halteproblem auch auf Quantencomputern nicht gelöst werden können.

Es lässt sich zeigen, dass die Simulation eines Quantencomputers in der Komplexitätsklasse PSPACE liegt. Man geht daher davon aus, dass es keinen Simulationsalgorithmus gibt, der einen Quantencomputer mit polynomiellen Zeitverlust simuliert.

Umgekehrt kann ein Quantencomputer auch einen klassischen Computer simulieren. Dazu muss man zunächst wissen, dass jeder logischer Schaltkreis allein aus NAND-Gattern gebildet werden kann. Mit dem Toffoli-Gatter kann man bei geeigneter Beschaltung der drei Eingänge nun ein Quantengatter erhalten, das sich auf Qubits in der Basis der klassischen Bits wie ein NAND-Gatter verhält. Außerdem lässt sich das Toffoli-Gate dazu verwenden, ein Eingangsbit zu verdoppeln. Aufgrund des No-Cloning-Theorems ist dies allerdings nur für die Zustände möglich. Diese Verdopplung (Auch Fan-out genannt) ist deshalb nötig, weil es bei einem klassischen Schaltkreis möglich ist, ein Bit auf zwei Leitungen zu verteilen.

Komplexität

Im Rahmen der Komplexitätstheorie ordnet man algorithmische Probleme sogenannten Komplexitätsklassen zu. Die bekanntesten und wichtigsten Vertreter sind die Klassen P und NP. Dabei bezeichnet P diejenigen Probleme, deren Laufzeit polynomiell von der Eingabelänge abhängt. Solche Probleme werden als praktisch lösbar angesehen. In NP liegen die Probleme, für die man die Korrektheit einer Lösung einfach (also in P) verifizieren kann. Das tatsächliche Finden einer Lösung kann dabei sehr schwer sein.

Für Quantencomputer definiert man die Komplexitätsklasse BQP. Diese enthält diejenigen Probleme, deren Laufzeit polynomiell von der Eingabelänge abhängt und deren Fehlerwahrscheinlichkeit unter 1 / 4 liegt. Aus dem vorhergehenden Abschnitt folgt, dass BQP PSPACE. Ferner gilt P BQP , da ein Quantencomputer auch klassische Computer mit nur polynomiellem Zeitverlust simulieren kann.

Wie BQP zur wichtigen Klasse NP in Beziehung steht, ist noch unklar. Man weiß nicht, ob ein Quantencomputer ein NP-vollständiges Problem effizient lösen kann oder nicht. Könnte man nachweisen, dass BQP eine echte Teilmenge von NP ist, wäre damit auch das P-NP-Problem gelöst: Dann gilt nämlich P NP. Andererseits würde aus dem Nachweis, dass NP echte Teilmenge von BQP ist, folgen, dass P echte Teilmenge von PSPACE ist. Sowohl das P-NP-Problem als auch die Frage P PSPACE sind wichtige ungelöste Fragen der theoretischen Informatik.

Algorithmen

Die bisher gefundenen Algorithmen für Quantencomputer lassen sich grob in drei Kategorien einteilen:

• Algorithmen, die auf der Quanten-Fouriertransformation beruhen. Darunter fällt auch der wohl berühmteste Algorithmus für Quantencomputer, der Shor-Algorithmus zur Faktorisierung von Zahlen. Der Zeitaufwand ist dabei polynomiell in der Anzahl der Ziffern. Im Gegensatz dazu benötigt der beste zur Zeit bekannte klassische Algorithmus exponentiell viel Zeit. Die Bedeutung von Shors Algorithmus beruht auf der Tatsache, dass die Sicherheit der weitverbreiteten asymmetrischen Verschlüsselungsverfahren wie RSA darauf basieren, dass keine effizienten Algorithmen zur Faktorisierung großer Zahlen bekannt sind.
• Quanten-Suchalgorithmen. Hierzu gehört der Grover-Algorithmus und Varianten davon. Er dient der effizienten Suchen in einem unsortierten Array. Ein gewöhnlicher Computer muss sich bei n Einträgen im schlimmsten Fall alle Einträge ansehen (d. h. vergleichen), klassisch ist dieses Problem also in Zeit Θ(n) lösbar. Auf einem Quantencomputer kann man dies mit dem Grover-Algorithmus in lediglich 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.
• Quanten-Simulation. Um quantenmechanische Systeme zu simulieren, bietet es sich an, wieder quantenmechanische Systeme zu benutzen. Mit einem geeigneten Satz von Quantengattern lässt sich jeder Hamiltonian darstellen, und in vielen Fällen reicht dazu eine geringe Zahl von Gattern aus. Algorithmen dieser Art würden insbesondere für die Quantenchemie eine immense Rolle spielen, da mit heutigen Mitteln selbst einfache Moleküle nicht ohne grobe Näherungen simuliert werden können.

Viele Algorithmen für Quantencomputer liefern nur mit einer gewissen Wahrscheinlichkeit ein korrektes Ergebnis; man spricht von probabilistischen Algorithmen. Durch wiederholtes Anwenden des Algorithmus kann die Fehlerwahrscheinlichkeit allerdings beliebig klein werden. Ist die anfängliche Erfolgswahrscheinlichkeit groß genug, reichen wenige Wiederholungen aus.

Forschung

Quantencomputer mit wenigen Qubits konnten bereits realisiert werden. So wurde Shors Algorithmus im Jahre 2001 mit einem auf Kernspinresonanz beruhenden Quantencomputer am IBM Almaden Research Center für ein System mit 7 Qubits realisiert und konnte die Zahl 15 erfolgreich in ihre Primfaktoren 3 und 5 zerlegen^[1]. Ebenso konnte im Jahre 2003 ein auf in Ionenfallen gespeicherten Teilchen basierender Quantencomputer den Deutsch-Jozsa-Algorithmus realisieren^[2].

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

Siehe auch

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

Software

libquantum 

C-Bibliothek zur Simulation von Quantencomputern

Literatur

• 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

Quellenangaben

1. ↑ L.M.K. Vandersypen et al.: Experimental realization of Shor's factorizing algorithm using nuclear magnetic resonance. In: letters to nature. Bd. 414, 20/27 Dezember 2001
2. ↑ S. Guide et al.: Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer. In: letters to nature. Bd. 421, 2003
3. ↑ H Häffner, W Hänsel, CF Roos, J Benhelm, D Chek-al-Kar, M Chwalla, T Körber, UD Rapol, M Riebe, PO Schmidt, C Becher, O Gühne, W Dür, R Blatt. Scalable multiparticle entanglement of trapped ions. Nature 438, 643 (2005)

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)