Mit anderen Worten, bleibt die Factoring-Forschung ausschließlich in der klassischen Welt oder gibt es in der Quantenwelt interessante Forschungsarbeiten zum Thema Factoring?
algorithm
shors-algorithm
R. Chopin
quelle
quelle
Antworten:
Asymptotisch ist Shors Algorithmus wirklich effizient. Im Grunde ist es nur: Überlagerung, modulare Exponentiation (der langsamste Schritt) und eine Fourier-Transformation. Modulare Exponentiation ist das, was Sie tun, um das RSA-Kryptosystem tatsächlich zu verwenden. Für einen Quantencomputer bedeutet dies, dass das legitime Ver- und Entschlüsseln von RSA ungefähr so schnell ist wie die Verwendung des Shor-Algorithmus, um das System zu beschädigen. Ich bin also skeptisch, dass es Verbesserungen an der Grundidee geben wird.
Das heißt, jede Verbesserung der Ganzzahladdition, der Ganzzahlmultiplikation oder der Quanten-Fourier-Transformation würde Shors Algorithmus verbessern, und das sind alles sehr allgemeine Unterprogramme, an denen die Leute mit ziemlicher Sicherheit arbeiten werden. Eine kurze Suche in Google Scholar zeigt viele Untersuchungen zur Verbesserung der quantenarithmetischen Schaltungen.
Ich denke, es wird mehr Forschung zu klassischen / Quanten-Kompromissen in Shors Algorithmus geben. Das heißt, wenn Sie einen kleinen oder verrauschten Quantencomputer haben, können Sie den Shor-Algorithmus so modifizieren, dass er immer noch funktioniert, aber möglicherweise viel mehr Vor- und Nachbearbeitung auf einem klassischen Computer benötigt oder eine geringere Erfolgswahrscheinlichkeit hat. usw.? In diesem Bereich gibt es Quantenalgorithmen zur Berechnung kurzer diskreter Logarithmen und zur Faktorisierung von RSA-Ganzzahlen . Es gibt auch das QuantenzahlfeldsiebEin Ansatz, bei dem ein "kleiner" Quantencomputer (zu klein, um Shors Algorithmus direkt zu verwenden) als Unterprogramm des klassischen Zahlenfeldsiebs verwendet wird, wodurch die Zeitkomplexität leicht verbessert wird (obwohl ich persönlich davon überzeugt bin, dass eine Fehlerkorrektur hierfür mehr erfordert physikalische Qubits als Vanilla Shors Algorithmus).
Kurz gesagt, ich erwarte keine radikalen neuen Quantenfaktor-Algorithmen und ich glaube nicht, dass irgendjemand daran arbeitet. Es gibt jedoch viele interessante Verbesserungen, die an bestimmte Anwendungsfälle angepasst werden müssen.
quelle
Als Ergänzung zur Antwort von Sam:
Nein, auch weil Shors Ansatz nicht die einzige Möglichkeit ist, Zahlen zu faktorisieren.
Faktorisierung kann auch als Optimierungsproblem geschrieben werden .
Dies kann mit der D-Wave-Maschine , aber auch mit einem Gate-basierten Quantencomputer gelöst werden .
quelle
Zur Erinnerung, Shors Algorithmus ist im Gate- Berechnungsmodell implementiert .
Die Laufzeit des adiabatischen Algorithmus ist, wie ich es verstehe, notorisch unbeständig zu bestimmen, da sie auf den spektralen Eigenschaften des Problems Hamiltonian basiert.
Obwohl numerische Simulationen manchmal ermutigend ausgesehen haben, ist es meines Erachtens immer noch eine offene Frage, ob ein adiabatischer Factoring-Algorithmus tatsächlich eine exponentielle Beschleunigung gegenüber klassischem Factoring bietet.
Weitere Einzelheiten finden Sie in diesem Artikel von Peng, Liao, Xu, Gan Qin, Zhou, Suter und Du. 3 Simulationen der Laufzeit deuten auf eine quadratische Anpassung hin; jedoch; Ich bin mir nicht sicher, ob weitere Untersuchungen zum Nachweis einer solchen Anpassung oder zum Nachweis einer polynomiellen Laufzeit durchgeführt wurden.
quelle