4.14

# Extracting Parity

Error correcting codes generally identify errors by calculating the parity of a set of bits.

Parity tells us whether the number of ones in a set of bits is even or odd; the parity of 001 and 111 is 1, while the parity of 000, 110, and 101 is 0. Parity can be calculated by taking the XOR (exclusive OR) of the set of bits. Extracting parity without destroying the superposition is the tricky part of QEC. The CNOT can help.

## Parity on a Bell pair

For example, let’s look at our Bell pair $\frac{|00\rangle + |11\rangle}{\sqrt{2}}$. Consider each element of the superposition separately. The parity of $|00\rangle$ is 0. The parity of $|11\rangle$ is also zero. If we try to find the parity by first measuring each qubit, then calculating the parity classically, we will destroy the superposition and entanglement.

Instead, let’s add another qubit, initialized to be $|0\rangle$, then use that to calculate the parity. Now our state is $\frac{(|00\rangle + |11\rangle)|0\rangle}{\sqrt{2}} = \frac{|000\rangle + |110\rangle}{\sqrt{2}}$.

Recall that the quantum equivalent of XOR is CNOT. Let’s first apply a CNOT using the left qubit as the control and the right qubit as the target. In each term of the superposition, if the left qubit is zero, it will leave the right qubit alone. If the left qubit is one, it will flip the right qubit. That will make the state $\frac{|000\rangle + |111\rangle}{\sqrt{2}}$.

Now do the same thing using the middle qubit as the control, and the right qubit as the target. If the middle qubit is zero, leave the right qubit alone; if it’s one, flip the right qubit. Now we have the state $\frac{|000\rangle + |110\rangle}{\sqrt{2}} = \frac{(|00\rangle + |11\rangle)|0\rangle}{\sqrt{2}}$. In the first term in the superposition, the parity of 00 is 0, and in the right term of the superposition, the parity of 11 is also 0. It’s the same!

Now if we go measure the right hand qubit, we will definitely find 0. Since it’s always 0, the rest of the state is unaffected, and our superposition and entanglement are the same!

On the other hand, consider another type of Bell pair, $\frac{|01\rangle + |10\rangle}{\sqrt{2}}$. This second type of Bell pair is the same as our first type, but with one qubit flipped – a single bit flip error. The operation would go differently. The first CNOT gate would take our state from $\frac{(|01\rangle + |10\rangle)|0\rangle}{\sqrt{2}} = \frac{|010\rangle + |100\rangle}{\sqrt{2}}$ to $\frac{|010\rangle + |101\rangle}{\sqrt{2}}$, then the second CNOT would advance the state to $\frac{|011\rangle + |101\rangle}{\sqrt{2}} = \frac{(|01\rangle + |10\rangle)|1\rangle}{\sqrt{2}}$. Now if we measure the last qubit, we find 1, and once again the superposition and entanglement of the first two qubits (our original Bell pair) are unaffected.

## Parity of larger states

That procedure gives us the ability to measure the parity without collapsing the state, at least for certain kinds of two-qubit states. If we can extend this concept to more qubits, we can build complete error correction.

Consider the three-qubit state $\frac{|000\rangle + |111\rangle}{\sqrt{2}}$. If we add a fourth qubit and calculate the parity of all three qubits, the problem is that the parity of the components of the superposition differ. We will end up with even (0) parity for the $|000\rangle$ state, and odd (1) parity for the $|111\rangle$ state, so we would have the state $\frac{|0000\rangle + |1111\rangle}{\sqrt{2}}$. Measuring the last (parity) qubit would collapse our superposition.

Instead, we use our technique to measure the parity of only a subset of the qubits. In this case, we’ll work two at a time, first calculating the parity of the left and middle qubits, which should be 0, then the parity of the middle and right qubits, which should also be 0.

This particular state forms the basis of the simplest quantum error correcting code, to which we turn next.