The Exercise

A register of $n+1$ qubits is in a state $\rho$. The quantum Fourier transform on its $2^{n+1}$ levels is applied, and then every qubit is measured in the computational basis. The exercise is to obtain the same measurement with no two qubit gate: the qubits are measured one at a time, every gate acts on a single qubit, and a gate may depend on the outcomes already read.

A Register of Qubits

A quantum system $S$ is a physical object whose state space is a finite dimensional complex Hilbert space.^✦ The qudit with $d$ levels is the system whose state space is $\mathbb{C}^d$, and the qubit $Q$ is the qudit with two levels, the system whose state space is $\mathbb{C}^2$, with computational basis $|0\rangle, |1\rangle$.

A state $\rho$ of $S$ is a density operator on the state space of $S$, that is, a positive operator of unit trace. A pure state $\psi$ of $S$ is a unit vector $|\psi\rangle$ in the state space of $S$, and it determines the state $|\psi\rangle\langle\psi|$, the projector onto that vector. A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ A unitary $U$ of $S$ takes a state $\rho$ of $S$ to the state $U \rho U^\dagger$ and is also called an evolution of $S$; the identity evolution of $S$ is the unitary $1$.

The register $Q_n$ of $n+1$ qubits is built by composing one qubit at a time on the left, $$Q_0 = Q, \qquad Q_{n+1} = Q \otimes Q_n ,$$(1)^✦ and its wires are numbered $0, 1, \dots, n$ from the left. A string of bits $r = (r_0, \dots, r_n)$ gives the computational basis state of $Q_n$ with $r_t$ on wire $t$, $$|r\rangle = |r_0\rangle \otimes |r_1\rangle \otimes \cdots \otimes |r_n\rangle .$$(2)^✦

An identification $e$ of a system $S$ with a system $T$ is a linear isometric bijection from the state space of $S$ onto that of $T$; it carries a unitary $U$ of $S$ to the evolution $e\, U e^{-1}$ of $T$. The qudit with $2^{n+1}$ levels is identified with $Q_n$ by the identification $e_n$ that splits off one qubit at a time along $\mathbb{C}^{2m} \cong \mathbb{C}^2 \otimes \mathbb{C}^m$, for every $m \geq 1$; for $n = 0$ it is the identity of the qubit.^✦

The Fourier Transform

For a dimension $d \geq 1$, let $\omega = e^{2\pi i/d}$ be the primitive $d$th root of unity.^✦ The Fourier matrix of dimension $d$ is the complex $d \times d$ matrix with entries $$F_{kj} = \frac{\omega^{jk}}{\sqrt{d}}, \qquad j, k = 0, 1, \dots, d-1,$$(3) and the quantum Fourier transform $F$ is the evolution of the qudit with $d$ levels whose matrix in the computational basis is (3). On the register $Q_n$ the transform is the one on $2^{n+1}$ levels carried along $e_n$, $$F_n = e_n\, F\, e_n^{-1} .$$(4)^✦

Measurements

A measurement $\mathcal{M}$ 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 = 1$.^✦ The positive operator valued measure of $\mathcal{M}$ assigns to the outcome $i$ the effect $E_i = M_i^\dagger M_i$.^✦ Performed on a state $\rho$, the measurement gives $i$ with the probability $$p_{\mathcal{M}}(i \mid \rho) = \operatorname{Tr}(M_i \rho M_i^\dagger) = \operatorname{Tr}(E_i \rho),$$(5) and when this probability is not zero the state after the outcome is $M_i \rho M_i^\dagger / p_{\mathcal{M}}(i \mid \rho)$.

The measurement $\mathcal{M}_n$ of every wire of $Q_n$ in the computational basis has the bit strings $r$ as outcomes, $r_t$ being the bit read on wire $t$.^✦ On one qubit it is the measurement in the basis $|0\rangle, |1\rangle$; on $Q_{n+1}$, split as in (1), it reads the first qubit and then performs $\mathcal{M}_n$ on the rest.^✦

The Semiclassical Transform

The phase gate $P(\alpha)$ with angle $\alpha$ is the unitary of the qubit that is diagonal in the computational basis, $P(\alpha) = \operatorname{diag}(1, e^{i\alpha})$.^✦ For a unitary $g$ of the qubit and a wire $t$ of $Q_n$, the gate $g^{(t)}$ on wire $t$ is the unitary of $Q_n$ that applies $g$ to wire $t$ and the identity to every other wire.^✦ A sequence of wires and angles $(t_1, \alpha_1), \dots, (t_m, \alpha_m)$ gives the cascade of phase gates $$\Phi = P(\alpha_1)^{(t_1)}\, P(\alpha_2)^{(t_2)} \cdots P(\alpha_m)^{(t_m)} .$$(6)^✦

On the wires of $Q_n$ take the angles $$\theta_t = \frac{2\pi \cdot 2^{\,n-t}}{2^{n+2}} = \frac{2\pi}{2^{t+2}}, \qquad t = 0, 1, \dots, n,$$(7)^✦ so that $P(\theta_t)$ is the book’s gate $R_{t+2}$, with $R_k = \operatorname{diag}(1, e^{2\pi i/2^k})$. For a bit $i$, the correction $C_i$ on $Q_n$ is the identity evolution for $i = 0$ and, for $i = 1$, the cascade (6) with $P(\theta_t)$ on each wire $t$: $$C_0 = 1, \qquad C_1 = P(\theta_0)^{(0)}\, P(\theta_1)^{(1)} \cdots P(\theta_n)^{(n)} .$$(8)^✦

Write $\mathcal{N} \circ U$ for a measurement $\mathcal{N}$ performed after a unitary $U$, and $\mathcal{Z}[\mathcal{N}_i]$ for the measurement on $Q \otimes Q_n$ that reads wire $0$ in the computational basis and, on the outcome $i$, performs a measurement $\mathcal{N}_i$ on the remaining register $Q_n$. With $H$ the Hadamard gate, the semiclassical measured transform $\mathcal{S}_n$ is the measurement on $Q_n$ defined by $$\mathcal{S}_0 = \mathcal{M}_0 \circ H, \qquad \mathcal{S}_{n+1} = \mathcal{Z}\bigl[\mathcal{S}_n \circ C_i\bigr] \circ H^{(0)} .$$(9)^✦ Its outcomes on $Q_{n+1}$, the bit read on wire $0$ together with an outcome of $\mathcal{S}_n$, are relabelled as strings of $n+2$ bits.

The Claim

Parts (10) and (12) answer the exercise.

What Is Checked

The claim is stated over the transform $F_n$ of (4), carried to the register from the qudit with $2^{n+1}$ levels, the measurement $\mathcal{M}_n$ of every wire, the semiclassical transform (9) with its corrections (8), the gates on single wires and the basis states (2), through the probability (5) and the state after an outcome.

About these constructions the library proves that the Fourier matrix is unitary, so that $F$ is a unitary of the qudit, and that a unitary carried along an identification is again unitary, which makes $F_n$ one. The phase gate $P(\alpha)$ is unitary, as a diagonal operator whose entries have unit modulus, and the effects $E_i$ of a measurement are positive and sum to $1$. Conjugation by a unitary takes density operators to density operators; the state after an outcome of nonzero probability, and the projector $|\psi\rangle\langle\psi|$ onto a unit vector, are density operators as well.