The Exercise

The first stage of phase estimation couples a register of $t$ control qubits to a target system through controlled powers $U, U^2, U^4, \dots, U^{2^{t-1}}$ of a unitary $U$ of the target, one power to each control. The controls start in a computational basis state $|j\rangle$, with $0 \le j < 2^t$, and the target in a state $|u\rangle$. The exercise is to show that the sequence of controlled operations takes $|j\rangle|u\rangle$ to $|j\rangle U^j|u\rangle$.^✦ The state $|u\rangle$ need not be an eigenstate of $U$.

A Quantum System

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $|u\rangle$ of $S$ is a vector of unit norm in the state space of $S$, $\langle u | u \rangle = 1$, determined physically up to a global phase.^✦

A unitary $U$ of $S$, the evolution of $S$ as a closed system, is an operator on the state space of $S$ with $$U^\dagger U = U U^\dagger = I .$$(1)^✦ Acting on a pure state $|u\rangle$ of $S$, the unitary $U$ gives the pure state $U|u\rangle$.^✦

The Control Register

For a system $S$ and a number $t$, the register of $t$ control qubits around $S$ is the system obtained by composing $t$ qubits with $S$ on its left, one at a time: $$\mathrm{qubit}^{\otimes t} \otimes S = \mathrm{qubit} \otimes \bigl( \mathrm{qubit}^{\otimes (t-1)} \otimes S \bigr) , \qquad \mathrm{qubit}^{\otimes 0} \otimes S = S .$$(2)^✦ Its wires are labelled $0, \dots, t-1$ from the outside in: wire $0$ is the outermost, and wire $t-1$ lies next to the target $S$.

The value $j$ of a bit string $b = b_0 b_1 \cdots b_{t-1}$ of length $t$ is the number it writes in binary, with $b_0$ the most significant bit: $$j = \sum_{k=0}^{t-1} b_k \, 2^{\,t-1-k} = 2^{t-1} b_0 + 2^{t-2} b_1 + \cdots + b_{t-1} .$$(3)^✦

For a bit string $b$ of length $t$ with value $j$ and a pure state $|u\rangle$ of $S$, the input state $|j\rangle|u\rangle$ is the pure state of the register (2) with wire $k$ in the computational basis state $|b_k\rangle$ and the target in $|u\rangle$, $$|j\rangle|u\rangle = |b_0\rangle \otimes |b_1\rangle \otimes \cdots \otimes |b_{t-1}\rangle \otimes |u\rangle .$$(4)^✦

For a unitary $U$ of $S$ and a number $t$ of controls, the controlled powers of $U$ are the unitary $C_t(U)$ of the register in which wire $k$ controls the power $U^{2^{t-1-k}}$ acting on the target alone, for each $k$ from $0$ to $t-1$.^✦ The exponent is the weight of the bit on wire $k$ in (3). With no controls, $C_0(U)$ is the identity on $S$.

The Claim

What Is Checked

The claim is stated over a unitary $U$ of a quantum system $S$, the register of $t$ control qubits around $S$, the controlled powers $C_t(U)$ of $U$ on that register, the input state $|j\rangle|u\rangle$ built from a bit string $b$ and a pure state $|u\rangle$ of $S$, and the value $j$ of the bit string $b$.