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.
Articles by others on the same topic
There are currently no matching articles.