Computacion cuantica

No voy a entrar aquí en justificar la utilidad de la computación cuántica frente a la clásica, hay infinidad de información en internet para ello, personalmente recomiendo esta: (El tamiz. Cuántica sin fórmulas), o esta otra:  Ecos del futuro. Tampoco voy a entrar en la teoría física que la sustenta por el mismo motivo, únicamente decir que para los efectos prácticos de la computación cuántica, de todos los estados físicos posibles de los sistemas, elegiremos un sistema con únicamente dos autoestados opuestos, los cuales constituyen la unidad básica de la computación cuántica: el qbit (el equivalente cuántico del bit de la computación clásica).

La diferencia fundamental con la computación clásica es que mientras en el bit únicamente puede darse uno de los dos estados simultáneamente, en la computación cuántica el qubit puede encontrarse en una superposición de ambos autoestados con una probabilidad determinada de colapsar, o definirse en uno de los dos, al realizar la medida u observación.

Si voy a aclarar, sin embargo algunos conceptos que me parecen poco claros en la mayoría de las páginas de internet visitadas, correspondientes a la teoría física que sustenta la base de la computación cuántica.

 

El Bit frente al Qbit:

 

En computación clásica, la unidad básica de información/computación es el Bit, puedes informarte sobre él en otros foros.

Por contra, en computación cuántica la unidad básica es el Qbit o mejor qbit. Tambien como antes hay en internet numerosa información, sin embargo intentaré aclarar un poco la diferencia entre ambos.

Mientras el bit es un objeto (imagínalo como una caja) que puede contener únicamente un 0 ó un 1, pero no ambos a la vez, el qbit es un objeto que contiene al mismo tiempo el 0 y el 1 con una probabilidad entre el 0 y el 100% de que al tomar la lectura obtengamos uno u otro valor, pero además al tomar la lectura y forzar que el qbit colapse (quede definido en uno de los dos valores) ello modifica de algún modo al resto de qbits relacionados con él. Es como si al obtener un resultado el hardware sobre el que corre el programa se modificase instantáneamente.

En física los sistemas tienen infinidad de estados, pero para la computación cuántica elegimos sistemas con dos autoestados (pongamos una moneda que no puede caer de canto y únicamente arroja cara o cruz, dos polaridades ortogonales de un fotón, los dos sentidos del spin de una partícula elemental etc.) El qbit, en nuestro ejemplo, vendría a ser la moneda girando en el aire salvo por un pequeño detalle: la moneda en el aire podríamos saber, conociendo su velocidad de giro y de ascenso y caida cual sería el resultado antes de que cayera. Con el qbit no existe esa posibilidad. Aún conociendo todos los datos sobre él (de hecho la fúnción que lo define los contiene) no podríamos predecir el resultado, porque éste depende del observador. En efecto, es el hecho de tomar la lectura, de medir u observar el que interfiere y "obliga" al qbit a definirse y a perder su cualidad de qbit para transformarse en un mísero bit común y corriente.

 

Si estás hecho un lío y te he confundido más que aclarado, te recomiento que visites esta página:

Cuántica sin fórmulas - El Tamiz

 

Dicho mal y pronto, la computación cuántica lo que pretende es modificar la probabilidad de los qbits de forma y manera que al final se tenga la "certeza" 100% de probabilidad de que la lectura producirá el resultado deseado que puede ser 0 ó 1. Si esto lo combinamos con el número de qbits que están en el registro de salida... nos podemos hacer una idea de la potencia de cálculo de un ordenador de estas características. La única dificultad reside en que la concepción de la programación es completamente diferente.

Quizás el mejor ejemplo sería una orquesta. Cuando todos los músicos tocan armónicamente habremos hallado el resultado que buscábamos, mientras que cuando están afinando sus instrumentos, cada uno por su cuenta, el resultado es un ruido desarmonizado. La computación verdría a equivaler a la dirección de la orquesta que persigue la armonía.

La computación cuántica, como la convencional, tambien utiliza puertas lógicas, registros, almacenamiento, en fin máquina de Turing cuántica en general. Con algunas sutiles diferencias. Por ejemplo: las puertas lógicas cuánticas son bidireccionales, pueden operar en ambos sentidos y de este modo afectar a pasos computacionales previos.

Por todo lo visto, parece complicado encontrar algún sistema intuitivo y sin fórmulas para poder ejemplificar la computación cuántica, sin embargo si que existe uno y muy conocido: el buscaminas de Windows.

Seguramente los más jóvenes que leáis este blog, no hayáis oído hablar del buscaminas de Windows (minesweeper). Fue un juego introducido en las primeras versiones de ese software con la modesta finalidad de que el usuario adquiriese soltura con un, entonces novedoso, artilugio introducido en los ordenadores personales: el ratón. Es seguro que muchos de los que lean esto tampoco sepan ¿qué es un ratón?, en términos de informática. Pues bien, para ellos diré que se trataba de un artilugio que permitía mover un puntero por la pantalla y seleccionar o pulsar opciones.

Este, al principio modesto juego, adquirió allá por el 2000 la categoría de tener al menos complejidad NP. Puedes consultar en internet si te interesa el tema, pero aquí baste decir que un problema NP es aquel en el que, al incrementar la cantidad de variables de entrada, el tiempo de resolución de dicho problema tratado con el mejor algoritmo conocido, crece de forma No Polinómica (puedes pensar en un crecimiento exponencial, por ejemplo). La persona que le dio ese estatus fue Richard W. Kaye, pero no sólo hizo eso, sino que demostró que también podía emular a una computadora clásica, porque con él podemos construir una máquina de Turing completa (en el enlace está el paper).

Yo quiero ir un poco más allá, porque estoy convencido de que además con él podemos construir una máquina de Turing cuántica, es decir, una computadora cuántica, y ese es el objeto del presente libro, junto con el deseo de acercar la computación cuántica a los profanos, y en especial a los niños. Porque, del mismo modo que en la informática clásica, un programador no necesita ser ingeniero electrónico y conocer todos los entresijos y funcionamiento de los chips que integran su computadora para crear programas (software) que se ejecuten en ella, un programador cuántico no necesita saber física cuántica para construir software cuántico. Por poner un ejemplo más cercano: un conductor puede cambiar de modelo de coche sin que ello le ocasione un gran trastorno y sin tener nociones de mecánica ni de cómo funciona un motor de explosión, o la transmisión y la caja de cambios de su coche.

Como éste libro no está escrito para físicos, sino para programadores, las explicaciones y demostraciones irán al final. Así que vamos a empezar explicando someramente las reglas del buscaminas, aunque recomiendo encarecidamente que la mejor manera de aprenderlas es jugar algunas partidas en dicho juego. Los que ya conozcan el juego pueden saltarse éste párrafo.

Reglas del buscaminas:

El juego nos presenta un tablero cuadriculado en celdas que contienen un determinado número de minas ocultas que se nos indica en un contador. Disponemos de banderolas señalizadoras que podemos colocar en las casillas en las que sospechemos o tengamos la certeza de que ocultan una mina y al hacerlo el contador resulta afectado. En cada casilla oculta, no puede haber más de una mina o hueco.

Iniciamos el juego “pisando” (haciendo clickclic) sobre alguno de los cuadros aún ocultos. El cuadro se abre y muestra su contenido. El contenido puede ser, bien una mina, con lo que estallarán todas las demás del tablero mostrando sus posiciones y acabándose la partida, o bien una No Mina o hueco. En el caso de que no haya mina. El cuadro mostrará un contenido numérico que indica CON TODA FIDELIDAD el número de minas que lo rodean. Se omiten las casillas cuyo contenido sería un cero para más claridad del juego y éstas se dejan en blanco, pero descubiertas. El juego consiste en ir descubriendo casillas sin que llegue a explotar ninguna mina con la ayuda de la información que nos muestran las casillas descubiertas y que SIEMPRE TIENE QUE SER CONGRUENTE, junto con la información del marcador que nos indica el número de casillas que aún no están señalizadas con una banderola. (fin del párrafo.).

Hemos finalizado la explicación de las reglas del juego con una palabra que he resaltado en mayúsculas y negrita porque es fundamental y que voy a explicar a continuación. ¿Es un determinado tablero congruente, o no lo es? Para entendernos mejor vamos a definir primero el término. Un tablero será congruente si existe una distribución de minas ocultas tal que los números que hay en las celdas descubiertas sean correctos; será incongruente o inconsistente en caso contrario. La figura 1 muestra un ejemplo de configuración incongruente o inconsistente.            

Figura 1.

Dejo al lector la tarea de averiguar por qué no es congruente. Como pista decir que es imposible que los números de la esquina superior derecha sean 1 y 3. Valores congruentes serían 2 y 4 ó 0 y 2.

Aprovecho este punto para castigar al lector apuntando que la propiedad de NP-Completitud del buscaminas se refiere al diagnóstico de CONGRUENCIA o NO de una posición arbitrariamente grande y compleja del buscaminas. Cuanto mayor sea el tablero y la cantidad de casillas en él, la dificultad de emitir un veredicto de congruencia o no, crece de forma exponencial.

Hecho este inciso, recomiendo encarecidamente al lector que quiera proseguir y avanzar que se instale la herramienta de diseño y evaluación de posiciones de buscaminas que Pedro Gimeno Fortea nos cede gentilmente y que puedes encontrar en su página web:

Diseñador de Buscaminas (124.973 bytes),

en castellano:

http://www.formauri.es/personal/pgimeno/compurec/Buscaminas.php#Fig_1,

y también en inglés:

http://www.formauri.es/personal/pgimeno/compurec/Minesweeper.php. 

Muchísimas gracias desde aquí puesto que ha sido para mí de una inestimable ayuda.

Sin más preámbulos vamos a hacer un repaso de lo que Richard W. Kaye publicó en su día, pero cambiando algunas de sus configuraciones por otras mucho más sencillas e intuitivas. 

Richard W. Kaye, para demostrar la NP-Completitud del buscaminas se apoyó en la demostración de que, con ese juego se pueden construir todas las configuraciones necesarias para equipararlo al problema SAT que también es NP-Completo (como siempre te remito a internet si quieres más información) (También en castellano…)

Con ello consiguió demostrar que, AL MENOS, el juego del buscaminas tiene una complejidad NP. Cuando digo al menos quiero decir, como mínimo, puesto que de hecho, tiene una complejidad mucho mayor: https://arxiv.org/pdf/1204.4659.pdf. 

Baste decir aquí que el problema SAT, o problema de satisfacibilidad booleana, trata de saber si, dada una expresión booleana con variables y sin cuantificadores, hay alguna asignación de valores para sus variables que hace que la expresión sea verdadera.

Esto, dicho así, suena bastante feo, pero en realidad se trata del mismo concepto de congruencia explicado antes, pero ahora referido a circuitos lógico/booleanos.

Así que no nos queda más remedio que introducir un poco de álgebra de Boole aplicada al buscaminas. 

Ya he mencionado antes que Kaye publicó un “paper” en el que demostraba que se podían construir configuraciones del buscaminas de Windows que emulasen los circuitos lógicos, por no que no voy a entrar en demostraciones ya realizadas, únicamente un repaso de las principales configuraciones.

Empezaremos por la configuración más sencilla: el conductor y sus variantes para doblar esquinas, cruces sin contacto, cambio de fase (o cambio de pie si te es más fácil), pozos de potencial etc…

Por convenio, el sentido de la “corriente” lógica, vendrá dado por la CONGRUENCIA y si no se contradice ésta de izquierda a derecha y de arriba abajo, aunque puede ser a la inversa. En general podemos elegir el sentido que más nos convenga porque en computación cuántica todos sus componentes son reversibles y el sentido de la corriente lógica es muy distinto al sentido de la computación ordinaria, como intentaré explicar más adelante.