Físicos demuestran que 15 es 3x5...¡casi el 50% de las veces!

A pesar del cachondeito en el título no debemos restarle mérito a la investigación, ya que el cálculo se ha realizado con un prototipo de ordenador cuántico de estado sólido. La publicación ha sido aceptada en Nature Physics por ser la primera implementación que usa esta tecnología, en lugar de p.ej. NMR. La relevancia de avances en la solución de este problema matemático son tales que tarde o temprano acabarán afectando a nuestra vida diaria, nuestras empresas y la seguridad de las transacciones financieras.
Se llama factorizar un número N a averiguar de qué números primos P,Q,... está compuesto, tal que si sólo existiesen dos factores, tendríamos N=P x Q. Por ejemplo, del número 9 sacamos que es 3x3; o del 15 que es 3x5.
La teoría es muy fácil. Solamente que se la cosa se complica un poquito cuando intentamos factorizar números más grandes. ¿Cómo factorizarías este numerazo?:

N = 31074182404900437213507500358885679300373460228427275457 20161948823206440518081504556346829671723286782437916272 83803341547107310850191954852900733772482278352574238645 4014691736602477652346609   

A pesar de ser trivial comprobar si un número dado es un factor correcto o no (basta con dividir y ver si el resto es cero), es obviamente una locura intentar adivinar los factores "al tuntún". Hacerlo con un ordenador no arregla mucho las cosas. Desde hace décadas se conoce un algoritmo (el  GNFS) para abordar el problema de factorizar números tan grandes como éste, pero el tiempo que necesita para obtener una respuesta crece casi exponencialmente (sub-exponential) con la longitud del número dado.

Para hacerse una idea de la magnitud del problema, el número de arriba fue propuesto como un reto en 1991 y no fue hasta 2005 que consiguieron factorizarlo, ¡ganando un premio de 10,000$!. Si te interesa la solución que costó 14 años en obtener, aquí está (aunque necesitarás una calculadora especial para probarlo):

N = 16347336458092538484431338838650908598417836700330923121 81110852389333100104508151212118167511579 
 × 
19008712816648221131268515739354139754718967899685154936 66638539088027103802104498957191261465571

Tan difíciles son de factorizar los números grandes que, hoy día, se puede afirmar que prácticamente toda la seguridad en comunicaciones electrónicas (Internet, TV de pago por satélite, etc.) depende en último extremo de ese simple hecho.

Cuando navegas por Internet y aparece junto a la dirección un "candado" que muestra que la comunicación no puede ser espiada y que el servidor es quien dice ser, por debajo existe un formidable aparato matemático y tecnológico que, al fin y al cabo, se apoya en un único punto seguro: la dificultad de factorizar una clave pública (e.g. RSA).

Aquí entran en juego los computadores cuánticos. De entre los poquísimos algoritmos teóricos existentes para ellos, da la casualidad que el algoritmo de Shor sirve precisamente para factorizar números enteros:

Representación esquemática con bloques (a) y en detalle (b) del algoritmo cuántico de Shor para factorización. Los bloques "H" son puertas de Hadamard; los 45 y 90 son puertas de desplazamientos de fase y los "circulitos" de abajo son puertas C-NOT, el equivalente cuántico del clásico XOR. (Créditos: Sambit Bikas Pal)

La potencia de usar un algoritmo cuántico radica en que su complejidad de ejecución es polinomial en lugar de sub-exponencial, lo que quiere decir que sería muy fácil factorizar números enormes... ¡si tuvieramos ya un ordenador cuántico capaz de ejecutar el programa necesario!

El experimento de factorizar el número 15 usando un computador cuántico se ha realizado con éxito en el pasado, pero la novedad hoy es que  Andre Cleland y su equipo han diseñado una implementación de estado sólido, mucho más pequeño y manejable que anteriores diseños, aunque eso sí, necesita temperaturas cercanas al 0K. La siguiente microfotografía muestra el chip, que completo ocupa unos 1,6cm²:

El circuito cuántico, compuesto de 9 elementos cuánticos: 4 qubits de fase y 5 resonadores superconductores (las pistas que "serpentean"). El patrón se repite alrededor del cuadrado enfocado en la foto, una técnica común al diseñar circuitos integrados para aprovechar y construir varios circuitos en una misma oblea. (Créditos: UCSB)

Naturalmente, al igual que en cualquier computador cuántico el resultado de la operación de factorización no se obtiene tras una ejecución determinista, sino que debe repetirse un elevado número de veces y hacer un post-procesado de los datos.

Los científicos dicen que han repetido el cálculo 150.000 veces, obteniendo los factores correctos (15=3x5) casi un 50% de las veces. Ya que el límite teórico está en exactamente 50%, consideran su implementación todo un éxito.

Explicación de las partes del circuito por los autores (fuente)

¿Llegaremos a ver chips cuánticos capaces de factorizar números más grandes? ¿En qué momento empezarán a resultar una amenaza seria para la seguridad de las telecomunicaciones?

Antes de que llegue, seguro que la alternativa habrá dado lugar a nuevas empresas generando un importante volumen de negocio a nivel mundial. Solamente los países y empresas que hayan apostado fuerte por el I+D recogerán esos bien merecidos beneficios.

Fuente:

Ciencia Explicada