La computación reversible es un modelo computacional que solo permite operaciones termodinámicamente reversibles. De acuerdo con el principio de Landauer, que establece que borrar un poco de información libera julios de calor, esto excluye las funciones de transición que no son uno a uno (por ejemplo, los operadores booleanos AND y OR). Es bien sabido que el cálculo cuántico es inherentemente reversible porque las operaciones permitidas en el cálculo cuántico están representadas por matrices unitarias.
Esta pregunta es sobre criptografía. Informalmente, la noción de "reversibilidad" parece anatema para los objetivos fundamentales de la criptografía, lo que sugiere la pregunta: "¿La criptografía tiene un costo termodinámico inherente?"
Creo que esta es una pregunta diferente a "¿Se puede hacer todo en cuanto?"
En sus notas de clase , el Dr. Preskill declara: "Hay una estrategia general para simular un cálculo irreversible en una computadora reversible. Cada puerta irreversible puede ser simulada por una puerta Toffoli fijando entradas e ignorando salidas. Acumulamos y guardamos toda la basura". 'bits de salida que son necesarios para invertir los pasos del cálculo ".
Esto sugiere que estas simulaciones cuánticas reversibles de operaciones irreversibles requieren una entrada, así como también algo de espacio "scratch". Luego, la operación genera salida junto con algunos bits de scratch "sucios". Todas las operaciones son reversibles con respecto a la salida más bits de basura, pero en algún momento, los bits de basura se "tiran" y no se consideran más.
Dado que la criptografía depende de la existencia de funciones unidireccionales de trampilla, una declaración alternativa de la pregunta podría ser: "¿Hay alguna función unidireccional de trampilla que pueda implementarse utilizando solo operaciones lógicas reversibles, sin espacio adicional de memoria virtual?" Si es así, ¿también es posible COMPUTAR una función unidireccional de trampilla arbitraria utilizando solo operaciones reversibles (y sin espacio de cero)?
Respuestas:
Como mencioné en mi comentario anterior, y como mencionas en la pregunta, cada cálculo puede hacerse reversible, y simplemente reteniendo los bits adicionales, no hay un costo termodinámico inherente.
Cada circuito generado mediante el uso de compuertas y ancillas Toffoli para reemplazar compuertas irreversibles se vuelve tan eficiente para revertir como para calcular, suponiendo que tenga acceso a todos los bits de salida. Claramente, este no es el caso de las funciones consideradas en criptografía, ya que se utilizan y descartan muchos accesorios. Es al mantener en secreto estos bits adicionales que hace que el cálculo sea difícil de revertir.
Sin embargo, al calcular la función de manera reversible, hacer una copia del subconjunto de bits correspondiente a la salida y luego invertir la función, el costo total de energía para calcular e invertir la función será cero, mientras que el único costo incurrido será hacer que copia de los bits de salida, que depende solo del número de bits de salida y no de la función que se está calculando. Esto es claramente lo mejor que puede hacer, ya que cuesta la misma energía que simplemente escribir la cadena de salida en un registro vacío.
Volviendo a su pregunta reformulada:
La respuesta es trivialmente no. Si aplica el inverso de cada puerta en orden inverso, calcula el inverso de la función. Suponiendo un modelo donde las compuertas actúan sobre un número fijo de qubits a la vez, entonces el inverso de cada compuerta reversible elemental se puede aplicar en tiempo constante. Por lo tanto, dicha función es tan fácil de invertir como de calcular (hasta una constante multiplicativa), y por lo tanto no es una función de puerta trampa.
fuente