Verschränkung bremst Quantenrechner

Zu stark verschränkte Anfangszustände sind schlecht für den Einweg-Quantencomputer

Warum ist ein Quantencomputer einem klassischen Computer so haushoch überlegen? Sowohl bei der Primfaktorenzerlegung großer Zahlen (mit Shors Algorithmus) als auch beim Durchsuchen großer Datenmengen (mit Grovers Algorithmus) ist der Quantencomputer viel schneller: die Zahl der Rechenschritten wächst nur wie ein Polynom mit der Größe der Eingangsdaten an. Beim herkömmlichen Computer nimmt die Zahl der Schritte hingegen exponentiell zu. Im Gegensatz zum klassischen Computer rechnet ein Quantencomputer nicht mit Bits aus Nullen und Einsen sondern mit Qubits, also jeweils Überlagerungen zweier Quantenzustände |0> und |1>. Zudem können die Qubits quantenmechanisch verschränkt sein, z. B. |0>|1>+|1>|0>. Womöglich ist die Verschränkung der Grund für die Überlegenheit. Doch zu viel Verschränkung kann auch schädlich sein, wie zwei neue Arbeiten für Einweg-Quantencomputer zeigen.

Abb.: Messen statt rechnen. Der Einweg-Quantencomputer führt eine Reihe von Messungen an einem Quantenzustand durch und berechnet nach jedem Schritt auf „klassische“ Weise das weitere Vorgehen. (Bild: Alan Stonebraker)

Der Einweg-Quantencomputer besteht aus einem Quantensystem mit möglichst vielen Qubits in einem verschränkten Zustand, einer Messvorrichtung sowie einem klassischen Computer. Die Arbeit dieses Quantencomputers besteht darin, jeweils ein einzelnes Qubit zu messen und das Messergebnis dem klassischen Computer als Input zu übergeben, der daraufhin nach einem vorgegebenen Algorithmus berechnet, welches Qubit auf welche Weise als nächstes gemessen werden soll. Das Ergebnis dieser Folge von Rechenschritten ist entweder ein Quantenzustand aus noch nicht gemessenen Qubits oder, nach Messung aller Qubits, ein klassisches Ergebnis in Form eines Bitstrings.

Viele Rechnungen eines universellen Quantencomputers, der Qubits nicht nur misst sondern auch transformiert, lassen sich auch auf einem Einweg-Quantencomputer effizient durchführen. In diesem Fall ist auch er schneller als ein klassischer Rechner. Dazu muss allerdings sein anfänglicher Quantenzustand hinreichend stark verschränkt sein. Ist er das nicht weil er z. B. ein Produkt von Qubits ist, so kann der Einweg-Quantencomputer nicht mehr leisten als ein klassischer Rechner. Daher wurde vermutet, dass ein Anfangszustand den Einweg-Quantencomputer umso leistungsfähiger macht, je stärker verschränkt er ist. Doch das ist nicht der Fall, wie Jens Eisert von der Universität Potsdam und seine Mitarbeiter sowie die Forschungsgruppe von Andreas Winter an der University of Bristol unabhängig voneinander gezeigt haben.

Den Grad der Verschränkung eines Zustands misst man z. B. als seinen Abstand von allen Produktzuständen im entsprechenden Hilbert-Raum. Wenn der Verschränkungsgrad eines Zustands einen bestimmten Wert überschreitet, wird der Zustand unbrauchbar als Anfangszustand für den Einweg-Quantencomputer. Statt Messungen an diesem Quantenzustand durchzuführen und die Ergebnisse in den Algorithmus einzufüttern, der dann ein bestimmtes Problem löst, könnte man ebenso gut einen klassischen Zufallsprozess benutzen, der den Input für einen entsprechend veränderten Algorithmus liefert, mit dem sich dasselbe Problem in derselben Zahl von Rechenschritten lösen ließe. Somit machen stark verschränkte Anfangszustände den Einweg-Quantencomputer so langsam wie einen klassischen Rechner. Nur weniger verschränkte Zustände haben besondere Eigenschaften, die ein Einweg-Quantencomputer so ausnutzen kann, dass er effizienter arbeitet.

Leider sind stark verschränkte Quantenzustände im Hilbert-Raum nicht die Ausnahme sondern die Regel, wie beide Forschergruppen zeigen konnten. Entsprechend selten sind Quantenzustände, die einen Einweg-Quantencomputer so effizient machen, dass er wie ein universeller Quantencomputer arbeitet: Für Zustände aus n Qubits beträgt der Bruchteil dieser nützlichen Zustände nur exp(-n2). Zufällig herausgegriffene Anfangszustände sind praktisch immer stark verschränkt und damit nutzlos für den Einweg-Quantencomputer. Andreas Winter und seine Mitarbeiter konnten noch mehr zeigen: Selbst wenn man die Menge der Zustände, aus der man den Anfangszustand zufällig auswählt, stark einengt, zieht man praktisch immer Nieten. Der Einweg-Quantencomputer, dessen Konzept so attraktiv ist, steht also vor einem großen Problem: Er benötigt Anfangszustände mit außergewöhnlichen Eigenschaften. Und um diese Zustände herzustellen, braucht man womöglich so etwas wie –einen universellen Quantencomputer. Warum aber Quantencomputer so viel schneller sind als klassische Rechner und welche Rolle dabei die verschränkten Quantenzustände spielen, bleibt weiterhin unklar.

RAINER SCHARF


Weitere Infos:

• Originalveröffentlichungen:
  D. Gross, S. T. Flammia, and J. Eisert: Most Quantum States Are Too Entangled To Be Useful As Computational Resources. Phys. Rev. Lett. 102, 190501 (2009)
  http://dx.doi.org/10.1103/PhysRevLett.102.190501
  http://arxiv.org/abs/0810.4331 
• Michael J. Bremner, Caterina Mora, and Andreas Winter: Are Random Pure States Useful for Quantum Computation? Phys. Rev. Lett. 102, 190502 (2009)
  http://dx.doi.org/10.1103/PhysRevLett.102.190502
  http://arxiv.org/abs/0812.3001 
• Gruppe von Jens Eisert an der Uni Potsdam:
  http://www.jense.qipc.org/ 
• Homepage von Andreas Winter an der University of Bristol:
  http://www.maths.bris.ac.uk/~csajw/
  

Weitere Literatur:

• Dave Bacon: Too entangled to quantum compute one-way. Physics 2, 38 (2009)
  http://physics.aps.org/articles/v2/38 
• Richard Jozsa and Noah Linden: On the role of entanglement in quantum-computational speed-up. Proc. R. Soc. London A 459, 2011 (2003) 
  http://dx.doi.org/10.1098/rspa.2002.1097 (frei) 
• Robert Raussendorf and Hans J. Briegel: A One-Way Quantum Computer. Phys. Rev. Lett. 86, 5188 (2001)
  http://dx.doi.org/10.1103/PhysRevLett.86.5188
  http://puhep1.princeton.edu/~mcdonald/examples/QM/raussendorf_prl_86_5188_01.pdf (frei) 
• M. Van den Nest et al.: Fundamentals of universality in one-way quantum computation. New J. Phys. 9, 204 (2007)
  http://dx.doi.org/10.1088/1367-2630/9/6/204 (frei)
  

AL