Entwurf eines nichtdeterministischen Computers zum Einsatz bei NP-Problemen

Das quantentheoretische Modell geht von einer - in gewissem Sinne - nichtdeterministischen Welt aus. Vereinfacht gesprochen wird jeder physikalischen Größe zu jedem möglichen Wert eine Wahrscheinlichkeitsdichte zugeordnet. Im Übergang zu Intervallen (z.B. Reduktion der Wahrscheinlichkeitsdichten aller Werte zwischen 0V und 2V für eine Spannung auf die Intervalle 0-1V, 1-2V) erhält man echte Wahrscheinlichkeiten. Allein diese Wahrscheinlichkeiten bestimmen, ob die entsprechenden Ereignisse eintreten.

In einer anderen Sichtweise existieren alle möglichen Universen nebeneinander, und die Wahrscheinlichkeitsfunktion wählt aus diesen Universen dasjenige aus, in dem wir uns nach der Entscheidung wiederfinden. Zu welchem Zeitpunkt findet diese Entscheidung statt? Die plausibelste Erklärung geht davon aus, daß die Trennung der Universen zum Zeitpunkt der jeweiligen Wahrnehmung stattfindet, also für alle Individuen getrennt.

Man spricht auch davon, daß Wellenfunktionen ,,zusammenbrechen``. Solange eine Wellenfunktion nicht zusammengebrochen ist, enthält das Universum die Möglichkeit aller Entscheidungen. Man sagt auch, daß jeder Zustand unbestimmt ist, bis er gemessen wird. Messen sei hier im Sinne von Wahrnehmen zu verstehen. Zu den Wellenfunktionen korrespondieren Teilchen und einer Messung entspricht eine Kollision (oder Wechselwirkung) dieses Teilchens mit der Außenwelt.

In Laborexperimenten geschieht dies in der Form, daß ein Lichtquantum durch einen Halbspiegel geschickt wird, so daß es zwei mögliche Wege gleichzeitig geht. Wenn wir an die Enden beider Wege jeweils einen Detektor stellen, wird sich das Licht entscheiden müssen, welchen Weg es genommen hat, allerdings erst, wenn es bei den Detektoren angekommen ist.

Die hier verwendete Methode basiert darauf, nur EINEN Detektor aufzustellen. Es gibt Universen, in denen das Licht den oberen Weg gegangen ist und andere, in denen es den unteren Weg nimmt. Wenn es den oberen Weg, wo der Detektor steht, wählt, nehmen wir es wahr und die Wellenfunktion bricht zusammen. Wenn es den unteren wählt, kann es nicht gemessen werden. Indem wir aber messen, zwingen wir die Welle zum Zusammenbruch. Wir sind also in der Lage selber zu entscheiden, in welchem Universum wir uns wiederfinden. Wir zwingen - bildlich gesprochen - die Welle, uns in das Universum zu bringen, in dem das Licht den oberen Weg genommen hat (im englischen: quantum state enforcement oder kurz QSE).

Was hilft uns das jetzt aber? Nun, es führt direkt über zur Konstruktion. Man nehme einen ganz normalen Computer, der den oben beschriebenen NP-Algorithmus ausführt, wenn er Eingangsdaten erhalten hat. Zur Vereinfachung nehmen wir ein NP-Problem, das auf Optimierung hinausläuft (alle anderen NP-Probleme lassen sich in polynomialer Zeit darauf zurückführen). Wir können also zu jedem Eingangsdatenvektor eine Zielfunktion (typischerweise ganzzahlig) berechnen, die möglichst groß (klein ist äquivalent) sein soll. Der Rang dieser Funktion sei bekannt und sie wird binär ausgegeben. Außerdem geben wir den Eingangsvektor mit aus.

Diesen Computer kapseln wir von der Außenwelt ab (was ein größeres technisches Problem ist, aber eben nur ein technisches). An die Eingangsleitungen schließen wir wie oben geteilte Lichtwege an. Um Mißverständnissen vorzubeugen: Die Wellen kollabieren nicht für uns, wenn sie mit dem Computer wechselwirken, sondern nur für den Computer. Dies geschieht aber in verschiedenen Universen, zwischen denen wir uns später entscheiden, auf verschiedene Arten. ;-)

Der Computer berechnet nun zu allen Eingangsvektoren die Zielfunktion. Wir wollen den größten Wert der Zielfunktion herausfischen. Dafür fordern wir zuerst, daß das höchste Bit 1 sein soll. Wenn das möglich ist, werden in Zukunft nur noch die Zustände möglich sein, in denen die Zielfunktion dort eine 1 hatte. Wenn es nicht möglich ist, haben alle Zustände dort eine 0. So fahren wir für alle Bits fort (inklusive der Ausgangsvektor-Bits, falls das Optimum von der Zielfunktion mehrfach angenommen wird). Am Ende steht der optimale Zustand eindeutig fest, da wir mit jedem QSE nur die bestmöglichen Zustände erlaubt haben. Das hat uns aber nur die Rechenzeit zur Auswertung EINER Zielfunktion gekostet, plus das Abfragen der Zielfunktion. Letzteres geht aber mit dem Logarithmus der Höchstgrenze der Zielfunktion und ist gewöhnlich vertretbar.

Technische Probleme treten allerdings nicht nur bei der Abkapselung auf. Bei gewöhnlichen Rechnern gibt man sich damit zufrieden, daß innerhalb von 10 hoch 100 Jahren (die exakte Zahl kenne ich nicht, sie ist aber wohl viel kleiner) vielleicht ein Fehler auftritt. Da wir hier praktisch mit extrem vielen Rechnern parallel gerechnet haben (das Problem wurde auf mehrere Universen verteilt), kann es gut sein, daß die effektive Rechenzeit weit mehr als 10 hoch 100 Jahre beträgt.

Mit entsprechenden Modifikationen läßt sich das Konzept auch für andere Probleme nutzen.

Mark Weyer