Complenitud NP del buscaminas (comparativa con el álgebra de boole).
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.
Comentarios
Publicar un comentario