Past exam of the laser science and quantum information processing course of the University of Oxford / 2010 / 6 / 2 (10 marks)

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.