Die künftige Geschichte der Quantencomputer

Ein Quantencomputer ist ein Computer, der die physikalischen Gesetze der Quantenmechanik ausnutzt, um gewisse Rechnungen effizienter (schneller) 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).

Der wohl berühmteste Algorithmus für Quantencomputer ist der Shor-Algorithmus (1994) zur Faktorisierung des Produktes zweier Primzahlen. Aber auch der generische Algorithmus von Grover zum Suchen innerhalb von unstrukturierten (z.B. unsortierten) Daten ermöglicht einen (wenn auch geringeren) Geschwindigkeitsvorteil gegenüber einem klassischen Computer.

Statt Bits benutzt ein Quantencomputer so genannte Qubits 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. 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 Quantenparallelismus (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. Der tatsächliche Geschwindigkeitsvorteil ist 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.

Quantencomputer mit einer sehr geringen Anzahl Qubits sind bereits gebaut worden und haben z.B. den Shor-Algorithmus erfolgreich ausgeführt (hierbei wurde die Zahl 15 in ihre Primfaktoren 3 und 5 zerlegt) [galliard.ch: Es ist zu bemerken, dass sich der Algorithmus eine Eigenschaft des Produktes 15 zu Nutze macht und demnach nicht allgemein arbeitet].

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, einzelnen Photonen oder Quantenpunkten. Es ist noch nicht abzusehen, welche dieser Technologien sich letztendlich durchsetzen wird.