Tricks für Quantenrechner
Quantencomputer kommen durch Nichtstun oder im freien Fall zum gewünschten Resultat.
Tricks für Quantenrechner
Quantencomputer kommen durch Nichtstun oder im freien Fall zum gewünschten Resultat.
Noch weiß niemand, ob ein Quantencomputer jemals mit herkömmlichen Elektronenrechnern konkurrieren kann, ob er seine Quantenbits in Atomen, Halbleiterquantenpunkten oder supraleitenden Bauelementen speichern wird. Doch schon jetzt hat die Suche nach dem Quantencomputer unser Verständnis der Quantentheorie tiefgreifend verändert, wie zwei neue Forschungsresultate belegen. Die Gruppe von Paul Kwiat hat einen (rudimentären) Quantencomputer gebaut, der ohne zu rechnen das richtige Ergebnis liefert. Michael Nielsen und seine Kollegen wiederum zeigen, dass ein Quantencomputer entlang einer geeigneten geodätischen Linie auf dem schnellsten Weg zur Lösung einer Aufgabe kommt.
Paul Kwiat und seine Mitarbeiter von der University of Illinois in Urbana-Champaign haben die so genannte Counterfactual Quantum Computation in die Praxis umgesetzt: das Rechnen ohne zu rechnen. Dabei nutzen sie die Möglichkeiten, die die quantenmechanische Interferenz bietet, nicht nur für die Quantenbits sondern gleich für den ganzen Quantencomputer. Während ein klassisches Bit den Wert 0 oder 1 hat, stehen einen Quantensystem mit einem Quantenbit (kurz: Qubit) neben den Grundzuständen |0> und |1> auch alle möglichen Überlagerungszustände der Form a|0> + b|1> (mit komplexen Zahlen a und b) zur Verfügung. Entsprechend ist ein herkömmlicher Elektronenrechner entweder im Wartezustand (Off) oder er führt eine Berechnung durch (On). Der Quantencomputer hingegen kann zugleich abwarten und rechnen: a|Off> + b|On>.
In solch einem On/Off-Überlagerungszustand befindet sich der Quantencomputer bei der kontrafaktischen Berechnung. Seine On-Komponente führt die gewünschte Rechnung durch und schreibt das Ergebnis auf einige Ergebnis-Qubits, deren Werte sich dabei ändern. Doch auch seine Off-Komponente trägt zum Endzustand sowohl des Quantencomputers als auch der Ergebnis-Qubits bei. So kann je nach Resultat der Berechnung der Endzustand des Quantencomputers eine Off-Komponente enthalten oder nicht. Zeigt eine abschließende Messung, dass der Computer „Off“ gewesen war, so kann man daraus dennoch Rückschlüsse auf das Rechenergebnis ziehen. Das Resultat lässt sich demnach in bestimmten Fällen erschließen, auch wenn der Computer nicht arbeitet – aber angeschaltet sollte er sein.
Abb.: Ein Quantencomputer kann zugleich abwarten und rechnen: a|Off> + b|On>. Näheres siehe Text. (Quelle: Hosten et al.)
Die Kontrafaktische Berechnung klappte aber bisher nicht immer. In einigen Fällen ließ sich aus dem Wert der Ergebnis-Qubits und der Tatsache, dass der Rechner „Off“ war, das gewünschte Resultat nicht eindeutig erschließen. Doch Kwiat und seine Kollegen haben einen Weg gefunden, um mit der Counterfactual Computation stets das richtige Ergebnis zu erhalten. Dabei benutzen sie den Quanten-Zeno-Effekt: Wird ein Quantensystem nur oft genug beobachtet, so kann es sich nicht entwickeln und bleibt in seinem Anfangszustand. Dabei kann man die Rückwirkung auf den Beobachter beliebig klein machen. Mit dieser Methode lässt sich z. B. mit Licht das Vorhandensein einer extrem lichtempfindlichen Bombe erschließen, ohne sie auszulösen.
Kwiat und seine Mitarbeiter haben einen Quantencomputer gebaut, der mit Hilfe von Photonen, Spiegeln, Polarisationsstrahlteilern und Photodetektoren einen äußerst effizienten Quantensuchalgorithmus abarbeitet, den Lov Grover vor einigen Jahren entwickelt hatte. Die Berechnung erfolgte jetzt allerdings „counterfactual“, also ohne dass der Quantencomputer wirklich rechnen musste. Dabei lenkte die On-Komponente des Quantencomputers seine Off-Komponente mit Hilfe des Quanten-Zeno-Effektes in den gesuchten Endzustand. Wurde dieser Zustand gemessen, so stellte sich heraus, dass die On-Komponente des Computers am Resultat gar nicht beteiligt war. Die Forscher vermuten, dass Unzulänglichkeiten des laufenden Quantencomputers wie z. B. Dekohärenz, die normalerweise das Ergebnis verfälschen, bei einer kontrafaktischen Berechnung nicht zu Buche schlagen. Das hätte weitreichende Konsequenzen, die den Bau eines leistungsfähigen Quantensupercomputers erheblich erleichtern würden.
Doch wie programmiert man einen Quantensupercomputer möglichst effizient? Dieser Frage sind Michael Nielsen und seine Kollegen von der University of Queensland in Australien nachgegangen. Bei den einzelnen Rechenschritten sollten möglichst jeweils nur ein, zwei oder vielleicht drei Quantenbits miteinander verknüpft werden. Aus vielen solchen Rechenschritten baut sich dann eine (unitäre) Transformation auf, die den Anfangszustand des Quantencomputers in den gewünschten Endzustand überführt. Je größer die Zahl der Qubits ist, die der Quantenzustand verarbeiten kann, umso größer wird auch die Zahl der Rechenschritte sein, die er ausführen muss, um ein Resultat zu erreichen.
Wächst die Zahl N der Rechenschritte exponentiell mit der Zahl n der Qubits, dann stößt der Quantencomputer an seine Grenzen und die Berechnung ist praktisch nicht durchzuführen. Wächst N hingegen wie ein Polynom von n, dann ist die Berechnung praktikabel. Doch wie findet man den schnellsten Weg zum gewünschten Resultat, bei dem N möglichst klein ist?
Die Australischen Forscher haben eine originelle Lösung für dieses Problem. Sie bewerten jeden „Rechenweg“ mit einer Kostenfunktion, die sehr schnell anwächst, wenn in einem Rechenschritt mehr als zwei Qubits verarbeitet werden sollen. Auf diese Weise erhalten sie ein Maß für die Länge eines Rechenweges. Sie können damit die Gesamtheit aller möglichen Berechnungen auf eine Riemannsche Mannigfaltigkeit abbilden. Der kürzeste Weg zum Rechenziel folgt dann einer geodätischen Linie – wie die Bewegung in einem Gravitationsfeld. Die Berechnung entwickelt sich gewissermaßen im freien Fall. Die Länge des so gefundenen Weges entspricht der Zahl der Rechenschritte, die nötig sind, um das gewünschte Ergebnis zu erhalten.
Rainer Scharf
Weitere Infos:
- Originalveröffentlichungen:
Onur Hosten et al.: Counterfactual quantum computation through quantum interrogation. Nature 439, 949 (2006).
http://dx.doi.org/10.1038/nature04523
Michael A. Nielsen et al.: Quantum Computation as Geometry. Science 311, 1133 (2006).
http://dx.doi.org/10.1126/science.1121541 - Gruppe von Paul Kwiat:
http://www.physics.uiuc.edu/Research/QI/Photonics/index.html - Gruppe von Michael Nielsen:
http://www.qinfo.org/?page_id=2
Weitere Literatur:
- Jonathan P. Dowling: To compute or not to compute? Nature 439, 919 (2005).
http://dx.doi.org/10.1038/439919a - Graeme Mitchison & Richard Jozsa: Counterfactual computation. R. Soc. Lond. A 457, 1175 (2001).
http://dx.doi.org/10.1098/rspa.2000.0714 (frei!) - Jonathan P. Dowling & Gerard J. Milburn: Quantum technology: the second quantum revolution. Phil. Trans. R. Soc. Lond. A 361, 1655 (2003).
http://dx.doi.org/10.1098/rsta.2003.1227 (frei!) - P. Kwiat, H. Weinfurter & A. Zeilinger: Quantum Seeing in the Dark. Sci. Am. 275(5), 72 (1996).
http://www.quantum.univie.ac.at/publications/pdffiles/1996-21.pdf (25 MB!) - Michael A. Nielsen: A geometric approach to quantum circuit lower bounds.
http://arxiv.org/abs/quant-ph/0502070
