La computación cuántica es un paradigma de computación que abre una vía diferente a la computación clásica. Si en computación básica utilizamos el bit para definir, sólo, dos estados posibles, en computación cuántica utlizamos el qubit.
Cuando en la década de los 80, del siglo pasado, empiezan asurgir la primeras teorías de computación cuántica, el nobel Richard Feynman expone que los fenómenos cuánticos habilitarían que algunos cálculos de gran dificultad se realizaran de manera más rápida en un ordenador cuántico. Estos fenómenos se derivaban en una complejidad cuántica (complejidad dada en las amplitudes de probabilidad que determinan el estado del sistema cuántico). Pero, ¿sería posible desarrollar esta complejidad cuántica en un proceso computacional? Feynman muestra que es probable que estados cuánticos complejos no sean viables de simular en la computación clásica existente, y propone cómo debería ser la nueva computación. Ahora nos falta un algoritmo que funcione en esa nueva concepción.
Este algoritmo vendrá de la mano del matemático Peter Shor. En 1995 publicaría Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, donde expondría un algoritmo cuántico para descomponer en factores un número N en tiempo $O((log N)^3)$. La demostración se vería en 2001 desarrollada por IBM, donde utilizaron el algoritmo de Shor para descomponer 15 en sus factores usando una computadora cuántica con 7 qubits.
El algoritmo de Shor ha pasado a ser considerado un paradigma de los algoritmos cuánticos y, su fama, en cierta medida, se debe al trasfondo de su utilización. La descomposición en factores primos es la clave para atacar al RSA. El algoritmo de Shor pone de manifiesto que la venidera era de los computadores cuánticos dejará obsoletos los actuales sistemas criptográficos.
Este post forma parte del Carnaval de Matemáticas, que en esta quincuagésima tercera edición, también denominada 6.3: Teorema de Pitágoras, está organizado por Rafael Martínez González a través de su blog El mundo de Rafalillo.
2 comentarios
Los comentarios están cerrados.