= Solution
Prepare the uniform <pure state>
$$
|s\rangle=\frac1{\sqrt d}\sum_{j=0}^{d-1}|j\rangle.
$$
Every <permutation matrix> fixes this <vector>, so `RandomPermute` returns $|s\rangle$ with certainty. Choose an <orthonormal basis> with first <vector> $|\psi_0\rangle=|s\rangle$, 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. Then
$$
\boxed{P_{\rm success}=\frac12\cdot1+\frac12\cdot\frac{d-1}{d}=1-\frac1{2d}.}
$$
This is <invariant-pure-state discrimination against a maximally mixed reset>. It also agrees with the <Holevo–Helstrom theorem>: the <eigenvalues> of $|s\rangle\langle s|-I/d$ are $1-1/d$ once and $-1/d$ with <multiplicity> $d-1$, giving optimal equal-prior success $1/2+\|\rho_P-\rho_R\|_1/4=1-1/(2d)$. This confirms optimal discrimination of these returned states, in addition to constructing the requested strategy.<The Theory of Quantum Information by John Watrous>[§3.1.1, Theorem 3.4 and equation (3.20), optimal binary-state discrimination]{ref} For $d=1$, the actions coincide and the formula correctly gives random-guessing success $1/2$.
Back to article page
