En teoría de números, la factorización de enteros o factorización de primos consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original.
Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos (RSA-200) tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos, como el RSA. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema.
A pesar de esto, un grupo de invewstigadores de la Universidad de California en Santa Bárbara, ha diseñado y fabricado un procesador cuántico capaz de factorizar un número compuesto, en este caso 15, en sus factores primos constitutivos, 3 y 5.
Aunque esto es modesto comparado con estos números de 200 o más cifras, el logro representa un extraordinario avance en el camino de construir una computadora cuántica capaz de factorizar números mucho más grandes, con implicaciones en criptografía y seguridad computacional. Los resultados se han publicado en la revista en línea del Journal Nature Physics.
“Quince es un número pequeño, pero lo que es importante es que hemos mostrado que podemos correr una versión del algoritmo de factorización de Peter Shor en un procesador cuántico de estado sólido. Esto es muy emocionante pues nunca antes se había hecho nada semejante”, dice Erik Lucero, el líder del proyecto y autor del artículo científico. Lucero era un estudiante de doctorado en física de la UCSB cuando se realizó la investigación y cuando se escribió el artículo. Ahora es un investigador posdoctoral en computación experimental cuántica de IBM.
“Lo que es importante es que los conceptos usados en la factorización de este pequeño número se mantienen igual cuando se trata de factorizar números mucho más grandes”, dice Andrew Cleland, un profesor de física de la UCSB y colaborador en el experimento. “Tenemos simplemente que escalar el tamaño del procesador a algo mucho más grande. No será fácil, pero la trayectoria a seguir es clara”.
De acuerdo a Lucero, las aplicaciones prácticas son las que motivaron la investigación, quien explicó que la factorización de números grandes es el corazón de los protocolos de ciberseguridad, como por ejemplo, la conocida encripción RSA. “Cada vez que se manda una transmisión segura, como la información de la tarjeta de crédito, se está confiando en la seguridad de los procedimientos asociados a este mensaje encriptado, los cuales se basan en la factorización de primos muy grandes”. De hecho, factorizar un número de unas 600 cifras podría tomar más tiempo que toda la edad del universo conocido, indica el investigador.
Una computadora cuántica podría reducir el tiempo de espera a unas décimas de minutos. “Una computadora cuántica puede resolver este problema más rápido que una computadora clásica por cerca de 15 órdenes de magnitud”, dice Lucero. ” Esto tiene un efecto ampliador. Una computadora cuántica podría ser el factor de cambio de muchas maneras y evidentemente en el tema de criptografía”.
Lucero y sus colegas diseñaron y fabricaron el procesador cuántico para factorizar el número 15 porque es el número compuesto más pequeño que satisface las condiciones apropiadas para probar el algoritmo de Shor: “es el producto de dos primos y no es par”, explicó el investigador.
El procesador cuántico se implementó usando un circuito cuántico compuesto de cuatro qubits de fase superconductores -el equivalente a los transistores- así como cinco resonadores de microondas. La complejidad de operación de estos nueve circuitos requirió construir un sistema de control que permitiese un grado significativo de automatización, un prototipo que facilite el escalar la arquitectura cuántica a circuitos mas grandes y complejos.
“Después de repetir el experimento 150,000 veces, mostramos que nuestro procesador cuántico obtuvo la respuesta correcta”, dijo Lucero. El siguiente paso, de acuerdo con Lucero es incrementar la cohesión cuántica e ir de nueve elementos a cientos, a miles, hasta llegar al millón.
Referencia: Science Daily