La descomposición booleana

Classical and Quantum Logic Gates:

An Introduction to Quantum Computing

1.1. Descomposición booleana

1.1.1. Explique en qué consiste la descomposición booleana y porque el número de compuertas NAND requeridas para simular una función con n entradas, se escalaría exponencial en n.

La descomposición booleana se enfoca en descomponer funciones booleanas arbitrarias utilizando solo compuertas AND, OR Y NOT que son conocidas como compuertas universales para la lógica booleana clásica. Como una simplificación adicional, estas tres puertas se pueden reducir a una sola puerta, la puerta NAND, la cual es significativa debido a que cualquier función booleana se puede implementar mediante el uso de una combinación de puertas NAND. Esta propiedad se llama integridad funcional.

El procedimiento para descomponer una función booleana en puertas de dos bits, es ineficiente. Es decir, el número de compuertas NAND necesarias para simular una función con n entradas de esta manera escalaría exponencialmente en n. Esto es esencialmente porque una función booleana nbit tiene 2n líneas en su tabla de verdad.

1.2. Reversibilidad de la computación

1.2.1. Explique en qué consiste la reversibilidad lógica.

La Computación Reversible se ocupa de poder obtener, a partir de un resultado, los valores que lo originaron (una función uno a uno). La reversibilidad lógica inherente en el modelo reversible implica que una implementación de tal máquina también sería físicamente reversible. Las operaciones AND, NAND, OR, XOR son IRREVERSIBLES: A partir de la salida no se puede reconstruir la entrada

1.2.2. Consulte y explique la relación entre la entropía de un sistema de cómputo y la reversibilidad de la computación (en su informe de lectura indique la bibliografía utilizada).

La reversibilidad lógica hace referencia a la capacidad de reconstruir la entrada de la salida de un cálculo o función de compuerta. Por ejemplo, la puerta NAND es explícitamente irreversible, teniendo dos entradas en una salida, mientras que la puerta NOT es reversible (es su propia inversa). La conexión a la reversibilidad física generalmente se realiza de la siguiente manera. Dado que la compuerta NAND solo tiene una salida, una de sus entradas se ha borrado efectivamente en el proceso, cuya información se ha perdido irremediablemente.

El cambio en la entropía que asociaríamos con la pérdida de un bit de información es ln 2, que, termodinámicamente, corresponde a un aumento de energía de kT ln 2, aquí k es la constante de Boltzman y T es la temperatura. El calor disipado durante un proceso generalmente se toma como un signo de irreversibilidad física, de que el estado físico microscópico del sistema no se puede restaurar exactamente como estaba antes de que se llevara a cabo el proceso.

Se dice que un proceso es físicamente reversible si no produce un incremento de entropía, siendo por tanto isoentrópico (es aquel en el que la entropía del sistema permanece constante). Probablemente la mayor motivación para el estudio de tecnologías enfocadas a la implementación de una computación reversible es que ofrecen la que se considera única forma potencial de mejorar el rendimiento energético computacional más allá del límite impuesto por el principio de Landauer2​ que establece el mínimo aumento de entropía posible en una operación de bit no reversible. Aunque el límite de Landauer estaba millones de veces por debajo del consumo de las computadoras en los años 2000, y miles de veces en los años 2010, los partidarios de la computación reversible argumentan que la diferencia es atribuible en gran parte a efectos acumulados de la arquitectura que magnifican el impacto del límite de Landauer en los diseños prácticos de circuitos, de manera que puede ser difícil para la tecnología práctica el progreso hacia mayores niveles de eficiencia energética sin recurrir a los principios de la computación reversible.

Tal como argumentó por primera vez Rolf Landauer de IBM, para que un proceso computacional sea físicamente reversible también debe ser lógicamente reversible. El principio de Landauer es la observación rigurosamente válida de que el borrado de n bits de información conocida debe incurrir siempre en un coste de nkT ln 2 en entropía termodinámica. Se dice que un proceso computacional discreto y determinista es lógicamente reversible si la función de transición que conecta los estados computacionales viejos con los nuevos es una función inyectiva, esto es, los estados lógicos de salida determinan de forma única los estados lógicos de entrada de la operación computacional.

1.2.3. Explique la afirmación: “Reversible logic gates are symmetric with respect to the number of inputs and outputs”.

Dado que las puertas lógicas reversibles son simétricas con respecto al número de entradas y salidas, podemos representarlas de manera distinta a la tabla de verdad, que enfatiza esta simetría, vale aclarar que en estas compuertas no existe la pérdida de información.

i. Qué representación enfatiza esta simetría? Presente un ejemplo.

Podemos mostrar la compuerta reversible NOT, cuya tabla de verdad se muestra a continuación. También podríamos escribir esto en forma de matriz, o como un gráfico.

[pic 2]

La representación gráfica a la derecha es una representación comprimida de la compuerta NOT. La línea horizontal representa un bit, cuyo valor variable inicial es a1 y se muestra a la izquierda; el valor final es NOT a1 y se muestra a la derecha. El funcionamiento de la compuerta NOT en el medio está simbolizado por el signo mostrado.

1.2.4.Explique la afirmación “It turns out that classical reversible logic differs in one significant respect from classical irreversible logic in that two-bit gates are not sufficient for universal reversible computation”.

i. Use como ejemplo la tabla de verdad mostrada en la expresión (10).

Las compuertas de dos bits no son suficientes para la lógica booleana reversible debido a que no es posible conocer las entradas con tener solo la salida, para esto es necesario introducir un tercer bit. Vale aclarar que la compuerta NAND no cumple esta afirmación, debido a que cuando se lleva uno de los bits de entrada a la salida y se genera la NAND entre las dos entradas y posteriormente se lleva a la salida, no es posible conocer las entradas con total certeza teniendo solo las 2 salidas, la siguiente tabla de verdad confirma que esta compuerta sigue siendo irreversible.

...