Ancilla bit

An ancilla bit is an extra bit which has a secondary role in a logic circuit.

File:NOT gate with 5 controls constructed from 4 Toffoli gates and 3 ancilla bits.png

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.

A trivial use for ancilla bits is downgrading complicated gates into simple gates. For example, by placing controls on ancilla bits known to be ON, a Toffoli gate can be used as a controlled NOT gate or a NOT Gate.

A single ancilla bit is necessary and sufficient for universal classical reversible computation. Additional ancilla bits are not necessary for universality, but the extra workspace can allow for simpler circuit constructions that use fewer gates.

In quantum computing, 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). Quantum computers also use ancilla bits for quantum error correction.