万物皆有裂痕,那是光照进来的地方

# 量子线路

# 单量子比特运算

  • 重要的量子比特运算由2×22\times 2 的酉矩阵给出:

    Pauli 阵:

    X=σ1=(0110)Y=σ2=(0ii0)Z=σ3=(1001)X=\sigma_1=\begin{pmatrix}0&1\\1&0\end{pmatrix}\\ Y=\sigma_2=\begin{pmatrix}0&-i\\i&0\end{pmatrix}\\ Z=\sigma_3=\begin{pmatrix}1&0\\0&-1\end{pmatrix}

    Hadamard 门:

    H=12(1111)H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}

    相位门:

    S=(100i)S=\begin{pmatrix}1&0\\0&i\end{pmatrix}

    T 门(π/8\pi/8 门):

    T=(100exp(iπ/4))T=\begin{pmatrix}1&0\\0&exp(i\pi/4)\end{pmatrix}

  • 当出现在指数时,Pauli 矩阵导出三类有用的酉矩阵,称为关于x^,y^,z^\hat{x},\hat{y},\hat{z} 轴旋转的旋转算子,如下定义:

    Rx(θ)=eiθX/2=cosθ2Iisinθ2X=(cosθ2isinθ2isinθ2cosθ2)Ry(θ)=eiθY/2=cosθ2Iisinθ2Y=(cosθ2sinθ2sinθ2cosθ2)Rz(θ)=eiθZ/2=cosθ2Iisinθ2Z=(eiθ/200eiθ/2)R_x(\theta)=e^{-i\theta X/2}=cos\frac{\theta}{2}I-isin\frac{\theta}{2}X= \begin{pmatrix}cos\frac{\theta}{2}&-isin\frac{\theta}{2}\\-isin\frac{\theta}{2}&cos\frac{\theta}{2}\end{pmatrix}\\ R_y(\theta)=e^{-i\theta Y/2}=cos\frac{\theta}{2}I-isin\frac{\theta}{2}Y= \begin{pmatrix}cos\frac{\theta}{2}&-sin\frac{\theta}{2}\\sin\frac{\theta}{2}&cos\frac{\theta}{2}\end{pmatrix}\\ R_z(\theta)=e^{-i\theta Z/2}=cos\frac{\theta}{2}I-isin\frac{\theta}{2}Z= \begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix}\\

    推广地,设(nx^,ny^,nz^)(\hat{n_x},\hat{n_y},\hat{n_z}) 是三维空间中的单位向量,则绕其旋转θ\theta 的算子定义为:

    Rn^(θ)=exp(iθn^σ/2)=cosθ2Iisinθ2(nxX+nyY+nzZ)R_{\hat{n}}(\theta)=exp(-i\theta\hat{n}\cdot\overrightarrow{\sigma}/2)=cos\frac{\theta}{2}I-isin\frac{\theta}{2}(n_xX+n_yY+n_zZ)

  • 单量子比特的酉算子都可以写成:

    U2×2=eiαRn^(θ)U_{2\times 2}=e^{i\alpha}R_{\hat{n}}(\theta)

    其中:

    U=aI+bX+cY+dZa=cosθ2eiαb=inxsinθ2eiαc=inysinθ2eiαd=inzsinθ2eiα若U=aI+bX+cY+dZ\\ a=cos\frac{\theta}{2}e^{i\alpha}\\ b=-in_xsin\frac{\theta}{2}e^{i\alpha}\\ c=-in_ysin\frac{\theta}{2}e^{i\alpha}\\ d=-in_zsin\frac{\theta}{2}e^{i\alpha}

  • 单量子比特上的酉算子可以写成很多形式,例如旋转的组合乘上全局相移:

    (单量子比特的zyz-y 分解)U 是单量子比特上的任意酉算子,则存在α,β,γ,δ\alpha,\beta,\gamma,\delta,使得

    U=eiαRz(β)Ry(γ)Rz(δ)U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)

    证明:因为 U 是酉的,则 U 的行列均构成正交标准基,因此可以将U=(abcd)U=\begin{pmatrix}a&b\\c&d\end{pmatrix} 四个自由度写成:

    U=(ei(αβ/2δ/2)cosγ2ei(αβ/2+δ/2)sinγ2ei(α+β/2δ/2)sinγ2ei(α+β/2+δ/2)cosγ2)=eiαRz(β)Ry(γ)Rz(δ)U=\begin{pmatrix}e^{i(\alpha-\beta/2-\delta/2)}cos\frac{\gamma}{2}&-e^{i(\alpha-\beta/2+\delta/2)}sin\frac{\gamma}{2}\\ e^{i(\alpha+\beta/2-\delta/2)}sin\frac{\gamma}{2}&e^{i(\alpha+\beta/2+\delta/2)}cos\frac{\gamma}{2} \end{pmatrix}=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)

    * 这其实也告诉我们酉矩阵的一般形式。

    由证明,可以看出,若U=(abcd)U=\begin{pmatrix}a&b\\c&d\end{pmatrix},

    γ=2arctanbaβac的辐角差δcd的辐角差α可以最后观察下差的相位\gamma=2arctan\frac{|b|}{|a|}\\ \beta是a和c的辐角差\\ \delta是c和d的辐角差\\ \alpha可以最后观察下差的相位

    本质在于,U 描述的是 Bloch 球面上一点怎么到另一点的。

    例如ψ=Uψ|\psi'\rang=U|\psi\rang,可以先绕 Z 轴将ψ,ψ|\psi\rang,|\psi'\rang 均转入zOxzOx 平面,在绕 Y 轴在zOxzOx 平面内让它们重合。所以其实就是ψ|\psi\rang 先绕 Z 轴进入zOxzOx 平面,再绕 Y 轴转至ψ|\psi'\rangzOxzOx 上的投影,再绕 Z 轴转到ψ|\psi'\rang

  • 推论:设 U 是单量子比特上的酉门,则存在单量子比特上的酉算子 A,B,C 使得 ABC=I 且U=eiαAXBXCU=e^{i\alpha}AXBXC

    证明:仍采用zyz-y 分解的记号,记

    A=Rz(β)Ry(γ/2),B=Ry(γ/2)Rz((δ+β)/2),C=Rz((δβ)/2)A=R_z(\beta)R_y(\gamma/2),B=R_y(-\gamma/2)R_z(-(\delta+\beta)/2),C=R_z((\delta-\beta)/2)

    则有ABC=IABC=I(绕着绕着绕回去了)

    又因为X2=IX^2=I, 且XRy(θ)X=Ry(θ)XR_y(\theta)X=R_y(-\theta)(Ex4.7,不难证明),所以

    XBX=(XRy(γ/2)X)(XRz((δ+β)/2)X)=Ry(γ/2)Rz((δ+β)/2)XBX=(XR_y(-\gamma/2)X)(XR_z(-(\delta+\beta)/2)X)=R_y(\gamma/2)R_z((\delta+\beta)/2)

    所以

    AXBXC=Rz(β)Ry(γ/2)Ry(γ/2)Rz((δ+β)/2)Rz((δβ)/2)=Rz(β)Ry(γ)Rz(δ=U)AXBXC=R_z(\beta)R_y(\gamma /2)R_y(\gamma/2)R_z((\delta+\beta)/2)R_z((\delta-\beta)/2)=R_z(\beta)R_y(\gamma)R_z(\delta=U)

    证毕

  • 量子门记号 ("-" 表示量子比特,“/" 表示量子比特束)

    1

# 受控运算

  • 受控运算的原型是受控非门(CNOT 门),它是具有分别称为控制量子比特(control qubit)和目标量子比特(target qubit)的双量子比特门。相当于ctctc|c\rang|t\rang\rightarrow|c\rang|t\oplus c\rang,,如果控制量子比特为1|1\rang,则目标量子比特进行比特翻转,否则不动。

    U=(1000010000010010)U=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}

    注意

(a0+b1)(α0+β1)=aα00+aβ01+bα10+bβ11 (a|0\rang+b|1\rang)\otimes(\alpha|0\rang+\beta|1\rang)=a\alpha|00\rang+a\beta|01\rang+b\alpha|10\rang+b\beta|11\rang

在经过 CNOT 门后,进入状态:

ψ=aα00+aβ01+bα11+bβ10 |\psi'\rang=a\alpha|00\rang+a\beta|01\rang+b\alpha|11\rang+b\beta|10\rang

此时,ψ|\psi'\rang 将无法写成两个单量子比特状态的张量积,故它是个纠缠态。

CNOT 门常用1表示。

  • 推广地,有一般受控酉算子门:1

    如果控制量子比特是1|1\rang,则对目标量子比特作用酉算子 U。

  • 在 Hadamard 门作用后,控制量子比特和目标量子比特的角色会互换。在 CNOT 门作用下:

    ++++++++|++\rang\rightarrow|++\rang\\ |-+\rang\rightarrow|-+\rang\\ |--\rang\rightarrow|+-\rang\\ |+-\rang\rightarrow|--\rang

    即第二量子比特为|-\rang 时第一量子比特±\pm 变换。因此:1

  • 下面考虑如何实现受控任意酉运算。

    首先,根据前面推论,任意单量子比特酉算子U=eiαAXBXCU=e^{i\alpha}AXBXC,其中ABC=IABC=I

    所以可以先实现受控相移:

    1

    注意到左线路之所以等价于右线路,是因为作为一个双量子比特系统,左线路和右线路都能完成:

    0000,0101,10eiα10,11eiα11|00\rang\rightarrow|00\rang,|01\rang\rightarrow|01\rang,|10\rang\rightarrow e^{i\alpha}|10\rang,|11\rang\rightarrow e^{i\alpha}|11\rang

    下面注意受控 X 门就是 CNOT 门,然后加上 ABC,则有:

    1

    ” 受控 “全部用 CNOT 门解决。因为ABC=IABC=I,所以若第一量子比特不为1|1\rang,第二量子比特也只会不变。

  • 多控制量子比特算子。设共有n+kn+k 个量子比特,前 n 个量子比特为控制比特,当且仅当前 n 个量子比特都为1|1\rang 时,将 U(一个 k 量子比特酉门)作用于后 k 个量子比特。即:

    Cn(U)x1x2...xnψ=x1x2...xnUx1x2...xnψC^n(U)|x_1x_2...x_n\rang|\psi\rang=|x_1x_2...x_n\rang U^{x_1x_2...x_n}|\psi\rang

    1 1

    Toffoli 门(即C2(X)C^2(X)) 就可以在 Figure4.8 中取V=(1i)(I+iX)/2V=(1-i)(I+iX)/2 得到。即 Toffoli 门可以仅通过单、双量子比特门实现,而经典比特门做不到。

  • 最终我们将证明,任意一个酉算子可以仅由 Hadamard、相位、CNOT、和 T 门组合来实现,这实现是一个很好的近似,下图展示了 Toffoli 门的一个构造,它非常有用:

    1
  • 下面解决如何利用已有的量子门实现Cn(U)C^n(U)

    1

    上图是一个实现Cn(U)C^n(U) 的特别简单的线路,氛围三段,由 n 个控制量子比特,n-1 个工作量子比特和一个目标量子比特构成。

    工作量子比特初始都是0|0\rang , 而左半边做的工作就是把控制量子比特 “与” 起来。最后一个工作量子比特就是与的结果。然后右侧再把工作量子比特还原回去。

  • 当然受控门有时候也需要反过来,例如 “当控制比特为0|0\rang 翻转目标比特”,这也有记号和等价的控制门:

    1

    如果控制比特数量大于 1 时,控制信息可以变成一个二进制串,例如当且仅当控制比特为010|010\rang 时翻转目标比特:

    1

    同样,目标量子比特也可以有多个:

    1
  • 线路恒等式:(令 C 是第一量子比特做控制比特,第二量子比特做目标量子比特的受控非门,XiX_i 表示作用在第 i 量子比特上的 X 门,则有:

    CX1C=X1X2,CY1C=Y1X2,CZ1C=Z1CX2C=X2,CY2C=Z1Y2,CZ2C=Z1Z2Rz,1(θ)C=CRz,1(θ),Rx,2(θ)C=CRx,2(θ)CX_1C=X_1X_2,CY_1C=Y_1X_2,CZ_1C=Z_1\\ CX_2C=X_2,CY_2C=Z_1Y_2,CZ_2C=Z_1Z_2\\ R_{z,1}(\theta)C=CR_{z,1}(\theta),R_{x,2}(\theta)C=CR_{x,2}(\theta)

# 测量

  • 出现在量子线路最后的元素就是测量。量子线路中的测量符号都表示投影测量,因为一般测量可以通过引入酉变换和辅助量子来用投影测量表示。

    1
  • 量子测量的两大原理:

    • 推迟测量原理:总可以把测量从量子线路的中间步骤移到线路的末端。如果测量的结果被用于线路的某些阶段,则经典的条件运算可以被条件量子运算代替。例如:

      1 1

      上图两个线路是等价的。图一有一个经典条件运算,即 “判断实验结果M1,M2M_1,M_2 是否是 1”,而这可以转换成量子的受控运算。

      其实我认为这也是因为图 1 中测量后第一、第二量子比特没有继续操作和测量了。

    • 隐含测量原理:量子电路中任何未终结的量子连线(即该连线对应的量子位在演化过程中没有被测量),最终总可以假设为该连线(对应的量子位)已经被测量,而不影响其他量子位的计算结果。

  • 测量扮演着量子世界和经典世界之间的界面,被视为一个不可逆运算。

# 通用量子门

  • 一组门对量子计算是通用的,如果用这组门的量子线路可以以任意精度近似任意的酉运算。现在描述量子计算的三个通用性构造步骤,这些可以层层推进,最后可以证明 Hadamard、相位、CNOT、和 T 门以任意精度近似任意酉运算。以下三个步骤分别对应要介绍的三个部分:

    • 步骤 1:任意酉算子可以精确表示为一些两级酉算子的乘积。(两级酉门是通用的)
    • 步骤 2:所有两级酉算子都可以精确地用单量子比特门和 CNOT 门表示(U=eiαAXBXCU=e^{i\alpha}AXBXC)(单量子比特门和 CNOT 门是通用的)。
    • 步骤 3:单量子比特运算可由 Hadamard、相位和 T 门以任意精度近似(通用运算的离散集合)。
  • 注:两级酉算子即为一个作用在 d 维 Hilbert 空间上的酉矩阵 U,但它只作用于两个或更少的分量。也就是说,U 至少有 d-2 行为只有对角线元素为 1 的单位矩阵。例如 d=4:

    U=(12120012120000100001)U=\begin{pmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0&0\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}

    就是一个二级酉算子,因为其只作用四维向量的前两个分量。

# 两级酉门(two-level unitary gate)是通用的

考虑一个作用在 d 维 Hilbert 空间上的酉矩阵 U。本节将说明怎样将 U 分解成两级酉矩阵的乘积。

  • 先考虑三阶矩阵的情况。设U=(adgbehcfi)U=\begin{pmatrix}a&d&g\\b&e&h\\c&f&i\end{pmatrix},我们要找出两级酉矩阵U1,U2,U3U_1,U_2,U_3 使得U3U2U1U=IU_3U_2U_1U=I

    U=U1U2U3U=U_1^\intercal U_2^\intercal U_3^\intercal 即为一个两级酉门分解。

    • 先构造U1U_1

      若 b=0,则U1=IU_1=I,否则

      U1=(aa2+b2ba2+b20ba2+b2aa2+b20001)U_1=\begin{pmatrix}\frac{a^*}{\sqrt{|a|^2+|b|^2}}&\frac{b^*}{\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{pmatrix}

      此时,U_1U=\begin{pmatrix}a'&d'&g'\\0&e'&h'\\c'&f'&i'\end

      其中,重点在于把第二行第一列变成 0. 而且U1UU_1U 仍为酉矩阵。

    • 再构造U2U_2,我们希望在这个基础上使得U2U1UU_2U_1U 的第三行第一列也变成 0。

      c=0c'=0,则U2=(a00010001)U_2=\begin{pmatrix}a'^*&0&0\\0&1&0\\0&0&1\end{pmatrix},否则:

      U2=(aa2+c20ca2+c2010ca2+c20aa2+c2)U_2=\begin{pmatrix}\frac{a'^*}{\sqrt{|a'|^2+|c'|^2}}&0&\frac{c'^*}{\sqrt{|a'|^2+|c'|^2}}\\ 0&1&0\\ \frac{c'}{\sqrt{|a'|^2+|c'|^2}}&0&\frac{-a'}{\sqrt{|a'|^2+|c'|^2}} \end{pmatrix}

      此时,U_2U_1U=\begin{pmatrix}a''&d''&g''\\0&e''&h''\\0&f''&i''\end

      由于U2U1UU_2U_1U 仍是酉的,可以导出a=1,d=g=0a''=1,d''=g''=0

    • 最后,构造

      U3=(U2U1U)=(1000ef0hi)U_3=(U_2U_1U)^\intercal=\begin{pmatrix}1&0&0\\0&e''^*&f''^*\\0&h''^*&i''^*\end{pmatrix}

      则有U3U2U1U=IU_3U_2U_1U=I。结束。

    此时,U=U1U2U3U=U_1^\intercal U_2^\intercal U_3^\intercal 即为一个 U 的两级酉门分解。

  • 再考虑一般情况,例如一个 d 维的矩阵,则先可以找到两级酉矩阵V1,V2,...,Vd1V_1,V_2,...,V_{d-1},使得Vd1...V1VV_{d-1}...V_1V 的第一列第一行除了第一个元素都是 0,第一个元素为 1。再重复这个过程,寻找V1,V2,...,Vd2V_1',V_2',...,V_{d-2}' 使得第二行第二列也变成只有第二个元素为 1 的单位向量,以此类推。

    最后,有Vk...V1U=I,U=V1...VkV_{k}...V_1U=I,U=V_1^\intercal...V_k^\intercal。其中,k(d1)+(d2)+...+1=d(d1)/2k\leq(d-1)+(d-2)+...+1=d(d-1)/2

    则 n 个量子比特系统上的酉门可以写成至多2n(2n1)/22^{n}(2^{n}-1)/2 个两级酉矩阵之积。

    但存在d×dd\times d 的酉矩阵UU,它不能分解为少于d1d-1 个两级酉矩阵的积。

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

  • 证明了 d 维 Hilbert 空间上的任意酉矩阵可以写成两级酉矩阵的乘积形式,现在证明单量子比特门和受控非门可以实现 n 量子比特空间上的任意二级酉运算。这两个结论结合起来可以看到单量子比特门和受控非门可以实现 n 量子比特上的任意酉运算,于是它们对于量子计算来说是通用的。

  • 设 U 是一个 n 量子比特计算机上的两级酉矩阵。设 U 在状态s,t|s\rang,|t\rang 张成的状态空间上的作用是不平凡的,其中s=s1..sn,t=t1...tns=s_1..s_n,t=t_1...t_n 是状态的二进制展开。令U~\tilde{U}UU 的一个2×22\times 2 的不平凡子酉阵,则U~\tilde{U} 可以看作是作用在单量子比特上的酉算子。

    现在的目标是基于单量子比特门和受控非门,构造一个实现UU 的线路。为此,我们需要使用 Gray 码

    * 连接 s 和 t 的 Gray 码:以 s 开头 t 结尾的一组二进制数,使得相邻两个二进制数恰有一位不同。* 例:

    s=(101001)2,t=(110011)2Gray={(101001)2(101011)2(100011)2(110011)2}s=(101001)_2,t=(110011)_2\\ Gray=\{\\ (101001)_2\\ (101011)_2\\ (100011)_2\\ (110011)_2\\ \}

    g1g_1gmg_m 是连接 s 和 t 的 gray 码,其中g1=s,gm=tg_1=s,g_m=t。则mn+1m\leq n+1,因为 s 和 t 最多有 n 位不同。

  • 实现 U 的基本想法是通过一系列门(比特翻转)实现变换g1g2...gm1|g_1\rang\rightarrow|g_2\rang\rightarrow...\rightarrow|g_{m-1}\rang 然后进行受控U~\tilde{U} 运算,目标量子比特是gm1g_{m-1}tt 不同的那位,控制量子比特要求剩下相同的n1n-1 位和 t 一样。然后再通过一系列门还原回原本状态。例如酉矩阵:

    U=(ac111111bd)U=\begin{pmatrix}a&&&&&&&c\\&1&&&&&&\\&&1&&&&&\\&&&1&&&&\\&&&&1&&&\\&&&&&1&&\\&&&&&&1&\\b&&&&&&&d\end{pmatrix}

    a,b,c,d 是使得U~=(acbd)\tilde{U}=\begin{pmatrix}a&c\\b&d\end{pmatrix} 为酉矩阵的任意数。注意到此时UU 只有作用在000|000\rang111|111\rang 上是不平凡的。写出连接 000 和 111 的 Gray 码:(000)2,(001)2,(011)2,(111)2(000)_2,(001)_2,(011)_2,(111)_2 设计出如下线路:

    1

    考虑下这样做为什么是对的。因为 a,b,c,d 行列是 0 和 7,转为二进制即为(000)2,(111)2(000)_2,(111)_2 即它只作用于这两个状态时是非平凡的。然后将(000)2(000)_2(111)2(111)_2 的比特翻转实际上是把这两位通过交换移到某一个量子比特对应的两位上,最后再交换回去。

  • 回到一般情形,实现 n 个量子比特上的任意酉运算需要O(n24n)O(n^24^n) 个单量子比特门和受控非门的线路来实现。事实上,酉运算必须用指数数目的门来实现。为了寻找快速量子算法,必须采取和通用性结构不同的方法。

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

# 酉算子的近似

  • 首先,一个离散的门的集合不可能精确实现所有酉运算,因为酉矩阵是连续的。然而,一个离散的门的集合却可以去近似酉运算。

  • 设 U 和 V 是同一状态空间上的酉算子,U 是希望实现的酉算子,V 是实际实现的酉算子。定义用 V 实现 U 的误差为:

    E(U,V)maxψ(UV)ψE(U,V)\equiv max_{|\psi\rang}||(U-V)|\psi\rang||

    其中 max 要取遍状态空间中所有的归一化状态ψ|\psi\rang

  • 近似量子线路:

    设一个量子系统初态是ψ|\psi\rang,并设我要进行酉运算 U 和 V。令 M 是任一个与测量相联系的 POVM 元。则

    pU=ψUMUψ,pV=ψVMVψpUpV=ψUMUψψVMVψp_U=\lang\psi|U^\intercal MU|\psi\rang,p_V=\lang\psi|V^\intercal MV|\psi\rang\\ |p_U-p_V|=|\lang\psi|U^\intercal MU|\psi\rang-\lang\psi|V^\intercal MV|\psi\rang|

    Δ=(UV)ψ|\Delta\rang=(U-V)|\psi\rang,利用代数运算和 Cauchy-Schwarz 不等式:

    pUpV=ψUMΔ+ΔMVψψUMΔ+ΔMVψψUMΔ2ψUMMUψΔΔ1ΔΔ所以pUpVΔ+Δ=2E(U,V)|p_U-p_V|=|\lang\psi|U^\intercal M|\Delta\rang+\lang\Delta|MV|\psi\rang|\\ \leq|\lang\psi|U^\intercal M|\Delta\rang|+|\lang\Delta|MV|\psi\rang|\\ 而\lang\psi|U^\intercal M|\Delta\rang^2\leq\lang\psi |U^\intercal MM^\intercal U|\psi\rang\lang\Delta|\Delta\rang\leq1\cdot\lang\Delta|\Delta\rang\\ 所以|p_U-p_V|\leq|||\Delta\rang||+|||\Delta\rang||=2E(U,V)

    这个式子定量地表示了,若E(U,V)E(U,V) 足够小,则测量结果误差也会很小。事实上,有式子:

    E(UmUm1...U1,VmVm1...V1)i=1mE(Ui,Vi)E(U_mU_{m-1}...U_1,V_mV_{m-1}...V_1)\leq\sum_{i=1}^m E(U_i,V_i)

    因为利用三角不等式,有E(U2U1,V2V2)E(U2,V2)+E(U1,V1)E(U_2U_1,V_2V_2)\leq E(U_2,V_2)+E(U_1,V_1) 然后归纳即可。

  • 再精确地描述pUpV2E(U,V)|p_U-p_V|\leq 2E(U,V) 的含义:对任意初态ψ|\psi\rang,在状态VψV|\psi\rang 上进行测量将给出对UψU|\psi\rang 的测量的近似的测量统计值。

    假设希望完成一个包含 m 个酉门U1,...,UmU_1,...,U_m 的量子线路,不幸的是,只能用门VjV_j 去近似门UjU_j。为了使实际近似结果和正确结果在一个容许量Δ\Delta 内,只要保证E(Ui,Vi)Δ/(2m)E(U_i,V_i)\leq\Delta/(2m) 就行了。

# Hadamard 门 + 相位门 + 受控非门 +π/8\pi/8 门的通用性

  • 首先证明 Hadamard 门和π/8\pi/8 门可以用来以任意精度近似任意单量子比特的酉运算。

    • 考虑 T 门和 HTH 门。T 门除了一个不要紧的全局相位,相当于将一个状态对应 Bloch 球面上的点绕z^\hat{z} 轴旋转π/4\pi/4。而HTH=eiπ/8Rx(π4)HTH=e^{i\pi/8}Rx(\frac{\pi}{4}),即 HTH 门是绕x^\hat{x} 轴旋转π/4\pi/4。这两个门组合起来:

    THTH=eiπ/4Rz(π4)Rx(π4)=eiπ/4{cos2π8Ii[cosπ8(X+Z)+sinπ8Y]sinπ8}=eiπ/4[cos2π8icosπ8(X+Z)+sinπ8Y1+cos2π81+cos2π8sinπ8]=Rn^(α)THTH=e^{i\pi/4}R_z(\frac{\pi}{4})R_x(\frac{\pi}{4})=e^{i\pi/4}\{cos^2\frac{\pi}{8}I-i[cos\frac{\pi}{8}(X+Z)+sin\frac{\pi}{8}Y]sin\frac{\pi}{8}\}\\ =e^{i\pi/4}[cos^2\frac{\pi}{8}-i\frac{cos\frac{\pi}{8}(X+Z)+sin\frac{\pi}{8}Y}{\sqrt{1+cos^2\frac{\pi}{8}}}\cdot\sqrt{1+cos^2\frac{\pi}{8}}sin\frac{\pi}{8}]\\ =R_{\hat{n}}(\alpha)

    ​ 其中

    n^=(cosπ8,sinπ8,cosπ8)1+cos2π8,cosα2=cos2π8,sinα2=1+cos2π8sinπ8\hat{n}=\frac{(cos\frac{\pi}{8},sin\frac{\pi}{8},cos\frac{\pi}{8})}{\sqrt{1+cos^2\frac{\pi}{8}}},cos\frac{\alpha}{2}=cos^2\frac{\pi}{8},sin\frac{\alpha}{2}=\sqrt{1+cos^2\frac{\pi}{8}}sin\frac{\pi}{8}

    ​ 即仅用 Hadamard 门和 T 门就可以实现Rn^(α)R_{\hat{n}}(\alpha),且可以证明这个α\alpha2π2\pi 的无理数倍。

    • 下面证明用Rn^(α)R_{\hat{n}}(\alpha) 反复迭代就可以以任意精度近似Rn^(θ)R_{\hat{n}}(\theta)。令δ>0\delta>0 为希望的精度,且 N 为一个大于2π/δ2\pi/\delta 的整数。

      定义αi=(iα)mod2π,αi0\alpha_i=(i\alpha)\quad mod\quad 2\pi,\alpha_i\geq 0。由抽屉原理,在1,...,N1,...,N 范围内一定存在jkj\neq k 使得αjαk2π/N<δ|\alpha_j-\alpha_k|\leq 2\pi/N<\delta。不失一般性设j>kj>k。则在2π2\pi 剩余系里有αjk<δ\alpha_{j-k}<\delta。因为αjk\alpha_{j-k} 一定是2π2\pi 的无理数倍,则有αjk0\alpha_{j-k}\neq 0。因此可知{ai}\{a_i\} 的子序列{al}=lαjkmod2π=αl(jk)\{a_l\}=l\alpha_{j-k}\quad mod\quad 2\pi=\alpha_{l(j-k)} 可以填满整个[0,2π)[0,2\pi) 区间,使得子序列中相邻的数距离不超过δ\delta

      又因为对于任意α,β\alpha,\betaE(Rn^(α),Rn^(α+β))=1eiβ/2E(R_{\hat{n}}(\alpha),R_{\hat{n}}(\alpha+\beta))=|1-e^{i\beta/2}|

      所以对于任意ϵ>0\epsilon>0,存在nn 使得

      E(Rn^(θ),Rn^(α)n)=1ei(nαθ)/2<ϵE(R_{\hat{n}}(\theta),R_{\hat{n}}(\alpha)^n)=|1-e^{i(n\alpha-\theta)/2}|<\epsilon

      因为对于任意θ,δ\theta,\delta 存在 n,使得nαθ<δ|n\alpha-\theta|<\delta 。加上limx01eix/2=0\lim_{x\rightarrow 0}|1-e^{ix/2}|=0, 所以其实总能找到δ,n\delta,n 使得E<ϵE<\epsilon.

    • 又因为HRn^(θ)H=Rm^(θ)HR_{\hat{n}(\theta)}H=R_{\hat{m}}(\theta), 其中,m^=(cosπ8,sinπ8,cosπ8)1+cos2π8\hat{m}=\frac{(cos\frac{\pi}{8},-sin\frac{\pi}{8},cos\frac{\pi}{8})}{\sqrt{1+cos^2\frac{\pi}{8}}}

      所以E(Rm^(θ),Rm^(α)n)=Hψ2E(Rn^(θ),Rm^(α)n)<ϵE(R_{\hat{m}}(\theta),R_{\hat{m}}(\alpha)^n)=|H|\psi\rang|^2E(R_{\hat{n}}(\theta),R_{\hat{m}}(\alpha)^n)<\epsilon

      又因为 Ex4.11 证明,对于不平行的n^,m^\hat{n},\hat{m},任意酉算子都可以表示为U=eiαRn^(θ1)Rm^(θ2)...Rn^(θc1)Rm^(θc)U=e^{i\alpha}R_{\hat{n}}(\theta_1)R_{\hat{m}}(\theta_2)...R_{\hat{n}}(\theta_{c-1})R_{\hat{m}}(\theta_{c})(共 c 项,c 为一个有限数)。

      所以

      U=Rn^(θ)n1[HRn^(θ)H]n2...Rn^(θ)nc1[HRn^(θ)H]ncE(U,U)=i=1cE(Rn^(θi),Rn^(θ)ni)E(Rm^(θi),Rm^(θ)ni)<cϵ记U'=R_{\hat{n}}(\theta)^{n_1}[HR_{\hat{n}}(\theta)H]^{n_2}...R_{\hat{n}}(\theta)^{n_{c-1}}[HR_{\hat{n}}(\theta)H]^{n_{c}}\\ 则E(U,U')=\sum_{i=1}^c E(R_{\hat{n}}(\theta_i),R_{\hat{n}}(\theta)^{n_i})或 E(R_{\hat{m}}(\theta_i),R_{\hat{m}}(\theta)^{n_i})<c\epsilon

    即任给一个酉算子 U,可以只用 Hadamard 门和π/8\pi/8 门在ϵ\epsilon 范围下近似。

    所以说,给定一个包含 m 个受控或单量子比特酉门的量子线路,可以用 Hadamard 门、受控非门和π/8\pi/8 门以任意精度 (mϵm\epsilon) 近似这个线路。(复杂度分析书上看不懂,自己写的) 近似一个包含 m 个门的量子线路,若包含很多受控门时,此时效率较低,复杂度下限在 *“单量子比特门和 CNOT 门是通用的” 一节介绍的 “将二级酉门分解成单量子比特门和 CNOT 门”*,这是个指数级别的。但当线路中单量子比特门较多时或全是单量子比特门时,复杂度急剧减小到以Θ(1/ϵ)\varTheta(1/\epsilon) 的效率近似一个单量子比特门(因为式子E(Rn^(θ),Rn^(α)n)<ϵE(R_{\hat{n}}(\theta),R_{\hat{n}}(\alpha)^n)<\epsilon 中 n 一定是<2π/ϵ<2\pi/\epsilon 的),所以近似整个线路复杂度为Θ(mm/ϵ)\varTheta(m*m/\epsilon)。这里之所以又乘了个 m,是因为在前面推导中有E(U,U)<cϵE(U,U')<c\epsilon,如果整条线路想精确到ϵ\epsilon,就需要把每个门近似所需门数乘个 m 使得每个近似都近似到ϵ/m\epsilon/m,这样总近似才能是mϵ/mm*\epsilon/m

  • 事实上,由 Solovay-Kitaev 定理,任意单量子比特门可以用离散集合中的O(logc(1/ϵ))O(log^c(1/\epsilon)) 个门近似到ϵ\epsilon 精度,其中 c 是一个很接近 2 的常数。因此事实上要在ϵ\epsilon 精度内要近似一个包含 m 个受控非门和单量子比特酉门的线路,需要离散的O(mlogc(m/ϵ))O(mlog^c(m/\epsilon)) 个门。

# 近似任意酉门一般是难的

  • 给定 n 量子比特上的酉变换 U,是否存在 n 多项式规模的线路来近似 U?答案是否定的(一定是指数级别)。

    事实上,需要多少门来产生 n 量子比特的任意状态?是指数的。为了验证这一点,设有 g 类不同的门,每个门至多有 f 个输入量子比特。f 和 g 是由计算硬件所决定的,可视为常数。设有一个包含 m 个门的 n 个量子比特的量子线路,初态为计算基态0n|0\rang^{\otimes n}。(日常看不懂书上复杂度分析自己想的尽量贴合书本:)对于线路中某一个门,假设其有一个输入状态,考虑这个门作用于哪些量子比特,共有(nf)\begin{pmatrix}n\\f\end{pmatrix} 种取法,也就是O(nf)O(n^f)(事实上,我认为这里默认 f 很小,大概就是 1~4 差不多)。然后对于每一种取法,可以把 g 种不同的门都上一遍,故一共有O(nfg)O(n^{fg}) 种可能的产出的状态。实际上这里默认了很多东西,例如什么叫 “同一类门”,我的理解是以之前两级酉门为例,n 个量子比特上的两级酉门 U 有很多,但是对应的子酉矩阵U~\tilde{U} 若是一样的则称 U 是同类的(详见单量子比特门与受控非门是通用的)。因此同类的门可以因为作用的量子比特不同而不同。此外为什么说 “最多有 f 个输入量子比特” 结果结果就是O(nf)O(n^f) 个取法,因为我认为这里默认 f 很小,然后大 O 表示法求得是一个上限。(Cn1=O(n),Cn2=O(n2)...C_n^1=O(n),C_n^2=O(n^2)...)。

    因此,m 个门对于一个输入状态0n|0\rang^{\otimes n} 的可能输出为O(nfgm)O(n^{fgm}) 种状态。

# 物理仿真

  • 之前在量子系统里我们关心的是薛定谔方程idψdt=Hψi\hbar\frac{d|\psi\rang}{dt}=H|\psi\rang,之前讨论过对于定时的 H,薛定谔方程的解需要计算eHe^H,浙江非常难求。所以好的出发点是考虑一阶:

    ψ(t+Δt)(IiHΔt)ψ(t)|\psi(t+\Delta t)\rang\approx(I-iH\Delta t)|\psi(t)\rang

    \hbar 放到 H 里)的解。这是可解的,因为对许多 Hamilton 量 H 可以直接利用量子们来有效近似IiHΔtI-iH\Delta t。不过这样的解并不充分。

    近似到高阶的解对许多类 Hamilton 量是可能的。例如在大多数物理系统种,Hamilton 量可以写作局部作用和的形式:

    H=k=1LHkH=\sum_{k=1}^L H_k

    其中,HkH_k 最多作用在常数 c 数目的子系统上,而 L 是 n 的一个多项式。

  • (Trotter 公式)令 A 和 B 是 Hermite 算子,则对任意实数 t,有:

    limn(eiAt/neiBt/n)n=ei(A+B)t\lim_{n\rightarrow\infin}(e^{iAt/n}e^{iBt/n})^n=e^{i(A+B)t}

    证明:由泰勒展开

    eiAt/neiBt/n=I+1ni(A+B)t+O(1n2)(eiAt/neiBt/n)n=I+k=1n(nk)1nk[i(A+B)t]k+O(1/n)(nk)1nk=(1+O(1n))/k!limn(eiAt/neiBt/n)n=limnk=0n(i(A+B)t)kk!(1+O(1n))+O(1n)=ei(A+B)te^{iAt/n}e^{iBt/n}=I+\frac{1}{n}i(A+B)t+O(\frac{1}{n^2})\\ \Rightarrow (e^{iAt/n}e^{iBt/n})^n=I+\sum_{k=1}^n\begin{pmatrix}n\\k\end{pmatrix}\frac{1}{n^k}[i(A+B)t]^k+O(1/n)\\ \begin{pmatrix}n\\k\end{pmatrix}\frac{1}{n^k}=(1+O(\frac{1}{n}))/k!\\ \lim_{n\rightarrow\infin}(e^{iAt/n}e^{iBt/n})^n=\lim_{n\rightarrow\infin}\sum_{k=0}^n\frac{(i(A+B)t)^k}{k!}(1+O(\frac{1}{n}))+O(\frac{1}{n})=e^{i(A+B)t}

    与上面类似的证明,可以得到

    eiAΔteiBΔt+O(Δt2)=ei(A+B)teiAΔt/2eiBΔteiAΔt/2+O(Δt3)=ei(A+B)te^{iA\Delta t}e^{iB\Delta t}+O(\Delta t^2)=e^{i(A+B)t}\\ e^{iA\Delta t/2}e^{iB\Delta t}e^{iA\Delta t/2}+O(\Delta t^3)=e^{i(A+B)t}

# 算法:量子仿真

  • 输入

    • 作用在 N 维系统上的 Hamilton 量H=HkH=\sum H_k,其中每个HkH_k 作用在规模独立于NN 的小的子系统上。
    • 系统在t=0t=0 时刻的初态ψ0|\psi_0\rang
    • 正的精度δ\delta
    • 期望获得状态对应的时刻tft_f
  • 输出

  • 状态ψ~(tf)|\tilde{\psi}(t_f)\rang,使得(ψ~(tf),eiHtψ0)2=ψ~(tf)eiHtψ021δ(|\tilde{\psi}(t_f)\rang,e^{-iHt}|\psi_0\rang)^2=\lang\tilde{\psi}(t_f)|e^{-iHt}|\psi_0\rang^2\geq 1-\delta

  • 运行时间

  • O(poly(1/δ))O(poly(1/\delta))

  • 过程

    • 选择一个表示使得n=poly(logN)n=poly(logN) 个量子比特的状态ψ~|\tilde{\psi}\rang 能近似系统状态。并且选择一个近似方法和Δt\Delta t 使得期望误差是可以接受的,并且对某个整数 j,jΔt=tfj\Delta t=t_f。为迭代构造一个相应的量子线路UΔtU_{\Delta t},执行:

      (1) ψ0~ψi;j0|\tilde{\psi_0}\rang\leftarrow|\psi_i\rang;j\leftarrow 0 状态初始化

      (2) ψ~j+1UΔtψ~j|\tilde{\psi}_{j+1}\rang\leftarrow U_{\Delta t}|\tilde{\psi}_j\rang 迭代

      (3) j=j+1j=j+1,重复 (2) 直到jΔt=tfj\Delta t=t_f

      (4) ψ~(tf)=ψ~j|\tilde{\psi}(t_f)\rang=|\tilde{\psi}_j\rang

# 例 1:薛定谔方程的量子仿真

  • 考虑在一根直线上的运动的具有一维势能V(x)V(x) 的一个单粒子,其 Hamilton 量为

    H=P22m+V(X)H=\frac{P^2}{2m}+V(X)

    其中,X 是动量算子(Pψ=ixψP|\psi\rang=-i\hbar\frac{\partial}{\partial x}|\psi\rang),X 是位置算子Xψ=xψX|\psi\rang=x|\psi\rang。其中 X 的特征值(坐标Xx=xxX|x\rang=x|x\rang)是连续的。

    而系统状态ψ|\psi\rang 处于无穷维 Hilbert 空间,在基x|x\rang 下,可写成:

    ψ=xxψdx|\psi\rang=\int_{-\infin}^{\infin}|x\rang\lang x|\psi\rang dx

    实践中,我们只对某个有限趋于dxd-d\leq x\leq d 感兴趣。各异选择离散步长(与系统最短波长相比足够小),使得:

    ψ~=k=d/Δxd/ΔxakkΔx|\tilde{\psi}\rang=\sum_{k=-d/\Delta x}^{d/\Delta x}a_k|k\Delta x\rang

    成为ψ|\psi\rang 的一个好的物理近似。这个状态可以用n=log(2d/Δx+1)n=log(2d/\Delta x+1)(上取整)个量子比特表示。

    剩下的看不懂,寄!

# 例 2

  • 设我们有作用在 n 个量子比特上的 Hamilton 量:

    H=Z1Z2...ZnH=Z_1\otimes Z_2\otimes ...\otimes Z_n

    其中ZiZ_i 为作用在第 i 个量子比特上的 Z 门。事实上,H 就作用了一件事情,即若状态s1...sn|s_1...s_n\rang 种 s 有偶数个 1,就作用相移算子eiZΔte^{iZ\Delta t};若有基数个 1,则作用相移算子eiZΔte^{-iZ\Delta t} 到系统状态上。

    1

    上图就通过引入一个辅助量子比特就精确完成了这个工作。最后得到结果后需要抹除和初态一样的辅助量子比特。

事实上任意 Hamilton 量若具有H=k=1nσc(k)H=\otimes_{k=1}^n\sigma_{c(k)} 都可以类似以上线路完成,其中σ\sigma 是 Pauli 阵。因为 X,Y 都可以用单量子比特门转换为 Z 门。