№ 987Квантовые вычисленияУровень 3

Точный успех после одного шага Гровера

В алгоритме поиска Гровера среди $N$ состояний есть $M$ целевых. Чёрный ящик действует так:

Для целевого состояния:

$$O|x\rangle=-|x\rangle.$$

Для остальных состояний:

$$O|x\rangle=|x\rangle.$$

После одной итерации алгоритма целевое состояние находится с вероятностью 1. Что можно сказать об отношении $M/N$?