Ancilla bit

Ancilla bits are extra bits (units of information) used in computing paradigms that require reversible operations, such as classical reversible computing and quantum computing. Unlike classical computing where bits can be freely set to 0 or 1, reversible computation requires all operations on computer memory to be invertible. Ancilla bits, whose initial state is known, provide the necessary "workspace" for performing operations that would otherwise erase information. They play a crucial role in implementing complex logic gates and enabling universal computation within these reversible models.

Using three ancilla bits and four Toffoli gates to construct a NOT gate with 5 controls. The ancilla bits end up trashed because the effects on them were not uncomputed.

Ancilla bits can simplify complex operations. For example, an ancilla bit can be used to control a Toffoli gate, effectively turning it into a simpler gate like a controlled NOT or a NOT gate.^[1]: 29

Number of bits required

For classical reversible computation, a constant number O(1) of ancilla bits is necessary and sufficient for universal computation.^[2] While additional ancilla bits aren't strictly required, they can provide extra working space, leading to simpler circuit constructions using fewer logic gates.^[1]: 131

Ancilla qubits

The concept of ancilla bit can be extended for quantum computing in terms of ancilla qubits, that can be used for example in quantum error correction.^[3] One notable example for the use of ancilla qubits in quantum computing is the Deutsch–Jozsa algorithm.

Quantum catalysis uses ancilla qubits to store entangled states that enable tasks that would not normally be possible with local operations and classical communication (LOCC).^[4]