4.5 通用量子门

一小部分门如与、或、非门可用于计算任意经典函数，这样一组门对经典计算是通用的。若存在一组门使得任何酉操作都可以被仅涉及这组门的量子电路以任意精度近似，则这组门对量子计算是通用的。

本节描述三类量子计算的通用性构造，并证明任何酉操作都可以使用阿达玛门、受控非门、相位门和$\pi /8$门逼近至任意精度。

• 第一部分构造表明，任意酉算子可以精确地表示为仅在一个由两个计算基矢态张成的子空间上起非平凡作用的酉算子的乘积。
• 第二步构造将第一步构造与前一节的结果相结合，证明了任意酉算子可以用单量子比特和受控非门精确表示。
• 第三步构造将第二步的构造与单量子比特可使用阿达玛门、相位门和$\pi /8$门以任意精度近似的证明相结合。这也就意味着任何酉算子都可以用阿达玛门、受控非门、相位门和$\pi /8$门近似到任意精度。

4.5.1 两级酉门是通用的

考虑一个作用在$d$维希尔伯特空间上的酉矩阵$U$。本节描述了如何将$U$分解成两级酉矩阵的乘积，即只在两个或更少的向量分量上起非平凡作用的酉矩阵。

基本思想如下。

考虑$U$为$3\times 3$矩阵，假设$U$具有如下形式
$$U=\left[\begin{array}{ccc}a& d& g\\ b& e& h\\ c& f& j\end{array}\right](4.41)$$
可以找出两级酉矩阵$U_1,...,U_3$使得
$$U_3{U}_2{U}_{1}U=I(4.42)$$
即
$$U=U_1^{†}{U}_2^{†}{U}_3^{†}(4.43)$$
其中$U_1,U_2,U_3$是两级酉矩阵，则它们的逆$U_1^{†},U_2^{†},U_3^{†}$也是。那么如果能证明式4.42，就能证明$U$可分解成两级酉矩阵的乘积。

构造$U_1$：使得$U_{1}U$中左边列中间项为0。

若$b=0$，则令（不需要任何操作，因为原本$U$中左边列中间项就为0）
$$U_1\equiv \left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right](4.44)$$
若$b\ne 0$，则令（这样构造可以使得$U_{1}U$的左边列中间项为0）
$$U_1\equiv \left[\begin{array}{ccc}\frac{a^{\ast }}{\sqrt{|a{|}^2+|b{|}^2}}& \frac{b^{\ast }}{\sqrt{|a{|}^2+|b{|}^2}}& 0\\ \frac{b}{\sqrt{|a{|}^2+|b{|}^2}}& \frac{-a}{\sqrt{|a{|}^2+|b{|}^2}}& 0\\ 0& 0& 1\end{array}\right](4.45)$$
在这两种情况下，$U_1$都是两级酉矩阵，把矩阵相乘得到
$$U_{1}U=\left[\begin{array}{ccc}{a}^{\prime }& d^{\prime }& g^{\prime }\\ 0& e^{\prime }& h^{\prime }\\ c^{\prime }& f^{\prime }& j^{\prime }\end{array}\right](4.46)$$
注意到左边列的中间项是0，并且矩阵中的实际值并不重要。

类似地，构造两级酉矩阵$U_2$，使得$U_2{U}_{1}U$在左下角项为0，且左上角项为1。

若$c^{\prime }=0$，则（左下角项已经为0了，所以只需使得$a^{\prime \ast }{a}^{\prime }=1$）
$$U_2\equiv \left[\begin{array}{ccc}{a}^{{}^{\prime }\ast }& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right](4.47)$$
若$c^{\prime }\ne 0$，则令
$$U_2\equiv \left[\begin{array}{ccc}\frac{a^{{}^{\prime }\ast }}{\sqrt{|a^{\prime }{|}^2+|c^{\prime }{|}^2}}& 0& \frac{c^{{}^{\prime }\ast }}{\sqrt{|a^{\prime }{|}^2+|c^{\prime }{|}^2}}\\ 0& 1& 0\\ \frac{c^{{}^{\prime }}}{\sqrt{|a^{\prime }{|}^2+|c^{\prime }{|}^2}}& 0& \frac{-a^{{}^{\prime }}}{\sqrt{|a^{\prime }{|}^2+|c^{\prime }{|}^2}}\end{array}\right](4.48)$$
在这两种情况下，把矩阵相乘得
$$U_2{U}_{1}U=\left[\begin{array}{ccc}1& d^{\prime \prime }& g^{\prime \prime }\\ 0& e^{\prime \prime }& h^{\prime \prime }\\ 0& f^{\prime \prime }& j^{\prime \prime }\end{array}\right](4.49)$$
由于$U,U_1,U_2$是酉矩阵，则$U_2{U}_{1}U$也是酉的，鉴于第一行模为1，则$d^{\prime \prime }=g^{\prime \prime }=0$，最后令
$$U_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& e^{\prime \prime \ast }& f^{\prime \prime \ast }\\ 0& h^{\prime \prime \ast }& j^{\prime \prime \ast }\end{array}\right](4.50)$$
可以得到$U_3{U}_2{U}_{1}U=I$，则$U$的两级酉分解$U=U_1^{†}{U}_2^{†}{U}_3^{†}$。

推广至$d$维，设$U$作用于$d$维空间，可以找到两级酉矩阵$U_1,...,U_{d-1}$使得矩阵$U_{d-1}{U}_{d-2}\cdot \cdot \cdot U_{1}U$左上角为1，第一行和第一列的其余项为0。然后，对矩阵$U_{d-1}{U}_{d-2}\cdot \cdot \cdot U_{1}U$右下角的$(d-1)\times (d-1)$维酉子矩阵重复这一过程，最终可以将任意$d\times d$酉矩阵写成
$$U=V_1...V_k(4.51)$$
其中矩阵$V_i$是两级酉矩阵，$k\le (d-1)+(d-2)+...+1=d(d-1)/2$。

4.5.2 单量子比特门和受控非门是通用的

本节证明在$n$量子比特状态空间上，单量子比特门和受控非门可以表示任意两级酉操作。结合4.5.1的结论就有单量子比特门和受控非门可实现$n$量子比特上的任意酉操作。

假设$U$是$n$量子比特计算机上的两级酉矩阵，假设$U$在计算基矢态$|s⟩$ 和$|t⟩$所张成的空间上的作用是不平凡的，其中$s=s_1...s_n$和$t=t_1...t_n$是$s$和$t$的二进制展开式。令$\tilde{U}$是$U$的非平凡$2\times 2$酉子矩阵，$\tilde{U}$可以被看作是单量子比特上的酉算子。

目标：构建一个由单量子比特门和受控非门组成的实现$U$的电路。

定义1：Gray码

假设有不同的二进制数$s$和$t$，一个连接$s$和$t$的Gray码是一组以$s$开始，以$t$结尾的二进制数序列，使得列表中的相邻数恰好有一位不同。设$g_1$到$g_m$是连接$s$和$t$的Gray码元素，其中$g_1=s,g_m=t$。总可以找到一个Gray码使得$m\le n+1$，因为$s$和$t$最多有$n$个位置不同。

例如，$s=101001,t=110011$，则Gray码为
$$\begin{array}{cccccc}1& 0& 1& 0& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 1\\ 1& 1& 0& 0& 1& 1\end{array}(4.53)$$

实现量子电路$U$

基本思想是通过一系列门实现状态变化$|g_1⟩\to |g_2⟩\to ...\to |g_{m-1}⟩$，然后执行受控$\tilde{U}$运算，其中目标量子比特是$g_{m-1}$和$g_m$中不同的那一比特，然后还原第一阶段，进行转换$|g_{m-1}⟩\to |g_{m-2}⟩\to ...\to |g_1⟩$，以上每一步都可以使用前面的运算很容易实现，最后结果即是$U$的一个实现。

具体步骤：

1. 首先交换$|g_1⟩$和$|g_2⟩$的状态。假设$|g_1⟩$和$|g_2⟩$第$i$位数字不同，则通过对第$i$个量子比特执行受控比特翻转来完成交换，前提条件是$|g_1⟩$和$|g_2⟩$在其他量子比特的值相同。

2. 接下来使用受控运算交换$|g_2⟩$和$|g_3⟩$。并继续使用这种模式直到将$|g_{m-2}⟩$和$|g_{m-1}⟩$交换。这$m-2$个序列操作的效果是实现运算，每次的交换都是交换状态本身，见p163。

$$\begin{array}{rl}|g_1⟩& \to |g_{m-1}⟩\\ |g_2⟩& \to |g_1⟩\\ |g_3⟩& \to |g_2⟩\\ \cdots & \cdots \cdots \\ |g_{m-1}⟩& \to |g_{m-2}⟩(4.57)\end{array}$$

所有其他计算基状态都不受此操作序列的影响。

3. 接下来假设$|g_{m-1}⟩$和$|g_m⟩$在第$j$位上不同，以第$j$个量子比特为目标比特应用到受控$\tilde{U}$运算，条件是$g_{m-1}$和$g_m$在其他量子比特值相同。

4. 最后通过还原交换运算来完成$U$的运算：交换$|g_{m-1}⟩$和$|g_{m-2}⟩$，然后交换$|g_{m-2}⟩$和$|g_{m-3}⟩$，直到交换$|g_2⟩$和$|g_1⟩$。

例子：

假设我们要实现两级酉变换
$$U=\left[\begin{array}{llllllll}a& 0& 0& 0& 0& 0& 0& c\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ b& 0& 0& 0& 0& 0& 0& d\end{array}\right](4.58)$$
其中$a,b,c,d$是使得$\tilde{U}\equiv \left[\begin{array}{ll}a& c\\ b& d\end{array}\right]$为酉矩阵的任意复数。

注意$U$只作用在状态$|000⟩$和$|111⟩$上时不平凡，可以写成Gray码连接$000$和$111$：
$$\begin{array}{ccc}A& B& C\\ 0& 0& 0\\ 0& 0& 1\\ 0& 1& 1\\ 1& 1& 1\end{array}(4.59)$$
由此得出所需电路如图4.16所示。前两个门使状态$|000⟩$变为$|011⟩$，接下来受控运算$\tilde{U}$以第二第三量子比特状态为$|11⟩$作为条件应用于状态$|011⟩$和$|111⟩$的第一个量子比特。最后，还原各量子比特状态，以确保状态$|011⟩$和状态$|000⟩$交换。

一般情况，实现两级酉操作$U$最多需要$2(n-1)$次受控运算来交换$|g_1⟩$和$|g_{m-1}⟩$并还原，每个受控运算都可以使用$O(n)$个单量子比特门和受控非门来实现，受控$\tilde{U}$运算也需要$O(n)$个门。因此实现$U$操作需要$\underline{O(n^2)}$个单量子比特门和受控非门。由上节可知，在$2^n$维状态空间上任意作用在$n$量子比特上的酉矩阵可以写成$\underline{O((2^n{)}^2)=O(4^n)}$个两级酉操作的乘积。综上，在$n$量子比特上的任意酉操作可以用包含$\underline{O(n^2{4}^n)}$个单量子比特门和受控非门的电路来实现。

4.5.3 通用运算的一个离散集合

上一节得到受控非门和单量子比特酉算子一起构成量子计算的一个通用集，但目前没有一种直接的方法以抗噪声的形式实现这些门。

本节给出一个离散的门集合可以用来实现通用量子计算，并在第10章按照防错的形式用量子纠错码来实现这些门。

逼近酉算子

由于酉操作集合是连续的，一个离散的门集合不能用来确切实现任意的酉操作，但离散集合可以用来逼近任意酉操作。

假设$U$和$V$是作用在相同状态空间上的两个酉操作，$U$是希望实现的目标酉算子，$V$是实际实现的酉算子。定义当$V$代替$U$被实现时的误差：
$$E(U,V)\equiv \max ||(U-V)|\psi ⟩||(4.61)$$
其中极大取遍状态空间上所有归一化的量子态$|\psi ⟩$。

专题4.1得出的结论：

1. 测量误差可以解释为：如果$E(U,V)$很小，则对任意的初始态$|\psi ⟩$，在状态$V|\psi ⟩$上的任意测量将给出和在态$U|\psi ⟩$上近似的测量统计结果。具体地，如果$M$是一个POVM测量中的POVM元，$|\psi ⟩$是初始态，$P_U$或$P_V$是$U$或$V$​​被作用后的结果概率，则
   $$|P_V-P_U|\le 2E(U,V)(4.62)$$
   因此，如果$E(U,V)$很小，不管$U$还是$V$被作用，测量结果出现的概率相似。

2. 如果为了逼近某个门序列$U_1,...,U_m$，执行门序列$V_1,...V_m$，则误差最多按线性增加：
   $$E(U_m{U}_{m-1}...U_1,V_m{V}_{m-1}...V_1)\le \sum _{j=1}^{m}E(U_j,V_j)(4.63)$$

逼近结果4.62和4.63非常有用，假设我们希望执行一个从$U_1$到$U_m$包含$m$个量子门的量子电路，我们只能通过$V_j$门逼近$U_j$门。为了在逼近电路上不同测量结果的概率和正确概率相比偏差在$△>0$之内，根据上述结果，只需满足$E(U_j,V_j)\le △/(2m)$。

阿达玛门+相位门+受控非门+$\pi /8$门的通用性

由上述可知，可以利用离散门集合逼近任意的酉操作。考虑两种不同的离散门集合，两者都是通用的：

1. 第一类集合，通用门的标准集，由阿达玛门、相位门、受控非门和$\pi /8$门组成。
2. 第二类门集合，由阿达玛门、相位门、受控非门和Toffoli门组成。

证明阿达玛门、$\pi /8$门可以任意精度逼近任意单量子比特酉操作

1. 证明用阿达玛门和$\pi /8$门可以构造$R_{\vec{n}}(\theta )$

考虑门$T$和$HTH$，除了一个不重要的全局相位因子，

• $T$表示布洛赫球上围绕$\hat{z}$轴旋转$\pi /4$角，$T=R_Z(\frac{\pi }{4})=\exp (-i\frac{\pi }{8}Z)$
• $HTH$表示布洛赫球上围绕$\hat{x}$轴旋转$\pi /4$角，$HTH=R_X(\frac{\pi }{4})=\exp (-i\frac{\pi }{8}X)$

除去一个全局相位因子，复合这两种运算得到
$$\begin{array}{rl}\exp (-i\frac{\pi }{8}Z)\exp (-i\frac{\pi }{8}X)& =[\cos \frac{\pi }{8}I-i\sin \frac{\pi }{8}Z][\cos \frac{\pi }{8}I-i\sin \frac{\pi }{8}X]\\ & ={\cos }^2\frac{\pi }{8}I-i[\cos \frac{\pi }{8}(X+Z)+\sin \frac{\pi }{8}Y]\sin \frac{\pi }{8}(4.75)\end{array}$$
根据$R_{\vec{n}}(\theta )\equiv \exp (-i\theta \vec{n}\cdot \vec{\sigma }/2)=\cos \left(\frac{\theta }{2}\right)I-i\sin \left(\frac{\theta }{2}\right)\left(n_{x}X+n_{y}Y+n_{z}Z\right)$，复合运算时一个布洛赫球上绕轴$\vec{n}=(\cos \frac{\pi }{8},\sin \frac{\pi }{8},\cos \frac{\pi }{8})$旋转$\theta$角的一个变换，其中$\cos \theta /2\equiv {\cos }^2\pi /8$。即仅用阿达玛门和$\pi /8$门可以构造$R_{\vec{n}}(\theta )$。

• 可以证明这个$\theta$是$2\pi$的无理倍数。

2. 证明重复迭代$R_{\vec{n}}(\theta )$可以以任意精度逼近$R_{\vec{n}}(\alpha )$

初始值：

• 令$\delta >0$为想要的精度，令$N$为大于$2\pi /\delta$的整数。
• 定义${\theta }_k$使得${\theta }_k\in [0,2\pi ]$且${\theta }_k=(k\theta )\mathrm{mod}2\pi$。
• 根据鸽笼原理，在$1,...,N$中存在不同的$j,k$使得$|{\theta }_k-{\theta }_j|\le 2\pi /N<\delta$。

不失一般性，假设$k>j$，则有$|{\theta }_{k-j}|<\delta$，由于$j\ne k,\theta$是$2\pi$的无理倍数，故必有$|{\theta }_{k-j}|\ne 0$。

$\Rightarrow$ 这等于说随着$l$的变化${\theta }_{l(k-j)}$充满了$[0,2\pi )$整个区间，使得序列中相邻的数不会多于$\delta$​的分割。

$\Rightarrow$ 这等于说对于任意的$ϵ>0$，存在着$n$使得
$$E(R_{\vec{n}}(\alpha ),R_{\vec{n}}(\theta {)}^n)<\frac{ϵ}{3}(4.76)$$

3. 证明任意的单量子比特操作可以由阿达玛门和$\pi /8$门以任意精度逼近

简单的代数运算意味着，对于任意的$\alpha$，
$$H{R}_{\vec{n}}(\alpha )H=R_{\vec{m}}(\alpha )(4.78)$$
其中$\vec{m}$是一个沿着方向$(\cos \frac{\pi }{8},-\sin \frac{\pi }{8},\cos \frac{\pi }{8})$的单位向量，由它可以得到
$$E(R_{\vec{m}}(\alpha ),R_{\vec{m}}(\theta {)}^n)<\frac{ϵ}{3}(4.79)$$

习题4.11 假设$\hat{m} ,\hat{n} $是互不平行的三维实单位向量，证明存在合适的$\alpha ,\beta _k,\gamma _k$使得任意单量子比特酉算子可被表示为
$$U=e^{i\alpha }{R}_{\hat{n}}({\beta }_1)R_{\hat{m}}({\gamma }_1)R_{\hat{n}}({\beta }_2)R_{\hat{m}}({\gamma }_2)\dots (4.13)$$

根据习题4.11，除了一个不重要的全局相位变换，任意单量子比特上的$U$运算可以表示为
$$U=R_{\vec{n}}(\beta )R_{\vec{m}}(\gamma )R_{\vec{n}}(\delta )(4.80)$$
结果4.76和4.79再加上4.63的链不等式意味着，对于合适的正整数$n_1,n_2,n_3$，
$$E(U,R_{\vec{n}}(\theta {)}^{n_1}H{R}_{\vec{n}}(\theta {)}^{n_2}H{R}_{\vec{n}}(\theta {)}^{n_3})<ϵ(4.81)$$
即，对于任意的单量子比特运算$U$和任意$ϵ>0$，可以用阿达玛门和$\pi /8$门组合成的电路以$ϵ$逼近$U$。

结论

给一个含有$m$个门的量子电路，或者受控非门，或者单量子比特酉门，我们可以用阿达玛门、受控非门和$\pi /8$门逼近它（后面会发现相位门可以做容错的逼近）。如果对于整个电路想要$ϵ$的逼近，这可以通过上面的程序对每个单量子比特酉操作作以$ϵ/m$逼近，再用链不等式对整个电路以$ϵ$的逼近达到。

效率

用离散的门集合逼近量子电路的程序效率描述。

1. 假设在距离$ϵ$内逼近一个任意单量子比特酉门，从离散集合中需要$\Omega (2^{1/ϵ})$个门。则为了逼近$m$个门，需要$\Omega (m{2}^{1/ϵ})$个门，即随着电路尺寸的增加指数增长。
2. 区间$[0,2\pi )$上的角度${\theta }_k$序列多少采取一致的形式，这使得为了逼近一个单量子比特门大约从离散集中取$\Theta (1/ϵ)$个门，则以$ϵ$逼近一个$m$门电路需要的门数变成$\Theta (m^2/ϵ)$，这是一个随着电路尺寸$m$的平方递增。
3. Solovay-Kitaev定理意味着一个任意的单量子比特门可以用离散集中$O({\log }^c(1/ϵ))$个门以$ϵ$逼近，其中$c$是一个接近2的常数。Solovay-Kitaev定理因此意味着以不超过$ϵ$错误率逼近一个包含$m$个受控非门和单量子比特酉门的电路需要离散集中$O(m{\log }^c(1/ϵ))$个门，它随着电路尺寸以多项式量级增长。

4.5.4 逼近任意酉门一般是难的

存在一些$n$量子比特状态，需要花费$\Omega (2^n\log (1/ϵ)/\log (n))$次操作才能逼近到距离$ϵ$之内，这关于$n$是指数级的，是困难的。

$\Rightarrow$ 用上述通用构造和Solovay-Kitaev定理可以得到，任意一个$n$量子比特状态上的酉操作可以用$O(n^2{4}^n{\log }^c(n^2{4}^n/ϵ))$个门以$ϵ$距离逼近。

因此在一个多项式的因子内，通用构造是最优的，但也不能被有效计算。

4.5.5 量子计算复杂度

BQP定义

• PSPACE被定义为一类判定问题，可以在图灵机上使用关于问题规模是多项式的空间和任意时间来解决的问题。
• BQP本质上是一个量子复杂性类，由那些可以用多项式大小的量子电路在有界错误概率内来解决的判定问题组成。

BQP：如果存在一个多项式尺寸的量子电路可以判定语言$L$，按至少$3/4$的概率接受语言的串，按至少$3/4$的概率拒绝不在语言中的串，我们说语言工在BQP中。

• 量子电路以二进制串作为输入，试图决定他们是否在语言中。
• 在电路结束时，测量一个量子位，0表示串已被接受，1表示拒绝。
• 通过测试字符串几次来确定它是否在$L$中，我们可以以非常高的概率确定给定字符串是否在工中。

电路族

• 任何给定的量子电路只能决定某个有限长度的字符串是否在$L$中。

• 在BQP的定义中使用了一个完整的电路族：对于每个可能的输人长度，这个家族中都有一个不同的电路。

• 除了已经描述的接受/拒绝标准外，我们对电路设置了两个限制：

  • 首先，电路的尺寸应仅随着输入字符串$x$的尺寸(我们试图确定$x\in L$​)呈多项式增长。
  • 要求电路在与 3.1.2节所述类似的意义上一致地生成，即有一台图灵机能够有效地输出量子电路的描述。

BQP$\subseteq $PSPACE

BPP$\subseteq$BQP$\subseteq$PSPACE，证明BQP$\ne$BPP意味着BPP$\ne$PSPACE， 但目前不知道BPP$\ne$PSPACE是否成立。

4.6 量子计算电路模型总结

量子计算机与计算的量子电路模型同义。

量子电路计算模型的关键要素：

1. 经典资源：量子计算机由经典部分和量子部分两部分组成。
2. 一个合适的状态空间：一个量子电路作用在$n$量子比特上，因此状态空间是一个$2^n$维的复希尔伯特空间。$|x_1,...,x_n⟩$，其中$x_i=0,1$，被称为计算机的计算基矢态。$|x⟩$表示计算基矢态，其中$x$是二进制表示$x_1\dots x_n$所对应的十进制数。
3. 准备计算基矢态的能量：假设任意计算基矢态可以在最多$n$步内制备。
4. 执行量子门的能力：门操作可以应用于量子比特的任何子集，并且可以实现一个通用门族。例如阿达玛门、受控非门、相位门和$\pi /8$门构成一个门族，可以逼近任何酉操作。
5. 在计算基矢态上进行测量的能力：测量可以在计算基矢的一个或多个量子比特上进行。

4.7 量子系统的模拟

1. 描述了模拟问题的一些实例
2. 给出了一个量子模拟算法和一个示例
3. 对该应用进行展望

4.7.1 行为模拟

模拟的核心是微分方程的解，它捕捉了控制系统动态行为的规律。

exp. 牛顿定律，
$$\frac{d}{dt}\left(m\frac{dx}{dt}\right)=F(4.88)$$
泊松方程，
$$-\vec{\nabla }\cdot (k\vec{\nabla }\vec{u})=\vec{Q}(4.89)$$
电磁矢量波方程，
$$\vec{\nabla }\cdot \vec{\nabla }\vec{E}={ϵ}_0{\mu }_0\frac{{\partial }^2\vec{E}}{\partial t^2}(4.90)$$
扩散方程，
$${\vec{\nabla }}^2\psi =\frac{1}{a^2}\frac{\partial \psi }{\partial t}(4.91)$$
模拟的目标通常是：给定系统的初始状态，其他时间和/或位置的状态是什么。解通常是通过数字表示来逼近态，然后在时间和空间上离散化微分方程，使得程序的迭代应用从初始状态贯穿到最终状态。

• 此过程中的误差是有界的，并且已知不会比某个幂比较小的迭代增长得更快。
• 并非所有的动力系统都能有效地模拟，只有能够有效描述的系统可以有效地进行模拟

用经典计算机模拟量子系统是可能的，但通常效率非常低，很多简单量子系统的动力学行为受到薛定谔方程控制。
$$i\hslash \frac{d}{dt}|\psi ⟩=H|\psi ⟩(4.93)$$
可以发现，$\hslash$很容易吸收到$H$中，这节后续部分都会用到这个约定。对于处理空间中真实粒子感兴趣的典型哈密顿量，根据已知的位置表象$⟨x|\psi ⟩=\psi |x⟩$，可以约简为
$$i\frac{\partial }{\partial t}\psi (x)=\left[-\frac{1}{2m}\frac{{\partial }^2}{\partial x^2}+V(x)\right]\psi (x)(4.93)$$
这是一个椭圆方程，类似4.91.因此在量子系统的模拟中，仅模拟薛定谔方程并不是特别困难。

量子系统模拟的困难在于必须求解指数个微分方程。根据薛定谔方程，对于一个量子比特的演化，需要求解两个微分方程组成的系统；对于两量子比特，需要求解四个方程；对于$n$量子比特，需要求解$2^n$个方程。

• 可以通过逼近来简化有效方程的个数，使得量子系统的经典模拟称谓可能。

有许多重要的量子系统用经典模拟是不可能的，例如Hub-bard模型，它是一个相互作用的费米子粒子模型，其哈密顿量为
$$H=\sum _{k=1}^n{V}_0{n}_{k\uparrow }{n}_{k\downarrow }+\sum _{k,j\text{ neighbors },\sigma }{t}_0{c}_{k\sigma }^{\ast }{c}_{j\sigma }(4.94)$$
在研究超导和磁场中常用的伊辛模型
$$H=\sum _{k=1}^n{\vec{\sigma }}_k\cdot {\vec{\sigma }}_{k+1}(4.95)$$

量子计算机可以有效模拟没有有效经典模拟的量子系统。

4.7.2 量子模拟算法

经典的模拟是从解决一个简单的微分方程开始的，比如方程$dy/dt=f(y)$，其一阶解为$y(t+\Delta t)\approx y(t)+f(y)\Delta t$。类似的，量子情况考虑方程
$$|\psi (t)⟩=e^{-iHt}|\psi (0)⟩(4.96)$$
其中$H$是一个不依赖时间的哈密顿量，$H$通常是很难计算的，可能是稀疏的但指数很大。

其一阶解为$|\psi (t+\Delta t)⟩\approx (I-iH\Delta t)|\psi (t)⟩$，对于许多哈密顿量$H$，可以通过组成量子门来有效逼近$I-iH\Delta t$。一阶解是容易处理的，但一般不令人满意。

对于许多哈密顿量，方程4.96的高阶解的有效近似是可能的。例如，在大多数物理系统中，哈密顿量可以被作为许多局部相互作用的总和。对于$n$粒子系统，
$$H=\sum _{k=1}^L{H}_k(4.97)$$
其中，每个$H_k$最多作用于常数$c$个系统，$L$是$n$的多项式。例如，$H_k$通常是两体相互作用比如$X_i{X}_j$或一体哈密顿量$X_i$。Hubbard模型和Ising模型都有这种形式。

尽管$e^{-iHt}$很难计算，但$e^{-i{H}_{k}t}$作用于一个小得多的子系统，并且可以直接使用量子电路进行近似计算。但是$[H_j,H_k]\ne 0,e^{-iHt}\ne {\prod }_k{e}^{-i{H}_{k}t}$。在构造$e^{-iHt}$中，$e^{-i{H}_{k}t}$起作用如下。

Trotter公式

定理4.3（Trotter公式）令$A,B$为厄米算子。则对于任意实数$t$，
$$\underset{n\to \infty }{\lim }{\left(e^{iAt/n}{e}^{iBt/n}\right)}^n=e^{i(A+B)t}(4.98)$$
即使$A$和$B$不对易，式4.19也是正确的。它可以推广到对于某些半群的生成元$A$和$B$成立（将在8.4.1节中描述）。目前只考虑$A$和$B$​是厄米矩阵的情况。

Trotter公式提供了计算高阶近似的方法，用于进行量子模拟，可以得到
$$\underset{n\to \infty }{\lim }{\left(e^{iAt/n}{e}^{iBt/n}\right)}^n=e^{i(A+B)t}(4.103)$$

$$e^{i(A+B)\Delta t}=e^{iA\Delta t/2}{e}^{iB\Delta t}{e}^{iA\Delta t/2}+O\left(\Delta t^3\right)(4.104)$$

量子模拟算法概述

输入：

• $H={\sum }_k{H}_k$是一个作用$N$维系统上的哈密顿量算子，其中$H_k$作用在一个不依赖$N$的子系统
• 在$t=0$时，系统的初始状态为$|{\psi }_0⟩$
• 一个正的非零精度$\delta$
• 状态演化需要的时间$t_f$

输出：状态$|\tilde{\psi }\left(t_f\right)⟩$使得$|⟨\tilde{\psi }(t_f)|e^{-iH{t}_f}|{\psi }_0⟩{|}^2\ge 1-\delta$

运行时间：$O(poly(1/\delta )$次运算

程序：选择一个表示使得$n=poly(\log N)$量子比特$|\psi ⟩$逼近系统，且$e^{-\mathrm{i}{H}_k\Delta t}$有有效的量子电路逼近。选择一种逼近方法（如4.103-4.105）且$\Delta t$使得期望的错误率是可以接受的，且$j\Delta t=t_f$是一个整数。对于迭代步骤构造对应的量子电路$U_{\Delta t}$且做：
$$\begin{array}{l}\text{ 1. }|{\tilde{\psi }}_0⟩\leftarrow |{\psi }_0⟩;j=0\text{ 初始化态}\\ \text{ 2. }\to |{\tilde{\psi }}_{j+1}⟩=U_{\Delta t}|{\tilde{\psi }}_j⟩\text{ 迭代更新 }\\ \text{ 3. }\to j=j+1\text{; goto }2\text{ until }j\Delta t\ge t_f\text{循环}\\ \text{ 4. }\to |\psi \psi \psi \left(t_f\right)⟩=|{\tilde{\psi }}_j⟩\text{最后的结果}\end{array}$$

专题4.2 薛定谔方程的量子模拟

以下说明量子模拟的方法和局限性。以下例子来自于传统模型，而不是抽象的量子比特模型。

考虑直线上的单个粒子，一维势为$V(x)$，哈密顿量为
$$H=\frac{p^2}{2m}+V(x)(4.108)$$
其中$P$为能量算子，$x$是位置算子。$x$的特征值是连续的，系统状态$|\psi ⟩$存在于无限维希尔伯特空间中；在基$x$下，可以写为
$$|\psi ⟩={\int }_{-\infty }^{\infty }|x⟩⟨x|\psi ⟩dx(4.109)$$
在实践中，只关注范围为$-d\le x\le d$有限区域。此外，与系统中的最短波长相比，可以选择一个相当小的差分步长$\Delta x$，使得
$$|\tilde{\psi }⟩=\sum _{k=-d/\Delta x}^{d/\Delta x}{a}_k|k\Delta x⟩(4.110)$$
它提供了$|\psi ⟩$的一个好的物理逼近。这种状态可以用$n=\lceil \log (2d/\Delta x+1)\rceil$个量子比特来表示；我们用$n$个量子比特的计算基矢态$|k⟩$替换基$|k\Delta x⟩$(算子$x$的一个特征状态)。注意这种模拟仅需要$n$量子比特，而经典需要跟踪$2^n$个复数，因此在量子计算机上进行模拟时可以节省指数资源。

计算$|\tilde{\psi }(t)⟩=e^{-iHt}|\tilde{\psi }(0)⟩$必须利用方程(4.103)~(4.105)的逼近之一，因为一般的，$H_1=V(x)$与$H_0=p^2/2m$,不对易。因此，我们必须能计算$e^{-i{H}_1\Delta t}$和$e^{-i{H}_0\Delta t}$。因为$|\tilde{\psi }⟩$由$H_1$的特征基表示，$e^{-i{H}_1\Delta t}$是这样的对角形式$$
|k\rangle \rightarrow e^{-i V(k \Delta x) \Delta t}|k\rangle(4.111)
KaTeX parse error: Can't use function '$' in math mode at position 19: …可以直接计算，因为我们可以计算$̲V(k \Delta x) \…
|k\rangle \rightarrow U_{\mathrm{FFTe}} e^{-i x^{2} / 2 m} U_{\mathrm{FFT}}^{\dagger}|k\rangle(4.112)
$$

4.7.3 说明性示例

目前描述的量子模拟过程集中于模拟哈密顿量，其中哈密顿量是局部相互作用的总和。下面的例子说明，即使哈密顿量对一个大系统的所有或几乎所有部分都有作用，也可以进行有效的量子模拟。

假设作用在$n$量子比特上的哈密顿量
$$H=Z_1\otimes Z_2\otimes \cdots \otimes Z_n(4.113)$$
这是一个涉及所有系统的相互作用，但它也可以有效模拟。对于$\Delta t$的任意值，理想的是实现$e^{-iH\Delta t}$的简单量子电路。对于$n=3$​，图4.19的电路实现了这一点。

可以通过第一个经典的计算奇偶校验（将结果存储在辅助量子比特中），然后应用基于奇偶校验的适当相移，然后取消奇偶校验（擦除辅助）。

• 虽然哈密顿量涉及系统中的所有量子比特，但它是以经典的方式进行的：如果计算基中$n$个量子比特的奇偶性维偶数，则应用于系统的相移为$e^{-i\Delta t}$；否则，相移应为$e^{i\Delta t}$。

这个策略不仅适用于$n=3$，而且也适用于$n$的任意值。

扩展相同的过程允许模拟更复杂的扩展哈密顿量。可以有效模拟任何这种形式的哈密顿量
$$H=\underset{k=1}{\overset{n}{⨂}}{\sigma }_{c(k)}^k(4.114)$$
其中${\sigma }_{c(k)}^k$是作用在第$k$个量子比特上的泡利阵或恒等矩阵，其中c(k)∈{0,1,2,3}c(k) \in \{0,1,2,3\}c(k)∈{0,1,2,3}为{I,X,Y,Z}\{I, X, Y, Z\}{I,X,Y,Z}的指标。在其上执行恒等操作的量子比特可以被忽略，$X$或$Y$项可以通过单个量子比特门转换为$Z$操作。

小结

• 通用性：$n$量子比特上的任意酉操作可以确切地由单量子比特酉操作和受控非门运算来实现。
• 离散集的通用性：阿达玛门、受控非门、相位门和$\pi /8$门在如下意义下是量子计算的通用门，即任意$n$量子比特的酉操作可以由这些门组成的电路以任意精度$ϵ$逼近。用Toffoli门替代$\pi /8$门也可以得到一个通用门族。
• 并不是所有的酉操作都可以被有效实现：对任意的有限门集合，存在$n$量子比特上的酉操作需要用$\Omega (2^n\log (1/ϵ)/\log (n))$个门以$\epsilon $距离逼近。
• 模拟：令哈密顿量$H={\sum }_k{H}_k$，其中项数和为多项式个，$H_k$的有效量子电路可以被构造，则给了初始态$|{\psi }_0⟩$，存在量子计算机可以有效模拟$e^{-i H \Delta t} $的演化，逼近$|\psi(t)\rangle=e^{-i H t}|{\psi}_{0}\rangle$。