The Exercise

The three qubit bit flip code stores the qubit $a|0\rangle + b|1\rangle$ as $a|000\rangle + b|111\rangle$. A flip of one of the three qubits is found by a syndrome measurement and undone by flipping that qubit back. Here the syndrome is measured by the eight projectors $|x\rangle\langle x|$ onto the computational basis states of the three qubits, and the outcome has to tell which error occurred: no flip, or a flip of qubit $j$ for $j = 1, 2, 3$.

The recovery built on this measurement returns the codewords $|000\rangle$ and $|111\rangle$ unchanged, but not their superpositions; the quantity asked for is the least, over all encoded states, of the fidelity between an encoded state and its recovered state.

A Quantum System

A quantum system $S$ is given by its state space, a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$^✦, and a state $\rho$ of $S$ is a positive operator of unit trace on that space.^✦ Each pure state $|\psi\rangle$ determines the state $|\psi\rangle\langle\psi|$, the projector onto $|\psi\rangle$.^✦ A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = I$^✦; it carries a pure state $|\psi\rangle$ to the pure state $U|\psi\rangle$.^✦

The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ with its standard inner product.^✦ The computational basis of the qudit with $d$ levels is the orthonormal basis of standard unit vectors $|0\rangle, \dots, |d-1\rangle$ of $\mathbb{C}^d$, each of them a pure state of the qudit.^✦ Three qubits form the qudit with eight levels: writing a label in binary, $x = 4x_1 + 2x_2 + x_3$, the basis state $|x\rangle$ is $|x_1x_2x_3\rangle$, so that $|0\rangle = |000\rangle$ and $|7\rangle = |111\rangle$. For a permutation $\sigma$ of the labels, the basis permutation gate $U_\sigma$ is the unitary of the qudit that carries each $|x\rangle$ to $|\sigma(x)\rangle$.^✦

The Code and Its Errors

The logical states of the code are $$|0_L\rangle = |000\rangle,$$(1)^✦ $$|1_L\rangle = |111\rangle,$$(2)^✦ and for complex amplitudes $a$ and $b$ with $|a|^2 + |b|^2 = 1$ the encoded state is the pure state $$|\psi\rangle = a|0_L\rangle + b|1_L\rangle.$$(3)^✦

For a three bit label $m$, adding $m$ bit by bit modulo two, $x \mapsto x \oplus m$, permutes the eight labels.^✦ The error masks are $m_0 = 000$, $m_1 = 100$, $m_2 = 010$ and $m_3 = 001$^✦, and the single qubit bit flip error $E_j$, the identity for $j = 0$ and the flip of qubit $j$ for $j = 1, 2, 3$, is the basis permutation gate of $x \mapsto x \oplus m_j$: $$E_j|x\rangle = |x \oplus m_j\rangle, \qquad j = 0, 1, 2, 3.$$(4)^✦

The syndrome $s(x) \in \{0, 1, 2, 3\}$ of a label $x$ is the qubit on which $x$ disagrees with the other two, or $0$ when all three bits agree: $$s(000) = s(111) = 0, \quad s(100) = s(011) = 1, \quad s(010) = s(101) = 2, \quad s(001) = s(110) = 3.$$(5)^✦

Measurement and Recovery

A measurement on $S$ with a finite set of outcomes is a family of measurement operators $M_i$ on the state space of $S$, one for each outcome $i$, satisfying the completeness relation $\sum_i M_i^\dagger M_i = I$.^✦ Performed on a state $\rho$, it gives outcome $i$ with the Born probability $$p(i) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr),$$(6)^✦ the probability that the positive operator valued measure (POVM) with elements $M_i^\dagger M_i$ assigns to $\rho$. When the outcome is not read, the measurement leaves $S$ in the state $\sum_i M_i \rho M_i^\dagger$.^✦

The projective measurement in an orthonormal basis $\{|b_i\rangle\}$ of $S$ is the measurement whose operator for outcome $i$ is the projector $|b_i\rangle\langle b_i|$.^✦ Taken in the computational basis of three qubits, it is the measurement of the exercise, with outcomes $x = 0, \dots, 7$ and the eight projectors $$P_x = |x\rangle\langle x|.$$(7)^✦

A recovery by projective measurement and conditional unitaries on $S$ consists of a syndrome measurement $\{M_i\}$ whose operators are orthogonal projectors, and a unitary correction $W_i$ of $S$ for each outcome $i$, applied when $i$ is found.^✦ Composing each $M_i$ with its correction gives the measurement with operators $W_i M_i$^✦, and the recovery takes a state $\rho$ to the state this measurement leaves when its outcome is not read: $$\mathcal{R}(\rho) = \sum_i W_i M_i \rho M_i^\dagger W_i^\dagger.$$(8)^✦ For three qubits the recovery measures the projectors $P_x$ and corrects outcome $x$ by the flip $E_{s(x)}$ that its syndrome names, so that (8) becomes $$\mathcal{R}(\rho) = \sum_{x=0}^{7} E_{s(x)} P_x \rho P_x E_{s(x)}^\dagger.$$(9)^✦

The Claim

The fidelity of two states $\rho$ and $\sigma$ of a system is the nonnegative number $$F(\rho, \sigma) = \operatorname{Tr}\sqrt{\sqrt{\rho}\,\sigma\sqrt{\rho}},$$(10)^✦ with the square roots of positive operators taken on their eigenvalues.

The measurement acts on a codeword after one of the errors $E_j$; the recovery acts on the encoded states themselves, with no error before it.

What Is Checked

The claim is stated over the recovery (9), built from the computational basis measurement of three qubits and the corrections $E_{s(x)}$; over the Born probabilities (6) of that measurement on the corrupted codewords $E_j|c\rangle$; and over the fidelity (10) of each encoded state (3) with its recovered state.

About these constructions the library proves that the projectors $|b_i\rangle\langle b_i|$ of an orthonormal basis satisfy the completeness relation, and that each $P_x$ is an orthogonal projector, so the syndrome measurement is projective. Composing with unitaries keeps the completeness relation, $\sum_i (W_i M_i)^\dagger W_i M_i = I$, and so $\mathcal{R}(\rho)$ is again a positive operator of unit trace, a state of the three qubits.