Bit Ancilla

Los bits auxiliares son bits adicionales (unidades de información) que se utilizan en paradigmas de computación que requieren operaciones reversibles, como la computación reversible clásica y la computación cuántica . A diferencia de la computación clásica, donde los bits pueden establecerse libremente en 0 o 1, la computación reversible requiere que todas las operaciones en la memoria de la computadora sean invertibles. Los bits auxiliares, cuyo estado inicial se conoce, proporcionan el "espacio de trabajo" necesario para realizar operaciones que, de otro modo, borrarían información. Desempeñan un papel crucial en la implementación de puertas lógicas complejas y permiten la computación universal dentro de estos modelos reversibles.

En la computación cuántica, y a menos que se establezca explícitamente lo contrario, los valores de los cúbits auxiliares requieren descomputación , ya que de lo contrario pueden contener entrelazamiento no deseado y probablemente invalidarán el resultado del cálculo.

Los bits auxiliares pueden simplificar operaciones complejas. Por ejemplo, un bit auxiliar puede usarse para controlar una puerta Toffoli , convirtiéndola efectivamente en una puerta más simple como una puerta NOT controlada o una puerta NOT . ^{[ 1 ] : 29}

Para la computación reversible clásica, un número constante O(1) de bits auxiliares es necesario y suficiente para la computación universal. ^{[ 2 ]} Si bien los bits auxiliares adicionales no son estrictamente necesarios, pueden proporcionar espacio de trabajo adicional, lo que lleva a construcciones de circuitos más simples que utilizan menos puertas lógicas. ^{[ 1 ] : 131}

El concepto de bit auxiliar puede extenderse para la computación cuántica en términos de cúbits auxiliares , que pueden usarse, por ejemplo, en la corrección de errores cuánticos . ^{[ 3 ]} Un ejemplo notable del uso de cúbits auxiliares en la computación cuántica es el algoritmo de Deutsch-Jozsa .

La catálisis cuántica utiliza cúbits auxiliares para almacenar estados entrelazados que permiten realizar tareas que normalmente no serían posibles con operaciones locales y comunicación clásica (LOCC). ^{[ 4 ]}