= Solution
No classical one-query algorithm can determine $x_0$ with certainty. If it queries a string $x$ and receives $1$, then it knows $x_0=x$. But if it receives $0$, each of the other three strings remains compatible with the response. Randomization cannot remove this ambiguity when certainty is required. Thus
$$
\boxed{\text{one classical query is insufficient}.}
$$
Indeed, three adaptive classical queries are necessary and sufficient in the worst case: after three negative answers, the unqueried fourth string must be $x_0$.
Back to article page
