In den letzten 50 Jahren hat sich die Arbeitsgeschwindigkeit der elektronischen Rechner alle zwei Jahre verdoppelt, während die Größe ihrer Bauteile sich halbierte. Leitungen und Transistoren in heutigen integrierten Schaltkreisen sind nur noch ein Hundertstel so breit wie ein menschliches Haar. Aufgrund dieses explosionsartigen Fortschritts sind die Computer gegenwärtig millionenfach leistungsfähiger als ihre primitiven Vorgänger. Aber irgendwann klingt die Wirkung selbst der größten Explosion ab, und die Technologie der integrierten Schaltkreise nähert sich ihren physikalischen Grenzen.

Eine Verkleinerung um den Faktor 100 gegenüber den derzeit allgemein verfügbaren Bauteilen ist mit lithographischen Techniken zwar realisierbar. Doch in dieser Größenordnung funktionieren integrierte Schaltkreise kaum mehr, weil sich dann bemerkbar macht, dass die entscheidenden Strukturen aus relativ wenigen Atomen bestehen. Noch eine Größenordnung kleiner kann ein einziges Atom am falschen Platz das Bauteil unbrauchbar machen. Wenn also die Computer noch kleiner werden sollen, muß eine neue Technologie die heutige ersetzen oder ergänzen.

Computer sind physische Geräte, also werden ihre Grundoperationen von physikalischen Gesetzen bestimmt. Vor einigen Jahrzehnten begannen Pioniere wie Rolf Landauer und Charles H. Bennett vom Thomas-J.-Watson-Forschungszentrum der IBM in Yorktown Heights (New York), informationsverarbeitende Bauteile von diesem Standpunkt aus zu betrachten: Wo ist die theoretische untere Grenze für die Größe eines elektronischen Bauteils? Wieviel Energie verbraucht ein Rechenvorgang mindestens -aus prinzipiellen Gründen? Zu derartigen Prinzipien gehört auch, dass unterhalb bestimmter, sehr kleiner Abmessungen eine andere Art von Physik zu verwenden ist: die Quantenmechanik.

In den frühen achtziger Jahren zeigte Paul Benioff vom Nationallaboratorium der USA in Argonne (Illinois) auf der Grundlage der Arbeiten von Landauer und Bennett, dass ein Computer, der ausschließlich nach den Gesetzen der Quantenmechanik arbeitet, theoretisch funktionieren kann. Wenig später begannen David Deutsch vom Mathematischen Institut der Universität Oxford (England) sowie andere Wissenschaftler aus den USA und Israel, solche hypothetischen Geräte im Detail auszuarbeiten. Besonders interessierte sie, ob ein Quanten-Computer Berechnungen schneller oder auf völlig andere Art durchzuführen vermöchte als ein konventioneller Rechner.

Aus verschiedenen Gründen flaute das Interesse Mitte des Jahrzehnts ab. Bis dahin hatte man nur abstrakte Betrachtungen angestellt, statt sich mit konkreten Systemen zu befassen. Erst dabei, so hatte Landauer gewarnt, würde eine Fülle von Schwierigkeiten zutage treten. Zweitens ging aus den theoretischen Vorstudien hervor, dass ein Quanten-Computer relativ häufig Fehler machen würde und sie nur mühsam korrigieren könnte. Schließlich hatte zwar der Physiker Richard P. Feynman (1918 bis 1988) die Idee aufgebracht, man könnte mit einem Quanten-Computer andere Quantensysteme (zum Beispiel neue oder bislang unbeobachtete Materieformen) simulieren; aber davon abgesehen fand sich kein mathematisches Problem, das mit einer Quanten-Maschine besser oder schneller zu lösen wäre als mit einer klassischen.

In den letzten drei Jahren hat sich das Bild gewandelt. Als ich 1993 zeigte, dass eine große Klasse wohlbekannter physikalischer Systeme als Bauteile eines Quanten-Computers dienen können, waren einige von Landauers Einwänden entkräftet. Peter W. Shor von den AT&T-Bell-Laboratorien in Murray Hill (New Jersey) wies nach, dass ein Quanten-Computer große Zahlen relativ schnell faktorisieren kann – eine für konventionelle Maschinen notorisch äußerst mühsame Aufgabe. Und im letzten Jahr entstand auf Arbeitstagungen am Institut für wissenschaftlichen Austausch in Turin (Italien) eine Fülle neuer Entwürfe für Quanten-Schaltkreise; einige wurden jüngst in den Arbeitsgruppen von H. Jeff Kimble am California Institute of Technology (Caltech) in Pasadena und von David J. Wineland am amerikanischen National Institute of Standards and Technology (NIST) in der Bundeshauptstadt Washington als Prototypen realisiert. Winelands Prototyp geht auf Arbeiten von J. Ignacio Cirac von der Universität von Kastilien und La Mancha in Ciudad Real (Spanien) und Peter Zoller von der Universität Innsbruck zurück. Im folgenden beschreibe ich, wie ein Quanten-Computer aufgebaut sein und seine erstaunlichen Leistungen erbringen könnte, zu denen ein konventioneller nicht fähig ist.

Grundlagen

Geben wir es offen zu: Die Quantenmechanik ist absonderlich. Einer ihrer Schöpfer, der Däne Niels Bohr (1885 bis 1962, Nobelpreis 1922), sagte: »Wer über Quantenmechanik nachdenken kann, ohne wirr im Kopf zu werden, hat sie nicht wirklich verstanden.« Viele der Effekte, die sie vorhersagt, wirken intuitiv absurd, wurden aber immer wieder experimentell bestätigt.

Ein Beispiel möge genügen. Dinge wie Fußbälle oder Atome, die wir normalerweise für feste Materie halten, verhalten sich unter bestimmten Umständen wie Wellen; und was wir als Wellen beschreiben, wie Schall oder Licht, verhält sich gelegentlich wie Teilchen. Im wesentlichen beschreibt die Quantenmechanik, welche Sorte Wellen zu welcher Art von Teilchen gehört und umgekehrt.

Aus dem Welle-Teilchen-Dualismus ergeben sich einige absonderliche Konsequenzen. Erstens können kleine Systeme wie Atome nur in diskreten Energiezuständen existieren. Wenn ein Atom von einem Zustand in einen anderen übergeht, absorbiert oder emittiert es eine bestimmte Menge (ein »Quantum«) an Energie; dieses Energiestück wird Photon genannt, und Lichtwellen können als aus Photonen bestehend aufgefaßt werden. Zweitens können sich quantenmechanische Wellen wie Wasserwellen überlagern (superponieren). Im einfachsten Falle beschreibt die zu einem Teilchen gehörige Welle so etwas wie den Ort des Teilchens – mit der in der Quantenmechanik unvermeidlichen Unschärfe. Sie kann aber auch aus zwei Wellen zusammengesetzt sein, deren jede einen anderen Teilchenort beschreibt. In einem gewissen Sinne ist dann ein Elektron gleichzeitig hier und dort. Sein Ort bleibt unbestimmt – unter Umständen weit über die unvermeidliche Unschärfe hinaus –, bis eine Wechselwirkung (zum Beispiel mit einem Photon) die Zweideutigkeit auflöst. Ebenso wie der Ort kann jede andere physikalische Größe, die dem Teilchen zugeordnet ist, einer derartigen Unbestimmtheit unterliegen.

Zwei überlagerte Wellen, die in so perfektem Gleichtakt schwingen, dass sie sich wie eine einzige verhalten, nennt man kohärent; der Vorgang, durch den sie ihre Eigenständigkeit wiedererlangen, heißt Dekohärenz. Für ein Elektron, das sich in einer Überlagerung von zwei Zuständen (vereinfacht gesagt, auf zwei verschiedenen Umlaufbahnen um den Atomkern zugleich) befindet, dauert es mitunter sehr lange, bis Dekohärenz eintritt. Es können Tage vergehen, bis etwas so Kleines wie ein Elektron ein Photon emittiert oder absorbiert und sich dadurch auf einen seiner Zustände festlegt.

Im Prinzip könnte sich selbst ein Fußball an mehreren Stellen zugleich befinden. Nur ist die Zeit, bis das nächste Photon in Wechselwirkung mit dem Ball gerät, kürzer als jede meßbare Zeitspanne. Der Ball ist einfach zu groß, als dass seine Position auch nur für den kürzesten wahrnehmbaren Moment unklar sein könnte. Deshalb machen sich die Absonderlichkeiten der Quantenmechanik in aller Regel nur bei sehr kleinen Gegenständen bemerkbar.

Quanten-Information

Information ist – wie die Energie in der Quantenmechanik – aus diskreten Stücken zusammengesetzt. Das Quantum der Information ist das Bit. Ein Bit Information entspricht einer Entscheidung zwischen zwei Möglichkeiten – ja oder nein, 1 oder 0, wahr oder falsch.

In einem Digitalrechner repräsentiert beispielsweise die Ladung zwischen zwei Platten eines Kondensators ein Bit an Information: Ein aufgeladener Kondensator bezeichnet eine Eins, ein ungeladener eine Null. Ein Quanten-Computer funktioniert nun, indem er die gewohnten diskreten Strukturen der digitalen Informationsverarbeitung auf die ungewohnten diskreten Strukturen der Quantenmechanik abbildet.

Eine Aufreihung von Wasserstoffatomen kann im Prinzip ebensogut Bits speichern wie eine Reihe von Kondensatoren. Ein Atom im energetischen Grundzustand würde beispielsweise einer Null entsprechen und eines in einem angeregten Zustand einer Eins. Aber Speichern ist nicht alles. Es muß möglich sein, diese Information in das System einzubringen, sie zu verarbeiten, das heißt, aus den vorhandenen Bits durch logische Verknüpfungen neue zu gewinnen, und wieder aus dem System herauszuholen: Lesen, Rechnen und Schreiben sozusagen.

Der amerikanische Physiker Isidor Isaac Rabi (1898 bis 1988, Nobelpreis 1944) fand als erster eine Lösung für das Problem, Information einzubringen. Ein Wasserstoffatom befinde sich in seinem Grundzustand mit der Energie E0. Um eine Null einzuschreiben, tue man gar nichts. Um eine Eins einzuschreiben, muß man das Atom auf einen Zustand höherer Energie E1 anregen. Dazu bestrahle man es mit Laserlicht aus Photonen, deren Energie genau gleich der Differenz von E1 und E0 ist. Ein Laserpuls mit der richtigen Intensität und Dauer wird das Atom allmählich vom Grundzustand in den angeregten Zustand versetzen. Wenn es aber schon im angeregten Zustand ist, wird es auf denselben Laserpuls hin ein Photon emittieren und in den Grundzustand zurückkehren. Das Bit wird also gewissermaßen umgeklappt: Aus 0 wird 1 und umgekehrt. In der Informatik heißt die entsprechende Schaltung ein Flip-flop.

Was aber bedeutet hier »allmählich«? Um das zu verstehen, muß man vom Teilchen- zum Wellenbild übergehen. Ein oszillierendes elektrisches Feld wie etwa Laserlicht wirkt auf ein Elektron in einem Atom ähnlich wie ein Mensch, der eine Schaukel durch Stöße in den richtigen Momenten in immer größere Schwingungen versetzt. Die oszillierende Welle gibt dem Elektron gewissermaßen immer wieder einen kleinen Stoß. Wenn die Photonen die richtige Energie haben, nämlich E1-E0, sind ihre Schwingungen mit der Bewegung des Elektrons in einer Art Resonanz und wandeln dessen Welle in eine Überlagerung zweier Wellen unterschiedlicher Energie um. Und zwar sinkt die Amplitude der Welle, die dem Grundzustand entspricht, in dem Maße, wie die Welle des angeregten Zustands anwächst. Insgesamt geht das Atom vom Grundzustand in den angeregten Zustand über. Falls die Photonen eine andere Frequenz haben, sind die Stöße nicht synchron zur Bewegung des Elektrons, und nichts passiert.

Wenn man nun das richtige Laserlicht nur die halbe Zeit auf das Atom wirken läßt, befindet sich dieses hinterher in einem Zwischenzustand, in dem die Welle des Grundzustands und die des angeregten Zustands mit gleicher Amplitude überlagert sind. Ein solches Quantenbit oder kurz Qubit (gesprochen »kjubit«) ist dann sozusagen halb umgeklappt, halb 0 und halb 1. Dagegen ist ein klassisches Bit immer entweder 1 oder 0. Ein halb aufgeladener Kondensator in einem konventionellen Computer verursacht höchstens Fehler, wohingegen ein halb umgeklapptes Qubit neue Möglichkeiten des Rechnens eröffnet.

Das Auslesen von Bits aus einem Quantensystem funktioniert ähnlich wie das Schreiben. Man bestrahle das Atom mit Laserlicht der Energie E2-E1, wobei E2 ein instabiler Zustand mit noch höherer Energie ist. Ein Atom im Zustand E1 wird dadurch in den Zustand E2 versetzt, aus dem es sehr bald nach E1 zurückfällt und dabei ein Photon emittiert. Ist das Atom im Grundzustand, passiert gar nichts. Aus dem halb umgeklappten Zustand wird es in der Hälfte aller Fälle ein Photon aussenden und sich damit auf den Zustand E1 festlegen, ansonsten kein Photon aussenden und in den Grundzustand E0 übergehen.

Vom Schreiben und Lesen ist es nur ein kleiner Schritt zum Rechnen.

Quanten-Rechnen

Wie in einem konventionellen Computer besteht Rechnen aus der oftmals wiederholten Anwendung einiger weniger elementarer Operationen auf logische Variablen – solche, die nur die Werte 1 und 0 (wahr und falsch) annehmen können. Üblicherweise wählt man als elementare Operationen die aus der mathematischen Logik bekannten Verknüpfungen UND, ODER und NICHT. Diese Wahl ist jedoch keineswegs zwingend; es kann sogar sinnvoll sein, die Aktionen eines Quanten-Computers aus anderen Komponenten zusammenzusetzen.

Man teilt alle denkbaren logischen Operationen in (im algebraischen Sinne) lineare und nichtlineare ein. Zu den linearen gehört das Umklappen eines Bits, äquivalent zu der logischen Operation NICHT: Aus wahr wird falsch und umgekehrt. Ein weiterer linearer Elementarakt ist KOPIERE: Der Zustand eines Bits wird auf ein anderes übertragen. Dagegen ist die Operation UND nichtlinear: Nur wenn beide Eingangsbits 1 sind, wird das Ausgangsbit 1, andernfalls 0.

Schaltungen, die solche Operationen ausführen, nennt man logische Gatter. Ein Digitalrechner kann jede logische oder arithmetische Aufgabe bewältigen, wenn – und nur wenn – er über ein geeignetes Sortiment linearer und nichtlinearer logischer Gatter verfügt, beispielsweise NICHT, KOPIERE und UND. Das gilt auch für Quanten-Computer.

Überraschenderweise ist jedoch das UND-Gatter nahezu beliebig ersetzbar, wie Arthur Ekert von der Universität Oxford in Zusammenarbeit mit Deutsch und Adriano Barenco sowie unabhängig von ihnen auch ich zeigten: Wenn ein Quanten-Computer nur Bits umklappen kann, genügt jede nichtlineare Quantenwechselwirkung, um ihn mit den Fähigkeiten eines Universalrechners auszustatten. Deshalb lassen sich im Prinzip viele physikalische Effekte für ein Bauteil nutzen, das eine einzige nichtlineare Operation in das Sortiment einbringt.

So gesehen, gibt es universelle quantenlogische Gatter schon fast so lange wie den Transistor. In den späten fünfziger Jahren gelang es Forschern, einfache logische Zwei-Bit-Operationen mit dem Spin von Elementarteilchen auszuführen. Der Spin ist das quantenmechanische Analogon des Drehimpulses. In einem Magnetfeld kann er, ähnlich wie die Energie eines an einen Atomkern gebundenen Elektrons, nur diskrete Werte annehmen: Er ist quantisiert und deswegen zur Wiedergabe von Bits geeignet. Ein Wert des Spins könnte also eine Eins repräsentieren, der entgegengesetzte Wert eine Null.

In einem Wasserstoffatom stehen die Spins seiner beiden Bestandteile, eines Protons und eines Elektrons, in Wechselwirkung. Das nutzten die Wissenschaftler aus: Sie bauten ein System, in welchem der Spin des Protons nur dann umklappt, wenn der Spin des Elektrons eine Eins repräsentiert. Sie nannten diesen Effekt Doppelresonanz. Obwohl damals noch niemand an Quantenlogik dachte, realisierten sie damit die linearen Operationen NICHT und KOPIERE. Später wiesen Barenco, David DiVincenco von IBM, Tycho Sleator von der Universität New York und Harald Weinfurter von der Universität Innsbruck nach, dass man mit Hilfe der Doppelresonanz auch ein UND-Gatter bauen kann, wenn man mit halb umgeklappten Spins arbeitet.

Jetzt müßte man diese Bauteile nur noch miteinander verdrahten. Leider ist genau das etwas vom Schwierigsten. In einem herkömmlichen Computer genügt ein Metallstreifen, um Spannungssignale von einem Gatter zu einem anderen zu transportieren. Dagegen müßten in einem Quanten-Computer Wasserstoffatome zerlegt, Elektronen und Protonen getrennt an verschiedene Stellen transportiert und zu neuen Atomen zusammengesetzt werden, und das alles so, dass der Spin erhalten bleibt.

In jüngster Zeit haben Forscher weniger abenteuerliche Informationskanäle ersonnen. Zum Beispiel könnten einzelne Photonen durch Glasfasern oder durch die Luft Quantenbits übertragen. Eine besonders aussichtsreiche Entwicklung kommt vom Caltech: Durch Konzentration von Photonen zusammen mit einem einzelnen Atom in einem winzigen Volumen gelang es der Gruppe um Kimble, die normalerweise verschwindend geringe nichtlineare Wechselwirkung zwischen Photonen in merkliche Größenordnungen anzuheben. Daraus ergab sich ein quantenlogisches Gatter: Ein Photonenbit wird genau dann halb umgeklappt, wenn ein anderes eine Eins repräsentiert. Ein Computer aus solchen Gattern wäre schnell und relativ robust gegen externe Einflüsse, welche die Kohärenz zerstören könnten.

Gleichwohl bleiben viele der von Landauer angeführten Hindernisse bestehen. So müssen die Längen aller optischen Wege im System auf winzige Bruchteile der verwendeten Wellenlänge genau eingehalten werden.

Es gibt noch andere Lösungen des Verdrahtungsproblems. Cirac und Zoller haben vorgeschlagen, die Qubits in einer Ionenfalle zu speichern und sie so von unerwünschten äußeren Einflüssen zu isolieren (vergleiche Spektrum der Wissenschaft, September 1993, Seite 32). Ein Bit ist in einem solchen Gerät nicht repräsentiert durch den Zustand eines einzelnen Ions, sondern durch einen kollektiven Schwingungszustand aller Ionen in der Falle. Ionenfallen-Computer mit einigen zehn oder hundert Bits scheinen im Rahmen des Machbaren zu sein: Zwei-Bit-Operationen wurden schon realisiert, und die Anzahl der Bits im Computer läßt sich einfach durch Hinzufügen weiterer Ionen erhöhen.

Aber was sind schon einige zehn oder hundert Bits gegenüber den Milliarden, die ein klassischer Computer regelmäßig verarbeitet? Nun, ein Quanten-Computer kann sogar mit nur einem Bit Dinge tun, zu denen ein konventioneller überhaupt nicht fähig ist. Man denke an das Atom in einer Überlagerung der Zustände 0 und 1. Wenn wir dieses Quanten-Bit mit Hilfe des Lasers auslesen, ergibt sich 0 oder 1 in jeweils der Hälfte der Fälle – ohne irgendeine Regelmäßigkeit. Das Bit ist also eine echte Zufallszahl. Ein klassischer Computer kann so etwas als deterministisches Gerät grundsätzlich nicht erzeugen. (Die sogenannten Zufallszahlengeneratoren, die in vielen Programmpaketen enthalten sind, liefern in Wirklichkeit Pseudozufallszahlen: Das Bildungsgesetz der Zahlenfolge ist so undurchsichtig, dass die Zahlen wie zufällig wirken, obgleich sie durch einen Algorithmus berechnet sind.)

Quantenzustände mit mehreren Teilchen

Mit mehr als einem Bit sind noch merkwürdigere Dinge möglich. Man betrachte die erwähnte Operation KOPIERE: Der Wert eines Qubits soll auf ein zweites übertragen werden, das anfangs den Wert 0 hat. Ein Lichtpuls klappt das zweite Bit nur dann in den Zustand 1 um, wenn das erste auch im Zustand 1 ist. Wenn sich dieses jedoch in einer Überlagerung der Zustände 0 und 1 befindet, sind nach dem Lichtpuls beide Bits in derselben Überlagerung von 0 und 1. Der Zustand des ersten Bits ist jedoch nicht mehr der ursprüngliche, weil die Kopplung zum zweiten dazugekommen ist.

Keines der beiden Bits ist in einem festen Zustand; wird aber eines von ihnen gemessen und somit auf einen Zustand festgelegt, nimmt gleichzeitig auch das andere Bit diesen Zustand an. Es ist nicht etwa so, dass die Veränderung des einen Bits diejenige des anderen verursachte; vielmehr geht, weil durch den Meßvorgang die Kohärenz zerstört wird, auch die Unbestimmtheit des ungemessenen Bits verloren. Das ist das Einstein-Podolsky-Rosen-Paradox – vieldiskutiert, weil es unserer Vorstellung von Kausalität so eklatant widerspricht (siehe »Quanten-Philosophie« von John Horgan, Spektrum der Wissenschaft, September 1992, Seite 82). Noch seltsamere Verkopplungen gibt es mit drei Qubits.

Nur wenig mehr Qubits sowie einige quantenlogische Gatter genügen, wie ich darlegen konnte, einen Quanten-Computer zu konstruieren, der das Verhalten beliebiger quantenmechanischer Systeme simuliert. Mit der richtigen Programmierung gleicht die Dynamik des Computers exakt der eines gegebenen Systems einschließlich seiner Wechselwirkung mit der Außenwelt. Die Anzahl der erforderlichen Rechenschritte ist proportional zur Größe des Systems.

Mehr noch – ein Computer mit paralleler Architektur, die über Doppelresonanz zwischen benachbarten Spins in Atomen eines Kristalls zu realisieren wäre, könnte jedes Quantensystem unabhängig von dessen Größe in Echtzeit nachbilden. Das wäre eine immense Beschleunigung gegenüber konventionellen Verfahren. Wie Feynman zeigte, wächst die Anzahl der Rechenschritte, die ein klassischer Computer zur Simulation eines quantenmechanischen Systems benötigt, exponentiell sowohl mit der Größe des Systems als auch mit der Länge der Zeit, über die das Systemverhalten nachzubilden ist. Ein Quanten-Computer mit 40 Bits würde in etwa 100 Schritten dasselbe leisten wie ein klassischer Computer mit Billionen von Bits in mehreren Jahren.

Was läßt sich dann erst mit einem Quanten-Computer anstellen, der viele logische Operationen auf vielen Bits ausführen kann? Man setze alle Eingabebits einer solchen hypothetischen Maschine auf einen Überlagerungszustand von 0 und 1 zu gleichen Anteilen. Der Computer befindet sich dann in einer gleichmäßigen Überlagerung aller überhaupt möglichen Eingaben. Schicken wir diese Eingabe durch einen logischen Schaltkreis, der eine bestimmte Berechnung ausführt, so erhalten wir eine Überlagerung aller möglichen Ausgaben dieser Berechnung. Der Computer hat also alle möglichen Eingaben auf einmal verarbeitet. David Deutsch nennt diesen Effekt »Quantenparallelität«.

Das ist weniger exotisch, als es den Anschein hat. Man vergleiche quantenmechanische Wellen mit Schallwellen. Eine zu einem reinen Zustand wie 0 oder 1 gehörige Welle schwingt mit genau einer Frequenz, entsprechend einem einzelnen Ton. Eine Überlagerung von 0 und 1 ist ein Akkord. Genauso wie ein Akkord anders klingt als jeder seiner Bestandteile, unterscheidet sich eine Überlagerung von 0 und 1 von den reinen Werten. In beiden Fällen interferieren die beteiligten Wellen miteinander.

Wenn ein Quanten-Computer eine normale Berechnung anstellt, in der keine Bits überlagert werden, liefert er eine Folge von reinen Tönen ähnlich einem (einstimmigen) Glockenspiel. Eine quantenparallele Berechnung dagegen ist wie eine Symphonie: Der Klang setzt sich aus vielen Wellen zusammen, die miteinander interferieren.

Peter Shor hat vor kurzem dargelegt, dass der symphonische Effekt der Quantenparallelität geeignet ist, große natürliche Zahlen schnell in Faktoren zu zerlegen – eine Aufgabe, die für klassische Rechner und sogar Supercomputer notorisch schwierig ist. Eine quantenparallele Berechnung dagegen kann, wie Shor zeigte, so orchestriert werden, dass die Faktoren einer großen Zahl so deutlich hervortreten wie eine Melodie, die von Geigen, Bratschen und Celli in Oktavparallelen gespielt wird, gegenüber den Klängen der übrigen Instrumente.

Wenn also ein funktionierender Quanten-Computer überhaupt gebaut werden kann, ist Faktorisieren für ihn eine Kleinigkeit, und die Verwender von Chiffriersystemen mit veröffentlichtem Schlüssel (public-key cryptography) haben Anlaß zur Sorge. Denn die Sicherheit dieser Systeme, die beispielsweise Banken für die vertrauliche Kommunikation verwenden, beruht darauf, dass das Faktorisieren einer etwa 100stelligen Zahl in angemessener Zeit nicht möglich ist.

Ob aber Quanten-Computer überhaupt realisiert werden, ist heiß umstritten. Erinnern wir uns, dass ein überlagerter Quantenzustand nur erhalten bleibt, solange er nicht gemessen wird – allgemeiner: solange die Umgebung mit ihm nicht in Wechselwirkung tritt. Ein Quanten-Computer müßte aus Tausenden bis Millionen von Atomen bestehen; wird auch nur eines von außen gestört, ist die Kohärenz dahin. Bisherige Experimente lassen vermuten, dass einige Systeme die erforderliche totale Isolation und damit ihre überlagerten Zustände für einige Stunden aufrechterhalten können. Shor und seine Mitarbeiter haben gezeigt, dass sein Algorithmus selbst bei mäßigen Störungen der Kohärenz noch funktioniert.

Ein weiteres Problem ist die Fehlerkorrektur. Die verschiedenen Quantensysteme zur Speicherung und Verarbeitung von Information sind anfällig für Störungen, die zufällig Bits umklappen. Üblicherweise korrigiert man solche Fehler, indem man gewisse Kombinationen von Bits überprüft und – wenn nötig – ändert. Überprüfen heißt aber Messen; in einem Quanten-Computer läuft das auf Dekohärenz hinaus. Die Gruppe von Arthur Ekert und David Deutsch hat dargelegt, dass in einem Quanten-Computer eine Fehlerkorrektur auch ohne Dekohärenz im Prinzip zwar möglich, aber kaum praktikabel ist. Vielleicht kann also ein Quanten-Computer gebaut werden, wäre jedoch wegen der Häufung zufälliger Fehler ungeeignet für längere Rechnungen mit vielen Bits.

Um heutige Supercomputer im Faktorisieren zu übertreffen, müßte ein Quanten-Computer mit Shors Algorithmus Hunderte von Bits über Tausende von Rechenschritten verfolgen und dabei stets die Kohärenz aufrechterhalten. Das dürfte wegen der von Landauer angeführten Schwierigkeiten wie Dekohärenz, unkontrollierbarer Schwankungen in den Laserpulsen und unzureichender Fehlerkorrektur sehr schwierig werden. Um aber einen klassischen Computer bei der Simulation eines quantenmechanischen Systems auszustechen, würde eine zweistellige Anzahl von Bits und Rechenschritten ausreichen. Das Ziel schließlich, mit Hilfe der Quantenlogik seltsame Mehrteilchen-Quantenzustände zu schaffen und ihre Eigenschaften zu erforschen, ist bereits in greifbarer Nähe.