Ancilla bit: Difference between revisions
Multiple small changes for formality and grammar |
Petri Krohn (talk | contribs) Made easier for most readers to understand. {{Main|Reversible computing}} |
||
Line 2: | Line 2: | ||
{{use mdy dates|date=September 2021}} |
{{use mdy dates|date=September 2021}} |
||
{{Use American English|date=January 2019}}{{Technical|date=February 2011}} |
{{Use American English|date=January 2019}}{{Technical|date=February 2011}} |
||
{{Main|Reversible computing}} |
|||
'''Ancilla bits''' are |
'''Ancilla bits''' are extra bits being used to achieve some specific goals in [[reversible computing]] (e.g. quantum computing). In [[Classical computing|classical computation]], any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in [[quantum computing]] or classical reversible computing. In these [[Model of computation|models of computing]], all [[Operation (mathematics)|operations]] on [[computer memory]] must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit. For this reason, in a [[quantum algorithm]] there is no way to deterministically put bits in a specific prescribed [[Quantum state|state]] unless one is given access to bits whose original state is known in advance. Such bits, whose values are known ''a priori'', are known as '''ancilla bits''' in a quantum or reversible [[Task (computing)|computing task]]. |
||
[[File:NOT gate with 5 controls constructed from 4 Toffoli gates and 3 ancilla bits.png|thumb|300px|Using three ancilla bits and four [[Toffoli gate]]s to construct a NOT gate with 5 controls. The ancilla bits end up trashed because the effects on them were not [[uncomputed]].]] |
[[File:NOT gate with 5 controls constructed from 4 Toffoli gates and 3 ancilla bits.png|thumb|300px|Using three ancilla bits and four [[Toffoli gate]]s to construct a NOT gate with 5 controls. The ancilla bits end up trashed because the effects on them were not [[uncomputed]].]] |
Revision as of 13:34, 18 May 2023
![]() | This article may be too technical for most readers to understand.(February 2011) |
Ancilla bits are extra bits being used to achieve some specific goals in reversible computing (e.g. quantum computing). In classical computation, any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in quantum computing or classical reversible computing. In these models of computing, all operations on computer memory must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit. For this reason, in a quantum algorithm 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, whose values are known a priori, are known as ancilla bits in a quantum or reversible computing task.
![](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)
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 constant number O(1) of ancilla bits 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
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]
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
- ^ 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].