Algoritmul Shor, dezvoltat de Peter Shor în 1994, factorizează un număr întreg N în timp polinomial O((log N)³) folosind computere cuantice. Cel mai bun algoritm clasic cunoscut (ciurul general al câmpului de numere) rulează în timp sub-exponențial. Acest lucru este semnificativ deoarece criptarea RSA se bazează pe dificultatea factorizării numerelor mari. Algoritmul Shor folosește Transformata Fourier Cuantică pentru a găsi perioada unei funcții de exponențiere modulară. Deși algoritmul este semnificativ din punct de vedere teoretic, rularea sa pe hardware real pentru a sparge RSA-2048 ar necesita milioane de qubiți corectați de erori, mult peste capacitățile NISQ actuale (care au cel mult aproximativ 1000 de qubiți zgomotoși). Algoritmul Shor este principala motivație pentru cercetarea criptografiei post-cuantice și pentru efortul de standardizare al NIST în acest domeniu.
Termeni asociați
QFT
AlgorithmsQuantum Fourier Transform: analogul cuantic al transformatei Fourier discrete, exponențial mai rapid.
Estimarea Fazei Cuantice
AlgorithmsUn algoritm care estimează faza valorii proprii a unui operator unitar: subrutina care stă la baza algoritmului Shor și a calculelor de energie din chimia cuantică.
Corecția Erorilor Cuantice
HardwareTehnici de detectare și corectare a erorilor din circuitele cuantice fără a măsura (și deci prăbuși) qubiții.
NISQ
HardwareNoisy Intermediate-Scale Quantum: dispozitive cu 50-1000 de qubiți, fără corecție completă a erorilor.