The Exercise

Phase estimation runs on two registers: a control register $C$, measured at the end to give an estimate of a phase, and a target register $S$. With the target in an eigenstate $|u_j\rangle$ of the unitary whose phases are estimated, the procedure leaves the control in a state $|\varphi_j\rangle$ and the target in $|u_j\rangle$. The eigenstates $|u_j\rangle$ form an orthonormal basis of the target, and a target prepared in a superposition $\sum_j c_j |u_j\rangle$ ends, by linearity, with the two registers in $$|\Psi\rangle = \sum_j c_j \, |\varphi_j\rangle \otimes |u_j\rangle .$$(1)

Suppose that measuring the control in the state $|\varphi_k\rangle$ gives a good estimate, an outcome in a set $G$, with probability at least $1-\epsilon$. The exercise asks to show that measuring the control of $|\Psi\rangle$ in the same way, and the target in the basis of eigenstates, gives a good estimate together with the eigenstate $|u_k\rangle$ with probability at least $|c_k|^2(1-\epsilon)$.

Systems and States

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The composite system $A \otimes B$ of two quantum systems $A$ and $B$ is the quantum system whose state space is the tensor product of the state spaces of $A$ and $B$.^✦ The two registers of phase estimation form the composite system $C \otimes S$.

A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦ A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$.^✦ A pure state $|\psi\rangle$ of $S$ determines the state $|\psi\rangle\langle\psi|$ of $S$, the projector onto the vector $|\psi\rangle$.^✦

Measurements

A measurement $M$ on a quantum system $S$ with a finite set $\Omega$ of outcomes is a family of operators $M_i$ on the state space of $S$, one for each outcome $i \in \Omega$, satisfying the completeness relation $$\sum_{i \in \Omega} M_i^\dagger M_i = 1 .$$(2)^✦ The positive operator valued measure (POVM) of $M$ assigns to the outcome $i$ the effect $E_i = M_i^\dagger M_i$.^✦ The probability of the outcome $i$ when $M$ is performed on a state $\rho$ of $S$ is given by the Born rule, $$p^M_\rho(i) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr) = \operatorname{Tr}(E_i \rho) .$$(3)^✦ On a pure state $|\psi\rangle$ we write $p^M_\psi(i)$ for the probability on its state $|\psi\rangle\langle\psi|$.

The projective measurement of $S$ in an orthonormal basis $\{|u_j\rangle\}$ of its state space, indexed by a finite set $J$, is the measurement on $S$ with outcomes in $J$ whose operator for the outcome $j$ is the projector $|u_j\rangle\langle u_j|$.^✦

For a measurement $M$ on $A$, the measurement $M$ on the first factor of $A \otimes B$ is the measurement on $A \otimes B$ with the same outcomes whose operator for the outcome $i$ is $M_i \otimes 1_B$, with $1_B$ the identity on the state space of $B$.^✦ Likewise a measurement $M$ on $B$, on the second factor, has the operators $1_A \otimes M_i$.^✦

The cascade of two measurements $L$ and $M$ on the same system $S$, with outcome sets $\Omega$ and $\Omega'$, is the measurement on $S$ that performs $L$ and then $M$.^✦ Its outcomes are the pairs $(l, m)$ in $\Omega \times \Omega'$, and its operator for $(l, m)$ is the composite $M_m L_l$.

The joint readout of a measurement $M$ on $C$ and an orthonormal basis $\{|u_j\rangle\}$ of the state space of $S$ is the measurement $N$ on $C \otimes S$ that performs $M$ on the first factor and then the projective measurement in the basis on the second factor.^✦ Its outcomes are the pairs $(i, j)$, and its operators are $$N_{(i,j)} = \bigl(1_C \otimes |u_j\rangle\langle u_j|\bigr)\bigl(M_i \otimes 1_S\bigr) = M_i \otimes |u_j\rangle\langle u_j| .$$(4)

The Claim

In the claim below the states $|\varphi_j\rangle$ and the basis $\{|u_j\rangle\}$ are arbitrary, so the output of phase estimation is a special case of it.

What Is Checked

The claim is stated over the joint readout $N$ of (4) on the composite system $C \otimes S$, and over the Born probabilities (3) of $M$ and of $N$ on the states $|\varphi_k\rangle\langle\varphi_k|$ and $|\Psi\rangle\langle\Psi|$.

The library proves that the projector onto a unit vector is a density operator, so that $|\varphi_k\rangle\langle\varphi_k|$ and $|\Psi\rangle\langle\Psi|$ are states, and that the effects $E_i$ are positive and sum to the identity. It proves the completeness relation (2) for the projectors of an orthonormal basis, which satisfy $P^\dagger P = P$ for each projector $P$ of the basis and sum to the identity; for the operators $M_i \otimes 1_B$ and $1_A \otimes M_i$, since $(M_i \otimes 1_B)^\dagger (M_i \otimes 1_B) = M_i^\dagger M_i \otimes 1_B$; and for the composites $M_m L_l$ of a cascade, from the relations of $L$ and $M$.