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

With the restricted operations, begin in $|0⟩|0⟩$ and apply $F$ to the first register:Now applyFor every basis state this compute-phase-uncompute construction acts asThe first register is therefore the same phase state used in part (a). Apply $F^{-1}$ and measure. Again, outcome $0$ occurs with probability one for a constant string and probability zero for a balanced string. The construction uses exactly two queries to $O_x$ and only the permitted operations.