Shors Algorithmus, entwickelt von Peter Shor im Jahr 1994, kann eine Ganzzahl N mithilfe von Quantencomputern in polynomieller Zeit O((log N)³) faktorisieren. Der beste bekannte klassische Algorithmus (General Number Field Sieve) läuft in subexponentieller Zeit. Dies ist bedeutsam, weil die RSA-Verschlüsselung auf der Schwierigkeit beruht, große Zahlen zu faktorisieren. Shors Algorithmus verwendet die Quanten-Fourier-Transformation, um die Periode einer modularen Exponentialfunktion zu finden. Obwohl der Algorithmus theoretisch mächtig ist, würde seine Ausführung auf realer Hardware, um RSA-2048 zu brechen, Millionen fehlerkorrigierter Qubits erfordern — weit jenseits der aktuellen NISQ-Fähigkeiten (die höchstens ~1000 verrauschte Qubits haben). Shors Algorithmus ist die primäre Motivation für die Forschung an Post-Quanten-Kryptografie und für die Standardisierungsbemühungen der NIST zur Post-Quanten-Kryptografie.
Verwandte Begriffe
QFT
AlgorithmsQuanten-Fourier-Transformation — das Quantenanalogon zur diskreten Fourier-Transformation, exponentiell schneller.
Quantenfehlerkorrektur
HardwareTechniken zum Erkennen und Korrigieren von Fehlern in Quantenschaltkreisen, ohne die Qubits zu messen (und zu kollabieren).
NISQ
HardwareNoisy Intermediate-Scale Quantum — Geräte mit 50–1000 Qubits ohne vollständige Fehlerkorrektur.