Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 57 / 2 / d / Solution

Initialize the register inThis can be prepared by Pauli X gates on the one-bits of $y$, starting from $|0^N⟩$, followed by Hadamard gates on all qubits. Alternatively, prepare the original uniform state and apply Pauli Z gates at those same bit positions. The conjugation calculation givesThe final diagonal sign operator changes no computational basis outcome probabilities. Thus the success probability and the iteration count in part (b) are unchanged. No final correction is needed when the objective is to measure a marked string.