# Quantum Bayesian Networks

## January 29, 2011

### The Great Communicator: the CNOT

Filed under: Uncategorized — rrtucci @ 8:16 pm

Political commentators dubbed Ronald Reagan (USA president from 1981 to 1989) “the Great Communicator”. You may or may not agree that he deserved that accolade, but in quantum information theory, there is no doubt, at least in my mind, that one particular operator deserves the title of Great Communicator more than any other: the CNOT.

The building blocks of “information” are bits in the classical world and qubits (quantum bits) in the bizarro world of quantum mechanics. You can transform a single qubit by rotating it with a U(2) transformation. But you also need to invent a really simple, unitary, 2-body interaction to send messages from one qubit to another. That’s what a CNOT (controlled not) does. In concise notation explained here, a CNOT can be expressed as $\sigma_X(\tau)^{n(\kappa)}$, where $\kappa$ labels the control qubit, $\tau$ labels the target qubit, $\sigma_X(\tau)$ is a Pauli matrix, and $n(\kappa)$ is a number operator.

Any unitary operation acting on any number of qubits, can be expressed as a sequence of elementary gates that are either single-qubit rotations or CNOTs. The time complexity of a quantum circuit can be measured by expressing it in terms of these elementary gates and then counting the number of CNOTs. A CNOT can send classical or quantum messages and it can entangle two qubits. Much of Shannon information theory, both quantum and classical, concerns counting how many CNOTs connect the labs of Alice and Bob.