Quantencomputer

Ein Quantencomputer bzw. Quantenrechner ist ein Computer, der die Gesetze der Quantenmechanik ausnutzt, um gewisse Rechnungen effizienter durchzuführen als konventionelle Computer (die zwar quantenmechanische Effekte in der Realisation ihrer Bauteile nutzen, für deren Rechenprozesse jedoch die klassische Physik ausreichen würde).

Prinzip

Statt Bits benutzt ein Quantencomputer so genannte Qubits (Abkürzung für Quantenbits) als Grundlage. Qubits können nicht nur die Werte (Zustände) 0 und 1 annehmen, sondern auch beliebige Superpositionen dieser Zustände. Außerdem sind verschränkte Zustände mehrerer Qubits möglich.

Nochmal als tabellarische Übersicht:

\neq

a_1 \cdot | 01 \rangle + a_2 \cdot | 10 \rangle

Rechnerart	Datenart	=	Schreibweise oder Beispiel
Analog-Rechner	4-Kanäle	=	$a_1, a_2, a_3, a_4$
Analog-Rechner erlaubt Superposition		=	$a_1 \cdot$ ^*
Digital-Rechner	2-Bit	=	$00,01,10,11$
Digital-Rechner	1-Bit	=	$0,1$
Quanten-Rechner Schreibweise	1-Qubit	=	> 0 \rangle ,
Quanten-Rechner erlaubt Superposition	1-Qubit	=	a_1 \cdot > 0 \rangle+ i \cdot a_2 \cdot
Quanten-Rechner Schreibweise	2-Qubit	=	> 00 \rangle ,
Quanten-Rechner. Superposition eines 2-Qubit erlaubt Verschränkung	> a_2,a_1 \rangle

Ein praktischer Quantencomputer wird wegen der Dekohärenz nur einzelne Teilrechnungen mit Qubits ausführen können und nicht ohne klassische Bits auskommen. Nach dem von-Neumann-Mess-Schema tritt dabei kein Kollaps der Wellenfunktion auf.

Ein Quantencomputer kann prinzipiell genau dieselben Probleme berechnen wie ein klassischer Computer, da ein klassischer Computer einen Quantencomputer simulieren kann und umgekehrt. Allerdings ist ein Quantencomputer bei einer bestimmten Klasse von Problemen schneller als ein klassischer Computer. Dies liegt daran, dass geeignete Quantenalgorithmen, die Quantenparallelismen (d. h. die Möglichkeit, mit einer Superposition verschiedener Eingabedaten zu rechnen) und/oder Verschränkung geschickt nutzen, ein Problem mit sehr viel weniger Operationen lösen können als ein klassischer Computer.

Zum Beispiel kann ein Quantencomputer in 8 Qubits grundsätzlich alle 2⁸ = 256 Werte gleichzeitig (in Superposition) speichern, und nicht nur einen wie im klassischen Fall. Wenn er nun auf diesen Qubits Rechenoperationen ausführt, werden alle Werte gleichzeitig verarbeitet, und er ist genauso schnell, als wäre nur ein einzelner Wert gespeichert. Mit (8-Qubit-)Quantencomputern ist es also prinzipiell möglich, die Werte einer Funktion an 256 Stellen gleichzeitig ohne Geschwindigkeitsverlust zu berechnen. Somit wäre ein Quantencomputer exponentiell schneller als ein klassischer Computer. Das Problem besteht jetzt nur darin, dass es nicht möglich ist, alle 256 Rechenergebnisse aus den Qubits auszulesen. Aus quantenmechanischen Gründen kann man nur das Endergebnis der Rechnung für einen zufällig gewählten Eingabewert erhalten. Das heißt, die anderen 255 Berechnungen werden einfach „vergessen“, womit ein Quantencomputer dann wieder doch nicht schneller als ein klassischer Computer wäre. Allerdings kommt man manchmal mit gewissen Tricks trotzdem an eine gewünschte Information, für die man alle 256 Rechenergebnisse benötigt, wie zum Beispiel im Algorithmus von Shor. Der Unterschied ist dabei allerdings, dass die 256 Rechenergebnisse nur Zwischenergebnisse sind und nie als Endergebnis zu Tage treten.

Der tatsächliche Geschwindigkeitsvorteil ist jedoch abhängig davon, wie schnell eine einzelne Operation in einer konkreten physikalischen Realisierung eines Quantencomputers abläuft. Ein klassischer Computer kann einen Quantencomputer i. A. nur mit exponentiellem Aufwand simulieren, wohingegen ein Quantencomputer einen Quantencomputer (von dem der klassische Computer ein Spezialfall ist) mit polynomiellem Aufwand simulieren kann.

Dem Quantencomputer verwandt ist der Quanten-Simulator, gewissermaßen ein spezieller Quantencomputer, der für die Simulation bestimmter anderer Quantensysteme optimiert ist.

Algorithmen

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

n

Einträgen im schlimmsten Fall alle Einträge ansehen (d. h. vergleichen), klassisch ist dieses Problem also in Zeit

\Theta(n)

lösbar. Auf einem Quantencomputer kann man dies mit dem Grover-Algorithmus in lediglich

O(\sqrt{n})

Operationen erledigen. Diese Schranke ist sogar scharf, das heißt, kein Quantenalgorithmus kann dieses Problem in (asymptotisch) weniger Operationen lösen.

Forschung

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 an 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.

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.

Siehe auch

Literatur

Einsteins unverhofftes Erbe. Quanteninformationstechnologie. 2005
Broschüre des Bundesministeriums für Bildung und Forschung

Weblinks

Elektronischer Pressespiegel zum Thema Quantencomputer
Telepolis: Wissen schaffen mit Quantencomputern
Telepolis: Alice und die grinsende Schrödingerkatze
Quantencomputer knacken die Codes von morgen
QCL - eine Programmiersprache für Quantencomputer (engl.)
An Introduction to Quantum Computation and Communication Vortrag von Rob Pike (Audio und Folien)
Fraunhofer Quantum Computing Simulator - Ein kostenloser web-basierter paralleler Quantensimulator, der Quantenschaltkreise und Hamiltonians bis 31 qubit simuliert (engl.)
www.quantencomputer.de - leicht verständliche Einführung
www.wissenschaft.de: 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

Quantenphysik | Quanteninformatik | Rechnerarchitektur