User:Danawr/sandbox/QIP
This my QIP sandbox.
 | This article may be too technical for most readers to understand. (February 2011) |
An Ancilla Bit is an extra bit used to enable (or simplify) calculations in quantum or classical reversible systems. An ancilla bit, or a larger system containing multiple ancilla bits, spans the computation's outcome space[1]: 94 and is sometimes known in advance.
Ancilla bits in reversible computing
[edit]Reversible computing requires a one-to-one mapping of inputs to outputs, in order to determine the original input by the output. A NOT gate is reversible, as one can determine the input by the output. A XOR gate is irreversible, as one can not determine the original bits given the outcome. However, the XOR operation can be attained in a reversible manner, by introducing an extra, assistance bit - an ancilla bit. Performing classical Controlled NOT (CNOT) on the two input bits, and storing the control bit in addition to the desired outcome, gives the following reversible function:
| Input | Output | ||
|---|---|---|---|
| Control | Target | Control | Target |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
This example shows how adding ancilla bits is necessary to allow reversible computation. Once having a reversible circuit[nb 1], a constant amount (O(1)) of ancilla bits is necessary and sufficient for universal computation.[2] Additional ancilla bits may not be necessary, but the extra workspace can allow simpler circuit constructions that use fewer gates.[1]: 131
Ancilla bits in quantum computation
[edit]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 computations, in which one cannot know a qubit's state without measuring it - and losing information. For this reason, 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.
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
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]
Notes
[edit]- ^ A reversible circuit connects reversible gates without fanouts and loops.
References
[edit]- ^ a b c Chuang, Michael A. Nielsen & Isaac L. (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035.
- ^ Aaronson, Scott; Grier, Daniel; Schaeffer, Luke (2015). "The Classification of Reversible Bit Operations". arXiv:1504.05155 [quant-ph].
- ^ Azuma, Koji; Koashi, Masato; Imoto, Nobuyuki (2008). "Quantum catalysis of information". arXiv:0804.2426 [quant-ph].
- ^ 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.