= Solution
Write $a=a_1a_2$ and $x=x_1x_2$, with the top wire carrying $x_1$, the middle wire $x_2$, and the bottom wire the <ancilla bit> $y$. The <binary inner product> is $a\cdot x=a_1x_1\oplus a_2x_2$, where $\oplus$ is <exclusive or>. Let $C_{j\to y}$ denote a <CNOT gate> controlled by wire $j$ and targeting $y$. The four <linear Boolean functions> and their <Boolean quantum oracles> are:
|| $a$
|| $f_a(x)$
|| <Reversible circuit> for $U_a$
| $00$
| $0$
| $I$: three unchanged wires
| $01$
| $x_2$
| $C_{2\to y}$
| $10$
| $x_1$
| $C_{1\to y}$
| $11$
| $x_1\oplus x_2$
| $C_{2\to y}C_{1\to y}$
The <CNOT gates> in the last row commute: their common target acquires the <exclusive or> of the two controls. Each input wire is preserved, and applying any of these <reversible circuits> twice restores $y$.
\Image[/past-exam-of-the-laser-science-and-quantum-information-processing-course-of-the-university-of-oxford/2010/6-circuits.png]
{title=The four two-bit linear oracles and their exact simplifications after Hadamard gates on all three wires; a filled dot is a control and a circled plus is a target}
For classical <reversible computation>, call the unknown <function oracle> on $|10\rangle|0\rangle$ and $|01\rangle|0\rangle$. The resulting <ancilla bits> are respectively $a_1$ and $a_2$:
$$
U_a|10\rangle|0\rangle=|10\rangle|a_1\rangle,
\qquad U_a|01\rangle|0\rangle=|01\rangle|a_2\rangle.
$$
Use a fresh zero <ancilla bit> for each call, or preserve the first result in workspace before restoring the target to zero. Thus \b[two classical calls determine the two-bit string].
For $n$ input <bits>, query the <standard basis> strings $e_j$, since $a\cdot e_j=a_j$. This gives an upper bound of $n$ calls. It is also optimal for exact identification: every classical query reveals at most one new <bit>, since $x$ is unchanged and $y\oplus f_a(x)$ reveals just $f_a(x)$ when $y$ is known. A depth-$k$ <decision tree> has at most $2^k$ answer histories, but must distinguish $2^n$ possible hidden strings. Hence $k\ge n$, including adaptive strategies. The <classical query complexity of linear Boolean function identification> is therefore
$$
\boxed{D(n)=n\quad(n\ge1).}
$$
Back to article page
