前言

这是量子计算的课程笔记，教材是:

Ronald de Wolf. Quantum Computing: Lecture Notes
Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information

推荐入门和实践向的书有:

付鹏, 向宏, 向涛. 量子算法与编程入门. 重庆大学出版社
李承祖等. 量子通信和量子计算. 国防科技大学出版社
赵生妹, 郑宝玉. 量子信息处理技术. 北京邮电大学出版社
陈汉武. 量子信息与量子计算简明教程. 东南大学出版社
张镇九, 张昭理, 李爱民. 量子计算与通信加密. 华东师范大学出版社

以下大概是把那个Lecture Note的重要部分加以汉译、补充和注解。

量子计算

元哲学: 忽略量子力学的物理意义和哲学争端，只是去嫁接半透明的已知事实，并用以做出我们想要的高速计算机器
计算材料: 不是我们所熟悉的从若干沙砾或绳结中抽象出来的边界清晰的自然数，而是从一堆微观粒子的状态中抽象出来的可观测表象(这使得它最初可能看上去有点反数学)
计算方法: 不是从复杂的约束条件组出发一步步循序构造等价规约而得到一个简化式作为答案，而是用疑似答案的猜想作为筛子在一个完备的解空间中筛查以验明是否存在此分量——像是个滤波过程

数学基础: 内积空间与Dirac记号

这一套记号用来代替实空间线性代数里的那些符号，没有什么新东西，但它很好用，主要是在表记共轭和对偶元素上体现出了简洁的美感w

矢量

论域: 带内积的有限维复空间，其实就是希尔伯特空间的某些离散子空间
元素: 空间里的列向量，即(x1, x2, …, xn)^T，其中xi∈C
右矢(ket): 就是个列向量，符号记作|ψ>，比如|ψ>=(2-3i, -1+5i)^T；从右尖括号就可以看出是列向量，因此以后不再注明转置角标T
左矢(bra): 就是个行向量，符号记作<ψ|，比如<ψ|=(2+3i, -1-5i)
左右矢关系: 不妨设左矢在空间V中，右矢在空间W中，对V中的任何一个左矢取其共轭转置就会出现在W中，即有关系<ψ| = |ψ>†，这个十字符号即先共轭再转置，读作dagger(匕首)——反之亦然；也就是说这两个空间是对偶的

算子/空间变换、内外积

线性算子: 就是个矩阵A，表示了从空间V到空间W的某个变换
特征值/特征向量: 若对线性算子A来说存在向量|v>和数v，使得A|v>=v|v>，则称A对应于特征向量|v>的特征值为v；注意这里|v>和v不能混淆，也可以按线性代数的符号把v写作λ
厄米共轭: 任何线性算子A都有其共轭转置版本记作A†，使得对任意|v>, |w>有<v|A|w> = <w|A†|v>

内积: 一个函数f: (v: V, w: W) -> C，定义为<v|w>，就是个左矢(行)乘以右矢(列)，内积是个复数
外积: 一个函数f: (v: V, w: W) -> Cⁿ，定义为|v><w|，就是个右矢(列)乘以左矢(行)，外积是个复矩阵
正交: 两个向量内积为0，即<v|w>=0
模: ||v||₂ = sqrt(<v|v>)
归一: 一个向量模为1，即<v|v>=1
完备关系: Σ_i|i><i| = I，其中{|i>}是空间V中的一组标准正交基，I是单位阵
e.g. A = IvAIw = Σ|vi><vi|A|wj><wj| = Σ<vi|A|wj>|vi><wj|，其中vi, wj分别是V, W中的正交基

几类常用算子

正规算子: 满足A†A = AA†的算子A，特性是可作对角化/谱分解
酉算子: 满足A†A = AA† = I的算子U，特性是正规、保内积不变；相当于实阵中的正交阵
厄米算子: 满足H = H†的算子H，特性是正规、主对角线全实数、主对角两侧翻折共轭、特征值全实数；相当于实阵中的对称阵
投影算子: 满足P^2 = P的厄米算子P，或可写作P = Σ[x, k]|i><i|，其中|i>是空间V中的一组标准正交基，特征是只有主对角线上元素才可能非零

张量积、算子函数、对易/反对易

张量积: 矩阵上的某二元运算，可以把维度为n和m的两个小矩阵变称维度为n*m的大矩阵，即有An ⊗ Bm = Cnm，具体算法例如下例:

A = [1 2   B = [-1 0 1]
     3 4]

A ⊗ B = [-1*A 0*A 1*A]
      = [-1 -2 0 0 1 2
         -3 -4 0 0 3 4]

向量间张量积的记号简写: |v>⊗|w> = |v>|w> = |v,w> = |vw>
张量积和矩阵乘积的运算律:

(A⊗B)(C⊗D) = (AC)⊗(BD)
(A⊗B)|vw> = (A⊗B)(|v>⊗|w>) = (A|v>)⊗(B|w>)

算子函数: f: A -> A，若A可作谱分解A = Σa|a><a|，则定义f(A) = Σf(a)a|a><a|即把f作用在特征值上
e.g. 迹: tr(A) = ΣAii
两个有用的迹公式:

tr(A|ψ><ψ|) = Σ<i|A|ψ><ψ|i>     // 按基分解，对i求和
            = Σ<ψ|i><i|A|ψ>     // 标量的乘法交换律
            = <ψ(Σ|i><i|A|ψ>)   // Σ内无关求和变量i的成分外提
            = <ψ|A|ψ>           // 基的完备性: Σ|i><i| = I

// 即: tr(算子*右矢*左矢) = 左矢*算子*右矢

tr(|v><w|) = <v|w>
// 即，tr(外积) = 内积

对易式: [A, B] = AB - BA，其中A, B为算子，若该式为0则称A与B对易
反对易式: {A, B} = AB + BA，其中A, B为算子，若该式为0则称A与B反对易

量子力学基础

量子的叠加态矢，是一系列经典态矢的线性组合，系数因子为振幅(amplitude)
对它的操作可以是测量(measurement)，这是不可逆的；或者酉变换(unitary operation)，这是可逆的

叠加态

测量

我们无法直接去观察叠加态，只能观察到坍缩后所落在的某个经典态，我们也不会确切地知道是哪个经典态，这是随机的（可以相信这是真随机）
但我们知道坍缩后落在各个经典态的概率、即对应分量振幅的平方，也就是p(i) = α_i²，这就是波恩的几率解释
如果我们去测量一个|ψ>，它就会以概率p(i)的分布列给出结果i；这个结果i同时意味着这个量子会变成经典态|i>；(这意味着之后对它反复测量，结果都是确定且一致的而不再具随机性?)

测量的方式有很多，这几个常用:

投影测量: 使用计算基/标准基，即|i> = (0, …, 1, …, 0)，即第i个位置上为1其余为0，其实就是取单位矩阵的各个列向量
Observable: 使用密度算子
POVM测量: 使用一组完备的正定算子Ei

演化

封闭系统的演化可用一个酉矩阵描述，例即: |b> = U|a>，初态为叠加态|a>，一段时间之后变成另一个叠加态|b>，算子U只与时间相关(假设是系统定态的)、故U(t)简写作U

量子比特及存储器

量子比特: 可以表示为二维复空间里的矢量，假设空间的基是|0>和|1>，通常我们取计算基

1 2	\|0> = (1, 0) \|1> = (0, 1)

即有|ψ> = α|0> + β|1>，其中常数满足归一化α^2 + β^2 = 1

两个量子比特的复合系统状态空间就是两个单量子状态空间的张量积，因此有四个基向量、一般取:

|0> = |0>|0> = |00> = (1, 0, 0, 0)
|1> = |0>|1> = |01> = (0, 1, 0, 0)
|2> = |1>|0> = |10> = (0, 0, 1, 0)
|3> = |1>|1> = |11> = (0, 0, 0, 1)

以后我们会广泛使用|dec(i)> = |bin(i)> = (0, ..., 1(i-th), ..., 0)这个符号简写

纠缠: 一个复合系统无法拆分为几个子系统的张量积，比如态EPR = (|00> + |11>) / sqrt(2)

存储器状态两个重要公式:

全局相位外提公式: 

  |x> - |1^x> = |x> - |~x> = (-1)^x * (|0> - |1>)

哈达玛打散公式: 

  H^⊗n|x> = H^⊗n|x1,x2,x3,...,xn>
          = ⊗[1,n](H|xi>)           // 连续张量积
          = 1/sqrt(2^n) * Σ[y∈B^n](-1)^(xy)|y>    // B^n即长度为0的01串
  
*该公式重要应用: 取|x>=|0^n>时，为均匀打散

  H^⊗n|0^n> = 1/sqrt(2^n) * Σ[y∈B^n]|y>
            = (Σ[0,2^n]|x>) / sqrt(2^n)
            = (|0> + |1> + |2> + ... + |2^n>) / sqrt(2^n)

基本量子门

量子门就是个酉阵，可以写作很多种形式:

矩阵名U，或其分解Σαi|i><j|
矩阵展开形式[Uij]，单比特通常这么写
基态变换表U|i> = |i’>，多比特门通常这么写
量子线路中的一个门框图 -|U|-

常用量子门

单比特门通常有:

I = [1 0      // 单位门
     0 1]
  = |0><0| + |1><1|
I|x> = |x>

X = [0 1      // 非门，因为它的真值表是 X|i> = |1-i>
     1 0]
  = |0><1| + |1><0|
X|x> = |~x>
X|0> = |1>
X|1> = |0>

Y = [0 -i
     i  0]
  = i|0><1| - i|1><0|
Y|x> = (-1)^x*i|~x>
Y|0> = i|1>
Y|1> = -i|0>

Z = [1  0
     0 -1]
  = |0><0| - |1><1|
Z|x> = (-1)^x|x>
Z|0> = |0>
Z|1> = -|1>

(这四个称为Pauli门)

H = [1  1        // Hadamard门，H = (X+Z)/sqrt(2)
     1 -1] / sqrt(2)
H|x> = (|0> + (-1)^x|1>) / sqrt(2)
H|0> = |+> = (|0> + |1>) /sqrt(2)
H|1> = |-> = (|0> - |1>) /sqrt(2)

Rθ = [1  0       // 相移门簇，θ为参数
      0 e^iθ]
Rθ|0> = |0>
Rθ|1> = e^iθ|1>

S = [1 0         // 相位门，S = R(π/2) = T^2
     0 i]
S|0> = |0>
S|1> = i|1>

T = [1     0     // π/8门，T = R(π/4)；因为除去一个全局相位exp(πi/8)后 = diag(exp(-πi/8), exp(πi/8))
     0 e^(iπ/4)]
T|0> = |0>
T|1> = e^(iπ/4)|1>

多比特门通常有:

SWAP = [1 0 0 0        // 交换门
        0 0 1 0
        0 1 0 0
        0 0 0 1]
SWAP|xy> = |yx>

C-U = [1 0 0 0         // 单控U门，第一个比特才对第二比特作U变换
       0 1 0 0         //          右下角即为任意给定的酉矩阵U
       0 0 ? ?
       0 0 ? ?]
    = [I O
       O U]
C-U|xy> = |x>(U^x)|y>
C-U|0y> = |0y>
C-U|1y> = |1>U|y>

CNOT = [1 0 0 0        // 控制非门，第一个比特为1时才对第二比特做非门
        0 1 0 0
        0 0 0 1
        0 0 1 0]
     = [I O
        O X]
CNOT|xy> = |x,x^y>
CNOT|0y> = |0y>
CNOT|1y> = |1,~y>

Toffoli = [I O O O     // 托佛利门/CCNOT门/控控非门
           O I O O
           O O I O
           O O O X]
CCNOT|xyz> = |x,y,x&y^z>
CCNOT|0yz> = |0yz>
CCNOT|x0z> = |x0z>
CCNOT|11z> = |11,~z>

Fredkin = I ⊗ SWAP     // 受控交换门
Fredkin|0yz> = |0yz>
Fredkin|1yz> = |1zy>

门的常用关系:

H = (X + Z) / sqrt(2)

HXH = Z
HYH = -Y
HZH = X

XZ = -ZX
XZX = -Z
XYX = -Y
ZXZ = -X

C-[e^(iθ)*I] = R(θ) ⊗ I
C-Z = Z ⊗ I
C-Z(c,t) = C-Z(t,c)   // c为控制位，t为目标位

(X⊗I) * CNOT(c,t) * (X⊗I) = CNOT(~c,t)
H^⊗2 * CNOT(c,t) * H^⊗2 = CNOT(t,c)

量子线路

就是用量子门和量子导线搭建的线路，是一个巨大的酉变换

基本连接方式:

串联: 对应矩阵乘积，H1(H2|ψ>) = (H1H2)|ψ>
并联: 对应哈达玛乘积，(H1|ψ1>)⊗(H2|ψ2>) = (H1⊗H2)(|ψ1>⊗|ψ2>)

模拟经典门

1 2	NAND = CCNOT\|xy1> -> \|x,y,x&y^1> -> \|x,y,~(x&y) 扇出: CNOT\|x0> -> \|xx> 或者 CCNOT\|x10> -> \|x1x>

完备性/通用性

精确的组合:

two-level U
CNOT + U
C^N-NOT + U + X
Toffoli + C-U + U

高效逼近任意给定酉算子的组合:

CNOT + H + T
CNOT + H + T + S (S用于容错)
Toffoli + H

应用: 制作纠缠态

这个线路可以把独立的|00>变成纠缠的(|00>-|11>)/sqrt(2):

1
2
3

|0>--|H|--|    |-------> (|0>+|1>)/sqrt(2)
          |CNOT|
|0>-------|    |--|Z|--> (|00>-|11>)/sqrt(2)

应用: 量子隐形传态

设想Alice有一个未知态量子比特|φ>=α|0>+β|1>，她想经由经典信道将其(量子态|φ>)传送给Bob，这在没有更多资源的情况下是做不到的——但如果它们分有一对处于EPR态的量子对，例如|xy>=(|00>+|11>)/sqrt(2)的话，就可以实现

此时系统总状态可以描述为:

       = (α|0>+β|1>)(|00>+|11>)/sqrt(2)
=   (1/2) * |00> ⊗ (α|0>+β|1>)
  + (1/2) * |01> ⊗ (α|1>+β|0>)
  + (1/2) * |10> ⊗ (α|0>-β|1>)
  + (1/2) * |11> ⊗ (α|1>-β|0>)
          (Alice)     (Bob)

四种状态以p=1/4等概率出现

现在，Alice只需要测量自己手上的|φx>并将测量结果(2bit)通过经典信道发送给Bob，则Bob根据Alice的测量结果相应地对自己手上的|y>做如下操作:

若为00则作I变换: I(α|0>+β|1>) = (α|0>+β|1>) = |φ>
若为01则作X变换: X(α|1>+β|0>) = (α|0>+β|1>) = |φ> // X门交换|0>和|1>
若为10则作Z变换: Z(α|0>-β|1>) = (α|0>+β|1>) = |φ> // Z门把|1>反号
若为11则作ZX变换: XZ(α|1>-β|0>) = (α|0>+β|1>) = |φ>

即可让|y>变成|φ>，总的线路图如下:

Alice |φ>-|    |-|H|-|m1|========||
          |CNOT|                 ||
      |x>-|    |-----|m2|=||     ||
                          ||     ||
Bob   |y>---------------|X^m2|-|Z^m1|--> |φ>

随着Alice手中|φ>的坍缩、量子态消失，信道中2bit经典信息的发送，Bob借助该经典信息和|y>而获得/生成/重现了量子态|φ>；最终认为，该实验实现了通过经典信道传输量子态

补: 我们可以利用|x>和|y>的非定域性纠缠做一些仿似超距作用的事，但看似必须有经典信息的传输，才能最终确切产生有效的语义和理解、即信息的交换，因此信息传递仍然未能超过光速。

量子算法

算法一般思路框架: (FIXME: 叙述有问题！)

把问题视作计算一个高阶函数f: f -> B，问题的输入视作一个布尔函数f: B^n -> B^m，即n个输入m个输出
有两个寄存器Ra和Rb，Ra初始化全是|0>作为初值，Rb全是|0>或者|->作为终值
一个巨复杂的酉变换Uf/Ox作用于Ra和Rb上，以Rb中的叠加态作为有效信息
测量Rb，根据测量结果再作分析

算法的一般步骤:

准备初态|ψ>=|0^n>
哈达玛打散
作用在量子黑箱Uf上，亦即一次Ox查询
…(其他处理、多次Ox查询等等)
哈达玛还原(即再次打散)
测量全部或局部

布尔函数

所有计算问题都可以经过某种方式的编码、从而统一抽象为n元向量布尔函数f: B^n -> B^m，又可进一步拆解为m个n元布尔函数f: B^n -> B；给定某个具体的n，可知n元布尔函数一共有2^(2^n)个，Deutsch-Jozsa算法中考虑的均衡布尔函数，是n元布尔函数全集下的一个子集

要实现对于向量布尔函数f/n->m的可逆计算，首先就要把输入输出数量对齐，一般套路是设计如下的新函数F:

F: B^(n+m) -> B^(m+n)
∀(x,y) ∈ (B^n)×(B^m), st. F(x,y)=(x,y^f(x))  // y^f(x)中^为按位异或

性质: F是对合函数，即有FF=id
  F(F(x,y)) = F(x,y^f(x)) = (x,y^f(x)^f(x)) = (x,y)

特别地，对于判定性问题来说m=1，即设计
F: B^(n+1) -> B^(1+n)
∀(x,y) ∈ (B^n)×B, st. F(x,y)=(x,y^f(x))

将其迁移到量子线路上，为这个新函数F设计对应的量子线路，即定义出线性算子Uf:

|x>和|y>分别为n和m位量子寄存器
Uf|xy> = |x,y^f(x)>

同理可知，Uf是对合算子(UfUf=I)、酉算子(Uf†Uf=I)、自伴算子(Uf=Uf†)

下面不再区分布尔函数f和将其在量子线路上实现出来的线性算子Uf

量子并行性

设想经典计算中的一个n元布尔函数f/n，我们需要2^n次计算f以求得真值表

为该函数设计对应的量子线路，即一个巨大的酉变换Uf，令其输入|x>为哈达玛打散的|0^n>，即使用一次Uf即可得到完备解空间的叠加态，即U(Σ[z]|z>|0>) = Σ[z]|z>|f(z)>(此处省略了归一化因子)；这就是所谓的量子并行性

当然，止步于此并不能超出经典得随机，因为对该叠加态的测量会退相干而只得到一个结果

(正确的用法: 获得完备解空间后，继续其他酉变换以实现”滤波”，直到把想要的答案结构过滤出来，然后测量以查看是否的确存在答案)

量子黑箱Black Box/预言机Oracle/查询query

量子黑箱Uf封装了某个布尔函数f，设想n元布尔函数f: B^n -> B，箱子是黑的、内部构造不明，故将其想象为一个可进行查询的随机访问存储器(RAM):

Ox: |i,0> -> |i,xi>     // 默认初值|0>
Ox: |i,b> -> |i,b^xi>   // 按位异或，如果目标比特已经有信息为|b>

前i个比特称为地址比特(串)，最后一个比特称为目标比特
Ox称为该内存的查询机/函数的预言机

这种查询通常会改变目标比特的线性叠加分量系数

还有另一种查询方式，通常用于f输出是单个比特时，预先在目标比特中放置|->，则查询机变为:

Ox,±: |i,−> -> |i> ⊗ ((|0> - |1>)/sqrt(2) ^ xi)
            -> |i> ⊗ (|xi> - |~xi>)/sqrt(2)    // 全局相位外提
            -> |i> ⊗ (-1)^xi|->
            -> (-1)^xi * |i,−>

这种查询只改变了目标比特的全局相位: xi=0不变，xi=1反号

给定经典布尔函数f，将其用量子线路包装成量子黑箱Uf，典型的做法:

定义Uf: Uf|xy> = |x,y^f(x)>

  |x>的长度为f的输入长度
  |y>为单比特辅助位/预示位: 当且仅当f(x)=1时将预示位|y>取反，实现上Uf就是个n+1元的受控门(X + CC..CNOT)

Deutsch算法

考虑最简单的布尔函数，即一元布尔函数f: B -> B，一共只有4个:

f1(x) = 0
f2(x) = x
f3(x) = ~x
f4(x) = 1

其中f1和f4称为恒值的，f2和f3称为均衡的，则有Deutsch问题:

输入: 上述四个函数中任何一个f(x)
输出: 若f(x)恒值则0，均衡则1

则解决方案为，构建量子系统:

使用两个量子比特的寄存器|ψ>=|xy>，选基为标准计算基{|00>, |01>, |10>, |11>}
算法的酉算子: 哈达玛H
问题的量子黑箱(这就是对输入的wrap!!): 设代表/包裹f(x)的酉算子为Uf，定义Uf|xy>=|x,y^f(x)>

算法流程如下:

初始化寄存器，|ψ> = |01>
对寄存器进行哈达玛打散，|ψ> -> H^(⊗2)|ψ> = (|00>-|01>+|10>-|11>)/2
调用量子黑箱Uf，|ψ> -> Uf|ψ> = (-1)^f(0) * ((|0> + (-1)^(f(0)^f(1))|1>) / sqrt(2)) ⊗ |->
仅对第一个比特进行哈达玛(还原)，然后测量它
由理论计算公式的: 测量结果为r(即意味着最后的态为|r>)，当且仅当f(0)^f(1) = r，即r=0意味着恒值

需注意，这是个确定性算法

算法分析/具体计算步骤:

      |ψ> = |01>
H^(⊗2)|ψ> = (|00> - |01> + |10> - |11>) / 2     // 哈达玛打散
    Uf|ψ> = (|0>(|f(0)>-|~f(0)>) - |1>(|f(1)>-|~f(1)>))/2     // 全局相位外提
          = (|0>(-1)^(f(0))(|0>-|1>) - |1>(-1)^(f(1))(|0>-|1>))/2
          = (|0>(-1)^f(0) - |1>(-1)^f(1)) ⊗ (|0>-|1>) / 2
          = (|0>(-1)^f(0) - |1>(-1)^(f(0)^f(0)^f(1))) ⊗ |-> / sqrt(2)  // 异或，为了提出公因子
              (此处符号有点混乱) 次方  异或 异或
          = (-1)^(f(0)) * (|0> - (-1)^(f(0)^f(1))|1> ⊗ |-> / sqrt(2)
          = [(-1)^(f(0))] * [(|0> - (-1)^(f(0)^f(1))|1> / sqrt(2)] ⊗ [|->]
             [全局相位]           [第一个比特]                     [第二比特]
     |ψ1> = (|0> - (-1)^(f(0)^f(1))|1> / sqrt(2)
    H|ψ1> = ((1 + (-1)^(f(0)^f(1))|0> + (1 - (-1)^(f(0)^f(1))|1>) / 2
          = if f(0)^f(1) == 0    // 亦即 f(0) == f(1)
            then |0>
            else |1>

Deutsch-Jozsa算法

将Deutsch算法扩展到n元布尔函数上，得到一个非确定的概率算法

线路和流程都和Deutsch算法类似，只是使用n+1量子比特的寄存器，测量时不管末位
测量结果代表了f(x)为恒值的概率，若为1则恒值(产生|0^n>)，否则强制判定为均衡

1	H^(⊗n) * (Ox,±) * H^(⊗n)

Grover算法

情景来源: 无辅助结构(排序/索引/哈希)的数据库搜索，数据库有N条记录，快速计算给定的某个匹配准则f: Obj -> B(想象一张巨大的成绩表，每一行写着人名以及”合格/不合格”，现在需要快速查找所有不合格的人名)

问题抽象: 给定一个布尔函数f(x)，求所有使得f(x)=1的x；假设定义域大小为N，令f为1的x有M个

效率对比声明: 经典算法需要遍历表，Grover算法能在O(sqrt(N/M))次搜索后以任意大的概率找到一个匹配

考虑最简单的Grover问题:

输入: 一个n元布尔函数f(x)、只在一个点上取1其余取0，并记N=n^2
输出: 使得f(x)=1的x