Adressierungsfreie Quanten-Zellularautomaten

Adressierungsfreie Quanten-Zellularautomaten.

Die Regeln, die in der Welt der Quantenteilchen gelten, widersprechen unserer Intuition und unseren Erfahrungen aus der Alltagswelt. Auf ähnliche Überraschungen stößt man, wenn man von der klassischen Informationstheorie zur Theorie der Quanteninformationsverarbeitung übergeht: der Speicherung von Information auf und Übertragung zwischen so genannten Quantenbits. Die Grundpfeiler für die Quanteninformationstheorie schuf der amerikanische Informationstheoretiker Peter Shor (1994) mit der Entwicklung eines Algorithmus, der es erlaubt, sehr große Zahlen in ihre Primfaktoren zu zerlegen. Der Algorithmus erzielt seine besondere Effektivität durch die Ausnutzung eines Phänomens, das nur Quantenteilchen eigen ist: mehrere Input-Werte können gleichzeitig verarbeitet werden, indem man ihre Zustände kohärent überlagert. Dadurch und durch eine geschickte Ausnutzung von Quantenkorrelationen sind Quanten-Computer in der Lage Probleme zu lösen, welche die Möglichkeiten klassischer Rechnerarchitekturen sprengen, da hier die Zahl der notwendigen Speichereinheiten exponentiell mit der Länge des Problems anwächst. Zu dieser Art von Problemen zählen z.B. das Faktorisieren großer Zahlen und andere zahlen- und gruppentheoretische Probleme, oder das Potenzieren großer Matrizen und das Berechnen von Knoteninvarianten. Eine vor allem für Geheimdienste interessante Anwendung des Shor’schen Algorithmus ist die dadurch mögliche Dekodierung von verschlüsselten Daten.

In der klassischen Informationstheorie werden Bits und Bytes unabhängig davon definiert, wie sie physikalisch implementiert werden. Universelle Turing-Maschinen oder Zelluläre Automaten bieten von der Physik losgelöste Konzepte zur Datenverarbeitung. Dieser hohe Grad der Abstraktion erlaubt es, Informationstheorie als ein übergeordnetes Konzept zu betreiben, statt für jedes physikalische System eine eigene Informations- und Datenverarbeitungstheorie zu entwerfen. Die Erfolge dieses Ansatzes sind unbestritten und haben einen nicht zu vernachlässigen Beitrag für den Übergang in das heutige Informationszeitalter geleistet.

Die Quanten-Informationstheorie versucht, nach dem klassischen Vorbild eine neue Abstraktion der Begriffe der Quanteninformation und der Quantenverarbeitung losgelöst von deren physikalischen Implementierungen zu definieren. Dabei tritt das Quanten-Bit (Qubit) an die Stelle des klassischen Bits: ein abstrahierter zwei-dimensionaler Hilbertraum, der neben den klassischen Zuständen 0 und 1 auch sämtliche Überlagerungen (Superpositionen) der beiden Zustände zulässt (siehe Abb.1).

Es gibt eine Vielzahl unterschiedlicher Konzepte und Modelle, wie Quanten-Datenverarbeitung gestaltet werden kann: schaltkreisbasierte Quantencomputer, Quanten-Turingmaschinen, messbasierte Quantencomputer, adiabatische Grundzustands-Quantencomputer, etc. Für all diese Konzepte stellt sich die Frage nach ihrem theoretischen rechnerischen Potential sowie nach möglichen physikalischen Realisierungen. Ein weiteres Modell ist der Quanten-Zellularautomat, der sowohl als theoretisches Konzept in Analogie zum klassischen Zellulären Automaten als auch als konkreter Implementierungsvorschlag in optischen Gittern von Interesse ist.

Zellularautomaten kann man sich als ein Netz von miteinander verbundenen autonomen kleinen Einheiten, den Zellen, vorstellen. Übergangsregeln, die nur von der Wechselwirkung mit den nächsten Zellen-Nachbarn abhängen, legen fest, wie sich der interne Zustand der Zelle mit der Zeit ändert. Anhand dieser Regeln wird der interne Zustand für alle Zellen gleichzeitig nach festen diskreten Taktzyklen neu berechnet. Bereits unter Verwendung relativ einfacher Übergangsregeln zeigen die Zellen als Verbund ein komplexes Verhalten. Sie können als universelle Rechenmaschinen dienen, deren unterschiedliche Rechenprogramme bereits in die Anfangszustände der einzelnen Zellen kodiert werden. Aufgrund der dadurch erzielten massiven Parallelität sind Zellularautomaten für die Lösung bestimmter Probleme besser geeignet als z.B. Turing Maschinen.

Ein Quanten-Zellularautomat besteht nun ebenfalls aus solchen vernetzten elementaren Zellen, deren interner Zustand jeweils durch ein Quantensystem beschrieben wird. Die Definition einer Übergangsregel ist hier weitaus schwieriger als beim klassischen Analogon. Um die zugrunde liegende Quantenstruktur auszunutzen, sollten solche Übergangsregeln in der Lage sein, Verschränktheit zwischen verschiedenen Zellen zu erzeugen. Operationen, die Verschränktheit erzeugen, vertauschen aber im Allgemeinen nicht miteinander, so dass es hier eine Rolle spielt, in welcher Reihenfolge die Übergangsregel auf die einzelnen Zellen angewendet wird. Dies verträgt sich aber nicht mit dem charakteristischen Merkmal, das einen klassischen Zellularautomaten von einem herkömmlichen Rechner unterscheidet: die Übergangsregeln gleichzeitig auf alle Zellen anzuwenden.

Die Definition eines Quanten-Zellularautomaten verzweigt sich darum an dieser Stelle in eine Vielzahl möglicher Ansätze. Für jedes dieser Modelle stellt sich unter anderem die Frage, ob es dieselben, bessere oder schlechtere rechnerische Möglichkeiten als ein schaltkreisbasierter Quantencomputer erlaubt. Ein Ansatz besteht z.B. darin, nur solche Übergangsregeln zuzulassen, deren zugehörige Operationen miteinander vertauschen. Dies stellt aber eine so massive Einschränkung dar, dass es fraglich ist, ob noch das volle Potential der Quantentheorie ausgenutzt werden kann.

Die klassische Informationstheorie basiert auf der Adressierbarkeit der kleinsten Speichereinheiten. Bei der experimentellen Realisierung von Quanten-Bits kann sich diese schwierig gestalten oder sogar ausgeschlossen sein. Eine der viel versprechenden Möglichkeiten zur Darstellung von Quanten-Zellularautomaten stellen z.B. Atome in optischen Gittern dar. Ein optisches Gitter entsteht durch eine Überlagerung gekreuzter Laserstrahlen in der Art, dass ein Lichtfeld entsteht, dessen Form an einen Eierkarton erinnert. Neutrale Atome können in den Vertiefungen dieses Feldes festgehalten werden und bilden so eine regelmäßige Struktur. Jedes Atom mit seinen internen Zuständen kann als eine einzelne Zelle eines Quanten-Zellularautomaten betrachtet werden. Durch Veränderung der Parameter des optischen Gitters (indem Intensität und Wellenlänge des Laserlichtes modifiziert werden) sowie durch Anwendung zusätzlicher elektromagnetische Felder können eine Vielzahl von möglichen Übergangsregeln realisiert werden. Die Atome sind dabei allerdings sehr dicht beieinander, so dass die Adressierung einzelner Atome an die experimentellen und auch physikalischen Grenzen stößt. Die Präpäration von komplizierten Anfangszuständen sowie das Messen einzelner Zellen gestalten sich hier daher als schwierig.

Das Konzept des Zellulären Automaten wird daher an dieser Stelle so modifiziert, dass der Zwang zur Adressierbarkeit umgangen wird. Das bedeutet auch, dass die Rechenprogramme nicht mehr in den Anfangszustand der einzelnen Zellen kodiert werden. Vielmehr wird der Startzustand so festgelegt, dass alle Zellen einheitlich in demselben Zustand‚ z.B. ‚0’ sind. Auch das Ergebnis einer Berechnung muss daher durch eine kollektive globale Messung ausgelesen werden, ohne dabei einzelne Zellen zu adressieren. Die Übergangsregel hingegen darf nun von Schritt zu Schritt geändert werden.
Die Möglichkeiten eines solchen adressierungsfreien Zellularautomaten scheinen im Vergleich zu der adressierbaren Bauart sehr beschränkt. Da sowohl der Ausgangszustand symmetrisch, d.h. für alle Zellen gleich ist, als auch die Übergangsregeln translationssymmetrisch sind, d.h. auf alle Zellen in der gleichen Weise wirken, lassen sich auch nur Zustände erzeugen, die selbst wieder translationssymmetrisch sind.

Im klassischen (deterministischen) Fall würde das eine sehr starke Einschränkung bedeuten, denn hier verfügt jede Zelle nur über eine begrenzte Anzahl von Zuständen, so dass keine komplexen Berechnungen mehr möglich sind. In einem adressierungsfreien Quanten-Zellularautomat skaliert hingegen die Anzahl der möglichen translationssymmetrischen Zustände weiterhin mit der Anzahl der Zellen, wenn auch weit weniger stark als ohne diese Einschränkung. Da aber der (reduzierte) Zustand aller Zellen gleich ist, können nicht in verschiedene Zellen unterschiedliche Informationen kodiert werden. Es muss daher ein neues Konzept gefunden werden, mit dem mehrere Qubits gleichzeitig realisiert und verarbeitet werden können.

Um Informationen auszulesen, kann man einen Lese/Schreibe-Kopf – realisiert durch eine Störstelle – über das Gitter der Speicherzellen laufen lassen. Dieses Verfahren setzt aber voraus, dass die Störstelle adressierbar ist, was z.B. bei neutralen Atomen in optischen Gittern nicht machbar ist. Die Stärke der Quantenmechanik liegt in der Möglichkeit, verschiedene Zustände miteinander zu überlagern. So ist es möglich, einen beliebigen, auf wenige Zellen beschränkten Zustand (i.e. die Störstelle) in einen globalen (translationssymmetrischen) Zustand zu überführen, indem man ihn durch eine Superposition aus allen möglichen verschobenen Versionen des Ausgangszustandes ersetzt. Es wird also global (in allen Zellen) eine Überlagerung von einem Defekt und einem normalen Zustand erzeugt, und die Information wird relativ zu dem delokalisierten Defekt gespeichert.

Eine Idee ist nun, einen kompletten Quantencomputer bzw. eine Quanten-Turingmaschine nach diesem Konzept aufzubauen. Eine solche Quanten-Turing-Maschine besteht aus einer bestimmten Menge von Daten-Qubits und einem Lese/Schreibe-Kopf. Dies kann zum Beispiel auf einem Quanten-Zellularautomaten mit Zellen, die jeweils drei Qubits beinhalten, realisiert werden (siehe Abb.2).

Das erste Qubit ist jeweils das Daten-Qubit, das zweite Qubit definiert die An- bzw. Abwesenheit des Schreibkopfes und das dritte Qubit erlaubt die Speicherung eines internen Zustandes des Schreibkopfes. Der symmetrisierte Zustand besteht aus der Superposition von allen möglichen Positionen, an der diese Quanten-Turing-Maschine sitzen könnte, d.h. man erhält eine Art delokalisierte Quanten-Turingmaschine (siehe Abb.3). Um diese Quanten-Turing-Maschine zu betreiben, muss sich der Lese/Schreibe-Kopf bewegen und mit den Daten-Qubits wechselwirken können. Diese Aufgabe lässt sich leicht in die jeweiligen Übergangsregeln für den Quanten-Zellularautomaten übersetzen. Da die Daten-Qubits nur mit dem Kopf wechselwirken und nicht miteinander, vertauschen die Übergangsregeln der einzelnen Zellen miteinander.

Man erhält so eine Superposition von Quanten-Turingmaschinen, die alle gleichzeitig dieselbe Berechnung durchführen, d.h. eine voll funktionstüchtige delokalisierte Quanten-Turingmaschine. Das Auslesen der Daten-Qubits nach Beendigung des Rechenvorgangs lässt sich ebenfalls ohne Adressierung durchführen. Man muss nur durch eine entsprechende Übergangsregel das gewünschte Daten-Qubit in den internen Speicher des Kopfes transferieren. Dessen Zustand kann dann global ausgelesen und davon ausgehend auf den Zustand des Daten-Qubits zurück geschlossen werden. Die einzelnen Daten-Qubits sind hier nicht in den einzelnen Zellen des Quanten-Zellularautomaten gespeichert, sondern in dem kollektiven Superpositionszustand kodiert. Dasselbe Konzept funktioniert auch, wenn man statt nur einer solchen Quanten-Turingmaschine mehrere Quanten-Turingmaschinen im Quanten-Zellularautomaten implementiert und symmetrisiert.

Dieser Ansatz bietet also die Möglichkeit, trotz der Translationssymmetrie mehrere verschiedene Qubits zu kodieren und zu verarbeiten. Die Frage bleibt, wie es möglich ist, die notwendige Anfangsstruktur zu erzeugen. Eine Möglichkeit besteht darin, alle Zellen in eine Überlagerung von ‚Kopf Anwesend’ und ‚Kopf Abwesend’ zu bringen, welches leicht aus dem Anfangszustand erreicht werden kann. Dieser Zustand verhält sich dann genau so, als hätte man zufällig Lese/Schreibköpfe auf die Zellen verteilt. Bei geeigneter Wahl der Amplituden von ‚Kopf Anwesend’ und ‚Kopf Abwesend’, sind diese Köpfe im Mittel weit auseinander, so dass sie sich nicht gegenseitig behindern.

Im Ergebnis erhält man einen adressierungsfreien Quanten-Zellularautomaten, der in der Lage ist, eine Superposition von verschiedenen Konfigurationen von delokalisierten Quanten-Turing-Maschinen effektiv zu simulieren. Er hat damit dieselben rechnerischen Möglichkeiten wie ein herkömmlicher Quantencomputer, ist aber physikalisch viel leichter umzusetzen.