One-step exact Grover search with a quarter of the inputs marked

ID: one-step-exact-grover-search-with-a-quarter-of-the-inputs-marked

Start from , negate amplitudes at marked indices, and apply . If the marked fraction is , the oracle-state mean amplitude is . Inversion about the mean therefore gives amplitudes on unmarked indices and on marked ones. The marked success probability is . At it is exactly one: unmarked amplitudes vanish and each marked amplitude is . The output is uniform among the marked indices. This is an exact special case of Grover's algorithm, using one phase oracle call under the stated promise.

New to topics? Read the docs here!