The Exercise

Three qubits enter the circuit of Figure 4.17: two ancillas, each prepared in $|0\rangle$, and a target in an arbitrary pure state $|\psi\rangle$. Each ancilla first passes a Hadamard gate. A Toffoli gate controlled by the two ancillas then acts on the target, followed by the phase gate $S$ on the target and a second Toffoli gate, and a Hadamard on each ancilla closes the circuit. Last, both ancillas are measured in the computational basis.

The exercise is to show that the two outcomes are both $0$ with probability $5/8$, and that the target has then undergone the rotation $R_z(\theta)$ about the $z$ axis by the angle $\theta$ with $\cos\theta = 3/5$; any other pair of outcomes leaves the Pauli $Z$ applied to the target.

Qubits and Gates

A quantum system $S$ is described by its state space, a finite dimensional complex Hilbert space, and the composite system $S\otimes T$ of two systems $S$ and $T$ has as its state space the tensor product of theirs. A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$; pure states $|\psi\rangle$ of $S$ and $|\varphi\rangle$ of $T$ give the product state $|\psi\rangle\otimes|\varphi\rangle$ of $S\otimes T$. The qubit is the system with state space $\mathbb{C}^2$, and its basis states $|0\rangle$ and $|1\rangle$ are the standard basis vectors $(1,0)$ and $(0,1)$. The circuit acts on three qubits, the first two the ancillas and the third the target, with input $|0\rangle\otimes(|0\rangle\otimes |\psi\rangle)$, written $|0\rangle|0\rangle|\psi\rangle$.

A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = UU^\dagger = 1$, and it carries a pure state $|\psi\rangle$ to the pure state $U|\psi\rangle$. The identity $1$ is a unitary of every system.^✦ For unitaries $U$ and $V$ of $S$, the unitary $UV$, $U$ after $V$, applies $V$ first and then $U$.^✦ For a unitary $U$ of $S$ and a unitary $V$ of $T$, the product unitary $U\otimes V$ of $S\otimes T$ is the tensor product of the two operators; $U\otimes 1$ is $U$ acting on the first factor, the first wires of the composite, and $1\otimes V$ is $V$ acting on the last factor, its last wires.

In the computational basis, the matrices of the Hadamard, of the three Pauli operators and of the phase gate are $$H = \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \quad S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}.$$(1) The Hadamard $H$, the Pauli $X$ and $Z$ and the phase gate $S$ are the unitaries of the qubit whose operators have these matrices.

For a vector $\vec n = (n_x, n_y, n_z)$ of $\mathbb{R}^3$, the Pauli vector $\vec\sigma = (X, Y, Z)$ gives the matrix $\vec n\cdot\vec\sigma = n_xX + n_yY + n_zZ$, and the rotation about $\vec n$ by a real angle $\theta$ is $$R_{\vec n}(\theta) = \exp\Bigl(-\frac{i\theta}{2}\,\vec n\cdot\vec\sigma\Bigr), \qquad R_z(\theta) = R_{\hat z}(\theta) = e^{-i\theta Z/2},$$(2) where $\hat z = (0,0,1)$; about a unit vector $\hat n$ it is written $R_{\hat n}(\theta)$. The rotation gate $R_z(\theta)$ is the unitary of the qubit whose operator has the matrix $e^{-i\theta Z/2}$.^✦

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite of a control qubit with $S$ given by $$C(U) = |0\rangle\langle 0|\otimes 1 + |1\rangle\langle 1|\otimes U.$$(3) For a unitary $U$ of a qubit, the doubly controlled gate $C^2(U) = C(C(U))$ of three qubits applies $U$ to the third exactly when the first two are both $|1\rangle$; the Toffoli gate is $C^2(X)$.

The Circuit

The Hadamard layer $W$ of the circuit is the unitary of the three qubits $$W = H\otimes H\otimes 1.$$(4)^✦ The middle gate $G$ of the circuit is the unitary $$G = C^2(X)\,(1\otimes 1\otimes S)\,C^2(X),$$(5) and the circuit $Q$ is $W$, then $G$, then $W$ again: $$Q = W\,G\,W.$$(6) The rotation angle $\theta$ of the circuit is the real number $$\theta = \arccos\frac35.$$(7)^✦

For ancilla outcomes $a'$ and $b'$ and a target label $t$, all in $\{0,1\}$, the amplitude $A_{a'b'}(t)$ of the outcome $a'b'$ on the target state $|t\rangle$ is the complex number $$A_{a'b'}(t) = \Bigl(\frac{1}{\sqrt2}\Bigr)^4 \sum_{a,b\in\{0,1\}} i^{\,t\oplus ab}\, (-1)^{aa'}(-1)^{bb'},$$(8)^✦ with $t\oplus ab$ the sum modulo two. It is the amplitude of $|a'\rangle|b'\rangle|t\rangle$ in $Q|0\rangle|0\rangle|t\rangle$.

Measuring the Ancillas

A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$; a pure state $|\psi\rangle$ gives the state $|\psi\rangle\langle\psi|$, the projector onto its vector. 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$, with $\sum_i M_i^\dagger M_i = 1$.^✦ The positive operator valued measure (POVM) of a measurement on $S$ with operators $M_i$ is the family of effects $E_i = M_i^\dagger M_i$; the probability of the outcome $i$ on a state $\rho$ of $S$ is given by the Born rule, $p(i) = \operatorname{Tr}(E_i\rho) = \operatorname{Tr}(M_i\rho M_i^\dagger)$.

The projective measurement of $S$ in an orthonormal basis $\{|b_i\rangle\}$ has the operators $M_i = |b_i\rangle\langle b_i|$.^✦ A measurement with operators $M_i$ on $S$ is made on the first wires of $S\otimes T$ with the operators $M_i\otimes 1$, and one on $T$ is made on the last wires with $1\otimes M_i$. The measurement of the control qubit, on a composite of a qubit with $S$, is the projective measurement of the qubit in the computational basis, with operators $|i\rangle\langle i|\otimes 1$.^✦ Two measurements $L$ and $M$ of $S$, with operators $L_l$ and $M_m$, performed in turn with $L$ first, form the cascaded measurement of $S$ with outcomes $(l,m)$ and operators $N_{(l,m)} = M_mL_l$.^✦

The measurement of both ancillas has, for each outcome $a'b'$, the measurement operator $$N_{a'b'} = (1\otimes|b'\rangle\langle b'|\otimes 1)\,(|a'\rangle\langle a'|\otimes 1\otimes 1) = |a'\rangle\langle a'|\otimes|b'\rangle\langle b'|\otimes 1.$$(9)

The Claim

What Is Checked

The claim is stated over the circuit $Q$ of (6), the measurement (9) of both ancillas with its Born probabilities, the amplitudes (8) and the angle (7), with the gates $R_z(\theta)$ and $Z$ acting on the target.

About these constructions the library proves that the controlled gate (3) is unitary for every unitary $U$, and with it the Toffoli gate; that $H$, $X$, $Z$, $S$ and $R_z(\theta)$ are unitary because their matrices are; and that products and tensor products of unitaries are unitary. It proves too that a unitary carries a pure state to a unit vector, that the product of two pure states has unit norm, that $|\psi\rangle\langle\psi|$ is a state, a positive operator of unit trace, and that every measurement built here, on the first or last wires or as a cascade, has operators $M_i$ with $\sum_i M_i^\dagger M_i = 1$.