Past exam of the computer science course of the University of Oxford / 2019 / Quantum information / 1 / d

Choose $|{\psi }_0⟩=|+⟩$ and its orthogonal companion $|{\psi }_1⟩=|-⟩$. Since $X|+⟩=|+⟩$, either branch of RandomFlip returns the same pure state. Alice therefore obtains label 0 with certainty, andThe alternative choice $|-⟩$ also works: its sign change under $X$ is only a global phase. The useful property is being a Pauli eigenstate of the Pauli X gate.

Use the preparation and measurement from part (i). RandomReset returns the density matrix ${\rho }_R=(|0⟩⟨0|+|1⟩⟨1|)/2=I/2$, a maximally mixed state. In the $|+⟩,|-⟩$ basis its two outcomes each have probability $1/2$. In contrast, RandomFlip always gives outcome 0.

Guess RandomFlip after 0 and RandomReset after 1. With the supplied equal priors,An outcome 1 identifies the reset action, but outcome 0 does not identify the flip action with certainty. For example, Bayes' theorem gives posterior probability $2/3$ for the flip action after 0. The total success rate already accounts for the reset runs that also produce 0.

Prepare the uniform pure stateEvery permutation matrix fixes this vector, so RandomPermute returns $|s⟩$ with certainty. Choose an orthonormal basis with first vector $|{\psi }_0⟩=|s⟩$, for example the quantum Fourier transform basis. Under RandomReset, the returned state is $I/d$, which gives each of the $d$ measurement labels probability $1/d$.

Guess RandomPermute on label 0 and RandomReset on every other label. ThenThis is invariant-pure-state discrimination against a maximally mixed reset. It also agrees with the Holevo–Helstrom theorem: the eigenvalues of $|s⟩⟨s|-I/d$ are $1-1/d$ once and $-1/d$ with multiplicity $d-1$, giving optimal equal-prior success $1/2+\Vert {\rho }_P-{\rho }_R{\Vert }_1/4=1-1/(2d)$. This confirms optimal discrimination of these returned states, in addition to constructing the requested strategy.^[ref] For $d=1$, the actions coincide and the formula correctly gives random-guessing success $1/2$.