In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the controlled NOT gate (also C-NOT or CNOT), controlled-''X'' gate, controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a
quantum logic gate
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of qua ...
that is an essential component in the construction of a
gate-based quantum computer
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing takes advantage of this behavior using specialized hardware. ...
. It can be used to
entangle and disentangle
Bell state
In quantum information science, the Bell's states or EPR pairs are specific quantum states of two qubits that represent the simplest examples of quantum entanglement. The Bell's states are a form of entangled and normalized basis vectors. Thi ...
s. Any quantum circuit can be simulated to an arbitrary degree of accuracy using a combination of CNOT gates and single
qubit
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical syste ...
rotations.
The gate is sometimes named after
Richard Feynman
Richard Phillips Feynman (; May 11, 1918 – February 15, 1988) was an American theoretical physicist. He is best known for his work in the path integral formulation of quantum mechanics, the theory of quantum electrodynamics, the physics of t ...
who developed an early notation for quantum gate diagrams in 1986.
The CNOT can be expressed in the
Pauli basis as:
:
Being both
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation
* Unitarity (physics)
* ''E''-unitary inverse semigr ...
and
Hermitian {{Short description, none
Numerous things are named after the French mathematician Charles Hermite (1822–1901):
Hermite
* Cubic Hermite spline, a type of third-degree spline
* Gauss–Hermite quadrature, an extension of Gaussian quadrature me ...
, CNOT
has the property and
, and is
involutory.
The CNOT gate can be further decomposed as products of
rotation operator gates and exactly one
two qubit interaction gate, for example
:
In general, any single qubit
unitary gate can be expressed as
, where ''H'' is a
Hermitian matrix
In mathematics, a Hermitian matrix (or self-adjoint matrix) is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the -th row and -th column is equal to the complex conjugate of the element in the ...
, and then the controlled ''U'' is
.
The CNOT gate is also used in classical
reversible computing
Reversible computing is any model of computation where every step of the process is time-reversible. This means that, given the output of a computation, it's possible to perfectly reconstruct the input. In systems that progress deterministica ...
.
Operation
The CNOT gate operates on a
quantum register
In quantum computing, a quantum register is a system comprising multiple qubits. It is the quantum analogue of the classical processor register. Quantum computers perform calculations by manipulating qubits within a quantum register.
Definitio ...
consisting of 2 qubits. The CNOT gate flips the second qubit (the target qubit) if and only if the first qubit (the control qubit) is
.
If
are the only allowed input values for both qubits, then the TARGET output of the CNOT gate corresponds to the result of a classical
XOR gate
XOR gate (sometimes EOR, or EXOR and pronounced as Exclusive OR) is a digital logic gate that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an exclusive disjunction, exclusive or (\nleftrightarrow) ...
. Fixing CONTROL as
, the TARGET output of the CNOT gate yields the result of a classical
NOT gate
Not or NOT may also refer to:
Language
* Not, the general declarative form of "no", indicating a negation of a related statement that usually precedes
* ... Not!, a grammatical construction used as a contradiction, popularized in the early 1990 ...
.
More generally, the inputs are allowed to be a linear superposition of
. The CNOT gate transforms the quantum state:
into:
The action of the CNOT gate can be represented by the matrix (
permutation matrix
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. ...
form):
:
The first experimental realization of a CNOT gate was accomplished in 1995. Here, a single
Beryllium
Beryllium is a chemical element; it has Symbol (chemistry), symbol Be and atomic number 4. It is a steel-gray, hard, strong, lightweight and brittle alkaline earth metal. It is a divalent element that occurs naturally only in combination with ...
ion in a
trap was used. The two qubits were encoded into an optical state and into the vibrational state of the ion within the trap. At the time of the experiment, the reliability of the CNOT-operation was measured to be on the order of 90%.
In addition to a regular controlled NOT gate, one could construct a function-controlled NOT gate, which accepts an arbitrary number ''n''+1 of qubits as input, where ''n''+1 is greater than or equal to 2 (a
quantum register
In quantum computing, a quantum register is a system comprising multiple qubits. It is the quantum analogue of the classical processor register. Quantum computers perform calculations by manipulating qubits within a quantum register.
Definitio ...
). This gate flips the last qubit of the register if and only if a built-in function, with the first ''n'' qubits as input, returns a 1.
The function-controlled NOT gate is an essential element of the
Deutsch–Jozsa algorithm.
Behaviour in the Hadamard transformed basis
When viewed only in the computational basis
, the behaviour of the C
NOT appears to be like the equivalent classical gate. However, the simplicity of labelling one qubit the ''control'' and the other the ''target'' does not reflect the complexity of what happens for most input values of both qubits.
Insight can be gained by expressing the CNOT gate with respect to a Hadamard transformed basis
. The Hadamard transformed basis of a one-qubit
register
Register or registration may refer to:
Arts, entertainment, and media
Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), ...
is given by
:
and the corresponding basis of a 2-qubit register is
:
,
etc. Viewing CNOT in this basis, the state of the second qubit remains unchanged, and the state of the first qubit is flipped, according to the state of the second bit. (For details see below.) "Thus, in this basis the sense of which bit is the ''control bit'' and which the ''target bit'' has reversed. But we have not changed the transformation at all, only the way we are thinking about it."
The "computational" basis
is the eigenbasis for the spin in the Z-direction, whereas the Hadamard basis
is the eigenbasis for spin in the X-direction. Switching X and Z and qubits 1 and 2, then, recovers the original transformation."
This expresses a fundamental symmetry of the CNOT gate.
The observation that both qubits are (equally) affected in a C
NOT interaction is of importance when considering information flow in entangled quantum systems.
Details of the computation
We now proceed to give the details of the computation. Working through each of the Hadamard basis states, the results on the right column show that the first qubit flips between
and
when the second qubit is
:
A quantum circuit that performs a Hadamard transform followed by C
NOT then another Hadamard transform, can be described as performing the CNOT gate in the Hadamard basis (i.e. a
change of basis
In mathematics, an ordered basis of a vector space of finite dimension allows representing uniquely any element of the vector space by a coordinate vector, which is a sequence of scalars called coordinates. If two different bases are conside ...
):
The single-qubit Hadamard transform, H
1, is
Hermitian {{Short description, none
Numerous things are named after the French mathematician Charles Hermite (1822–1901):
Hermite
* Cubic Hermite spline, a type of third-degree spline
* Gauss–Hermite quadrature, an extension of Gaussian quadrature me ...
and therefore its own inverse. The tensor product of two Hadamard transforms operating (independently) on two qubits is labelled
H2. We can therefore write the matrices as:
When multiplied out, this yields a matrix that swaps the
and
terms over, while leaving the
and
terms alone. This is equivalent to a CNOT gate where qubit 2 is the control qubit and qubit 1 is the target qubit:
Constructing a Bell state
A common application of the C
NOT gate is to maximally entangle two qubits into the
Bell state
In quantum information science, the Bell's states or EPR pairs are specific quantum states of two qubits that represent the simplest examples of quantum entanglement. The Bell's states are a form of entangled and normalized basis vectors. Thi ...
; this forms part of the setup of the
superdense coding
In quantum information theory, superdense coding (also referred to as ''dense coding'') is a quantum communication protocol to communicate a number of classical bits of information by only transmitting a smaller number of qubits, under the ass ...
,
quantum teleportation
Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from on ...
, and entangled
quantum cryptography
Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure soluti ...
algorithms.
To construct
, the inputs A (control) and B (target) to the C
NOT gate are
:
and
.
After applying C
NOT, the resulting Bell state
has the property that the individual qubits can be measured using any basis and will always present a 50/50 chance of resolving to each state. In effect, the individual qubits are in an undefined state. The correlation between the two qubits is the complete description of the state of the two qubits; if we both choose the same basis to measure both qubits and compare notes, the measurements will perfectly correlate.
When viewed in the computational basis, it appears that qubit A is affecting qubit B. Changing our viewpoint to the Hadamard basis demonstrates that, in a symmetrical way, qubit B is affecting qubit A.
The input state can alternately be viewed as
:
and
.
In the Hadamard view, the control and target qubits have conceptually swapped and qubit A is inverted when qubit B is
. The output state after applying the C
NOT gate is
which can be shown as follows:
:
:
:
:
C-ROT gate
The C-ROT gate (controlled
Rabi rotation) is equivalent to a C-NOT gate except for a
rotation of the nuclear spin around the z axis.
Implementations
Trapped ion quantum computers:
*
Cirac–Zoller controlled-NOT gate
*
Mølmer–Sørensen gate
Regulation
In May, 2024, Canada implemented
export restrictions
Export restrictions, or a restriction on exportation, are limitations on the quantity of goods exported to a specific country or countries by a Government. Export restrictions could be aimed at achieving diverse policy objectives such as envir ...
on the sale of quantum computers containing more than 34
qubits and error rates below a certain CNOT
error threshold
In evolutionary biology and population genetics, the error threshold (or critical mutation rate) is a limit on the number of base pairs a self-replicating molecule may have before mutation will destroy the information in subsequent generations o ...
, along with restrictions for quantum computers with more qubits and higher error rates. The same restrictions quickly popped up in the UK, France, Spain and the Netherlands. They offered few explanations for this action, but all of them are
Wassenaar Arrangement
The Wassenaar Arrangement on Export Controls for Conventional Arms and Dual-Use Goods and Technologies, also known simply as the Wassenaar Arrangement, is a multilateral export control regime governing the international transfer of conventional ...
states, and the restrictions seem related to
national security
National security, or national defence (national defense in American English), is the security and Defence (military), defence of a sovereign state, including its Citizenship, citizens, economy, and institutions, which is regarded as a duty of ...
concerns potentially including
quantum cryptography
Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure soluti ...
or
protection from competition.
See also
*
Toffoli gate (controlled-controlled-NOT gate)
Notes
References
{{reflist
External links
not gate">Michael Westmoreland: "Isolation and information flow in quantum dynamics" - discussion around the Cnot gate
Quantum gates
Quantum information science