Моделирование локального гамильтониана квантовой схемой

Рассмотрим вопрос Фейнмана 1982 года: если классическим компьютерам трудно моделировать квантовую механику, может ли квантовый компьютер делать это лучше?

На линии расположены $n$ частиц со спином $1/2$. Их гамильтониан $H=H_{1,2}+H_{2,3}+\cdots+H_{n-1,n}$ состоит из взаимодействий соседей. Формально

$$\begin{gathered}H_{i,i+1}=I_2^{\otimes(i-1)}\\{}\otimes h_{i,i+1}\otimes I_2^{\otimes(n-i-1)}.\end{gathered}$$

где $h_{i,i+1}$ — двухкубитный гамильтониан; разные $h$ не обязаны совпадать. В единицах $\hbar=1$ требуется эффективно приближать $e^{-iHt}$ произведением двухкубитных унитарных операций — вентилей схемы.

(a) Как реализовать $e^{-iH_{i,i+1}t}$ одним вентилем? [Указание: не усложняйте.]

(b) Пусть $n=2m$ и

$$\begin{gathered}H_O=H_{1,2}+H_{3,4}+\cdots\\=\sum_{i=1}^m H_{2i-1,2i},\end{gathered}$$

$$\begin{gathered}H_E=H_{2,3}+H_{4,5}+\cdots\\=\sum_{i=1}^{m-1}H_{2i,2i+1}.\end{gathered}$$

Тогда $H=H_O+H_E$. Как реализовать $e^{-iH_Ot}$ и $e^{-iH_Et}$? Сколько вентилей требуется?

(c) Докажите

$$\begin{gathered}e^{-iHt}=e^{-iH_Ot}e^{-iH_Et}\\{}+O(t^2).\end{gathered}\tag{21}$$

(d) Для унитарных $A_1,\ldots,A_L,B_1,\ldots,B_L$ с $A_i-B_i=O(\delta)$ докажите

$$\begin{gathered}A_1\cdots A_L-B_1\cdots B_L\\=O(L\delta).\end{gathered}\tag{22}$$

(e) Формула (21) даёт хорошее приближение лишь при очень малом $t$. Для произвольного $t$ разобьём его на $L$ малых интервалов и приблизим эволюцию выражением

$$\left(e^{-iH_Et/L}e^{-iH_Ot/L}\right)^L.$$

Оцените ошибку через $t,L$. Какое $L$ нужно для ошибки $O(\epsilon)$? Сколько вентилей в полученной схеме? Достаточно асимптотических ответов в обозначениях $O(\cdot)$.