nLab CNOT gate

Idea

The controlled NOT or reversible XOR-gate is the logic gate acting between pairs of bits which identically keeps the first bit in the pair and negates the second IFF the first was set.

This may be understood equivalently as

• the controlled quantum gate-version of the quantum NOT-gate

• the reversible version of the XOR-gate.

In quantum computing/quantum information theory, by the controlled NOT gate or CNOT gate one means the quantum logic gate which acts on a pair of qbits by the linear map which is given in this way on the canonical linear basis-elements of a pair of qbits:

Similarly, by the CCNOT-gate (or Toffoli gate) one means the operation on triples of bits/qbit which (always retains the first two and) reverses the third iff the first two are both set.

Related entries

• controlled quantum gate

• Hadamard gate

• reversible computation

References

Original discussion:

• David E. Deutsch, Figure 2 in: Quantum computational networks, Proceedings of the Royal Society A, 425 1868 (1989) 73-90 [doi:10.1098/rspa.1989.0099, jstor:2398494]

• Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, Harald Weinfurter, pp. 8 of: Elementary gates for quantum computation, Phys. Rev. A52 (1995) 3457 [arXiv:quant-ph/9503016, doi:10.1103/PhysRevA.52.3457]

First proposal for experimental realization (on trapped ions):

• J. Ignacio Cirac, Peter Zoller: Quantum Computations with Cold Trapped Ions, Phys. Rev. Lett. 74 (1995) 4091 [doi:10.1103/PhysRevLett.74.4091]

Textbook accounts:

• Michael A. Nielsen, Isaac L. Chuang, p. 21 in: Quantum computation and quantum information, Cambridge University Press (2000) $[$doi:10.1017/CBO9780511976667, pdf, pdf$]$

See also:

• Wikipedia, Controlled NOT gate

• Wikipedia, Toffoli gate