Computación cuántica para niños (sin fórmulas)
Este blog está reservado para la futura construcción del tema del
título, mientras tanto puedes visitar otras páginas del mismo autor como
por ejemplo:
Antigravedad para niños (sin fórmulas)
En construcción...............
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.
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.
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.
El hilo conductor:
Figura 2.
Para que se conserve la congruencia, en cada pareja de celdas ocultas, sólo puede existir una única mina. Y además éstas deben estar separadas por 3 casillas una de otra. Lo mismo en lo que se refiere a los huecos.
Aceptado el convenio anterior, diremos que la configuración de la figura 3 transporta un uno hacia la derecha, porque la mina se halla en la posición adelantada derecha de cada pareja de casillas ocultas. Cómo es lógico, en el sentido opuesto el conductor transporta un cero.
Quiero aprovechar este punto para insistir en una diferencia fundamental, poco resaltada a mi modo de ver, en la bibliografía consultada, entre el álgebra de Boole clásica y la que nos proporciona el buscaminas y que nos permitirá, espero, construir algoritmos de computación cuántica: LA REVERSIBILIDAD.
En efecto, el álgebra de Boole sólo permite la circulación en un sentido, y en general prohíbe el sentido contrario excepción del conductor y la puerta NOT.
La REVERSIBILIDAD es una
propiedad fundamental de las computadoras cuánticas que las diferencia (junto
con otras propiedades que veremos más adelante: – la
superposición, la acción instantánea a distancia y el entrelazamiento o enredo,
“entanglement”–), de las computadoras clásicas, así
que me permitiréis que insista en lo fundamental de este concepto y para hacer
la distinción, aunque usaré los mismos símbolos que usa el álgebra de Boole en
mis ejemplos, introduciré una Q (de cuántica, en inglés quantum) en su interior
para que se distingan de las NO REVERSIBLES cotidianas que usa el álgebra de
Boole.
Un
conjunto de elementos son necesarios para unir las diferentes partes del
circuito y son los siguientes:
Todos los elementos de la figura 4, junto con las puertas lógicas que mostraré a continuación son necesarios y SUFICIENTES para que el buscaminas de Windows emule cualquier configuración que se pueda construir con circuitos lógicos. Para ello, teniendo ya los elementos complementarios necesarios para unir las puertas lógicas, únicamente nos falta un CONJUNTO DE PUERTAS LÓGICAS COMPLETO:
Conjunto de puertas lógicas completo:
Según se define, un conjunto de puertas lógicas completo (luego veremos el conjunto de puertas lógicas CUANTICAS completo) en el álgebra de Boole está constituido por las puertas NOT y NAND.
Para aquellos que desconozcan el álgebra de Boole, decir que los números bajo las letras se corresponden con los valores de entrada, la raya horizontal sobre la letra indica negación NOT o inversión del valor. El símbolo v invertida es la AND o Y exclusiva, significa que la salida únicamente será 1 cuando A y B lo sean. La v es la OR u O inclusiva, la salida será 1 (o verdadera) cuando lo sea al menos una de las dos entradas y únicamente será 0 (o falsa) cuando ambas entradas sean cero.
Así pues, basta con presentar las puertas NOT y NAND implementadas en el buscaminas, para tener un emulador COMPLETO de circuitos lógicos clásicos para el buscaminas. Vamos a ello:
No obstante lo anterior, se suele usar un conjunto más amplio de puertas lógicas para facilitar la construcción de circuitos. A continuación presentaré algunas de ellas, pero antes una puerta lógica que se evidenciará como FUNDAMENTAL en computación cuántica y que tampoco es trivial en la clásica, la puerta XOR u O exclusiva o excluyente. Esta puerta pone un uno (o valor verdadero) en la salida únicamente cuando las entradas son distintas y un cero en caso contrario. A continuación su símbolo y su tabla de verdad:
Y su correspondiente en el buscaminas:
Aquí podemos ver que en función del número 6 central, debe cumplirse la siguiente ecuación:
En consecuencia, por la segunda conclusión, si x=1 y a ó b son 1, c tiene que ser necesariamente cero y su inverso 1.
Y por la primera, si x=0, entonces c necesariamente tiene que ser 1 y su inverso 0. En definitiva,a=b implica c=1; a distinto de b implica c=0.
Puedes comprobar que esta solución se corresponde con la tabla de verdad de la compuerta lógica XOR.
Cómo ya he adelantado antes, sería muy mezquino por mi parte dejarlo aquí, así que voy a presentar algunas puertas auxiliares más que se utilizan en álgebra de Boole para simplificar los circuitos.
Primero los símbolos booleanos con sus tablas de verdad y a continuación sus equivalentes en el buscaminas.
Las puertas NOT y XOR ya las he presentado en las figuras 5 y 6-7 respectivamente.
El lector ya se habrá percatado de que la puerta de la figura 7, en realidad no es una puerta XOR, porque, o bien las entradas, o bien la salida, no se corresponden con la tabla de verdad. En realidad se trata de una puerta NXOR, y para convertirla en XOR únicamente hay que, o bien negar las dos entradas o bien negar la salida.
La puerta AND es una pequeña variación de la NAND vista con anterioridad en la que se invierte la salida:
Y las puerta AND, OR, XOR juntas para que puedas compararlas:
Si te fijas, la compuerta OR únicamente niega todos los conductores de la puerta AND. Hay un inversor en cada uno de ellos.
La puerta OR equivale a una suma sin arrastre y se suele representar por el signo de la suma rodeado por un círculo. Similarmente, la puerta AND equivale al producto lógico y se representa por el aspa del producto rodeada por un círculo.
Con éstos elementos ya podríamos construir una computadora clásica con el buscaminas de Windows. (Véase el artículo Infinite versions of minesweeper are Turing complete).
Pero lo que a nosotros nos interesa es programar una computadora cuántica, en consecuencia, lo que precisamos es una Máquina de Turing Cuántica, es decir: un juego de conectores cuántico y un juego de puertas cuánticas completo.
No voy a entrar en la teoría de la Máquina de Turing. Para el que esté interesado, al final dejo los enlaces de una página en donde se explica y en la que además existe un simulador para practicar.
Únicamente decir que una máquina de Turing Cuántica funcionará de forma similar a la máquina de Turing ordinaria pero en la que los bits han sido substituidos por QBits.
Recapitulemos. Un ordenador convencional, no es sino una máquina de Turing muy compleja que maneja bits. El bit es la unidad fundamental de información que puede tener uno de los dos valores 0 y 1, V ó F etc. Generalmente se asocia 0=F(also) y 1=V(erdadero).
La máquina de Turing consiste en un cabezal que puede desplazarse lateralmente o quedarse quieto, una cinta conteniendo celdas ordinalmente numeradas de izquierda a derecha (o al revés según se convenga), y un alfabeto de instrucciones que deben ser seguidas por el cabezal. La máquina de Turing “computa” (opera) desde el estado inicial hasta que: o bien entra en un bucle sin final o bien finaliza en un estado determinado que será el resultado de la computación.
Como dije anteriormente, y si no lo digo ahora, utilizaré los símbolos del álgebra de Boole con una Q en su interior para significar que son puertas cuánticas, además y por su propiedad de REVERSIBILIDAD, la cantidad de entradas debe ser igual a la de salidas. Ello viene dado sin mayor complicación en el hilo conductor y en las puertas sencillas de las cuales el álgebra de Boole dispone únicamente de la NOT.
No así en
las que tienen más de una entrada y una única salida. Por poner un ejemplo
veamos cómo quedaría la puerta C-Not, éesta
es una puerta de dos conductores en la que por convenio el superior es el QBit
de control y el inferior varía en función del contenido del de control.
Así, en éste caso, C-Not cambia el QBit
inferior únicamente si el de control está a 1. Pongo a continuación el esquema
y la tabla de verdad:
Como veis, se ha tenido que añadir un conductor X para que el número de salidas sea igual al de entradas.
El valor del bit de control en x no se ve alterado, mientras que y queda modificado en función del valor de x. Eso es lo que significa la operación indicada por el círculo que circunscribe el signo de la suma.
Figura 12.
Ya
sé que hablaba de presentar la puerta C-Not, pero en
realidad es la misma que la puerta qXOR.
Si os fijáis, el valor X no varía y el y pasa a ser f(x), en este caso: y NOT y,
si x=1.
A continuación algunas puertas más que necesitaremos para mejor comprensión y simplicidad implementadas con el buscaminas.
La puerta Swap:
Esta es una variante del cruce sin contacto cuya función es permutar los valores del conductor superior e inferior. Pero con una sutil diferencia, mientras que en el cruce sin contacto la información no se “mezcla” en esta configuración, en su parte central, la información se entremezcla. Esto lo veremos más adelante cuando hablemos del “entanglement”.
Otra variante de la puerta NOT:
Por el momento será suficiente. Si precisara de alguna más, las introduciré a medida que se requiera.
Antes de entrar en la computación cuántica con el buscaminas, no me queda más remedio que introducir algunos conceptos relativos al tema, por lo que el próximo capítulo está dedicado a la computación cuántica.
Considero que es conveniente leérselo aunque sea únicamente de pasada y volver a repasarlo si en los posteriores capítulos se encontrase el lector con la necesidad de hacerlo. Éste capítulo es algo complejo porque incide en los fundamentos de la computación cuántica y sus principales diferencias con la clásica. El lector puede arriesgarse a saltárselo, pero la comprensión de los siguientes capítulos puede hacerse mucho más complicada.
Computación cuántica.
Ya adelanté que una computadora cuántica, no es sino una máquina de Turing cuántica. De hecho, podría ser una máquina de Turing clásica con registros y operadores cuánticos, es decir una combinación de computador convencional con registros y operadores cuánticos. Una parte de las operaciones podría realizarse convencionalmente y aquellos algoritmos que precisen la potencia de la mecánica cuántica se realizarían en la parte cuántica de la computadora.
Para los que quieran profundizar en la mecánica cuántica (base y fundamento de la computación cuántica), recomiendo esta página:
Cuántica sin fórmulas - El Tamiz:
https://eltamiz.com/cuantica-sin-formulas/En la que se explica con mucha mayor precisión, claridad y sencillez de lo que podría hacerlo yo.
Por ello, voy a pasar por alto la mecánica cuántica en lo que no sea imprescindible para entender la computación cuántica.
El sistema físico.
A finales del siglo XIX, se había llegado al convencimiento de que la física estaba agotada. De que ya no quedaba sino perfeccionar los instrumentos de medida lo suficiente como para que, conociendo TODAS las variables de un sistema, pudiéramos conocer con total certeza su evolución futura. Esto fue así hasta que una serie de experimentos pusieron en evidencia que era imposible, por muy perfectos que fueran los instrumentos de medida, llegar a conocer TODAS las variables de un sistema físico dado. De hecho, el mero proceso de medir, alteraba el resultado de la medición y el estado mismo del sistema físico medido.
Los autoestados (eigenstates).
Un sistema físico cualquiera, por ejemplo el gato de Schrödinger, se describe en física por ⎢𝜓〉, este símbolo equivale TOTALMENTE al sistema que describe. En el caso del gato equivaldría a, no sólo todas las moléculas del animal, sino también a su disposición, localización, velocidad etc...
Así pues ⎢𝜓〉 describe si el gato está comiendo, jugando, corriendo, o cualquier otro estado que se nos ocurra. Incluso estados combinados: bañándose y comiendo, corriendo y saltando etc…
Sin embargo, hay dos estados de éste sistema, singulares y aparentemente incompatibles, a los que los físicos llaman autoestados (eigenstates): vivo y muerto.
La lógica nos dice que un gato no puede estar vivo y muerto a la vez, aunque pueda comer y bañarse, saltar y jugar etc… Los estados vivo y muerto parecen incompatibles.
Sin embargo, la física nos dice que ello sí es posible… Siempre y cuando NO observemos su estado (hagamos una medición del sistema), porque si lo observamos nos revelará que se halla en uno de los dos autoestados y eso se convertirá entonces en cierto y definitivo y dejará de estar en ambos estados a la vez.
En efecto, un gato puede estar vivo y muerto simultáneamente. Véase el Gato de Schrödinger:
https://es.wikipedia.org/wiki/Gato_de_Schr%C3%B6dingerY el significado físico no es que el gato se halle previamente en uno de los dos estados que nosotros desconozcamos hasta que realicemos la observación, y que únicamente se deba a nuestra ignorancia el que se nos muestre en un estado de superposición vivo/muerto. Los experimentos y la teoría demuestran que REALMENTE se halla vivo y muerto simultáneamente hasta que lo observemos.
Esto parece extremadamente paradójico, ¡pero así es la mecánica cuántica! Y es otra de las propiedades que hace que la computadora cuántica supere a la convencional. La superposición de estados.
Dejemos de momento la superposición y volvamos al título de este capítulo: los autoestados (eigenstates).
Como decía, un sistema físico cualquiera y en particular una partícula cuántica: fotón, electrón, molécula… incluso un gato. Puede tener una infinidad de estados pero…. No podemos conocer exactamente todas las propiedades de un sistema físico simultáneamente. Si ello fuera posible, en un único electrón podríamos almacenar una inmensa cantidad de información dado que puede hallarse en una infinidad de estados. Se podría asignar un valor numérico a cada uno de ellos y almacenar y recuperar la información en cualquier momento. Un único electrón podría almacenar toda la información que puede almacenar cualquier computadora actual.
Por desgracia, aunque podemos manipular una partícula cuántica según unas reglas muy precisas, más bien exactas, descritas por una ecuación: la ecuación de Schrödinger. No podemos leer con precisión, y ello no es debido a que los instrumentos no sean suficientemente precisos, sino porque lo prohíbe la física. No podemos leer con precisión el estado de una partícula cuántica.
La ecuación de Schrödinger describe EXACTAMENTE cómo evolucionará un sistema cuántico en función de las operaciones que realicemos sobre él. Si arrojamos una pelota al gato, aunque no lo veamos, la ecuación nos dice que el gato, si está vivo jugará con ella. Si le damos comida y está vivo se la comerá, pero si la comida esta envenenada y el gato estaba muerto, su estado NO cambiará, no estará más muerto. Si le aplicamos una poción resucitadora y estaba vivo no estará más vivo de lo que ya estaba, etc…
Podemos aplicar operaciones sobre un sistema cuántico y predecir exactamente cómo evolucionará… pero no podemos OBSERVAR estados intermedios. Cuando observemos el sistema, éste arrojará un único valor entre los dos autoestados: vivo/muerto, con una probabilidad determinada predicha por la ecuación mencionada.
La computación cuántica manipula sistemas físicos de dos autoestados incompatibles con el fin de que la probabilidad de que el estado final que arroje la observación sea próxima al 100% del autoestado que nos indique una entre dos posibilidades de una proposición computada.
Por ejemplo. Queremos saber si un número es par o impar. El número en cuestión es la entrada de la computación y el algoritmo de computación computará de forma que la probabilidad de que el resultado arroje un cero sea del 100% si el número fuera par y uno si fuera impar.
Es decir, aunque no veamos al gato, podemos saber que si le arrojamos una pelota jugará con ella si está vivo o no le hará caso si está muerto, aunque existen infinidad de otras posibilidades: si está comiendo una comida apetitosa no jugará, si le damos apio para comer no lo comerá y jugará…
Todas las reacciones del sistema están EXACTAMENTE descritas por la ecuación de Schrödinger y aunque no lo veamos, sabemos exactamente su evolución en función de las operaciones que le apliquemos. Esta es la base de la computación cuántica.
El qBit.
El equivalente del bit en la computación cuántica es el QBit, o mejor qBit, pero a diferencia del primero que únicamente puede almacenar uno de entre dos valores: 0 ó 1, V/F, Si/No, 0v., 5v. etc… Un qBit puede no sólo hallarse en una infinidad de estados, sino que además puede hallarse en un estado de superposición y no sólo eso, sino que además asociado a otros qBits puede el conjunto hallarse en un estado que se dice enredado o “entangled”.
Dejaremos para más adelante la combinación de qBits y el estado entangled, y nos centraremos de momento en qBits individuales.
La esfera de Bloch.
Para poder “visualizar” el comportamiento del qBit se utiliza una representación tridimensional conocida como la esfera de Bloch. Se trata de un vector normalizado (es decir de longitud constante = 1) que evoluciona en un espacio tridimensional, con lo que el origen del vector se halla siempre en el centro de una esfera de radio 1 y su extremo recorre toda su superficie. Cada uno de los infinitos puntos de la superficie de la esfera representa un estado posible del sistema, una infinita cantidad de estados en definitiva.
Un
sistema de coordenadas auxiliar x, y, z
se usa para medir los desplazamientos angulares relativos del vector.
Por convenio +z apunta arriba o norte, -z al sur, +x hacia nosotros y –x hacia
el lado opuesto, es decir hacia el fondo, +y apunta a la derecha y –y a la
izquierda. Otro convenio es el siguiente: ⎪+z〉=⎪0〉, ⎪-z〉=⎪1〉, ⎪+x〉=⎪+〉, ⎪-x〉=⎪-〉, ⎪+y〉=⎪i〉, ⎪-y〉=⎪-i〉
La i es del número imaginario:
Usando Java, puedes practicar en la esfera de Bloch en esta página:
http://eecs.ceas.uc.edu/~cahaymm/blochsphere/index.htmlSi no quieres instalar Java:
https://www.st-andrews.ac.uk/physics/quvis/simulations_html5/sims/bloch-timedev/bloch-timedev.htmlEsta es una modelización de un sistema físico limitado aunque infinito. En efecto, es limitado porque imponemos la normalización: el origen del vector se halla en un punto fijo u origen y su longitud es constante e igual a la unidad. Pero infinito como infinitos son los puntos de la superficie de una esfera de radio 1 a los que puede apuntar el vector.
Esta representación es totalmente válida para seguir visualmente la evolución de una partícula cuántica, a condición de que tengamos en consideración que el vector además de origen y extremo tiene caras laterales: delante/detrás, derecha/izquierda. Podemos visualizarlo por ejemplo pintando la flecha de color rojo en su mitad derecha y azul la izquierda, de modo que el vector además de trasladar su extremo por toda la superficie de la esfera, puede rotar sobre su propio eje cambiando de color.
Si los puntos de la superficie de la esfera son infinitos, considera además combinarlos con la rotación relativa del vector sobre su eje de hasta 360º. ¡Una única partícula cuántica podría almacenar una infinita cantidad de información!
En ésta descripción de la esfera de Bloch, existen dos puntos singulares: Norte y Sur, que se hacen corresponder con los autoestados reales de una partícula cuántica.
En efecto, podemos actuar sobre una partícula cuántica para llevarla a uno de sus dos autoestados, lo cual se puede hacer corresponder con una de las dos posiciones singulares de la esfera de Bloch… ¡Pero la información es incompleta! En efecto, aunque el sistema se halle en un autoestado, por ejemplo ⎪0〉 (ket 0), no poseemos toda la información del sistema físico, porque lo prohíben las leyes de la física y ello se ve reflejado en la esfera de Bloch en el hecho de que, aunque por convenio el vector apunte al norte, es decir hacia arriba, y se halle superpuesto al eje de coordenadas z, ¡desconocemos el ángulo de rotación del vector sobre sí mismo! Es decir, tenemos la certeza de que al realizar la medida sobre él, obtendremos un 0, con una probabilidad del 100%, pero NO tenemos TODA la información del sistema.
Recapitulemos, recordemos que las unidades de proceso cuántico, a las que denominamos qBit, similarmente a la denominación de la unidad clásica: bit y añadiendo la q como prefijo, son muy diferentes de estos últimos, no sólo en la denominación: bit, qBit, y en la notación: bit:{0,1} qBit: ⎪𝜓〉 sino en las operaciones que podemos aplicarles respectivamente.
Decía que a diferencia del bit que puede tener uno de los dos estados 0,1, el qBit tiene, en general, el estado: ⎪𝜓〉 (se lee psi ket) (utilizamos la notación de Dirac que se lee: 〈bra⎪ket〉 ). Así el estado general de un sistema físico en general y de un qBit en particular será psi ket. Que, en el caso del qBit, puede ser 0, 1 ó una superposición de ambos.
Como hemos visto arriba, podemos “forzar” al qBit a tomar un estado definido: ket 0 ó ket 1, pero seguirá siendo un qBit, no un bit, porque aunque tengamos la certeza, al realizar la medida, de obtener el valor elegido, podemos operar con él cuánticamente, cosa que no podríamos realizar con un bit, porque el qBit puede evolucionar, por ejemplo, a un estado de superposición, y el bit no.
Posiblemente haya confundido al lector más que aclarado, sin embargo tengo que decir que si lo que le interesa es la mecánica cuántica, ha elegido mal el blog. En éste blog pretendemos programar una computadora cuántica sin, necesariamente, saber física cuántica.
Ya tenemos la unidad básica para la computación cuántica: el qBit, y hemos mostrado una de las posibles formas de definir su estado inicial para que una eventual medida arroje un 0 ó un
Veamos cómo representarlo en el buscaminas:
Así que esa propiedad de la mecánica cuántica que impide conocer totalmente el estado de un sistema físico lo implemento en el buscaminas usando el tercer conductor, el que se halla en la parte inferior, junto con el hecho de que aunque sepamos que los dos interrogantes tienen idéntico contenido, desconocemos cuál es ese contenido.
Convendremos en que los tres conductores superpuestos representan los tres ejes de la esfera de Bloch. El superior al eje x, el central al y, y el inferior al z.
Utilizaremos el siguiente convenio: Establecido el sentido temporal por congruencia y/o en ausencia de ésta última, entenderemos que el sentido de circulación (léase evolución temporal) será de izquierda a derecha. En cada bloque de 6 cuadrados ocultos, la información correspondiente al autoestado que se nos permite medir, estará contenida en los dos cuadros superiores de la derecha, en la figura 15 señalados con interrogante. Quedando reservada la información no local a los dos cuadros inferiores. Y al contenido oculto, aunque idéntico en este caso, de las casillas marcadas con interrogante.
La medida podemos realizarla del siguiente modo: si ambos interrogantes tienen el mismo contenido diremos, como en el caso superior, que hemos medido un 0 (ket 0 |0> ) y viceversa (ket 1: |1> fig.: 16).
Como vemos, aunque conocemos el autoestado de cada uno de estos dos qBits: ket 0 y ket 1 respectivamente, desconocemos la información total del sistema: no sabemos si los interrogantes contienen mina o hueco y tampoco conocemos los valores del tercer conductor, la información no local, debemos entender que la ignoramos porque ésta se define en el futuro, NO en el presente.
Repito, hemos elegido usar tres conductores superpuestos para poder emular la esfera de Bloch y los nombraremos, para mejor comprensión y afinidad con ella con las letras de los ejes cartesianos: x, y y z.
Convendremos, en ausencia de imposición en contra y si la congruencia no se opone a ello, que el conductor superior será x, el central y y el inferior z.
Ahora ya estamos preparados para introducir los complementos que necesitaremos para, junto con las puertas cuánticas que construiremos posteriormente, completar, espero, una computadora cuántica con el buscaminas.
El hilo conductor y otros accesorios.
Empecemos pues por el conductor de buscaminas cuántico:
El lector puede ver en la figura 21, además de los extremos indefinidos, los bloques de 6 cuadrados que representan los tres ejes cartesianos, un cambio de fase, un inversor de los tres ejes y un elemento para las esquinas. Además de un duplicador de un hilo.
El resto no es necesario mostrarlo puesto que se puede construir con los elementos de un único conductor vistos con anterioridad, aunque a lo largo del libro iré poniendo algunos ejemplos más.
Llegados a este punto tengo que volver a la computación cuántica formal para, una vez explicada, construir los elementos del buscaminas que los emulen.
Así que ha llegado el momento de introducir un poco de la simbología de computación cuántica adoptada por consenso:
Puertas cuánticas de un QBit.
Puerta cuántica unitaria Universal:
Figura 22.
Ésta es una puerta que modifica el estado de un único qBit haciendo que su estado cambie (evolucione) de ⎪𝜓〉 a ⎪U⨂𝜓〉. Es decir, el estado inicial evolucionará al estado final compuesto en función de la operación que U aplique sobre psi.
Para aclarar un poco, diré que la puerta unitaria más sencilla es el inversor o NOT que tiene las siguientes representaciones:
Y que opera del siguiente modo: f(⎪0〉)→⎪1〉 y ⎪1〉 ⨁ X→⎪0〉
He puesto las dos notaciones porque ambas se utilizan.
Lo que hace es cambiar la probabilidad de que al medir obtengamos 0 ó 1. La probabilidad respectiva viene definida por alfa y beta del tercer ejemplo de la figura 23.
Para implementarla en el buscaminas utilizaremos 3 conductores como sigue:
Ambas configuraciones, son equivalentes porque ambas producen la inversión del autoestado con lo que la medida u observación arrojará el valor inverso. No obstante, la de la izquierda es inversa de la de la derecha, lo cual viene indicado por la cruz como exponente.
Aclarar que la raya encima de ket psi significa el inverso, NOT o negación.
¿Cómo opera esta puerta sobre los tres conductores?:
─ Los conductores superiores, x e y son los que definen la inversión del ket. ─ La información de z cambia solidaria con el y.
La puerta NOT cambia ket 0 a ket 1 y viceversa y ket i a ket –i. En resumen, la puerta X o NOT es una puerta cuántica unitaria inversora que aplica una rotación de 180º en la esfera de Bloch alrededor del eje Z.
Usando Java, puedes practicar en la esfera de Bloch en esta página:
http://eecs.ceas.uc.edu/~cahaymm/blochsphere/index.htmlTambién tienen una versión descargable para ejecutarla en local.
Existen infinitas puertas cuánticas unitarias, las cuales, junto con la puerta CNot que veremos más adelante constituyen un conjunto COMPLETO de puertas cuánticas. Es decir, si podemos hallar un conjunto finito y a ser posible reducido de puertas cuánticas unitarias con las que se podrá construir cualquier otra con la ayuda de CNot, tendremos un CONJUNTO UNIVERSAL COMPLETO DE PUERTAS CUÁNTICAS, y junto con los elementos accesorios, ya dispondremos de un emulador de computadora cuántica.
Por ello vamos a hacer un repaso de las principales puertas cuánticas y de cómo operan y también a ser posible de su emulación con el buscaminas de Windows.
Si tienes curiosidad aquí puedes practicar con el mejor simulador cuántico que he encontrado hasta ahora en Algorithmic Assertions:
(http://algassert.com/quirk). Puedes arrastrar y pegar puertas cuánticas y observar el resultado en esferas de Bloch.
IBM tiene un emulador parecido pero bastante más farragoso, aunque la ventaja es que puedes enviar tu computación a una computadora real de 5 qBits. Eso sí, no puedes exceder ese tamaño de momento.
https://www.qiskit.org/ibmqx-user-guides/index.html.
Las puertas unitarias que operan rotaciones de 180º en los diferentes ejes de la esfera de Bloch, también reciben el nombre de puertas de Pauli (Pauli gates). La puerta , X o NOT, que opera una rotación de 180º alrededor del eje X ya la hemos descrito. Sigue la puerta identidad: I, que no realiza ninguna operación, o bien realiza un giro de múltiplos de 360º (2 pi en radianes), con lo que el resultado es el ¿mismo? (Cinturón o correa de Dirac).
http://www.scielo.sa.cr/pdf/rmta/v24n1/1409-2433-rmta-24-01-00045.pdf
http://www.wetsavannaanimals.net/wordpress/twist-and-wonder/
En efecto, una de las sorpresas que depara el buscaminas de Windows, es que resulta más eficaz a la hora de representar fenómenos físicos como el spin. Mucho mejor que la esfera de Bloch. Puesto que aunque la rotación de 360º conduce a una inversión de los observables. En realidad se precisan dos rotaciones completas para volver a un estado idéntico al inicial como ocurre con el spin, los cuaterniones y las matrices.
La aplicación sucesiva de dos puertas NOT (o de su inversa) conduce a la identidad, pero con un sutil matiz: necesitamos dos rotaciones completas para volver exactamente a la situación inicial, como con el cinturón o cinta de Dirac, la cinta de Moebius, la rotación del spin….
Veamos cómo queda el esquema con álgebra de Boole cuántica:
En álgebra de Boole, el circulito delante de la puerta XOR, la convierte en NXOR, es decir invierte el valor de la salida.
La
aplicación de qNOT, seguida de su inversa vuelve EXACTAMENTE al estado inicial. No es así cuando aplicamos sucesivamente dos qNot, hay que aplicar dos más para llegar al estado inicial.
En la figura 27 vemos que la primera puerta qXOR (qNXOR en la inversa), controla las inversiones de los tres conductores. Si los dos superiores son iguales, en la directa, invierte los dos inferiores y si son distintos el superior. A la inversa para la puerta inversa.
Las
puertas
realizan giros de 180º respecto de los ejes
señalados en el subíndice.
A continuación su representación esquemática en los diagramas:
No voy a poner el equivalente del buscaminas porque es muy similar a lo visto para la puerta NOT, véase las figuras 24 y 25. Sólo hay que aplicar inversores en el eje (conductor) Y ó Z según el caso, o equivalentemente en los otros dos hilos como hicimos para NOT.
La figura 29 muestra representaciones esquemáticas para la puerta Y.
La puerta de Pauli Z también recibe el nombre de desplazamiento de fase pi (180º = pi en radianes).
En la figura 30 un
cuadro con las principales puertas unitarias, su esquema, su denominación
especial y su matriz.
Figura 30.
Éste conjunto de puertas cuánticas unitarias de la figura 30, junto con la puerta CNOT que veremos más adelante, constituye un CONJUNTO UNIVERSAL COMPLETO DE PUERTAS CUÁNTICAS.
Conjunto Universal de Puertas Cuánticas.
https://es.wikipedia.org/wiki/Puerta_cu%C3%A1ntica#Puertas_cu%C3%A1nticas_universales
He añadido el hipervínculo de la Wikipedia en donde hallarás la definición.
“Un conjunto de puertas cuánticas universales es cualquier conjunto de puertas al cual puede ser reducida cualquier operación posible en un ordenador cuántico, es decir, cualquier otra operación unitaria puede ser expresada como una secuencia finita de puertas del conjunto.”
En resumen, si conseguimos tener un conjunto universal de puertas cuánticas con el buscaminas de Windows, ello unido a los accesorios necesarios para unirlas y realizar cruces sin contactos así como cambios de fase (adelantar alguna casilla), como ya se ha demostrado que el buscaminas de Windows es una máquina de Turing, habremos demostrado que el buscaminas de Windows es una computadora cuántica.
Pero ¿existe un conjunto de puertas cuánticas universal? Y de ser así, ¿puede éste conjunto emularse con el buscaminas? A estas alturas del libro, y cómo ya he dicho, únicamente puedo responder afirmativamente a la primera pregunta, quien sabe si también podré hacerlo con la segunda cuando lo acabe.
Conjunto Universal de Puertas Cuánticas:
https://en.wikipedia.org/wiki/Quantum_gate#Universal_quantum_gates
Lo siento pero éste enlace sólo está en inglés.
En
realidad, y cómo puedes verificar en los enlaces mostrados, el Conjunto
Universal de Puertas Cuánticas, puede reducirse al siguiente: CNOT, H y π/8.
Es decir: Control-NOT, Hadamard, y desplazamiento de fase ɸ = π/4
,
o lo que equivale a una rotación de 45º respecto de Z (también se la denomina
además de π/8,
T, es la última de la figura 30, en la matriz asociada puedes ver que aplica una
rotación
respecto de Z). Es decir, el desplazamiento de fase, sea cual sea su valor, no altera el valor del ket 0/1, es un desplazamiento horizontal alrededor del eje Z.
Éste
conjunto se suele ampliar con la puerta S, desplazamiento de fase de 90º o ɸ = π/2
,
a la que suele denominarse simplemente Phase.
Con lo que el CUPQ (Conjunto Universal de Puertas Cuánticas) nos quedaría como sigue: CNOT, H, S y T. Recuerda la relación T2=S, que nos permitiría eliminar la S de la lista.
Así pues, nuestro programa para construir un emulador de computadora cuántica con el buscaminas de Windows se reduce a, además de haber presentado los accesorios cuánticos necesarios para unir las puertas cuánticas, construir las cuatro (en realidad 3) configuraciones que constituyen el CUPQ.
Vamos a ver si somos capaces de conseguirlo.
Empecemos con las puertas descritas en la figura 30.
Pauli gates.
Identidad: I
Como ya dije, esta puerta opera rotaciones múltiplos de 360º, o lo que es lo mismo: inversiones de los tres ejes.
Figura 31.
En la figura 31 vemos que es necesario completar 2 rotaciones completas para recuperar la situación exacta inicial, aunque la identidad de los observables se produzca cada 360º (2 pi).
NOT:
Pauli Y:
En realidad, todas las compuertas de Pauli pueden obtenerse a partir de NOT, simplemente trasponiendo (swapeando) los conductores adecuados…
Ahora pasemos a describir otras puertas unitarias no menos importantes.
Raíz cuadrada de NOT (Square root of NOT gate (sqrt(NOT)). Y sus variantes respectivas correspondientes a las Pauli gates.
No, no me he fumado nada extraño. En computación cuántica no sólo es posible sino que además es una puerta muy útil como podrá comprobarse más adelante.
La puerta S, o Phase, ya la vimos en la figura 30. Es la raíz cuadrada de la puerta de Pauli Z y representa un giro de 90º respecto del eje Z.
Como se puede ver en la figura 34, a la raíz de NOT, también suele llamársela V y a la raíz de Y, h ó pseudo Hadamard.
Enlaces referenciados en el texto:
Introducción a la computación con QCL (Quantum Computation Language).
http://slideplayer.com/slide/417509
Conjunto de puertas lógicas completo:
https://es.wikipedia.org/wiki/Puerta_l%C3%B3gica#Conjunto_de_puertas_l%C3%B3gicas_completoPágina dedicada al Buscaminas como juego. Entre las descargas hay varios programas para jugar al Buscaminas, algunos de ellos con encasillados diferentes del estándar cuadriculado (hexagonal, por ejemplo):
http://www.minesweeper.info/Si la versión Java no sirviera, desde la página del siguiente enlace podremos jugar en línea con cualquier navegador, aunque de una forma un poco engorrosa: http://www.linc.or.jp/~hamano/game/minesweeper.html
Sobre los problemas NP y un premio de un millón de dólares
Página de Stanislav Busygin sobre los problemas NP-completos.
http://www.busygin.dp.ua/npc.html
Página en español sobre el problema SAT.
http://www.mor.itesm.mx/~jfrausto/Algoritmos/pagina_sat/Sat.htmHay varias páginas en inglés dedicadas a algoritmos de resolución del problema SAT. Esta es una de ellas:
http://www.cs.duke.edu/~mlittman/topics/sat.htmlPágina sobre los premios ofrecidos por el Instituto Matemático Clay. Contiene una definición formal del problema «P=NP?».
http://www.claymath.org/millennium/Máquina de Turing:
https://borrowbits.com/2013/03/maquinas-de-turing/Simulador quántico muy bueno:
http://algassert.com/quirkBibliografía:
El Buscaminas de Windows es una máquina de Turing completa.
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdfReferences: http://www.ams.org/mathscinet-getitem?mr=MR1918623
1.- A. Barenco, C. H. Bennett, R. Cleve et al., “Elementary gates for quantum computation,” Physical Review A, vol. 52, no. 5, pp. 3457–3467, 1995. View at Publisher · View at Google Scholar · View at Scopus
2.- M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2003. View at MathSciNet
3.- A. Galindo and M. A. Martin-Delgado, “Information and computation: classical and quantum aspects,” Reviews of Modern Physics, vol. 74, no. 2, pp. 347–423, 2002. View at Publisher · View at Google Scholar · View at MathSciNet
4.- V. V. Shende, I. L. Markov, and S. S. Bullock, “Minimal universal two-qubit controlled-NOT-based circuits,” Physical Review A, vol. 69, no. 6, 2004. View at Publisher · View at Google Scholar · View at Scopus
5.- G. Vidal and C. M. Dawson, “Universal quantum circuit for two-qubit transformations with three controlled-NOT gates,” Physical Review A, vol. 69, Article ID 010301, 2004. View at Publisher · View at Google Scholar
6.- N. D. Mermin, “From classical state swapping to quantum teleportation,” Physical Review A, vol. 65, no. 1, Article ID 012320, 2001. View at Google Scholar
7.- K. Fujii, “Exchange gate on the qudit space and Fock space,” Journal of Optics B, vol. 5, no. 6, pp. S613–S618, 2003. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
8.- C. M. Wilmott, “On swapping the states of two qudits,” International Journal of Quantum Information, vol. 9, no. 6, pp. 1511–1517, 2011. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
9.- C. Wilmott and P. Wild, “On a generalized quantum swap gate,” International Journal of Quantum Information, vol. 10, no. 3, Article ID 1250034, 18 pages, 2012. View at Publisher · View at Google Scholar
10.- G. Paz-Silva, S. Rebić, J. Twamley, and T. Duty, “Perfect mirror transport protocol with higher dimensional quantum chains,” Physical Review Letters, vol. 102, Article ID 020503, 2009. View at Google Scholar
11.- J. C. Garcia-Escartin and P. Chamorro-Posada, “A SWAP gate for qudits,” Quantum Information Processing, vol. 12, no. 12, pp. 3625–3631, 2013. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
12.- C. Wilmott and P. R. Wild, “Towards an optimal swap gate,” Quantum Information Processing, vol. 13, no. 6, pp. 1467–1482, 2014. View at Publisher · View at Google Scholar · View at MathSciNet
13.- L. Liang and C. Li, “Realization of quantum SWAP gate between flying and stationary qubits,” Physical Review A, vol. 72, Article ID 024303, 2005. View at Google Scholar
14.- X. Wang, “Continuous-variable and hybrid quantum gates,” Journal of Physics A: Mathematical and General, vol. 34, no. 44, pp. 9577–9584, 2001. View at Publisher · View at Google Scholar · View at MathSciNet
15.- G. Alber, A. Delgado, N. Gisin, and I. Jex, “Efficient bipartite quantum state purification in arbitrary dimensional Hilbert spaces,” Journal of Physics A, vol. 34, no. 42, pp. 8821–8833, 2001. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
16.- A. Muthukrishnan and C. R. Stroud Jr., “Quantum fast Fourier transform using multilevel atoms,” Journal of Modern Optics, vol. 49, no. 13, pp. 2115–2127, 2002. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at Scopus
Comentarios
Publicar un comentario