L'algorithme de Shor, développé par Peter Shor en 1994, factorise un entier N en temps polynomial O((log N)³) à l'aide d'ordinateurs quantiques. Le meilleur algorithme classique connu (le crible général sur les corps de nombres) s'exécute en temps sous-exponentiel. Cela est significatif car le chiffrement RSA repose sur la difficulté de factoriser de grands nombres. L'algorithme de Shor utilise la Transformée de Fourier Quantique pour trouver la période d'une fonction d'exponentiation modulaire. Bien que l'algorithme soit théoriquement significatif, l'exécuter sur du matériel réel pour casser RSA-2048 nécessiterait des millions de qubits corrigés d'erreurs, bien au-delà des capacités NISQ actuelles (qui comptent au maximum environ 1000 qubits bruités). L'algorithme de Shor est la principale motivation de la recherche en cryptographie post-quantique et de l'effort de standardisation du NIST en la matière.
Termes associés
QFT
AlgorithmsQuantum Fourier Transform : l'analogue quantique de la transformée de Fourier discrète, exponentiellement plus rapide.
Estimation de Phase Quantique
AlgorithmsUn algorithme qui estime la phase de la valeur propre d'un opérateur unitaire : la subroutine sous-jacente à l'algorithme de Shor et aux calculs d'énergie en chimie quantique.
Correction d'Erreur Quantique
HardwareDes techniques pour détecter et corriger les erreurs dans les circuits quantiques sans mesurer (et donc effondrer) les qubits.
NISQ
HardwareNoisy Intermediate-Scale Quantum : des appareils de 50 à 1000 qubits sans correction d'erreur complète.