L'algoritme de Shor és un pun de referencia de la ncfcccd,  es un dels algoritmes quàntics més coneguts, proposat per Peter Shor el 1994, i és famós per la seva capacitat de factoritzar nombres enters en temps polinòmic en una computadora quàntica, cosa que té profundes implicacions per a la criptografia.

Principals Característiques:

• Objectiu: Factoritzar nombres enters grans en els seus factors primers. Això és crucial perquè molts sistemes criptogràfics, com l'RSA, es basen en la dificultat de factoritzar nombres grans.
• Complexitat: L'algoritme de Shor pot factoritzar un nombre

  $�$

  en temps

  $�((\log �{)}^3)$

  , que és molt més ràpid que els millors algoritmes clàssics coneguts, que tenen una complexitat essencialment exponencial per a nombres molt grans.
• Mètode:
  1. Elecció de nombres: Seleccionar un nombre aleatori

     $�$

     que sigui coprim amb

     $�$

     .
  2. Trobar l'ordre: Calcular l'ordre de

     $�$

     mòdul

     $�$

     , que és el més petit nombre enter

     $�$

     tal que

     ${�}^{�}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}�)$

     . Això és on entra la computació quàntica per fer-ho eficientment.
  3. Post-processament clàssic: Utilitzar

     $�$

     per trobar els factors de

     $�$

     amb mètodes clàssics, com el càlcul del MCD (Màxim Comú Divisor).
• Components Quàntics:
  • Transformada de Fourier Quàntica (QFT): És una eina clau per trobar l'ordre de

    $�$

    , convertint els problemes de període en problemes de fase.
  • Exponenciació Modular Quàntica: Encara que més complexa de implementar que la QFT, és essencial per calcular

    ${�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�$

    per valors de

    $�$

    en superposició.

Implicacions:

• Criptografia: Si es desenvolupen ordinadors quàntics capaços d'executar l'algoritme de Shor amb suficients qubits i correcció d'errors, podrien trencar la criptografia RSA actual, portant a la necessitat de noves formes de criptografia resistents als ordinadors quàntics, conegudes com a criptografia postquàntica.
• Recerca i Desenvolupament: L'algoritme de Shor ha estat un impuls important per a la investigació en computació quàntica, motivant el desenvolupament de tecnologies i algoritmes quàntics.

Implementacions Pràctiques:

• IBM 2001: La primera implementació física de l'algoritme va ser per part d'IBM, que va factoritzar el nombre 15 en 3 i 5 utilitzant un ordinador quàntic de 7 qubits amb NMR (Resonància Magnètica Nuclear).
• Investigacions Posteriors: Hi ha hagut altres intents i demostracions amb nombres més petits, però cap encara amb nombres de mida pràctica per a aplicacions reals de criptografia.

Desafiaments:

• Escalabilitat: Factoritzar nombres de tamany pràctic requereix molts més qubits i mètodes avançats de correcció d'errors.
• Error i Decoherència: Els qubits actuals són molt sensibles a errors, necessitant tècniques sofisticades de correcció d'errors per mantenir la integritat dels càlculs.

L'algoritme de Shor continua sent un punt de referència per a la potència potencial de la computació quàntica, impulsant la recerca i desenvolupament en aquest camp amb l'esperança de superar els obstacles tècnics per arribar a aplicacions pràctiques.