Past exam of the laser science and quantum information processing course of the University of Oxford / 2015 / 6

Use a classical target bit $t$ and initialized auxiliary bits. The NOT gate maps $t\mapsto 1\oplus t$, the CNOT gate maps $(a,t)\mapsto (a,t\oplus a)$, and the Toffoli gate maps $(a,b,t)\mapsto (a,b,t\oplus ab)$. They are bijections and are their own inverses. Explicit circuits with their retained input wires are:

These maps also give the truth tables for all input combinations. AND and OR are not themselves reversible maps if the inputs are discarded; the retained inputs are what make their implementations reversible. Classical CLONE copies a known orthogonal computational basis alphabet; the no-cloning theorem forbids interpreting it as a copier of arbitrary quantum superpositions.

A Boolean circuit can express any finite Boolean function using AND, OR and NOT. Replace its operations by the reversible versions, keeping inputs and intermediate bits. Copy the final output into a fresh answer register with CNOT gates, then run the entire computing network backward. Intermediate auxiliary bits return to zero, yieldingThis compute-copy-uncompute construction proves universality in the usual model with initialized auxiliary bits. If $f$ is a reversible permutation, compute $f(x)$, use a reversible implementation of $f^{-1}$ to clear $x$, and swap registers, leaving $f(x)$ with clean auxiliaries. The ancillary-resource qualification matters; a blanket claim about all permutations on an arbitrary fixed number of unassisted wires has parity restrictions.

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 casesTwo classical query circuits, $(0,0)\stackrel{U_f}{\to }(0,f(0))$ and $(1,0)\stackrel{U_f}{\to }(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 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 $|+⟩$, and gives phases $(-1{)}^{f(x)}$ on $|x⟩|-⟩$. 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.

A constant function has $f(0)=f(1)$, whereas a balanced one has one zero and one one, so $f(0)\ne f(1)$. The four oracles require only the following circuits:Prepare $|0⟩|1⟩$, apply a Hadamard gate to each qubit, apply the oracle once, apply another Hadamard gate to the first qubit, and measure that first wire in the computational basis. Immediately before the oracle the state is $|+⟩|-⟩$. The identity $X|-⟩=-|-⟩$ gives phase kickback:The output is certainly zero for constant and one for balanced. In circuit terms the target $X$ contributes only a global sign, and a controlled $X$ with target $|-⟩$ acts as $Z$ on the control; $HZH=X$ then turns that phase into a measured bit. These identities prove the network for all four explicit oracles. The unused sign contains $f(0)$ only as a global phase, consistent with the full-identification lower bound.