O algoritmo de Shor é un algoritmo cuántico para factorizar enteiros positivos, desenvolvido por Peter Shor en 1994. Shor presentou tamén un algoritmo relacionado para o logaritmo discreto; ambos empregan procedementos cuánticos para obter información sobre periodicidades.
O algoritmo de factorización ten un custo polinomial no número de bits do enteiro de entrada, nun modelo de computación cuántica con erro acoutado. Esta cota é asintoticamente menor que a dos mellores métodos clásicos xerais coñecidos. A aplicación práctica a tamaños criptográficos require computadores cuánticos con recursos e corrección de erros suficientes; a cota asintótica non fixa por si soa ese equipamento.
O algoritmo de Shor é un dos algoritmos cuánticos con aplicacións potenciais claras e unha aceleración superpolinomial fronte aos mellores algoritmos clásicos coñecidos. A aplicación a tamaños criptográficos require computadores cuánticos con recursos e corrección de erros suficientes. O número de qubits físicos depende da arquitectura, da taxa de erro, do tempo de execución e do circuíto empregado; non hai un requisito universal de millóns de qubits (véxase a sección de complexidade e recursos).
Shor propuxo varios algoritmos semellantes para resolver o problema da factorización de enteiros, o do logaritmo discreto e o da procura do período. «Algoritmo de Shor» adoita referirse ao de factorización, pero pode designar calquera dos tres. O de logaritmos discretos e o de factorización son casos do de procura do período, e os tres son casos do problema do subgrupo oculto. Tomando portas cuánticas da orde de con multiplicación rápida, o algoritmo demostra que a factorización de enteiros está na clase de complexidade BQP.
Viabilidade e implicacións miniatura|upright=1.2|alt=Un documento en claro cífrase coa chave pública e o documento cifrado descífrase coa chave privada.|Cifraxe e descifraxe mediante criptografía asimétrica. No diagrama, public key e private key son a chave pública e a privada; encryption e decryption, a cifraxe e a descifraxe; plaintext document e encrypted document, o documento en claro e o documento cifrado. Algúns destes esquemas poden ser vulnerados por computadores cuánticos suficientemente grandes. Supoñendo que un computador cuántico cun número suficiente de qubits puidese funcionar sen sucumbir ao ruído cuántico e a outros fenómenos de decoherencia cuántica, o algoritmo de Shor podería empregarse para romper esquemas de criptografía de chave pública, como os seguintes:
O esquema RSA O intercambio de chaves Diffie-Hellman sobre corpos finitos O intercambio de chaves Diffie-Hellman sobre curvas elípticas
A factorización eficiente permitiría vulnerar o sistema RSA. Non se coñece un algoritmo clásico xeral que factorice en tempo polinomial; esta afirmación non significa que calquera enteiro grande sexa difícil de factorizar. A posibilidade de executar Shor en computadores cuánticos axeitados é unha das motivacións da criptografía poscuántica.
Complexidade e recursos Para unha entrada de n bits, unha análise de circuítos con multiplicación rápida obtén unha cota de portas da orde de , fronte á cota cúbica da aritmética escolar.
Como exemplo dunha estimación con parámetros físicos concretos, Gidney e Ekerå publicaron en 2021 unha proposta para factorizar RSA-2048 en oito horas con vinte millóns de qubits físicos. É unha estimación dese modelo, non un requisito universal para executar o algoritmo.
En 2025, Gidney publicou unha estimación revisada para factorizar RSA-2048 en menos dunha semana con menos dun millón de qubits físicos ruidosos, baixo as hipóteses de hardware detalladas no traballo. É tamén unha estimación de recursos, non unha factorización realizada experimentalmente.
GEECM é unha variante cuántica da factorización con curvas de Edwards que incorpora o algoritmo de Grover. Bernstein e os seus colaboradores analizaron en 2017 casos nos que pode ter menor custo ca Shor, especialmente para módulos con factores relativamente pequenos; a comparación depende do modelo de custo e non é unha superioridade universal.
Implementación física As demostracións de laboratorio descritas a continuación, publicadas entre 2001 e 2016, traballaron con semiprimos pequenos e con distintos graos de simplificación dos circuítos. A probabilidade de obter un resultado útil nunha execución non depende só dos erros físicos: o propio algoritmo é probabilístico.
En 2001, un grupo de IBM e da Universidade Stanford fixo unha demostración do algoritmo de Shor na que factorizou en , usando unha implementación por resonancia magnética nuclear dun computador cuántico con sete qubits. En 2007, dous grupos independentes demostraron versións compiladas do algoritmo de Shor usando qubits fotónicos. En 2012, realizouse a factorización de con qubits de estado sólido. Tamén en 2012 se publicou unha demostración compilada da factorización de , cun qubit de control reciclado e un qutrit de traballo. En 2016, realizouse a factorización de usando qubits de ións atrapados. Monz e os seus colaboradores presentaron a súa arquitectura como escalable e afirmaron expresamente que non empregaban simplificacións que presupuxesen coñecer a solución. Nunha crítica publicada en 2013, Smolin, Smith e Vargo advertiran de que certas demostracións anteriores reducían o problema mediante coñecemento previo da solución. Para ilustrar o risco dunha simplificación excesiva, construíron unha versión adicional cuxa distribución de saída se podía reproducir lanzando moedas. Esa crítica é anterior ao experimento de Monz de 2016 e non o avalía.
Algoritmo O problema que tentamos resolver é: dado un número composto impar , atopar os seus factores enteiros.
Para conseguilo, o algoritmo de Shor consta de dúas partes:
Unha redución clásica do problema da factorización ao problema de atopar a orde. Esta redución é similar á usada noutros algoritmos de factorización, como a criba cadrática. Un algoritmo cuántico para resolver o problema de atopar a orde.
Redución clásica É posible obter un algoritmo de factorización completo se somos capaces de factorizar eficientemente un arbitrario en só dous enteiros e maiores que 1, xa que, se ou non son primos, o algoritmo de factorización pode executarse á súa vez sobre eles ata que só queden primos.
Unha observación básica é que, usando o algoritmo de Euclides, sempre podemos calcular eficientemente o máximo común divisor de dous enteiros. Tamén podemos comprobar eficientemente se é par, caso no que 2 é un factor. Supoñamos, daquela, que é impar no resto desta exposición. Despois, podemos usar algoritmos clásicos eficientes para detectar se é unha potencia perfecta , con e . Nese caso, xa é un divisor non trivial, que pode factorizarse recursivamente se é composto.Pódense probar os expoñentes enteiros , calcular candidatos a raíz enteira e comprobar exactamente . Véxase Nielsen e Chuang, exercicio 5.17, páxina 234. Isto cobre en particular as potencias de primos, polo que o resto do algoritmo pode supoñer que non é unha delas.
Se estes casos sinxelos non producen un factor non trivial de , o algoritmo continúa para tratar o caso restante. Escollemos uniformemente un enteiro aleatorio . Pódese atopar un posible divisor non trivial de calculando , o que pode facerse de forma clásica e eficiente usando o algoritmo de Euclides. Se isto produce un factor non trivial (é dicir, ), o algoritmo remata, e o outro factor non trivial é . Se non se identificou un factor non trivial, isto significa que e o valor escollido de son coprimos, polo que pertence ao grupo multiplicativo de enteiros módulo e ten un inverso multiplicativo módulo . Así, ten unha orde multiplicativa módulo , o que significa que
e é o menor enteiro positivo que satisfai esta congruencia.
A subrutina cuántica atopa . Da congruencia dedúcese que divide , o que se escribe . Isto pódese factorizar usando a diferenza de cadrados:Esta redución require que sexa par, para que sexa unha potencia de expoñente enteiro; se é impar, repítese a elección de . De aquí en diante supoñemos que é par. Non pode ocorrer que , pois contradiciría que é o menor expoñente positivo con esa propiedade. En cambio, pode ocorrer que . Se non divide , podemos atopar un factor non trivial. CalculamosSe , entón era certo que , non se pode obter un factor non trivial de a partir de e o algoritmo debe reiniciarse cun novo . En caso contrario, atopamos un factor non trivial de , sendo o outro , e o algoritmo remata. Para este paso tamén é equivalente calcular ; producirá un factor non trivial se é non trivial, e non o producirá se é trivial (cando ).
O algoritmo, reformulado brevemente, é o seguinte: sexa impar e non unha potencia dun primo. Queremos obter dous factores non triviais de . Escoller un número aleatorio . Calcular , o máximo común divisor de e . Se , entón é un factor non trivial de , sendo o outro factor , e rematamos. En caso contrario, usar a subrutina cuántica para atopar a orde de . Se é impar, volver ao paso 1. Calcular . Se é non trivial, o outro factor é , e rematamos. En caso contrario, volver ao paso 1.
Demostrouse que é probable que isto teña éxito tras unhas poucas execucións. Ekerå demostrou que, se se coñece a orde correcta dun elemento escollido uniformemente ao azar no grupo de unidades módulo , un posprocesamento clásico máis avanzado permite obter a factorización completa con probabilidade moi alta. Isto non garante que unha única medición cuántica proporcione esa orde correcta. (DOI de acceso libre).
Subrutina cuántica para atopar a orde O obxectivo da subrutina cuántica do algoritmo de Shor é, dados os enteiros coprimos e , atopar a orde de módulo , o menor enteiro positivo tal que . Para conseguilo, o algoritmo de Shor usa un circuíto cuántico con dous rexistros. O segundo rexistro usa qubits, onde é o menor enteiro tal que , é dicir, . O tamaño do primeiro rexistro determina a precisión da aproximación que produce o circuíto. Pódese demostrar que usar qubits dá precisión suficiente para atopar . O circuíto cuántico exacto depende dos parámetros e , que definen o problema. A seguinte descrición do algoritmo usa a notación bra-ket para denotar os estados cuánticos, e para denotar o produto tensorial.
O algoritmo consta de dous pasos principais:
Usar a estimación cuántica de fase coa matriz unitaria que representa a operación de multiplicar por (módulo ), e o estado de entrada (onde o segundo rexistro é , formado por qubits). Os valores propios desta codifican información sobre o período, e é unha superposición uniforme dos vectores propios relevantes. A medición produce un enteiro , cunha distribución concentrada preto dos valores , para . Estes valores ideais non son necesariamente enteiros. Usar o algoritmo de fraccións continuas para extraer o período dos resultados das medicións obtidos na etapa anterior. Trátase dun procedemento para posprocesar (cun computador clásico) os datos das medicións obtidos ao medir os estados cuánticos de saída e recuperar o período.
A conexión coa estimación cuántica de fase non se abordou na formulación orixinal do algoritmo de Shor, mais foi proposta máis tarde por Alexei Kitaev. Preprint, consultado o 9 de setembro de 2026.
Estimación cuántica de fase marco|alt=Circuíto con portas de Hadamard, multiplicacións modulares controladas, transformada de Fourier cuántica inversa e medición do rexistro de control.|Subrutina cuántica de Shor: H denota as portas de Hadamard e QFT inversa, a transformada de Fourier cuántica inversa. As portas inferiores multiplican polas sucesivas potencias cadradas da base módulo N.