Past exam of the laser science and quantum information processing course of the University of Oxford / 2010 / 6 (DPHY 2752, DPHP 2752)

Source extract: users.physics.ox.ac.uk/~Foot/C2/pdf/C22010Q6.pdf

The Oxford C2 support-page record attributes this extract to 2010. The held page prints the question number and identifiers above, but no year, examination stage or sitting date.

TODO: The remainder of the historical paper is not held; only this supplied question is covered.

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

Use the Hadamard basis states $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$. The Hadamard gate satisfies $H|0⟩=|+⟩$, $H|1⟩=|-⟩$, and $H^2=I$. After the first three Hadamard gates, the full quantum state isThe Pauli X gate obeys $X|-⟩=-|-⟩$. Consequently the Boolean quantum oracle produces phase kickback:Factoring out the ancilla qubit, the four states immediately after the function oracle areThe final Hadamard gates send $|+⟩$ to $|0⟩$ and $|-⟩$ to $|1⟩$. In particular, the printed quantum circuit includes a final Hadamard gate on the ancilla qubit too. Its full outputs, ordered as $x_1,x_2,y$, areThus one oracle call identifies $a$ with certainty: a computational-basis measurement of the first two qubits returns $a_1{a}_2$. The ancilla qubit returns to $|1⟩$ and carries no additional information about $a$. The Bernstein-Vazirani algorithm turns the pattern of relative quantum phases into a definite computational-basis state.

The required identity is CNOT control reversal in the Hadamard basis. To derive it using standard quantum circuit identities, let $\mathrm{CZ}$ be the Controlled-Z gate, which multiplies $|11⟩$ by $-1$ and fixes the other computational-basis states. Since $HXH=Z$,The Controlled-Z gate is symmetric in its two wires. Combining this symmetry with $H^2=I$ givesThis is an exact operator identity, including its global phase, and applies to arbitrary inputs. One can also check it directly from the orthogonal projectors $P_b=|b⟩⟨b|$: conjugating $C_{1\to 2}=P_0\otimes I+P_1\otimes X$ by $H\otimes H$ gives

For the three-wire quantum circuit, put $W=H^{\otimes 3}$. Conjugation distributes over products because $W^2=I$: $WABW=(WAW)(WBW)$. Each CNOT gate in $U_a$ therefore reverses direction, while the Hadamard gates on untouched wires cancel. The Hadamard-conjugated linear oracle isThese are the simplified quantum circuits in the figure: for $a=00$ there are no gates; for $a=01$ there is $C_{y\to 2}$; for $a=10$ there is $C_{y\to 1}$; and for $a=11$ there are both. The ancilla qubit becomes their common control. On every computational-basis state, the entire simplified circuit acts asStarting the data qubits at $|00⟩$, the prescribed computational basis preparation of the ancilla qubit must therefore be $|1⟩$: it activates the required flips and gives $|a⟩|1⟩$. Starting it at $|0⟩$ instead gives $|00⟩|0⟩$ for every $a$, so no information is obtained.

More generally, an initial ancilla qubit state $\alpha |0⟩+\beta |1⟩$ in this same fixed quantum circuit givesFor nonzero $a$, the desired data output has probability $|\beta {|}^2$, and exact identification for every $a$ requires $\alpha =0$. This condition refers to the displayed ancilla preparation for the Bernstein-Vazirani algorithm: the state entering the function oracle must be $|-⟩$, up to global phase. Other quantum state preparation procedures that deliver this same state are equivalent; $|1⟩$ is the prescribed input before the first Hadamard gate.

For arbitrary $n$, linearity of the linear Boolean function suppliesThis decomposition is for analysis: the Bernstein-Vazirani algorithm calls the unknown function oracle as one supplied operation. The common control starts at $1$, so the simplified quantum circuit takes $|0{⟩}^{\otimes n}|1⟩$ to $|a⟩|1⟩$. Equivalently, phase kickback gives a product statewhich the final Hadamard transform decodes to $|a⟩$. Thus one quantum oracle call suffices for every $n\ge 1$, compared with $n$ classical calls. This counts function oracle uses; the surrounding Hadamard gates and final computational-basis measurement still act on $n+1$ and $n$ qubits, respectively.