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

Настройка фазы для точного поиска Гровера

Изменим алгоритм Гровера так, чтобы оракул действовал как

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

$$O|x\rangle=e^{i\phi}|x\rangle.$$

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

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

Покажите, что замена стандартной итерации на

$$\widetilde G=H^{\otimes n}\left[(1-e^{i\phi})|0\rangle\langle0|-I\right]H^{\otimes n}O$$

при достаточно большом $M/N$ позволяет подобрать $\phi$, чтобы найти цель с вероятностью 1 после одной итерации. Для каких значений $M/N$ такая фаза существует?