Точный квантовый поиск с согласованными фазами

Квантовый поиск Гровера можно представить как непрерывное моделирование гамильтониана

$$H=|x\rangle\langle x|+|\psi\rangle\langle\psi|,$$

где начальное состояние $|\psi\rangle$ известно, а решение $|x\rangle$ неизвестно. Оракул реализует $U_x(\Delta t)=\exp(-i|x\rangle\langle x|\Delta t)$ для выбранного вами $\Delta t$. Доступен также $U_\psi(\Delta t)=\exp(-i|\psi\rangle\langle\psi|\Delta t)$, поскольку $|\psi\rangle$ известно.

(a) Покажите, что $U(\Delta t)=U_\psi(\Delta t)U_x(\Delta t)$ с точностью до общей фазы записывается следующим образом. Положим $c=\cos(\Delta t/2)$, $s=\sin(\Delta t/2)$. Тогда

$$\begin{aligned} U(\Delta t)\sim{}&(c^2-s^2\vec\psi\cdot\hat z)I\\ &-i\bigl[sc(\vec\psi+\hat z)\\ &\qquad+s^2(\vec\psi\times\hat z)\bigr]\cdot\vec\sigma. \end{aligned}$$

Используйте представления Блоха

$$|x\rangle\langle x|=(I+Z)/2=(I+\hat z\cdot\vec\sigma)/2,$$

$$\hat z=(0,0,1),\qquad |\psi\rangle\langle\psi|=(I+\vec\psi\cdot\vec\sigma)/2.$$

Можно выбрать $\vec\psi=(2\alpha\beta,0,\alpha^2-\beta^2)$: гамильтониан действует в пространстве, порождённом $|x\rangle$ и ненормированным ортогональным вектором $|y\rangle=|\psi\rangle-\langle x|\psi\rangle|x\rangle$.

(b) Докажите, что при $\Delta t=\pi$ операторы $U_\psi,U_x$ становятся отражениями, используемыми в алгоритме поиска Гровера.

(c) Выберите $\Delta t$ так, чтобы получить поиск за $O(\sqrt N)$ обращений к оракулу с конечным состоянием ровно $|x\rangle$: вероятность успеха должна равняться 1. Обозначения двумерного базиса: $\alpha=|\langle x|\psi\rangle|$, $\beta=\sqrt{1-\alpha^2}$, а ортогональный вектор $|\bar y\rangle=|y\rangle/\beta$ нормирован. Для(c) берётся стандартный равномерный вход поиска по $N$ состояниям: $\alpha=1/\sqrt N$, как в официальном разборе.