Past exam of the laser science and quantum information processing course of the University of Oxford / 2010 / 6 / 1 / Solution

Write $a=a_1{a}_2$ and $x=x_1{x}_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_1{x}_1\oplus a_2{x}_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:

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$.

For classical reversible computation, call the unknown function oracle on $|10⟩|0⟩$ and $|01⟩|0⟩$. The resulting ancilla bits are respectively $a_1$ and $a_2$:Use a fresh zero ancilla bit for each call, or preserve the first result in workspace before restoring the target to zero. Thus 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