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

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$.