El algoritmo cuántico de Peter Shor permite factorizar un número de n dígitos binarios usando O(n) cúbits conectados por O(n2 log n) puertas lógicas cuánticas (operaciones individuales), finalizando con O(1) medidas cuánticas (ejecuciones repetidas) y un prostprocesado clásico en tiempo polinómico. Oded Regev publicó el año pasado en arXiv un nuevo algoritmo de factorización que requiere O(n3/2) puertas lógicas cuánticas, aunque con O(n3/2) cúbits, O(n1/2) medidas cuánticas y un nuevo postprocesado clásico en tiempo polinómico.
Comentarios
Gracias por el envío #0 una explicación clara, concisa y muy esclarecedora, así da gusto entrar en MNM
#2 Es lo menos que podia hacer tras tu brillante envio de ayer.
Una exquisitez.
Ojo con esto, que es peliagudo.
Lo digo en serio. Los sistemas de seguridad de datos en Internet se basan algoritmos cuya seguridad depende que la imposibilidad de factorizar números altos en un tiempo asumible.
Un algoritmo cuántico que pudiera factorizar números altos en tiempo asumible, podría "cargarse" la seguridad de las conexiones de Internet.
De todas formas, Francis ya avisa de que el algoritmo de factorización aún sigue siendo muy lento. Aunque este tipo de cosas debería hacer que se empiecen a poner las pilas en temas de seguridad cuántica, por lo de la carrera armamentística entre los que intentan robar datos y los que intentan que no se roben:
En resumen, se ha logrado avanzar en un tema que ha estado bastante parado durante tres décadas. El nuevo impulso hará que se active este campo. Todos deseamos que aparezcan nuevas optimizaciones algorítmicas que permitan factorizar números mayores de 21 en ordenadores cuánticos NISQ actuales. Pero que nadie se engañe, factorizar números de interés en criptografía y seguridad informática no se logrará hasta la segunda década de este siglo.
#1 La segunda década de este siglo? Creo que estamos en la tercera...