Ancilla bit

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

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.[1] 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).[2] Quantum computers also use ancilla bits for quantum error correction.[3]

References

  1. ↑ Aaronson, Scott; Grier, Daniel; Schaeffer, Luke (2015). "The Classification of Reversible Bit Operations". arXiv:1504.05155 [quant-ph].
  2. ↑ Azuma, Koji; Koashi, Masato; Imoto, Nobuyuki (2008). "Quantum catalysis of information". arXiv:0804.2426 [quant-ph].
  3. ↑ Shor, Peter W. (1 October 1995). "Scheme for reducing decoherence in quantum computer memory". Physical Review A 52 (4). doi:10.1103/PhysRevA.52.R2493. Retrieved 6 June 2015.


This article is issued from Wikipedia - version of the Wednesday, October 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.