The Exercise

A qubit controls a unitary $U$ acting on a second system $S$, the target. In one circuit the controlled gate acts first, applying $U$ to the target when the control is $|1\rangle$ and nothing when it is $|0\rangle$, and the control is then measured in the computational basis. In the other the control is measured first, and its outcome, now a classical bit, decides whether $U$ is applied to the target. The exercise asks to show that the two circuits cannot be told apart: the measurement of a control qubit commutes with the gate it controls.

A Qubit and a Target

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The composite system $S \otimes T$ of two quantum systems $S$ and $T$ is the system whose state space is the tensor product of their state spaces.^✦

A pure state $|\psi\rangle$ of a system $S$ is a unit vector in the state space of $S$.^✦ A state $\rho$ of $S$, pure or mixed, is a positive operator of unit trace on the state space of $S$.^✦

The qubit $Q$ is the two level system whose state space is $\mathbb{C}^2$ itself.^✦ Its computational basis states are the pure states $|0\rangle = (1,0)$ and $|1\rangle = (0,1)$.^✦ The exercise takes place in the composite system $Q \otimes S$, the control first and the target second.

Gates

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ A state $\rho$ of $S$ evolves under a unitary $U$ of $S$ as $$\rho \mapsto U \rho\, U^\dagger .$$(1) The identity evolution of $S$ is the unitary whose operator is the identity $1$.^✦ For unitaries $U$ of $S$ and $V$ of $T$, the product unitary $U \otimes V$ is the unitary of $S \otimes T$ whose operator is the tensor product of the two; with the identity on the first factor it gives the gate $1 \otimes V$, which acts with $V$ on the second factor and leaves $S$ alone.

For a unitary $U$ of $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$ with operator $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(2)^✦ For a unitary $U$ of $S$, the classically controlled gate is the family of unitaries $V_i$ of $Q \otimes S$, one for each outcome $i \in \{0,1\}$ of the control: the identity evolution for $0$, and $U$ on the target for $1$, $$V_0 = 1, \qquad V_1 = 1 \otimes U .$$(3)

Measuring the Control

A measurement on a system $S$ with a finite set of outcomes $\iota$ is a family of measurement operators $M_i$ on the state space of $S$, one for each outcome $i \in \iota$, that satisfies the completeness relation $$\sum_i M_i^\dagger M_i = 1 .$$(4)^✦ The effects $E_i = M_i^\dagger M_i$ of a measurement $\{M_i\}$ on $S$ form the positive operator valued measure (POVM) of the measurement. On a state $\rho$ of $S$ the outcome $i$ occurs with the probability given by the Born rule, $p(i) = \operatorname{Tr}(M_i \rho M_i^\dagger) = \operatorname{Tr}(E_i \rho)$, and when it occurs with $p(i) \neq 0$ it leaves the system in the state $$\rho_i = \frac{M_i \rho M_i^\dagger}{p(i)} .$$(5)

The projective measurement of $S$ in an orthonormal basis $\{|b_i\rangle\}$ is the measurement whose operator for the outcome $i$ is the projector $|b_i\rangle\langle b_i|$.^✦ The measurement on the first factor of a composite $S \otimes T$ given by a measurement on $S$ with operators $M_i$ is the measurement of $S \otimes T$ with the same outcomes and operators $M_i \otimes 1$.^✦ The measurement of the control qubit is the projective measurement of $Q$ in its computational basis, made in this way on the first factor of $Q \otimes S$; its operators are $$P_i = |i\rangle\langle i| \otimes 1, \qquad i = 0, 1 .$$(6)^✦

The Claim

The controlled gate does not change the statistics of this measurement: for every state $\rho$ of $Q \otimes S$ and each outcome $i$, $$\operatorname{Tr}\bigl(P_i\, C(U) \rho\, C(U)^\dagger\bigr) = \operatorname{Tr}(P_i \rho) .$$(7)^✦ Write $p(i)$ for this common probability.

What Is Checked

The claim (8) is stated over states of the composite system $Q \otimes S$ of the qubit and a target, the controlled gate $C(U)$ of (2), the measurement of the control qubit (6) with the state (5) after an outcome, and the classically controlled gate $V_i$ of (3).

About these constructions the library proves that $C(U)$ is unitary, and that a product of unitaries, $1 \otimes U$ among them, is unitary. It proves that the projective measurement in a basis and the measurement on the first factor satisfy the completeness relation (4), and that a state evolved by a unitary as in (1), or left by an outcome of nonzero probability as in (5), is again a positive operator of unit trace.