Ancilla bit
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/NOT_gate_with_5_controls_constructed_from_4_Toffoli_gates_and_3_ancilla_bits.png/300px-NOT_gate_with_5_controls_constructed_from_4_Toffoli_gates_and_3_ancilla_bits.png)
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.
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
[edit]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
[edit]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]
References
[edit]- ^ a b Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3.
- ^ Aaronson, Scott; Grier, Daniel; Schaeffer, Luke (2015). "The Classification of Reversible Bit Operations". arXiv:1504.05155 [quant-ph].
- ^ Shor, Peter W. (October 1, 1995). "Scheme for reducing decoherence in quantum computer memory". Physical Review A. 52 (4): R2493 – R2496. Bibcode:1995PhRvA..52.2493S. doi:10.1103/PhysRevA.52.R2493. PMID 9912632. Retrieved June 6, 2015.
- ^ Azuma, Koji; Koashi, Masato; Imoto, Nobuyuki (2008). "Quantum catalysis of information". arXiv:0804.2426 [quant-ph].