Ancilla bit

In classical computation any memory bit can turned be turned on or off at will, requiring no prior knowledge or extra gadgetry. This is not the case in quantum (or classical reversible) computation, however, as operation in these models are reversible, while turning a bit on (or off) would lose the information about the initial value of that bit. For this reason, in a quantum computation there is no way to deterministically put bits in a specific prescribed state unless one is given access to bits whose original state is known in advance. Such bits which are known in advance to be in the state are called ancilla bits.

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 quantum gates into simple gates. For example, by placing controls on ancilla bits, a Toffoli gate can be used as a controlled NOT gate or a NOT Gate.[1]:29

For classical reversible computation it is known that a single ancilla bit is necessary and sufficient for universal computation.[2] Additional ancilla bits are not necessary, but the extra workspace can allow for simpler circuit constructions that use fewer gates.[1]:131

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

References

  1. 1 2 Chuang, Michael A. Nielsen & Isaac L. (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035.
  2. ↑ Aaronson, Scott; Grier, Daniel; Schaeffer, Luke (2015). "The Classification of Reversible Bit Operations". arXiv:1504.05155Freely accessible [quant-ph].
  3. ↑ Azuma, Koji; Koashi, Masato; Imoto, Nobuyuki (2008). "Quantum catalysis of information". arXiv:0804.2426Freely accessible [quant-ph].
  4. ↑ Shor, Peter W. (1 October 1995). "Scheme for reducing decoherence in quantum computer memory". Physical Review A. 52 (4). Bibcode:1995PhRvA..52.2493S. doi:10.1103/PhysRevA.52.R2493. Retrieved 6 June 2015.


This article is issued from Wikipedia - version of the 11/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.