Quantencomputer

Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er nicht auf der Basis der Gesetze der klassischen Physik bzw. Informatik, sondern auf der Basis quantenmechanischer Zustände, was wesentlich über die Regeln der klassischen Theorien hinausgeht (siehe zum Beispiel die Bellsche Ungleichung), und die Verarbeitung dieser Zustände erfolgt nach quantenmechanischen Prinzipien. Hierbei sind vor allem

1. das Superpositionsprinzip (d. h. die quantenmechanische Kohärenz, analog zu den Kohärenzeffekten, siehe z. B. Holographie, in der sonst inkohärenten Optik) und
2. die sog. Quantenverschränkung (s. u.) von besonderer Bedeutung.

Theoretische Studien legen nahe, dass unter Ausnutzung dieser Effekte bestimmte Probleme der Informatik, z. B. die Suche in extrem großen Datenbanken (siehe Grover-Algorithmus) und die Produktzerlegung extrem langer Zahlen (siehe Shor-Algorithmus) wesentlich effizienter gelöst werden können als mit klassischen Computern. Dies würde das mathematische Problem, das die Basis für die Sicherheit weit verbreiteter kryptographischer Verfahren darstellt, leicht lösbar und diese damit unbrauchbar machen.

Der Quantencomputer ist gegenwärtig noch ein überwiegend theoretisches Konzept. Es existiert aber schon jetzt eine Vielzahl von Vorschlägen, wie ein Quantencomputer realisiert werden könnte, und in kleinem Maßstab wurden einige dieser Konzepte im Labor erprobt und es wurden Quantencomputer mit wenigen Qubits realisiert; von einer tatsächlichen Anwendung und praktischem Nutzen ist man aber noch weit entfernt.

Qubits

Zur Definition des Begriffes Qubit:
Beim Quantencomputing arbeitet man mit allgemeinen Zuständen, die in bestimmter Weise durch Überlagerung  der beiden farbig gekennzeichneten Basiszustände entstehen, wogegen beim klassischen Computing nur die Basiszustände selbst auftreten.

In einem klassischen Computer wird sämtliche Information in Bits dargestellt. Physikalisch wird ein Bit dadurch realisiert, dass ein Spannungspotential entweder oberhalb eines bestimmten Pegels liegt (das entspricht dem binären Wert „1“) oder unterhalb („0“).

Auch in einem Quantencomputer wird Information in der Regel binär dargestellt. Dazu bedient man sich eines physikalischen Systems mit zwei Basiszuständen eines zweidimensionalen komplexen Raums, wie er in der Quantenmechanik auftritt. Ein Basiszustand repräsentiert den quantenmechanischen Zustandsvektor $ |0\rangle $, der andere den Zustandsvektor $ |1\rangle $. Dabei benutzt man die in der Quantenphysik gebräuchliche Dirac-Notation. Bei diesen „Zwei-Niveau-Systemen“ der Quantenmechanik kann es sich z. B. um den Spin eines Elektrons handeln, der entweder nach oben oder nach unten zeigt. Andere Implementierungen nutzen das Energieniveau in Atomen oder Molekülen oder die Flussrichtung eines Stroms in einem ringförmigen Supraleiter.

Die Bezeichnung Qubit soll den quantenmechanischen Charakter der auf diese Weise dargestellten Bits betonen und leitet sich aus Quanten-Bit ab.

Eine wichtige Eigenschaft quantenmechanischer Zustandsvektoren ist in diesem Zusammenhang, dass dieser eine Überlagerung anderer Zustände sein kann. Dies wird auch Superposition genannt. Im konkreten Fall bedeutet dies, dass ein Qubit nicht entweder $ |0\rangle $ oder $ |1\rangle $ sein muss, wie dies für die Bits des klassischen Computers der Fall ist. Vielmehr ergibt sich der Zustand eines Qubits in dem oben erwähnten zweidimensionalen komplexen Raum allgemein zu

$ \,|\Psi \rangle =c_{0}|0\rangle +c_{1}|1\rangle \,, $

wobei wie in der kohärenten Optik beliebige Überlagerungszustände zugelassen sind. Der Unterschied zwischen klassischem und Quanten-Computing ist also analog dem zwischen inkohärenter bzw. kohärenter Optik (im ersten Fall werden Intensitäten addiert, im zweiten direkt die Feldamplituden, wie etwa in der Holographie).

Hierbei sind $ \,c_{0} $ und $ \,c_{1} $ beliebige komplexe Zahlen. Zur Normierung fordert man aber ohne Beschränkung der Allgemeinheit noch $ \,|c_{0}|^{2}+|c_{1}|^{2}=1 $. Die Betragsquadrate der komplexen Zahlen $ c_{0}\,\,(\,:=\langle 0|\Psi \rangle ) $ und $ c_{1}\,\,(\,:=\langle 1|\Psi \rangle ) $ geben die Wahrscheinlichkeit dafür an, als Resultat einer Messung am Zustand $ \,|\Psi \rangle $ den Wert 0 bzw. 1 zu erhalten. Beispielsweise ist also $ \,P(0)=|c_{0}|^{2} $ die Wahrscheinlichkeit, eine 0 zu messen. Man darf dieses probabilistische Verhalten allerdings nicht so interpretieren, dass sich das Qubit mit einer bestimmten Wahrscheinlichkeit im Zustand $ |0\rangle $ und mit einer anderen Wahrscheinlichkeit im Zustand $ |1\rangle $ befindet, während andere Zustände nicht zugelassen sind. Ein solches „ausschließendes“ Verhalten könnte man auch mit einem klassischen Computer erzielen, der einen Zufallsgenerator verwendet, um beim Auftreten von überlagerten Zuständen zu entscheiden, ob er mit 0 oder 1 weiter rechnet. In der theoretischen Physik kommt ein entsprechendes ausschließendes Verhalten in der sog. Statistischen Physik vor, die also im Gegensatz zur Quantenmechanik inkohärent ist.

Bei Berücksichtigung der kohärenten Überlagerung erhält man dagegen allgemein

$ P(\Psi )\,:=\,|\Psi |^{2}\,\,=\,|c_{0}|^{2}+|c_{1}|^{2}+2\cdot {\mathcal {R}}\{c_{0}^{*}\cdot c_{1}\,\langle 0|1\rangle \}\,, $

wobei $ {\mathcal {R}}\{c\} $ den Realteil der komplexen Zahl $ \,c $ bedeutet, $ c_{0}^{*} $ die konjugiert-komplexe Zahl zu $ \,c_{0} $ ist und $ \langle \psi _{1}|\psi _{2}\rangle $ das quantenmechanische Skalarprodukt der betreffenden Zustände ist. ^[1]

Quantenregister, „Verschränkung“

Wie beim klassischen Computer auch, fasst man mehrere Qubits zu Quanten-Registern zusammen. Der Zustand eines Qubit-Registers ist dann gemäß den Gesetzen der Vielteilchen-Quantenmechanik ein Zustand aus einem $ 2^{N} $-dimensionalen Hilbert-Raum. Eine mögliche Basis dieses Vektorraums ist die Produktbasis über der Basis $ |0\rangle ,|1\rangle $. Für ein Register aus zwei Qubits erhielte man demnach die Basis $ |00\rangle ,|01\rangle ,|10\rangle ,|11\rangle $. Auch der Zustand des Registers kann eine beliebige Superposition dieser Basiszustände sein, also bei N Qubits von der Form $ \Psi :=\sum _{i_{1},\dots ,i_{N}}c_{i_{1}\dots i_{N}}\,(|i_{1}\rangle |i_{2}\rangle \dots |i_{N}\rangle )\,, $ mit beliebigen komplexen Zahlen $ c_{i_{1}\dots i_{N}} $ und der üblichen Dualbasis. Auch Summen bzw. Differenzen solcher Terme sind erlaubt, während bei klassischen Computern nur die Basiszustände selbst vorkommen, d.h. nur aus den Ziffern 0 bzw. 1 zusammengesetzte Vorfaktoren.

Eine wichtige Eigenschaft des Quanten-Registers ist, dass dessen Zustände nicht stets aus den Zuständen unabhängiger Qubits zusammengesetzt werden können: Z. B. kann man den Zustand $ \Psi :={\frac {1}{\sqrt {2}}}(|01\rangle +|10\rangle ) $ nicht in ein Produkt aus einem Zustand für das erste und einem Zustand für das zweite Qubit zerlegen.

Man nennt einen derartigen Zustand daher auch verschränkt (in der englischsprachigen Literatur spricht man von "entanglement"). Das Gleiche gilt auch für den von $ \Psi $ verschiedenen Zustand $ \Psi ':={\frac {1}{\sqrt {2}}}(|01\rangle -|10\rangle )\,. $ ^[2]

Die Eigenschaft der Verschränkung gibt auch einen Hinweis darauf, dass Quantencomputer mächtiger als klassische Computer sein können, d.h. dass sie prinzipiell bestimmte Probleme wesentlich schneller lösen können, als dies mit klassischen Computern möglich ist: Um den Zustand eines klassischen $ N $-Bit Registers darzustellen, benötigt man $ N $ Bits an Information. Der Zustand des Quanten-Registers ist aber ein Vektor aus einem $ 2^{N} $-dimensionalen Vektorraum, so dass man zu dessen Darstellung $ 2^{N} $ komplexwertige Koeffizienten angeben muss. Hier ist wesentlich, dass bei großem N die Zahl 2^N viel größer ist als N selbst.

Das Superpositionsprinzip wird oft so dargestellt, dass ein Quantencomputer in einem Quantenregister aus $ N $ Qubits gleichzeitig alle $ 2^{N} $ Zahlen von 0 bis $ 2^{N}-1 $ speichern könnte. Diese Vorstellung ist irreführend. Da eine am Register vorgenommene Messung stets genau einen der Basiszustände auswählt, lässt sich unter Anwendung des so genannten Holevo-Theorems zeigen, dass der maximale zugängliche Informationsgehalt eines einzelnen unverschränkten Qubits wie im klassischen Fall genau ein Bit beträgt.^[3][4] Es ist dennoch korrekt, dass das Superpositionsprinzip eine Parallelität in den Rechnungen erlaubt, die wesentlich über das hinausgeht, was in einem klassischen „Parallelrechner“ passiert. Bei der Vorstellung einiger Quanten-Algorithmen wird darauf näher eingegangen.

Quantengatter

Beim klassischen Computer werden durch Logikgatter (engl. Gates) elementare Operationen auf den Bits durchgeführt. Mehrere Gatter werden zu einem Schaltnetz verbunden, das dann komplexe Operationen wie das Addieren zweier Binärzahlen durchführen kann. Die Gatter werden dabei durch physikalische Bauelemente wie Transistoren realisiert und die Information als elektrisches Signal durch diese Bauelemente geleitet.

Berechnungen auf einem Quantencomputer laufen grundsätzlich anders ab: Ein Quantengatter (engl. Quantum Gate) ist kein technischer Baustein, sondern stellt eine elementare physikalische Manipulation eines oder mehrerer Qubits dar. Wie genau so eine Manipulation aussieht, hängt von der tatsächlichen physikalischen Natur des Qubits ab. So lässt sich der Spin eines Elektrons durch eingestrahlte Magnetfelder beeinflussen, der Anregungszustand eines Atoms durch Laserpulse. Obwohl also ein Quantengatter kein elektronischer Baustein, sondern eine im Verlauf der Zeit auf das Quanten-Register angewendete Aktion ist, beschreibt man Quanten-Algorithmen mit Hilfe von Schaltplänen, vgl. hierzu den Artikel Liste der Quantengatter.

Formal gesprochen ist ein Quantengatter eine unitäre Operation $ U $, die auf den Zustand des Quanten-Registers wirkt:

$ \Psi \rightarrow U\cdot \Psi . $

Ein Quantengatter kann daher als unitäre Matrix geschrieben werden. Ein Gatter, welches den Zustand eines Qubits umdreht (negiert), würde im Falle eines zweidimensionalen Zustandsraums der folgenden Matrix entsprechen:

$ U={\begin{pmatrix}0&1\\1&0\end{pmatrix}}. $

Komplizierter zu schreiben sind Quantengatter (unitäre Matrizen), die Zwei- oder Mehr-Qubitzustände modifizieren, z. B. das in $ \mathbb {C} ^{4} $ definierte CNOT-Gatter, mit der „Zwei-Qubit“-Zustandstabelle $ |00\rangle \to |00\rangle , $  $ |01\rangle \to |01\rangle , $  $ |10\rangle \to |11\rangle $ und $ |11\rangle \to |10\rangle . $ ^[5] Man kann das Ergebnis noch zusätzlich bezüglich der Stellenindizes a und b symmetrisieren bzw. antisymmetrisieren, etwa nach dem Schema $ |ab\rangle ={\frac {1}{2}}[(|ab\rangle +|ba\rangle )+(|ab\rangle -|ba\rangle )]\,, $ wodurch verschränkte Zustände entstehen, wie das für die Quantenmechanik charakteristisch ist.

Ein Quanten-Schaltkreis besteht nun aus mehreren Quantengattern, die in fester zeitlicher Abfolge auf das Quantenregister angewendet werden. Beispiele hierfür sind die Quanten-Fouriertransformation oder der Shor-Algorithmus. Mathematisch ist auch ein Quanten-Schaltkreis eine unitäre Transformation, deren Matrix einfach das Produkt der Matrizen der einzelnen Quantengatter ist.

Einweg-Quantencomputer

Ein weiterer Ansatz zur Implementierung eines Quantencomputers ist der sogenannte Einweg-Quantencomputer (one-way quantum computer, Hans J. Briegel, Robert Raussendorf 2001)^[6]. Dieser unterscheidet sich vom Schaltkreismodell dadurch, dass zuerst ein universeller (also vom Problem unabhängiger) verschränkter Quantenzustand generiert wird (beispielsweise ein sogenannter Clusterzustand), und die eigentliche Rechnung durch gezielte Messungen an diesem Zustand durchgeführt wird. Dabei bestimmen die Ergebnisse früherer Messungen, welche weiteren Messungen durchgeführt werden.

Anders als im Schaltkreis-Modell wird hier der verschränkte Quantenzustand nur als Ressource benutzt. Bei der eigentlichen Rechnung werden nur einzelne Qubits des verwendeten Zustands gemessen und klassische Rechnungen durchgeführt. Insbesondere werden dabei keine Mehr-Qubit-Operationen durchgeführt (die Herstellung des Zustands benötigt solche natürlich). Dennoch lässt sich zeigen, dass der Einweg-Quantencomputer genauso leistungsfähig ist wie ein auf dem Schaltkreis-Modell beruhender Quantencomputer.

Adiabatische Quantencomputer

Ein weiterer Ansatz für Quantencomputer beruht auf einem völlig anderen Konzept^[7]: Gemäß den Gesetzen der Quantenmechanik bleibt ein quantenmechanisches System, das sich anfangs im Grundzustand (Zustand minimaler Energie) eines zeitunabhängigen Systems befindet, auch bei Veränderungen des Systems im Grundzustand, wenn die Veränderung nur hinreichend langsam (also adiabatisch) passiert. Die Idee des adiabatischen Quantencomputers ist nun, ein System zu konstruieren, das einen Grundzustand hat, der der Lösung eines bestimmten Problems entspricht, und ein anderes, dessen Grundzustand leicht experimentell zu präparieren ist. Anschließend wird das leicht zu präparierende System in das System überführt, an dessen Grundzustand man interessiert ist, und dessen Zustand dann gemessen. Wenn der Übergang langsam genug erfolgt ist, hat man so die Lösung des Problems.

Die Firma D-Wave Systems hat 2007 erklärt, einen kommerziell verwendbaren Quantencomputer entwickelt zu haben, der auf diesem Prinzip beruht.^[8] Am 26. Mai 2011 verkaufte die Firma D-Wave Systems den ersten kommerziellen Quantencomputer "D-Wave One" an die Lockheed Martin Corporation.^[9]

Physikalische Realisierung

Das bisher beschriebene Konzept ist zunächst abstrakt und allgemein gültig. In theoretischer Hinsicht ist die Behandlung von Quantencomputern daher bereits recht weit fortgeschritten. Will man einen konkret nutzbaren Quantencomputer bauen, muss man die natürlichen physikalischen Einschränkungen beachten, die im Folgenden beschrieben werden.

Relaxation

Überlässt man ein System sich selbst, neigt es dazu, einen Zustand mit möglichst niedriger Energie einzunehmen. Dies führt dazu, dass ein Qubit aus dem Zustand $ |1\rangle $ nach einer gewissen Zeit mit einer bestimmten Wahrscheinlichkeit in den Zustand $ |0\rangle $ gesprungen ist. Diesen Prozess nennt man Relaxation. Die Relaxationszeit $ T_{1} $ ist dabei exponentialverteilt.

Dekohärenz

Mit Dekohärenz ist der Verlust der Superpositionseigenschaften eines Quantenzustands gemeint. Durch den Einfluss der Umgebung entwickelt sich aus einem beliebigen Superpositionszustand $ \{c_{0}|0\rangle +c_{1}|1\rangle \} $   (mit $ c_{i}\in \mathbb {C} , $ $ \sum |c_{i}|^{2}=1\, $) entweder der Zustand $ |0\rangle $ oder der Zustand $ |1\rangle $   (mit entsprechenden Wahrscheinlichkeiten, die zum Beispiel durch $ |c_{i}|^{2} $ gegeben sein können, während „gemischte Terme“ (z. B. $ \sim c_{0}^{*}c_{1}\, $) nicht  auftreten („Zustandsreduktion“; „inkohärente“ versus „kohärente“ Superposition; „Thermalisierung“, wie in der statistischen Physik)). Dann verhält sich das Qubit nur noch wie ein klassisches Bit. Die Dekohärenzzeit $ T_{2} $ ist in der Regel ebenfalls exponentialverteilt und typischerweise viel kleiner als die Relaxationszeit. Während die Relaxation auch für klassische Computer ein Problem darstellt (so könnten sich Magnete auf der Festplatte spontan umpolen), ist die Dekohärenz ein rein quantenmechanisches Phänomen.

Die Verlässlichkeit von Quantencomputern kann durch die sogenannte Quantenfehlerkorrektur erhöht werden.^[10]

Berechenbarkeits- und Komplexitätstheorie

Da formal festgelegt ist, wie ein Quantencomputer arbeitet, können die aus der theoretischen Informatik bekannten Begriffe wie Berechenbarkeit oder Komplexitätsklasse auch auf einen Quantencomputer übertragen werden. Man stellt dabei fest, dass ein Quantencomputer keine prinzipiell neuen Probleme lösen kann, einige Probleme allerdings schneller gelöst werden können.

Berechenbarkeit

Ein klassischer Computer kann einen Quantencomputer simulieren, da die Wirkung der Gates auf dem Quantenregister einer Matrix-Vektor-Multiplikation entspricht. Der klassische Computer muss nun einfach all diese Multiplikationen ausführen, um den Anfangs- in den Endzustand des Registers zu überführen.

Direkte Konsequenz dieser Simulierbarkeit ist, dass alle Probleme, die auf einem Quantencomputer gelöst werden können, auch auf einem klassischen Computer gelöst werden können. Umgekehrt bedeutet dies, dass Probleme wie das Halteproblem auch auf Quantencomputern nicht gelöst werden können.

Es lässt sich zeigen, dass die Simulation eines Quantencomputers in der Komplexitätsklasse PSPACE liegt. Man geht daher davon aus, dass es keinen Simulationsalgorithmus gibt, der einen Quantencomputer mit polynomiellem Zeitverlust simuliert.

Umgekehrt kann ein Quantencomputer auch einen klassischen Computer simulieren. Dazu muss man zunächst wissen, dass jeder logische Schaltkreis allein aus NAND-Gattern gebildet werden kann. Mit dem Toffoli-Gatter kann man bei geeigneter Beschaltung der drei Eingänge nun ein Quantengatter erhalten, das sich auf Qubits in der Basis der klassischen Bits $ |0\rangle ,|1\rangle $ wie ein NAND-Gatter verhält. Außerdem lässt sich das Toffoli-Gate dazu verwenden, ein Eingangsbit zu verdoppeln. Aufgrund des No-Cloning-Theorems ist dies allerdings nur für die Zustände $ |0\rangle ,|1\rangle $ möglich. Diese Verdopplung (Auch Fan-out genannt) ist deshalb nötig, weil es bei einem klassischen Schaltkreis möglich ist, ein Bit auf zwei Leitungen zu verteilen.

Komplexität

Im Rahmen der Komplexitätstheorie ordnet man algorithmische Probleme sogenannten Komplexitätsklassen zu. Die bekanntesten und wichtigsten Vertreter sind die Klassen P und NP. Dabei bezeichnet P diejenigen Probleme, deren Lösung deterministisch in zur Eingabelänge polynomieller Laufzeit berechnet werden kann. In NP liegen die Probleme, zu denen es Lösungsalgorithmen gibt, die nicht-deterministisch polynomiell sind. Der Nicht-Determinismus erlaubt, gleichzeitig verschiedene Möglichkeiten abzutesten. Da unsere aktuellen Rechner deterministisch laufen, muss der Nicht-Determinismus durch Hintereinanderausführung der verschiedenen Möglichkeiten simuliert werden, wodurch die Polynomialität der Lösungsstrategie verloren gehen kann.

Für Quantencomputer definiert man die Komplexitätsklasse BQP. Diese enthält diejenigen Probleme, deren Laufzeit polynomiell von der Eingabelänge abhängt und deren Fehlerwahrscheinlichkeit unter $ 1/4 $ liegt. Aus dem vorhergehenden Abschnitt folgt, dass BQP $ \subseteq $ PSPACE. Ferner gilt P $ \subseteq $ BQP , da ein Quantencomputer auch klassische Computer mit nur polynomiellem Zeitverlust simulieren kann.

Wie BQP zur wichtigen Klasse NP in Beziehung steht, ist noch unklar. Man weiß nicht, ob ein Quantencomputer ein NP-vollständiges Problem effizient lösen kann oder nicht. Könnte man nachweisen, dass BQP eine echte Teilmenge von NP ist, wäre damit auch das P-NP-Problem gelöst: Dann gilt nämlich P $ \not = $ NP. Andererseits würde aus dem Nachweis, dass NP echte Teilmenge von BQP ist, folgen, dass P echte Teilmenge von PSPACE ist. Sowohl das P-NP-Problem als auch die Frage P $ \not = $ PSPACE sind wichtige ungelöste Fragen der theoretischen Informatik.

Algorithmen für Quantencomputer

Die bisher gefundenen Algorithmen für Quantencomputer lassen sich grob in drei Kategorien einteilen:

• Algorithmen, die auf der Quanten-Fouriertransformation beruhen. Darunter fällt auch der wohl berühmteste Algorithmus für Quantencomputer, der Shor-Algorithmus zur Faktorisierung großer Zahlen. Der Zeitaufwand ist dabei polynomiell in der Anzahl der Ziffern. Im Gegensatz dazu benötigt der beste zur Zeit bekannte klassische Algorithmus, das Zahlkörpersieb, superpolynomiell (aber subexponentiell) viel Zeit. Die Bedeutung von Shors Algorithmus beruht auf der Tatsache, dass die Sicherheit der weitverbreiteten asymmetrischen Verschlüsselungsverfahren wie RSA darauf basiert, dass keine effizienten „klassischen“ Algorithmen zur Faktorisierung großer Zahlen bekannt sind.
• Quanten-Suchalgorithmen. Hierzu gehört der Grover-Algorithmus und Varianten davon. Er dient der effizienten Suche in einem unsortierten Array. Ein gewöhnlicher Computer muss sich bei $ n $ Einträgen im schlimmsten Fall alle Einträge ansehen (d. h. vergleichen), klassisch ist dieses Problem also in $ {\mathcal {O}}(n) $ Rechenschritten lösbar. Auf einem Quantencomputer kann man dies mit dem Grover-Algorithmus in lediglich $ {\mathcal {O}}({\sqrt {n}}) $ Operationen erledigen. Diese Schranke ist scharf, das heißt, kein Quantenalgorithmus kann dieses Problem in (asymptotisch) weniger Operationen lösen. Daraus folgt, dass im Allgemeinen kein exponentieller Geschwindigkeitsvorteil bei Verwendung von Quantenalgorithmen zu erwarten ist.
• Quanten-Simulation. Um quantenmechanische Systeme zu simulieren, bietet es sich an, wieder quantenmechanische Systeme zu benutzen. Mit einem geeigneten Satz von Quantengattern lässt sich jeder Hamiltonian darstellen, und in vielen Fällen reicht dazu eine geringe Zahl von Gattern aus. Algorithmen dieser Art würden insbesondere für die Quantenchemie eine immense Rolle spielen, da mit heutigen Mitteln selbst einfache Moleküle nicht ohne grobe Näherungen simuliert werden können.

Viele Algorithmen für Quantencomputer liefern nur mit einer gewissen Wahrscheinlichkeit ein korrektes Ergebnis; man spricht von probabilistischen Algorithmen. Durch wiederholtes Anwenden des Algorithmus kann die Fehlerwahrscheinlichkeit allerdings beliebig klein werden. Ist die anfängliche Erfolgswahrscheinlichkeit groß genug, reichen wenige Wiederholungen aus.

Architektur für Quantencomputer

Alle bisher experimentell demonstrierten "Quantencomputer" bestanden aus nur wenigen Qubits und waren weder in Hinsicht auf die Dekohärenz- und Fehlerraten noch in Hinblick auf die verwendete Architektur skalierbar. Unter Architektur versteht man in diesem Kontext insbesondere das Konzept zur skalierbaren Anordnung einer sehr großen Zahl von Qubits: wie kann sichergestellt werden, dass die Fehlerrate pro Gatter klein ist (unterhalb der Schwelle für fehlertolerantes Rechnen) und zwar unabhängig von der Zahl der Qubits des Quantencomputers und von der räumlichen Entfernung der beteiligten Qubits im Quantenregister.

Das Problem wurde von David P. DiVincenzo in einem Katalog von 5 Kriterien, die ein skalierbarer, fehlertoleranter Quantencomputer erfüllen muss, zusammengefasst. Die DiVincenzo-Kriterien sind^[11]

1. Er besteht aus einem skalierbaren System gut charakterisierter Qubits.
2. Alle Qubits können in einen wohldefinierten Anfangszustand gebracht werden (z.B. $ |00...0\rangle $).
3. Ein universelles Set elementarer Quantengatter kann ausgeführt werden.
4. Einzelne Qubits (zumindest eines) können ausgelesen (gemessen) werden.
5. Die relevante Dekohärenzzeit ist viel länger als die Zeit, die benötigt wird, ein elementares Quantengatter zu realisieren, sodass mit geeignetem fehlerkorrigierendem Code die Fehlerrate pro Gatter unter der Schwelle für fehlertolerantes Quantenrechnen liegt.

Die größten Anforderungen ergeben sich dabei aus dem ersten und dem letzten Punkt. Skalierbarkeit heißt in diesem Fall, dass es im Prinzip möglich sein muss, die Zahl der Qubits beliebig groß zu wählen und dass die anderen Eigenschaften unabhängig von der Zahl der Qubits erfüllt sein müssen. Die Schwelle für fehlertolerantes Rechnen liegt je nach verwendetem Code und verwendeter Geometrie des Quantenregisters bei einer Fehlerwahrscheinlichkeit von $ 10^{-4}-10^{-2} $ (oder noch kleineren Werten) pro Gatter.^[12] Bisher ist kein universelles Set von Gattern mit dieser Genauigkeit realisiert worden. Oft werden die Kriterien um zwei weitere ergänzt, die sich auf die die Vernetzung von Quantencomputern beziehen:

6. Eine Quanten-Schnittstelle ("quantum interface") zwischen stationären und mobilen Qubits. und

7. Mobile Qubits können zwischen verschiedenen Orten verlässlich ausgetauscht werden.

Die Suche nach einer skalierbaren Architektur für einen fehlertoleranten Quantencomputer ist Gegenstand intensiver aktueller Forschung. Die zentrale Fragestellung hier ist, wie man erreichen kann, dass Quantengatter auf verschiedenen Qubits parallel zueinander (gleichzeitig) ausgeführt werden können auch wenn die Wechselwirkung zwischen den physikalischen Qubits lokal ist, d.h. nicht jedes Qubit mit jedem anderen in direkter Wechselwirkung steht. Je nach dem verwendeten Konzept (Gatter-Netzwerk, Einweg-Quantencomputer, adiabatischer Quantencomputer,...) und der gewählten Implementierung (gefangene Ionen, supraleitende Schaltkreise,...) gibt es hierzu viele verschiedene Vorschläge, die bislang aber allenfalls für sehr kleine Prototypen demonstriert wurden. Zu den konkretesten und weitest fortgeschrittenen Vorschlägen gehören die folgenden:

• Quantencomputer in mikrostrukturierter Ionenfalle: Qubits werden durch den internen Zustand einzelner gefangener Ionen realisiert. In einer mikrostrukturierten Falle werden die Ionen kontrolliert zwischen Speicher- und Wechselwirkungsregionen hin- und herbewegt.^[13] Anstatt die miteinander zu koppelnden Ionen in eine gemeinsame Wechselwirkungsregion zu bewegen, könnten auch langreichweitige Wechselwirkungen zwischen ihnen benutzt werden. In Experimenten an der Universität Innsbruck wurde demonstriert, dass zum Beispiel die elektrische Dipolwechselwirkung zwischen kleinen Gruppen von oszillierenden Ionen (die als Antenne wirken) zur Kopplung von Ionen, die mehr als 50 Mikrometer voneinander entfernt sind, verwendet werden kann.^[14]
• Supraleitende Qubits in einem zweidimensionalen Netzwerk von supraleitenden Streifenleitungsresonatoren (stripline resonators)^[15]
• Quantencomputer auf Basis von Stickstoff-Fehlstellen-Zentren ("NV-Zentren") in Diamant: Als Qubits fungieren Kernspins von Stickstoff-Atomen in einem zweidimensionalen Gitter von NV-Zentren; Auslese und Kopplung erfolgen über den elektronischen Spin des NV-Zentrums, wobei die Kopplung durch die magnetische Dipolwechselwirkung erreicht wird; inhomogene Magnetfelder ermöglichen die individuelle Adressierung und parallele Operation auf vielen Qubits.^[16]

Forschung

Quantencomputer mit wenigen Qubits konnten bereits realisiert werden. So wurde Shors Algorithmus im Jahre 2001 mit einem auf Kernspinresonanz beruhenden Quantencomputer am IBM Almaden Research Center für ein System mit 7 Qubits realisiert und konnte die Zahl 15 erfolgreich in ihre Primfaktoren 3 und 5 zerlegen^[17]. Ebenso konnte im Jahre 2003 ein auf in Ionenfallen gespeicherten Teilchen basierender Quantencomputer den Deutsch-Jozsa-Algorithmus realisieren^[18].

Im November 2005 gelang es Rainer Blatt am Institut für Experimentalphysik der Universität Innsbruck erstmals, ein Quantenregister mit 8 verschränkten Qubits zu erzeugen. Die Verschränkung aller acht Qubits musste durch 650.000 Messungen nachgewiesen werden und dauerte 10 Stunden^[19].

Im März 2011 haben die Innsbrucker Wissenschaftler diesen Rekord noch einmal beinahe verdoppelt. In einer Ionenfalle haben sie 14 Kalziumatome gefangen, welche sie, einem Quantenprozessor gleich, mit Laserlicht manipulieren.^[20]

An der Yale University, New Haven kühlte ein Forscherteam um Leo DiCarlo ein Zwei-Qubit-Register auf einem 7 mm langen und 2 mm breiten, von einem mehrfach gekrümmten Kanal durchzogenen Quantenprozessor auf eine Temperatur von 13 mK ab, und erzeugte damit einen 2-Qubit-Register-Quantencomputer aus einem Stück. Der supraleitende Chip spielte nach einer Veröffentlichung von Nature zum ersten Mal Quantenalgorithmen durch.^[21][22]

Einer Forschergruppe am National Institute of Standards and Technology (NIST) in Boulder, USA, ist es 2011 gelungen, Ionen mittels Mikrowellen für den Einsatz in einem Quantencomputer zu verschränken. Die NIST-Forschergruppe hat gezeigt, dass man solche Operationen nicht nur mit einem komplexen, raumfüllenden Lasersystem realisieren kann, sondern auch mit miniaturisierter Mikrowellenelektronik. Um die Verschränkung zu erzeugen, integrierten die Physiker die Mikrowellenquelle in die Elektroden einer so genannten Chipfalle, einer mikroskopischen chipartigen Struktur zur Speicherung und Manipulation der Ionen in einer Vakuumzelle. Mit ihrem Experiment haben die Forscher gezeigt, dass die Verschränkung der Ionen mit Mikrowellen in 76 Prozent aller Fälle funktioniert. Die bereits seit mehreren Jahren in der Forschung verwendeten laserbasierten Quantenlogikgatter sind mit einer Quote von 99,3 Prozent derzeit noch besser als die Gatter auf Basis von Mikrowellen. Das neue Verfahren hat aber den entscheidenden Vorteil, dass es nur ungefähr ein Zehntel des Platzes eines Laser-Experiments beansprucht.^[23][24]

Siehe auch

• Quanteninformatik
• Quanteninformation
• Qubit
• Bloch-Kugel
• Quantenverschränkung
• Quantenteleportation
• David Deutsch
• Richard Feynman
• DNA-Computer
• QNN (quantum neural network)
• Quantenkryptografie
• Grover-Algorithmus
• Shor-Algorithmus

Weblinks

 Commons: Quantencomputer – Album mit Bildern, Videos und Audiodateien

• Quantum Computing. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of PhilosophyVorlage:SEP/Wartung/Parameter 1 und Parameter 2 und nicht Parameter 3
• Quantensprung für verschränkte Atome - Forscher erzielen Erfolg auf dem langen Weg zum Quantencomputer - Bericht über einen Artikel im Wissenschaftsmagazin Nature (Bd. 438, S. 639 und 643, 2005)
• Erstes "Quantenbyte" erzeugt (Pressebericht der Österreichischen Akademie der Wissenschaften)
• Physik-Nobelpreisträger Theodor W. Hänsch erklärt Aspekte des Quantencomputers Umfangreiches Interview zur Quantenmechanik vom 22. Juli 2008
• Quantencomputer.de - Seite von Matthias Bezold, die aus einer Facharbeit hervorgegangen ist.
• Howstuffworks "How Quantum Computers Work" - Eine englische Beschreibung von Quantencomputern
• QCL - A Programming Language for Quantum Computers (QCL - eine Programmiersprache für Quantencomputer)
• libquantum, C-Bibliothek zur Simulation von Quantencomputern
• Uni Innsbruck: Digitalen Quantensimulator gebaut. (Pressemitteilung bei idw)
• Frischer Wind fürs Quantencomputing - in der Onlineausgabe der Technology Review vom 12. Januar 2012

Literatur

• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge 2000, ISBN 0-521-63503-9
• Matthias Homeister: Quantum Computing verstehen. Vieweg, Wiesbaden 2005, ISBN 3-528-05921-4
• J.B. Waldner: Nanocomputers and Swarm Intelligence, ISTE, S.150-S.159, ISBN 1-84704-002-0.
• Wolfgang Tittel u.a.: Quantenkryptographie in: Physikalische Blätter 55 (6) 1999, S. 25
• Dagmar Bruß: Quanteninformation. Fischer Taschenbuch Verlag, Frankfurt am Main 2003, ISBN 3-596-15563-0
• Einsteins unverhofftes Erbe. Quanteninformationstechnologie. 2005 (PDF-Datei; 1,64 MB), Broschüre des Bundesministeriums für Bildung und Forschung
• Joachim Stolze, Dieter Suter: Quantum Computing: A Short Course from Theory to Experiment, Wiley-VCH, ISBN 3-527-40787-1

Einzelnachweise und Fußnoten