Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 10D / a / Solution

Use the available unitaries to preparein the first register andin the answer qubit. The quantum phase kickback identity givesChoose a unitary $F$ with $F|0⟩=|s⟩$, apply $F^{-1}$ to the first register, and measure it. Its amplitude at $|0⟩$ isThis equals $+1$ or $-1$ for a constant string and zero for a balanced string. Thus outcome $0$ means constant, while every other outcome means balanced, with certainty after one oracle query. This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary.