Controlled NOT gate

From Wikipedia, the free encyclopedia
  (Redirected from Cnot)
Jump to: navigation, search
The classical analog of the CNOT gate is a reversible XOR gate.
How the CNOT gate can be used (with Hadamard gates) in a computation
Representation of the CNOT gate
Answer on output depending on input and CNOT function
The first qubit flips only if the second qubit is 1.

In computing science, the controlled NOT gate (also C-NOT or CNOT) is a quantum gate that is an essential component in the construction of a quantum computer. It can be used to entangle and disentangle EPR states. Specifically, any quantum circuit can be simulated to an arbitrary degree of accuracy using a combination of CNOT gates and single qubit rotations.

Operation[edit]

The CNOT gate flips the second qubit (the target qubit) if and only if the first qubit (the control qubit) is 1.

Before After
Control Target Control Target
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

The resulting value of the second qubit corresponds to the result of a classical XOR gate.

The CNOT gate can be represented by the matrix (permutation matrix form):

 \operatorname{CNOT} =  \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\  0 & 0 & 1 & 0 \end{bmatrix}.

The first experimental realization of a CNOT gate was accomplished in 1995. Here, a single Beryllium 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). 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. CNOT is also a kind of universal gate(in the classical sense of the word). It is easy to see that if the CONTROL is set to '1' the TARGET output is always NOT. So, a NOT GATE can be constructed using CNOT.

Proof of operation[edit]

Let \left\{ 
|0\rangle =\! \begin{bmatrix} 1 \\ 0 \end{bmatrix}, 
|1\rangle =\! \begin{bmatrix} 0 \\ 1 \end{bmatrix} 
\right\} be the orthonormal basis (using bra–ket notation).

Let | \psi \rangle = a | 0 \rangle + b | 1 \rangle =\! \begin{bmatrix} a \\ b \end{bmatrix}.

Let | \phi \rangle = b | 0 \rangle + a | 1 \rangle =\! \begin{bmatrix} b \\ a \end{bmatrix} be the flip qubit of  | \psi \rangle.

Recall that |\alpha\rangle\!\otimes\!|\beta\rangle 
                  = |\alpha\rangle |\beta\rangle 
                  = |\alpha,\beta\rangle .

When control qubit is 0[edit]

Here is a proof that 
\operatorname{CNOT}\ |0,\psi\rangle = |0,\psi\rangle
:

Note that here the specific definition of  \operatorname{CNOT}\ assumes an eigenbasis of

 |00\rangle = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, |01\rangle = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} , |10\rangle = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}, |11\rangle = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}

It's straightforward to verify that if 
|0,\psi\rangle = a|0\rangle |0\rangle + b|0\rangle |1\rangle = \begin{bmatrix} a \\ b \\ 0 \\ 0 \end{bmatrix}

Then \operatorname{CNOT}\ |0,\psi\rangle = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a \\ b \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} a \\ b \\ 0 \\ 0 \end{bmatrix} = |0,\psi\rangle.

Therefore CNOT doesn't change the  |\psi\rangle qubit if the first qubit is 0.

When control qubit is 1[edit]

Here is a proof that  \operatorname{CNOT}\ |1,\psi\rangle = |1,\phi\rangle, which means that the CNOT gate flips the |\psi\rangle qubit.

Similarly to the first demonstration,  |1,\psi\rangle = \begin{bmatrix} 0 \\ 0 \\ a \\ b \end{bmatrix}.

Then  \operatorname{CNOT}\ |1,\psi\rangle = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ a \\ b \end{bmatrix} = a \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} + b \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}

It can be seen that  |1,1\rangle = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} and  |1,0\rangle = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}, using these on the equation above gives


\begin{align}
\operatorname{CNOT}\ |1,\psi\rangle 
     & = a |1,1\rangle + b |1,0\rangle \\
     & = |1\rangle \left( a |1\rangle  + b |0\rangle \right) \\
     & = |1,\phi\rangle \\
\end{align}

Therefore the CNOT gate flips the |\psi\rangle qubit into |\phi\rangle if the control qubit is set to 1. A simple way to observe this is to multiply the CNOT matrix by a column vector, noticing that the operation on the first bit is identity, and a NOT gate on the second bit.

Behaviour of CNOT when viewed in the Hadamard basis[edit]

When viewed only in the computational basis \{|0\rangle,|1\rangle\}, the behaviour of the CNOT 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 what happens for most input values of both qubits.

CNOT gate in Hadamard Basis

"consider the Cnot gate in the Hadamard basis \{|+\rangle,|-\rangle\}... it is the state of the second qubit that remains unchanged, and the state of the first qubit that is flipped depending on the state of the second bit. 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."[1]

"the key is to notice the symmetric behavior of the CNOT gate. If we switch X and Z and qubits 1 and 2, we get back the original transformation."[2] The observation that both qubits are affected in a CNOT interaction is of importance when considering information flow in entangled quantum systems.[3]

Working through each of the Hadamard basis states, the first qubit flips between |+\rangle and |-\rangle when the second qubit is |-\rangle:

Initial state in Hadamard basis Equivalent state in computational basis Apply operator State in computational basis after CNOT Equivalent state in Hadamard basis
|++\rangle |00\rangle + |01\rangle + |10\rangle + |11\rangle CNOT |00\rangle + |01\rangle + |11\rangle + |10\rangle |++\rangle
|+-\rangle |00\rangle - |01\rangle + |10\rangle - |11\rangle CNOT |00\rangle - |01\rangle + |11\rangle - |10\rangle |--\rangle
|-+\rangle |00\rangle + |01\rangle - |10\rangle - |11\rangle CNOT |00\rangle + |01\rangle - |11\rangle - |10\rangle |-+\rangle
|--\rangle |00\rangle - |01\rangle - |10\rangle + |11\rangle CNOT |00\rangle - |01\rangle - |11\rangle + |10\rangle |+-\rangle

A quantum circuit that performs a Hadamard transform followed by CNOT then another Hadamard transform can be described in terms of matrix operators:

(H1 ⊗ H1) . CNOT . (H1 ⊗ H1)-1

The single-qubit Hadamard tranform, H1, is 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:

H2 . CNOT . H2

When multiplied out, this yields a matrix that swaps the |01\rangle and |11\rangle terms over, while leaving the |00\rangle and |10\rangle terms alone. This is equivalent to a CNOT gate where qubit 2 is the control qubit and qubit 1 is the target qubit:

\begin{align}
  \frac{1}{4}
   &\begin{bmatrix}\begin{array}{rrrr}
    1 &  1 &  1 &  1\\
    1 & -1 &  1 & -1\\
    1 &  1 & -1 & -1\\
    1 & -1 & -1 &  1
   \end{array}\end{bmatrix}
.
\begin{bmatrix}\begin{array}{rrrr}
    1 & 0 & 0 & 0\\
    0 & 1 & 0 & 0\\
    0 & 0 & 0 & 1\\
    0 & 0 & 1 & 0
   \end{array}\end{bmatrix}
.
\begin{bmatrix}\begin{array}{rrrr}
    1 &  1 &  1 &  1\\
    1 & -1 &  1 & -1\\
    1 &  1 & -1 & -1\\
    1 & -1 & -1 &  1
   \end{array}\end{bmatrix}
=
\begin{bmatrix}\begin{array}{rrrr}
    1 & 0 & 0 & 0\\
    0 & 0 & 0 & 1\\
    0 & 0 & 1 & 0\\
    0 & 1 & 0 & 0
   \end{array}\end{bmatrix}

\end{align}

See also[edit]

References[edit]

  1. ^ Eleanor G. Rieffel; Wolfgang H. Polak (4 March 2011). Quantum Computing: A Gentle Introduction. MIT Press. p. 80. ISBN 978-0-262-01506-6. 
  2. ^ Gottesman, Daniel (1998). "The Heisenberg Representation of Quantum Computers". Group: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, eds. S. P. Corney, R. Delbourgo, and P. D. Jarvis, pp. (Cambridge, MA, International Press, ) 22 (1999): 32–43. arXiv:quant-ph/9807006. 
  3. ^ Deutsch, David; Hayden, Patrick (1999). "Information Flow in Entangled Quantum Systems". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 456 (1999): 1759–1774. arXiv:quant-ph/9906007. doi:10.1098/rspa.2000.0585. 

External links[edit]