En los últimos días se está hablando mucho de computadores cuánticos, sobre todo tras la presentación del Sistema Orión de D-Wave, que muestran como la primera implementación comercial de un computador quántico. Estos computadores funcionan en base a qbits en lugar de los tradicionales bits. Su estado se basa en el spin de las partículas, y puede ser 0, 1 o una superposición de ambos. No es sobre esto sobre lo que me quería centrar, así que si te interesa hay unos maravillosos artículos en la wikipedia sobre circuitos quánticos y puertas lógicas quánticas. El caso es que a la gente le encanta decir que la criptografía moderna caerá en manos de la computación quántica. Y cierto es. Pero como también se dice que la criptografía moderna se basa en operaciones "difíciles", pues la gente se emociona y se imagina ordenadores capaces de resolverlo todo. Craso error. Veamos por partes. Para empezar, un Máquina de Turing puede emular un computador quántico. Por tanto, no va a resolver problemas irresolubles (o sea, que no son turing-computables). Por otro lado, hay una mezcla de conceptos con resolubilidad y complejidad. Que algo sea difícil de calcular (complejo) no quiere decir que no se pueda hacer (irresoluble). De hecho, los sistemas criptográficos actuales, como RSA o Elgamal, se basan en problemas como la factorización de números o los logaritmos discretos. Todos hemos factorizado números en el colegio. Pero los algoritmos que se conocen son muy ineficientes para número grandes. Formalmente hablando, los computadores quánticos, debido a las propiedades físicas con las que operan, permiten desarrollar algoritmos para esos problemas con una complejidad menor que los ordenadores actuales (basados en sumas, cargas en memoria, bucles, etc). En concreto los problemas con los que trabaja un computador quántico pertenecen a la clase BQP (Bounded error, Quantum, Polynomial time). Esto quiere decir, que encontrará en tiempo polinómico (eficiente) una solución al problema con un margen de error promedio inferior a 1/4. Los problemas BQP se cree que contienen a los P (polinómicos), y son estrictamente disjuntos de los NP-Completos (así a grosso modo, los realmente difíciles). Y digo se cree por que aquí entran temas de uno de los grandes problemas de las matemáticas actuales: P=NP? Lo que ocurre es que la factorización y el logaritmo discreto pertenecen a BQP. Pero eso no quiere decir nada acerca de probelmas complejos de verdad, ni es la panacea que resolverá lo irresoluble...