真实情况似乎是，我们不愿意承认在世界上还有其他生物具有与人类同等的智慧或者道德，不愿意承认其他生物与我们具有相同的重要性，并且认为其他生物命中注定在世界上扮演某些额外角色…… 我们不打算承认它们或许与我们类似，我们宁可相信除人之外的其他生物都是愚蠢的，只能靠本能生存和活动。 —— 梅特林克《花的智慧》

# 背景设定和定性分析

考虑薛定谔方程

$i\frac{\partial}{\partial t}|\psi(t)\rangle = H(t)|\psi(t)\rangle,$

其中 $H(t)\in \mathbb{C}^{N\times N}$ 是一个 Hermitian matrix，其中 $N=2^n$ 。
我们希望找到一个 gate complexity $poly(n,t,1/\epsilon)$ 的量子算法，来模拟 $|\psi(0)\rangle\mapsto |\psi(t)\rangle$ 。
（其中我们允许算法输出和 $|\psi(t)\rangle$ 的 norm 差 $\leq \epsilon$ ）
如果这个算法能找到，我们说 $H(t)$ 是可以被 efficiently simulate 的。

下面我们考虑定时 Hamiltonian $H(t)$ ，即 $H(t)=H$ 是一个常数矩阵。

(Local) 如果 $H$ acts on $O(1)$ qubits，那么 $H$ 是可以被 efficiently simulate 的。
(Scalability) 如果 $H$ 是可以被 efficiently simulate 的，那么 $c=poly(n)$ 时 $c\cdot H$ 也可以被 efficiently simulate 的。
(Unitary) 如果 $H$ 是可以被 efficiently simulate 的，那么 $UHU^\dagger$ 也可以被 efficiently simulate 的，其中 $U$ 是 unitary。
(Addition) 如果 $H_1$ 和 $H_2$ 是可以被 efficiently simulate 的，那么 $H_1+H_2$ 也可以被 efficiently simulate 的。(注意 $H_1,H_2$ 可能不交换)
(Commutator) 如果 $H_1$ 和 $H_2$ 是可以被 efficiently simulate 的，那么 $i[H_1,H_2]$ 也可以被 efficiently simulate 的。
(Diagonal) 如果 $H$ 是对角的，那么 $H$ 是可以被 efficiently simulate 的。
(Sparse) 如果 $H$ 是 $O(1)$ -sparse 的，那么 $H$ 是可以被 efficiently simulate 的。这里会有一些 matrix access oracle，关于 oracle 的 query complexity 也是 polynomial 的。

Example: 对于一个粒子的 Hamiltonian $H=\frac{p^2}{2m}+V(x)$ ，其中 $p^2=-\frac{d^2}{dx^2}$ 是 square of the momentum operator， $\frac{p^2}{2m}$ 是动能部分， $V(x)$ 是势能部分。势能部分是对角的， $P^2$ 可以在 Fourier transformation（unitary）下是对角的，因此 $H$ 是可以被 efficiently simulate 的。

# 定量分析

(一阶 Lie-Trotter-Suzuki Formula)
考虑 $H=A+B$ ，其中 $A,B$ 都是 Hermitian。令

$U(t)=e^{-iHt},\qquad U_1(t)=e^{-iAt}e^{-iBt},$

考虑泰勒展开带余项，

$f(t)=f(0)+f'(0)t+\int_0^t f''(s)(t-s)ds,$

那么是 Hermitian 时，矩阵也可以套入:

$\begin{aligned} & U(t)=I-i(A+B)t+\int_0^t -\left (A^2+AB+BA+B^2\right )e^{-i(A+B)s}(t-s)ds,\\ & U_1(t)=I-i(A+B)t+\int_0^t e^{-iAs}\left (-A^2-2AB-B^2\right )e^{-iBs}(t-s)ds. \end{aligned}$

注意到 $e^{-iAt},e^{-iBt}$ 是 unitary，放在 norm 里可以丢掉（这里不是完全丢掉，需要放缩 2 倍 $\|UA-BV\|\leq 2\|A-B\|$ 其中 $U,V$ 是 unitary，需要仔细分析），所以

$\|U(t)-U_1(t)\|\leq\int_0^t2\|AB-BA\|(t-s)ds\leq 2\int_0^t (\|A\|+\|B\|)^2(t-s)ds=t^2(\|A\|+\|B\|)^2.$

因此，对于分割 $l$ ，如果希望通过迭代逼近：

$\left \|e^{-i(A+B)t}-\left (e^{-iAt/l}e^{-iBt/l}\right )^l \right \|\leq l\cdot\frac{t^2}{l^2}(\|A\|+\|B\|)^2\leq\epsilon,$

那么 $l=O\left (\frac{t^2(\|A\|+\|B\|)^2}{\epsilon}\right )$ 。

(二阶 Lie-Trotter-Suzuki Formula / Gilbert Strang Formula)
考虑 $H=A+B$ ，其中 $A,B$ 都是 Hermitian。令

$U_2(t)=e^{-iAt/2}e^{-iBt}e^{-iAt/2},$

$U_2(t)$ 和 $U(t)$ 的二阶展开是一样的： $U(0)=U_2(0), U'(0)=U_2'(0), U''(0)=U_2''(0)$ ，所以要考虑三阶展开。最后可以得到

$\|U(t)-U_2(t)\|\leq t^3(\|A\|+\|B\|)^3.$

类似地，我们知道

$\|U(t)-U_2^l(t/l)\|\leq \frac{t^3(\|A\|+\|B\|)^3}{l^2}.$

这就比之前的一阶 Trotter formula 要好。

高阶 Suzuki 公式的话

$U_{2k}(t)=U_{2k-2}(s_kt)^2\cdot U_{2k-2}((1-4s_k)t)\cdot U_{2k-2}(s_kt)^2,$

其中

$s_k=\frac{1}{4-4^{\frac{1}{2k-1}}}.$

误差是

$\|U(t)-U_{2k}(t)\|\leq \frac{t^{2k+1}(\|A\|+\|B\|)^{2k+1}(K^{2k+1}+1)}{(2k+1)!},$

其中 $K=2\cdot 5^{k-1}$ 。那么类似前面分析，

$l=O\left (\frac{(tK(\|A\|+\|B\|))^{1+\frac{1}{2k}}}{\epsilon^{\frac{1}{2k}}}\right ).$

实际上已知 $A,B$ 和时间 $t$ 后，可以取到一个最优的 $k$ ，使得 $l$ 是最小的：

$k=\max\left \lceil 1,\sqrt{\frac{\log (t(\|A\|+\|B\|)/\epsilon)}{\log 5}}\right \rceil.$

所以并不是越高阶越好，高阶可能常系数指数爆炸。[Paper：A Theory of Trotter Error，用 commutator 去 bound]

Interacting picture
考虑 $H=A+B$ ，而且 $\|H_1\|>>\|H_2\|$ 时。考虑

$i\frac{\partial}{\partial t}|\psi(t)\rangle=H|\psi(t)\rangle,$

定义

$|\psi_1(t)\rangle\triangleq e^{iH_1t}|\psi(t)\rangle,$

那么

$\begin{aligned} i\frac{\partial}{\partial t}|\psi_1(t)\rangle&=i(iH_1)e^{iH_1t}|\psi(t)\rangle+e^{iH_1t}H|\psi(t)\rangle\\ &=(-H_1e^{iH_1t}+e^{iH_1t}(H_1+H_2))|\psi(t)\rangle\\ &=e^{iH_1t}H_2|\psi(t)\rangle\\ &=e^{iH_1t}H_2e^{-iH_1t}|\psi_1(t)\rangle. \end{aligned}$

这就定义了一个新的 Hamiltonian 的薛定谔方程。此时模拟的复杂性可以把 $\|H_1\|$ 从复杂度里剔除，相当于对 $H_2$ 做了个 unitary 变换。

# 背景设定和定性分析

# 定量分析

Sylow Theorem