(c) DX, Fotolia

Die quelloffene C-Bibliothek Libquantum ermöglicht simuliertes Quantencomputing auf einem gewöhnlichen PC. Der erste Teil des zweiteiligen Artikels führt in Quantencomputing ein und endet mit einer allgemeinen Beschreibung von Libquantum. Der zweite Teil zeigt an einem Beispiel, was sich mit der Libquantum-Bibliothek anstellen lässt.

Heutige Computer leisten genug Rechenarbeit, um zum Beispiel Systeme der klassischen Physik mit Milliarden von Teilchen zu simulieren. Ein Beispiel ist die Millenium-Weltallsimulation auf Superrechnern. Dieselbe Rechenleistung wird mit den Gesetzen der Quantenphysik aber schon bei 40 Teilchen erforderlich: Quantenphysik gehorcht anderen, komlizierteren Gesetzen als die klassische Physik.

Um auch quantenmechanische Systeme mit hohen Teilchenzahlen zu simulieren, sind Quantencomputer erforderlich. Quantencomputer leisten mehr Rechenarbeit als klassische Rechenmaschinen, unter anderem deshalb, weil sie mit mehr als zwei Zuständen arbeiten.

Anfänge heute und Rechner von morgen

Für Quantenrechner bedarf es entsprechend anderer Algorithmen. Der erste speziell für einen Quantencomputer erstellte Algorithmus mit praktischer Anwendbarkeit war der 1995 von Peter Shor entdeckte Algorithmus zur Primfaktorzerlegung: Er ermöglichte, RSA-verschlüsselten Nachrichten zu knacken. Ein weiteres praktisches Beispiel ist die Suche in unsortierten Datenstrukturen. Das können herkömmliche Algorithmen nur langsam, da sie alle Datensätze sequentiell durchsuchen.

Der Hauptnutzen der Rechenkraft von Quantencomputern liegt jedoch in der Simulation komplexer, den Gesetzen der Quantenmechanik folgender Systeme. Das schafft völlig neue Möglichkeiten zum Untersuchen von Materialien in Physik, Chemie, Biologie und Medizin. So ist es beispielsweise denkbar, Quantencomputer zur Simulation komplizierter biochemischer Vorgänge im menschlichen Körper einzusetzen. Es gibt Wissenschaftler, die sich theoretisch mit solchen Konzepten beschäftigen, beispielsweise in der Quantenbiologie.

Die bisher durchgeführten Experimente gehören in die Kategorie “Proof of Concept” und demonstrierten Quantencomputing mit bis zu 8 Bit. Im Moment sind ernstzunehmende Quantencomputer noch Zukunftsmusik. Wie der Quantencomputer der Zukunft aussieht, ist noch völlig offen.

Quantenrechner: Null, Eins, Beides

Um die Funktionsweise eines Quantenrechners zu verstehen, hilft es, die Unterschiede zu einem klassischen Rechner zu betrachten. In einem klassischen Computer ist die kleinste Informationseinheit das Bit, welches mit den Werten 0 oder 1 einen von zwei Zuständen darstellt. In einem Quantencomputer ist die kleinste Informationseinheit ein Qubit, welches mehr als zwei Zustände kennt: Ein Qubit zeigt einen Überlagerungszustand (Superposition) von Zuständen an.

Quantenmechaniker beschreiben die Zustände eines Quantums mit |0> und |1> (Dirac-Notation). Diese Notation unterscheidet zwischen dem Zustand (zum Beispiel |0>) und der eigentlichen Zahl (zum Beispiel 0). Auf die Art zeigen Wissenschaftler an, dass sich ein Quantum nur mit einer gewissen Wahrscheinlichkeit in dem einen oder anderen Zustand befindet. Ein Qubit zeigt nun einen Überlagerungszustand aus den Basiszuständen |0> und |1> an, also die Wahrscheinlichkeit für den einen oder den anderen Zustand.

Anschaulich lässt sich ein Qubit am besten als Vektor in der sogenannten Bloch-Kugel darstellen. Je näher der Endpunkt des Vektors an einem Basiszustand liegt, desto größer ist die Wahrscheinlichkeit, dass das Qubit ihn einnimmt. Die Zustände |0>+|1> und |0>-|1> bezeichnen die größtmögliche Überlagerung der Basiszustände: Hier besteht die Wahrscheinlichkeit von 50 Prozent, den Wert 0 oder 1 zu messen.

Ein Qubit stellt den Überlagerungszustand aus zwei Basiszuständen dar. Je näher der Endpunkt des Vektors an einem Basiszustand liegt, desto größer ist die Wahrscheinlichkeit, dass das Qubit ihn einnimmt. Ein Wert auf der Plus-Minus-Eins-Achse beschreibt das so genannte Phasenverhältnis der beiden Basiszustände, das heißt die Verschiebung zueinander.

Das Plus- und Minuszeichen bezeichnet das so genannte Phasenverhältnis der beiden Basiszustände, das heißt die Verschiebung zueinander. Dieses Phasenverhältnis ist ein zusätzlicher Freiheitsgrad, der in klassischen Systemen nicht auftritt – er ist ein Grund für die Überlegenheit des Quantencomputers. Da es das Phasenverhältnis in allen Superpositions-Zuständen gibt, spielen diese zusätzlichen Zustände eines Qubits in jedem Quantenalgorithmus eine große Rolle.

Gatter in Quantenrechnern: Zwingend reversibel

Am Ende des Rechenprozesses eines Quantencomputers muss das Ergebnis aber wieder in den klassischen Werten 0 oder 1 vorliegen, denn letzten Endes haben wir es mit binären Maschinen zu tun. Um zu entscheiden, in welchem der Basiszustände |0> oder |1> sich das Qubit befindet, ist eine Messung nötig. Nun ist zu beachten, dass die Messung den Zustand des Qubits verändert: Wenn eine Messung den Wert 0 ergibt, befindet sich das Qubit nach der Messung in einem anderen Zustand als vorher.

Analog zu klassischen Bits können Qubits durch Gatter manipuliert werden, die dann Quantengatter heißen. Der Programmierer implementiert Quantenalgorithmen, indem er elementare Gatter, von denen nur einige wenige nötig sind, hintereinander schaltet. Allerdings müssen Quantengatter reversibel arbeiten. Ein typisches Beispiel eines nicht-reversiblen Gatters ist das AND-Gatter. Der Endzustand |0> sagt hier nichts über die beiden Anfangszustände, da das Gatter diese Information nicht transportiert. In einem klassischen System würde durch Setzen des Endzustandes jedoch keine Information verloren gehen. In einem System von Qubits ginge jedoch die Superposition verloren – der entscheidende Informationsträger. Die Quantengatter müssen also reversibel sein, damit die Phaseninformation nicht verloren geht.

Das hat zur Folge, dass Quantencomputer speziell angepasste Quantenalgorithmen mit Quantengattern benötigen. Denn mit Quantengattern ist es möglich, Phasenverhältnisse zwischen Basiszuständen in Wahrscheinlichkeitsverteilungen umzuwandeln, anstatt sie im Endzustand aufzuheben.

Im Netz der Quanten: Verschränkung

Interessant wird es, wenn ein Quantengatter auf mehrere Qubits wirkt. Das Gatter kann ein Qubit in Abhängigkeit von einem anderen Qubit ändern. Die Superposition des einzelnen Qubits wirkt sich dann auf das Gesamtsystem aus. Ein solcher innerer Abhängigkeitszustand des Systems wird als verschränkt bezeichnet.

Verschränkung lässt sich nur auf der Ebene des Gesamtsystems aller verschränkten Qubits beschreiben. Die Beschreibung des einzelnen Qubits verliert an Bedeutung (“Das Ganze ist mehr als die Summe der Teile”). Bei einem maximal verschränkten System geht bei der Messung eines Teilsystems nicht nur die Superposition des Teilsystems verloren, sondern auch die Superposition des restlichen Systems bricht zusammen und es befindet sich zwingend ebenfalls in einem klassischen Zustand.

Allerdings ist Verschränkung nicht mit geläufigen Korrelationen vergleichbar. Eine einfache geläufige Korrelation ist: Wenn man die Farbe eines Sockens einer Person kennt, kann man in der Regel die Farbe des anderen Sockens vorhersagen. Es gibt Quantengatter, nach denen sich verschränkte Zustände völlig anders verhalten als solche klassischen Korrelationen.

Die Entfernung der verschränkten Teilsysteme voneinander spielt keine Rolle. Quantenphysiker beobachteten Verschränkung von Teilsystemen, die über 100 Kilometer auseinander lagen. Dies ermöglicht Anwendungen wie Quanten-Teleportation oder Quantenkryptographie. Die Verschränkung ist ein wichtiger Grund, warum Quantencomputer sehr viel schneller arbeiten als herkömmliche Rechner. Gleichzeitig sorgt sie aber auch dafür, dass man Quantencomputer auf klassischen Rechnern nicht effizient simulieren kann, da der Rechenaufwand unter Berücksichtigung aller möglichen verschränkten Zustände exponentiell mit der Anzahl der Qubits wächst. Daher lassen sich auf herkömmlichen Rechnern nur wenige Qubits mit vertretbarem Aufwand simulieren.

Manchmal ist die Verschränkung allerdings ein unerwünschter Effekt. In jedem realen Experiment treten die Qubits mit der Umgebung in Kontakt. Dies kann durch zufällige Stöße mit anderen Teilchen oderdurch die Wechselwirkung mit elektromagnetischem Vakuum geschehen. Solch eine Wechselwirkung führt zu einerVerschränkung der Qubits mit der Umgebung. Und dies führt wiederum dazu, dass die Superpositions-Zustände der Qubits zerstört werden und ein Quantenalgorithmus ein falsches Ergebnis liefert. Dieser Mechanismus wird als Dekohärenz bezeichnet und stellt das Hauptproblem auf dem Weg zu einem Quantencomputer mit einer großen Zahl von Qubits dar.

Libquantum: Tool für simuliertes Quantencomputing

Will man zum gegenwärtigen Zeitpunkt also Quantenalgorithmen untersuchen, bleibt nur der klassische Computer. Für Simulationen eines Quantencomputers auf einem normalen Rechner ist die C-Bibliothek Libquantum da:

• Libquantum ist universell, das heisst beliebige Quantenalgorithmen, die auf einem echten Quantencomputer lauffähig wären, können implementiert werden.
• Die Simulation bildet die physikalischen Gesetzmäßigkeiten möglichst genau ab, denen ein Quantencomputer unterliegt (zum Beispiel Dekohärenz).
• Die Performance der Bibliothek ist hoch, damit auch komplexe Systeme mit akzeptablem Zeit- und Hardwareaufwand untersucht werden können.
• Die Lizenzierung als GPL-Software stellt sicher, dass Vorgehensweise und Ergebnisse der Simulation nachvollziehbar sind.

Hier zerlegt der Shor-Algorithmus wird mit Hilfe von Libquantum die Zahl 15 in ihre Primfaktoren. Der erste speziell für einen Quantencomputer erstellte Algorithmus mit praktischer Anwendbarkeit war der 1995 von Peter Shor entdeckte Algorithmus zur Primfaktorzerlegung.

Die erste Version von libquantum wurde 2003 veröffentlicht. Seitdem kamen viele Features hinzu, beispielsweise Quantenfehlerkorrektur-Verfahren oder Zustände mit klassischen Wahrscheinlichkeitsverteilungen. Die im September letzten Jahres erschienene Version ermöglicht die Simulation von beliebigen Problemen aus der Quantenmechanik (siehe die Meldung auf Linux-Magazin Online). Eine Simulation des Faktorisierungsalgorithmus von Shor, die mit Hilfe von Libquantum erstellt wurde, ist im SPEC-Benchmark CPU2006 enthalten.

Hier geht es zum zweiten Teil des Artikels, einem Workshop mit Libquantum.