Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 10D / c / 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. ThusIndeed, three adaptive classical queries are necessary and sufficient in the worst case: after three negative answers, the unqueried fourth string must be $x_0$.