Quantenrechnen: Eine Anleitung

Veröffentlicht am: 18. Juli 2015

Quelle: http://www-users.cs.york.ac.uk/~schmuel/comp/comp.html
Samuel L. Braunstein

Kurzbeschreibung:

Stelle dir einen Computer vor, dessen Gedächtnis exponentiell größer ist als seine scheinbare Größe; ein Computer, der ein exponentielles Set an Inputs zur selben Zeit verarbeiten kann; ein Computer, der in der Zwielichtzone des Hilbert-Raums arbeitet. Du würdest an einen Quantenrechner denken. Relativ wenige und simple Konzepte der Quantenmechanik sind notwendig, um Quantenrechner Wirklichkeit werden zu lassen. Die Raffinesse bestand darin, zu lernen, diese Konzepte zu manipulieren. Ist ein solcher Computer ein Ding der Unmöglichkeit, oder wird er zu schwierig zu bauen sein?

In diesem Aufsatz geben wir ein Tutorial, wie die Quantenmechanik benutzt werden kann, um die Berechnung mit Computern zu verbessern. Unsere Herausforderung: ein exponentiell schwieriges Problem mit einem konventionellen Computer zu lösen – nämlich das Faktorisieren großer Zahlen. Als Einstand werden wir die Standardwerkzeuge für diese Berechnung ansehen, universelle Gates und Maschinen.Diese Ideen werden dann erst auf klassische, dissipationsarme Computer und schließlich auf Quantencomputer angewendet. Ein schematisches Modell eines Quantencomputers wird ebenso beschrieben wie einige der Feinheiten zu seinem Programmieren. Der Shor-Algorithmus [1,2], der benötigt wird, um effizient Zahlen auf einem Quantenrechner zu faktorisieren, wird in zwei Teilen vorgestellt: der Quantenprozedur im Algorithmus und dem klassischen Algorithmus, der die Quantenprozedur aufruft. Die mathematische Struktur beim Faktorisieren, der den Shor-Algorithmus möglich werden lässt, wird diskutiert. Wir schließen mt einem Ausblick zur Machbarkeit und den Perspektiven der Quantencomputerrechnung in den kommenden Jahren.

Lasst uns starten, indem wir das vorliegende Problem beschreiben:  eine Zahl N in ihre Primfaktoren zu faktorisieren (z.B. kann die Zahl 51688 in zerlegt werden). Ein zufriedenstellender Weg, zu quantifizieren, wie schnell ein bestimmter algorithmus ein Problem lösen kann, ist, zu fragen, wie die Zahl der Schritte, die benötigt werden, um den Algorithmus zu komplettieren, mit der Größe des „Inputs“, mit dem der Algorithmus gefüttert wird, skaliert. Für das Faktorisierungsproblem bedeutete dieser Input die Zahl N, die wir faktorisieren wollen; daher ist die Länge des Inputs . (Die Basis des Logarithmus’ wird bestimmt von unserem Zahlensystem. Daher bedeutete eine Basis von 2 die Länge in einem Binärsystem; eine Basis von 10 in einem Dezimalsystem.) `Vernünftige’ Algorithmen sind solche, die als kleingradige Polynome in der Inputgröße skalieren (mit einem Grad von vielleicht 2 oder 3).

Auf konventionellen Computern läuft der bekannteste Faktorisierungsalgorithmus in Schritten [3]. Dieser Algorithmus skaliert also exponentiell mit der Inputgröße . Beispielsweise wurde 1994 eine 129stellige Zahl, bekannt als RSA129 [3′]), erfolgreich faktorisiert, indem dieser Algorithmus auf geschätzten 1600 Arbeitsstationen auf der ganzen Welt benutzt wurde; die gesamte Faktorisierung dauerte acht Monate. [4]. Benutzen wir dies, um den Vorfaktor für die obenstehende exponentielle Skalierung zu schätzen, kommen wir zu dem Ergebnis, dass es grob geschätzte 800.000 Jahre dauern würde, um  mit derselben Computerkraft eine 250-stellige Zahl zu faktorisieren; gleichermaßen würde eine 1000-stellige Nummer Jahre benötigen (signifikant länger, als das Alter des Universums beträgt). Die Schwierigkeit, große Zahlen zu faktorisieren, ist von entscheidender Bedeutung für  Kryptosysteme mit öffentlichem Schlüssel, wie sie etwa von Banken benutzt werden. Dort verlassen sich die Codes auf die Schwierigkeit, Zahlen mit etwa 250 Stellen zu faktorisieren. y

Kürzlich wurde ein Algorithmus entwickelt, mit dem Zahlen auf einem Quantenrechner faktorisiert werden können, der in  Schritten läuft,  klein ist. [1]. Dies ist grob quadratisch in seiner Inputgröße, was bedeutet, dass das Faktorisieren einer 1000-stelligen Zahl mit einem solchen Algorithmus nur ein paar Millionen Schritte benötigen würde. Die darunterliegende Implikation ist, dass auf dem Faktorisieren basierende Kryptosysteme mit öffentlichem Schlüssel geknackt werden können.T

Um dir eine Vorstellung davon zu geben, wie diese exponentielle Verbesserung möglich sein könnte, schauen wir uns ein elementares quantenmechanisches Experiment an, welches zeigt, wo dies Kraft verborgen liegen könnte. [5]. Das zweischneidige Experiment ist prototypisch für die Beobachtung von quantenmechanischem Verhalten: Eine Quelle emittiert Photonen, Elektronen oder andere Partikel, die einen Doppelschlitz erreichen. Diese Partikel unterlaufen eine einheitliche Entwicklung und schließlich Messung. Wir sehen ein  Interferenzmuster, mit beiden Schlitzen offen, das vollständig verschwindet, sobald einer der Schlitze bedeckt wird. In manchem Sinne dringen die Partikel durch beide Schlitze parallel ein. Wenn solch eine einheitliche Entwicklung  eine Berechnung repräsentieren könnte (oder eine Operation in einer Berechnung), dann würde das Quantensystem parallele Berechnungen durchführen. Quantenparallelen kosten nichts. Der Output dieses Systems würde sich aus der konstruktiven Interferenz zwischen den parallelen Berechnungen ergeben.