En informática reversible , los bits auxiliares son bits adicionales que se utilizan para implementar operaciones lógicas irreversibles. En la computación clásica , cualquier bit de memoria se puede activar o desactivar a voluntad, sin necesidad de conocimientos previos ni complejidad adicional. Sin embargo, este no es el caso de la computación cuántica o de la computación reversible clásica. En estos modelos de computación , todas las operaciones en la memoria de la computadora deben ser reversibles, y al activar o desactivar un bit se perdería la información sobre el valor inicial de ese bit. Por esta razón, en un algoritmo cuántico no hay forma de poner bits de manera determinista en un estado prescrito específico a menos que se dé acceso a bits cuyo estado original se conozca de antemano. Estos bits, cuyos valores se conocen a priori , se conocen como bits auxiliares en una tarea de computación cuántica o reversible .
Un uso trivial de los bits ancilla es degradar puertas cuánticas complicadas a puertas simples. Por ejemplo, al colocar controles en bits auxiliares, una puerta Toffoli se puede usar como una puerta NOT controlada o una puerta NOT . [1] : 29
Para el cálculo reversible clásico se sabe que un número constante O(1) de bits auxiliares es necesario y suficiente para el cálculo universal. [2] No son necesarias brocas auxiliares adicionales, pero el espacio de trabajo adicional puede permitir construcciones de circuitos más simples que utilizan menos puertas. [1] : 131
El concepto de bit ancilla puede ampliarse a la computación cuántica en términos de qubits ancilla , que pueden utilizarse, por ejemplo, en la corrección de errores cuánticos . [3] Un ejemplo notable del uso de ancilla qubits en computación cuántica es el algoritmo Deutsch-Jozsa .
La catálisis cuántica utiliza qubits ancilla para almacenar estados entrelazados que permiten tareas que normalmente no serían posibles con operaciones locales y comunicación clásica (LOCC). [4]