= Solution
In the <oracle machine> model, a function is accessed through a black box whose internal gate cost is excluded; the resource counted is the number of calls. A reversible classical oracle maps basis inputs as $(x,y)\mapsto(x,y\oplus f(x))$. Its <quantum oracle> extension applies the same permutation coherently to arbitrary superpositions, without measuring its input. A classical random mixture of inputs is not that coherent extension.
Write the two truth-table entries as $f(0)=b$, $f(1)=a\oplus b$. Then $f(x)=ax\oplus b$, with the four cases
$$
\begin{array}{c|c|c|c}
(a,b)&f(0)&f(1)&f(x)\\\hline
(0,0)&0&0&0\\
(0,1)&1&1&1\\
(1,0)&0&1&x\\
(1,1)&1&0&1\oplus x
\end{array}.
$$
Two classical query circuits, $(0,0)\xrightarrow{U_f}(0,f(0))$ and $(1,0)\xrightarrow{U_f}(1,f(1))$, recover the whole function with certainty. One call fixes only one entry, leaving two compatible functions; hence two are necessary classically. Randomization cannot remove this obstruction to certainty.
The minimum for \b[full exact function identification remains two even with coherent quantum queries]. To see this, expand the oracle target into its $X$ eigenstates: it is identity on $|+\rangle$, and gives phases $(-1)^{f(x)}$ on $|x\rangle|-\rangle$. Any one-query input, including an auxiliary system, has orthogonal sector weights $w_+$, $w_0$ and $w_1$ summing to one. The output overlap between functions differing only at $0$ is $1-2w_0$, so perfect distinction requires $w_0=1/2$; differing only at $1$ likewise requires $w_1=1/2$. Then $w_+=0$, but functions differing at both entries have overlap $1-2(w_0+w_1)=-1$. They are the same ray rather than distinguishable states. Thus one query cannot identify all four functions. The following one-query task recovers only whether the entries agree.
Back to article page
