The Exercise

An ancilla is prepared in a cat state on a block of qubits and verified before it is used. The verification copies the parity of two qubits of the block onto a check qubit, with a controlled NOT (CNOT) from the first of them onto it followed by a CNOT from the second.^✦ The exercise asks to show that a single fault anywhere in the preparation or the verification either shows up in a parity check or leaves at most one bit flip on the ancilla.^✦

The library takes a single fault to be a set of bit flips, either on the qubits of the prepared cat state or on the qubits of the verification at one moment of it.

Qubits and Gates

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space^✦, and a pure state $\psi$ of $S$ is a unit vector in that space, $\lVert \psi \rVert = 1$.^✦ The qubit is the system with state space $\mathbb{C}^2$^✦; its basis states $|0\rangle$ and $|1\rangle$ are the standard basis vectors.^✦ The composite system $S \otimes T$ of two systems $S$ and $T$ has the tensor product of their state spaces as its state space.^✦

A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$^✦, and it carries a pure state $\psi$ of $S$ to the pure state $U\psi$.^✦ Of two unitaries $U$ and $V$ of $S$, the unitary $UV$ applies first $V$ and then $U$^✦; the identity evolution $1$ is the unitary whose operator is the identity.^✦ Unitaries $U$ of $S$ and $V$ of $T$ give the product unitary $U \otimes V$ of $S \otimes T$, the tensor product of the two operators^✦, and $1 \otimes V$ is the gate $V$ acting on the second factor and leaving the first alone.

The Pauli $X$ is the unitary of the qubit with the matrix below^✦, and for a unitary $U$ of a system $S$ the controlled gate $C(U)$ is the unitary of $\mathrm{qubit} \otimes S$ that applies $U$ to $S$ when the control qubit is $|1\rangle$ and the identity when it is $|0\rangle$: $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(1)^✦ The CNOT gate is the unitary $C(X)$ of two qubits.^✦

The Cat State

The bit register over a finite set $\iota$ is the system of qubits labelled by $\iota$; its state space is $\mathbb{C}[\mathbb{Z}_2^{\iota}]$, with an orthonormal computational basis $\{|w\rangle\}$, one vector for each bit vector $w \in \mathbb{Z}_2^{\iota}$.^✦ For bit vectors $v$ and $u$ over $\iota$, the bit flip string $X^v$, the unitary that flips the qubits where $v$ is one, and the phase flip string $Z^u$ act on the basis as $$X^v |w\rangle = |w + v\rangle, \qquad Z^u |w\rangle = (-1)^{u \cdot w} |w\rangle .$$(2)^✦

An observable $A$ on a system $S$ is a self adjoint operator on its state space, $A^\dagger = A$^✦, and a pure state $\psi$ of $S$ is an eigenstate of $A$ with eigenvalue $\mu \in \mathbb{R}$ when $A|\psi\rangle = \mu|\psi\rangle$.^✦ For $i, j \in \iota$, the parity $Z_iZ_j$ is the phase flip string $Z^u$ of (2) with $u$ the sum of the bit vectors that have a single one, at $i$ and at $j$: a Hermitian unitary, taken as an observable.^✦

For a finite set $\iota$, the cat vector of the bit register over $\iota$ is the vector $|0\cdots0\rangle + |1\cdots1\rangle$ of its state space, the sum of the basis vectors of the all zero and the all one bit vectors.^✦ For nonempty $\iota$, the cat state $|\mathrm{cat}\rangle$ of the register over $\iota$ is the pure state obtained by dividing the cat vector by its norm, $$|\mathrm{cat}\rangle = \tfrac{1}{\sqrt{2}} \bigl( |0\cdots0\rangle + |1\cdots1\rangle \bigr) .$$(3)^✦

The Verification Gadget

The gadget acts on the three qubit register $\mathrm{qubit} \otimes (\mathrm{qubit} \otimes \mathrm{qubit})$, whose qubits are numbered $0$, $1$ and $2$, the last in the role of the check qubit. The gate $\mathrm{CNOT}_{02}$ is the controlled gate $C(1 \otimes X)$, with qubit $0$ as control and the Pauli $X$ on qubit $2$^✦, and $\mathrm{CNOT}_{12} = 1 \otimes \mathrm{CNOT}$ is the CNOT gate on the last two qubits. The verification gadget applies the first and then the second, $$G = \mathrm{CNOT}_{12} \, \mathrm{CNOT}_{02} .$$(4)^✦

For a bit $a$, the flip $X^a$ selected by $a$ is the identity for $a = 0$ and the Pauli $X$ for $a = 1$.^✦ A pattern $e = (e_0, e_1, e_2)$ of three bits gives the unitary $X^e = X^{e_0} \otimes X^{e_1} \otimes X^{e_2}$ of the register^✦, and a fault is such a pattern striking at one of three time slices $s$ of the gadget, which sit around the two CNOTs as $$\text{input} \;\longrightarrow\; \mathrm{CNOT}_{02} \;\longrightarrow\; \text{between} \;\longrightarrow\; \mathrm{CNOT}_{12} \;\longrightarrow\; \text{output} .$$(5)^✦ The gadget with the fault $e$ at the slice $s$ is the unitary $$G_s(e) = \begin{cases} G \, X^e, & s = \text{input}, \\ \mathrm{CNOT}_{12} \, X^e \, \mathrm{CNOT}_{02}, & s = \text{between}, \\ X^e \, G, & s = \text{output}. \end{cases}$$(6)^✦

The Claim

What Is Checked

The claim is stated over the cat state (3) of the register over $\iota$, the bit flip strings applied to it and the parities $Z_iZ_j$, and over the gadget (4), its time slices (5) and the faulty gadgets (6) built from the patterns $X^e$.

About these constructions the library proves that the cat vector is nonzero, so that it can be normalized^✦, and that the controlled gate $C(U)$ is unitary for every unitary $U$, the CNOT gate and $\mathrm{CNOT}_{02}$ among them.^✦ Products and tensor products of unitaries are unitary as well, so $G$, the patterns $X^e$ and every $G_s(e)$ are unitaries of the three qubit register.