Past exam of the computer science course of the University of Oxford / 2019 / Quantum information / 3 / f / Solution

Use the Bernstein-Vazirani algorithm: initialize n qubits in $|0^n⟩$, apply $H^{\otimes n}$, query the supplied phase oracle once, apply $H^{\otimes n}$ again, and measure all n computational bits. Immediately after the query the state iswhere the dot product in the exponent is taken modulo two. The Walsh-Hadamard transform gives amplitudeEvery factor is one if $y_j=a_j$ and zero otherwise. Thus the final state is exactly $|a⟩$, and the measurement outputs a with certainty after one oracle query. This is the character cancellation behind Bernstein-Vazirani phase kickback; because access here is already to the reduced phase oracle, no extra target ancilla or conversion from a bit-flip oracle is required.