Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 15D (Quantum Information and Computation)

A Bell measurement is the projective measurement of two qubits in the orthonormal Bell state basisIts four classical outcomes identify the corresponding rank-one projector.

Alice holds the unknown input $|\alpha ⟩$ and one qubit of a shared $|{\varphi }^{+}⟩$ pair; Bob holds the other. Alice performs a Bell measurement on her two qubits and sends its two-bit outcome to Bob. For outcomes
${\varphi }^{+},{\varphi }^{-},{\psi }^{+},{\psi }^{-}$, Bob's qubit is respectivelyup to global phase. Bob applies respectively $I,Z,X,ZX$ and obtains $|\alpha ⟩$. This is quantum teleportation.

Replacing the resource by $(I\otimes U)|{\varphi }^{+}⟩$ applies $U$ to Bob's uncorrected output. If $P\in \{I,Z,X,XZ\}$ labels the Bell outcome, the uncorrected state is $UP|\alpha ⟩$, and the unchanged correction producesThus the four outputs are $U|\alpha ⟩$, $ZUZ|\alpha ⟩$, $XUX|\alpha ⟩$, and $(XZ{)}^{-1}U(XZ)|\alpha ⟩$, up to global phases.

For two nonorthogonal input states $|\alpha ⟩,|\beta ⟩$, preservation of inner products by $G$ givesHence the two output-program states agree up to phase. Any two qubit states can be joined through a state nonorthogonal to both, so after absorbing phases
$|{\tilde{P}}_U⟩$ is independent of the input.

Inner-product preservation between programs for $U$ and $V$ givesfor all $|\alpha ⟩,|\beta ⟩$. If $⟨P_U|P_V⟩\ne 0$, this identity forces every matrix element of $U^{†}V$ to be the same scalar multiple of the corresponding identity matrix element. Hence $U^{†}V=e^{i\theta }I$, contrary to physical distinctness. Therefore

There are uncountably many physically distinct one-qubit unitaries. Part (ii) would require an orthogonal program state for every one, whereas a $K$-qubit register has dimension only $2^K$. This contradiction is the no-programming theorem, so no deterministic gate satisfying (PROG) exists.

Yes. Store $U$ in the two-qubit programApply the teleportation Bell measurement to the input and the first program qubit. On the ${\varphi }^{+}$ outcome, which has probability $1/4$ independently of $U$ and $|\alpha ⟩$, the remaining qubit is exactly $U|\alpha ⟩$. Accept that heralded outcome and declare failure otherwise. This gives a probabilistic universal programmable gate with constant success probability $p=1/4$.