量子计算与量子密码基础

时间:2024-03-29 15:21:25

1 量子力学基础

1.1 什么是量子力学?

量子力学是针对物理理论的构建提出的一个数学框架或者规则的集合.
Quantum mechanics is a mathematical framework or set of rules for the construction of physical theories.

1.2 量子力学的结构

  • 描述一个封闭系统的量子状态:状态向量和状态空间(Hilbert space)
  • 描述量子状态随时间的变换:酉变换(Unitary transformation)
  • 描述对量子系统所进行的测量:投影测量(Measurement)
  • 描述一个复合系统的量子状态:张量积(Tensor product of components)

1.2.1 状态空间

任意一个量子系统都有一个复内积空间(希尔伯特空间)作为其状态空间. 封闭量子系统的状态是状态空间中的一个单位长向量.

量子比特(quantum bit, qubit)
其状态空间为二维复内积空间 C2C^2: α0+β1(αβ)\alpha |0 \rangle + \beta|1\rangle\equiv\dbinom{\alpha}{\beta}
基向量: 0=(10),1=(01)|0\rangle=\dbinom{1}{0}, |1\rangle=\dbinom{0}{1}
α2+β2=1|\alpha|^2+|\beta|^2=1
一个量子比特可以处于 0|0\rangle1|1\rangle 的叠加态(superposition)
ψ=(αβ)|\psi\rangle=\dbinom{\alpha}{\beta}

量子比特的物理模型
用原子的能级态(Energy states)表示:
基态: 0|0\rangle
激发态: 1|1\rangle
叠加态: (0+1)/2(|0\rangle+|1\rangle)/\sqrt{2} (叠加态是一种确定的状态)

1.2.2 状态演化

一个封闭量子系统状态随时间的演化可以描述为一个酉(Unitary)变换:ψ=Uψ|\psi^\prime\rangle=U|\psi\rangle, U(t1,t0)U(t_1,t_0)是只取决于时刻 t1t_1t0t_0 的酉变换:ψ(t1)=U(t1,t0)ψ(t0)\psi(t_1)=U(t_1,t_0)|\psi(t_0)\rangle

酉变换(Unitary transformations)
保持向量长度不变的线性变换. UU=IUU^\dagger=I, II 为单位算子, UU^\daggerUU 的共轭转置

量子逻辑门
量子计算与量子密码基础

酉变换是可逆的, 这是量子逻辑门的一大特点.
量子计算与量子密码基础

单量子比特门
The unitarity constraint is the only constraint on quantum gates; any unitary matrix specifies a valid quantum gate.

Pauli门
I=[1001],X=[0110],Y=[0ii0],Z=[1001]I=\begin{bmatrix}1 & 0 \\0 & 1\end{bmatrix},X=\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix},Y=\begin{bmatrix}0 & -i \\i & 0\end{bmatrix},Z=\begin{bmatrix}1 & 0 \\0 & -1\end{bmatrix}

Hadamard门
量子计算与量子密码基础

H0=0+12,H1=012,H=12[1111]H|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}},H|1\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}},H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\1 & -1\end{bmatrix}
H2=I,H=(X+Z)/(2)H^2=I, H=(X+Z)/\sqrt(2)
HXH=Z,HZH=X,HYH=YHXH=Z, HZH=X, HYH=-Y

双量子比特门
控制非门(controlled-NOT, CNOT)
两个输入qubit, 控制量子位(control qubit) 和目标量子位(target qubit), 如果控制位是0, 目标位保持不变; 如果控制位是1, 目标位反转.
0000,0101|00\rangle\to|00\rangle, |01\rangle\to|01\rangle
1011,1110|10\rangle\to|11\rangle, |11\rangle\to|10\rangle
x,yx,yx|x,y\rangle\to|x,y\bigoplus x\rangle (\bigoplus: 模2加运算, 此处可以看作异或)
量子计算与量子密码基础
量子计算与量子密码基础
CNOT门的矩阵表示
UCNOT=[1000010000010010]U_{CNOT}=\begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 0 & 1\\0 & 0 & 1 & 0\end{bmatrix}

普适量子计算: 任何一个量子计算过程(酉变换)都可以由有限个控制非门和所有单量子比特门一起实现.

1.2.3 量子测量

假设用规范正交基 e1, ,ed{|e_1\rangle, \cdots, |e_d\rangle}去测量状态 x|x\rangle, 则获得结果 jj 的概率是 P(j)=ejx2P(j)=|\langle e_j|x\rangle|^2.
测量会干扰系统, 使其状态根据测量结果 jj 变为 ej|e_j\rangle.

用标准基测 0|0\rangle, 1|1\rangle 测量叠加态 α0+β1\alpha|0\rangle+\beta|1\rangle 可得:

  • 结果为0的概率为 α2|\alpha|^2,
  • 结果为1的概率为 β2|\beta|^2.

重复测量会得到同样的结果.
可以使用任意一组正交基进行测量.
例如使用 +,{|+\rangle, |-\rangle} 对叠加态 α0+β1\alpha|0\rangle+\beta|1\rangle 进行测量, 其中 +=(0+1)/2|+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}, =(01)/2|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}

  • 测得结果为 +|+\rangle 的概率为 12(α+β)2\frac{1}{2}(\alpha+\beta)^2;
  • 测得结果为 |-\rangle 的概率为 12(αβ)2\frac{1}{2}(\alpha-\beta)^2.

可观测量(Observable)
可观测量即所谓的物理量, 数学上表示为一个自共轭的算子(矩阵)
所谓对物理量进行测量, 指用相应的算子的一组完备特征向量所组成的规范正交基对系统进行测量, 其测量结果为相应的特征值.

1.2.4 复合系统

一个复合物理系统的状态空间是其各个子系统状态空间的张量积.

2qubit2-qubit 状态空间 (C2C2=C4C^2\otimes C^2=C^4)
计算基态: 00,01,10,11|0\rangle\otimes|0\rangle, |0\rangle\otimes|1\rangle, |1\rangle\otimes|0\rangle, |1\rangle\otimes|1\rangle
符号表示: 00=00=0,0=00|0\rangle\otimes|0\rangle = |0\rangle|0\rangle = |0,0\rangle=|00\rangle

多量子比特
kqbitk-qbit 是一个 2k2^k 维的量子系统, 可以由 kk 个量子比特的张量积构成.

基向量: x=x1x2xk,(xi0,1)|x\rangle=|x_1x_2\cdots x_k\rangle, (x_i\in {0, 1})

一般的 2qubit2-qubit 状态:
α00+β01+γ10+δ11\alpha|00\rangle + \beta|01\rangle+\gamma|10\rangle + \delta|11\rangleα2+β2+γ2+δ2=1|\alpha|^2+|\beta|^2+|\gamma|^2+|\delta|^2=1

乘积态: ab|a\rangle|b\rangle

1.3 贝尔态(Bell state)/EPR pair

共有四个贝尔态:
B00=12(00+11),B01=12(01+10)|B_{00}\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle), |B_{01}\rangle=\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)B10=12(0011),B11=12(0110)|B_{10}\rangle=\frac{1}{\sqrt{2}}(|00\rangle-|11\rangle), |B_{11}\rangle=\frac{1}{\sqrt{2}}(|01\rangle-|10\rangle)

贝尔态可以由一个输入通过一个Hadamard门和CNOT门的组合生成, 不同的输入对应不同的贝尔态.
量子计算与量子密码基础

输入( xy \mid xy\ \rangle) 输出
00 \mid 00\ \rangle B00 =12(00 +11 )\mid B_{00}\ \rangle=\frac{1}{\sqrt{2}}(\mid 00\ \rangle+\mid 11\ \rangle)
01 \mid 01\ \rangle B01 =12(01 +10 )\mid B_{01}\ \rangle=\frac{1}{\sqrt{2}}(\mid 01\ \rangle+\mid 10\ \rangle)
10 \mid10\ \rangle B10 =12(00 11 )\mid B_{10}\ \rangle=\frac{1}{\sqrt{2}}(\mid 00\ \rangle- \mid 11\ \rangle)
11 \mid 11\ \rangle B11 =12(01 10 )\mid B_{11}\ \rangle=\frac{1}{\sqrt{2}}(\mid 01\ \rangle-\mid 10\ \rangle)

贝尔态的测量结果是相关联的, 对第二个qubit测量的结果总是与第一个qubit的测量结果相同, 也就是说, 对贝尔态的测量结果只能是 00|00\rangle11|11\rangle.

1.4 Quantum teleportation

在发送者和接收者之间没有量子通信信道的情况下实现状态传输.

  • Alice有一个处于叠加态 ψ=α0+β1|\psi\rangle=\alpha|0\rangle+\beta|1\rangle 的量子比特. 她想把该状态发送给在远处的Bob.
  • Alice和Bob之间不允许直接进行量子比特传输, 但是Alice和Bob之间共享一个EPR对 B00|B_{00}\rangle

算法模型

  • Step 0: 系统的初始状态为ψ0=ψB00=12(α0+β1)(00+11)|\psi_0\rangle=|\psi\rangle|B_{00}\rangle=\frac{1}{\sqrt{2}}(\alpha|0\rangle+\beta|1\rangle)(|00\rangle+|11\rangle), 其中前两个qubit属于Alice, 最后一个qubit属于Bob.
  • Step 1: Alice首先用CNOT门作用于她的两个qubit, 从而状态变为ψ1=α20(00+11)+β21(10+01)|\psi_1\rangle=\frac{\alpha}{\sqrt{2}}|0\rangle(|00\rangle+|11\rangle)+\frac{\beta}{\sqrt{2}}|1\rangle(|10\rangle+|01\rangle).
  • Step 2: Alice用Hadamard门作用于第一个qubit, 从而得到 ψ2(00ψ+01Xψ+10Zψ+11XZψ)|\psi_2\rangle\propto(|00\rangle|\psi\rangle+|01\rangle X|\psi\rangle+|10\rangle Z|\psi\rangle+|11\rangle XZ|\psi\rangle).
  • Step 3: Alice对她的两个qubit做测量, 然后告诉Bob测量结果, 例如, 如果测量得到 01|01\rangle, 则 ψ3=01Xψ|\psi_3\rangle=|01\rangle X|\psi\rangle.
  • Step 4: 由于Bob获取了测量结果, 从而他可以用酉矩阵对量子态进行纠正. 在上面的例子中, X(Xψ)=X2ψ=ψX(X|\psi\rangle)=X^2|\psi\rangle=|\psi\rangle, 也就是说, Bob最终可以接收到 ψ4=01ψ|\psi_4\rangle=|01\rangle|\psi\rangle.

Teleportation 不能实现超光速通信, 因为为了完成teleportation, Alice必须通过经典通信信道发送她的测量结果给Bob.

2 量子密码基础

2.1 量子**分发(Quantum key distribution, QKD)

传统密码学中, 只有一次一密是信息论安全的.

QKD利用量子力学中的不确定性原则作为密码学的基础. 在传统的信息论和密码学中, 数字通信原则上是会受到被动地监听和复制的. 然而, 当信息被以非正交量子态(如偏振方向为0°, 45°, 90° 和135°的单光子)编码后, 窃听者在不知道传输过程中使用的**的情况下, 原则上不能可靠地读取或复制. 窃听者也不能在获取部分信息的同时不以随机不可控的方式改变它(这会被合法用户发现)
量子计算与量子密码基础

2.2 量子比特承诺

比特承诺一般包括两个阶段, 承诺阶段和打开阶段

  • 承诺阶段: Alice向Bob承诺一个比特b, 要求: Bob无法知道b的信息(隐蔽性)
  • 打开阶段: Alice向Bob正式她在第一阶段承诺的确实是b, 但Alice无法欺骗Bob, 即不能篡改b的值(约束性)

比特承诺是密码学的一个重要组成部分, 它是构造安全掷币协议, 不经意传输和零知识证明等的基础.

经典比特承诺协议的安全性基于计算复杂性假设. 人们希望通过量子途径, 探索实现无条件安全比特承诺的可行性.

[BB84] 提出的量子比特承诺协议

  • Alice和Bob首先协商一个安全参数 ss
  • 在承诺阶段, 若Alice承诺的是 b=0b=0, 则她制备 ss 个处于 zz 基基态的单光子, 即 0|0\rangle 态或 1|1\rangle 态; 反之若 b=1b=1, 则制备 ss 个处于 xx 基基态的单光子, 即 +|+\rangle 态或 |-\rangle 态. 最后将这 ss 个单光子发送给Bob. Bob收到这 ss 个单光子后, 随机选择 zz 基或 xx 基测量, 并记录测量结果.
  • 在打开阶段, Alice告诉Bob她的承诺 bb 和每个光子所处的量子态. Bob根据选择正确测量基的一半光子的测量结果判断Alice是否说谎. 若无, Bob相信Alice之前的承诺.

2.3 量子秘密共享(Quantum Secret Sharing, QSS)

多为 (n,n)(n,n) 门限方案, 最简单为 (2,2)(2,2) 情形.

QSS根据共享信息的不同, 可分为共享经典/量子信息两类.

2.3.1 KKI协议

KKI使用两粒子纠缠态实现QSS, 其安全性基于非正交态不可区分性.

双偏振纠缠粒子
The state generated from a type-II parametric down-conversion crystal: ψ=12(z+AzB+eiαzAz+B)|\psi\rangle=\frac{1}{\sqrt{2}}(|z+\rangle_A|z-\rangle_B+e^{i\alpha}|z-\rangle_A|z+\rangle_B)

  • α\alpha: 晶体的双折射相移(birefringent phase shift of the crystal)
  • z+|z+\rangle, z|z-\rangle: 自旋本征态(spin eigenstate)或水平和垂直偏振本征态(horizontal and vertical polarization eigenstates)
  • A, B: Alice and Bob

通过双折射相移(birefringent phase shift)或者偏振转换(polarization conversion)可以把上述状态转化为四个贝尔态:
ϕ±=12(z+Az+B±zAzB|\phi^{\pm}\rangle=\frac{1}{\sqrt{2}}(|z+\rangle_A|z+\rangle_B\pm|z-\rangle_A|z-\rangle_Bψ±=12(z+AzB±zAz+B|\psi^{\pm}\rangle=\frac{1}{\sqrt{2}}(|z+\rangle_A|z-\rangle_B\pm|z-\rangle_A|z+\rangle_B

上述状态用zz方向的基z+,z{|z+\rangle,|z-\rangle}表示. 下面定义xx-自旋本征态:
x+=12(z++z),x=12(z+z)|x+\rangle=\frac{1}{\sqrt{2}}(|z+\rangle+|z-\rangle), |x-\rangle=\frac{1}{\sqrt{2}}(|z+\rangle-|z-\rangle)
用这两组基重新表示贝尔态:

ϕ+=12(x+Ax+B+xAxB)|\phi^+\rangle=\frac{1}{\sqrt{2}}(|x+\rangle_A|x+\rangle_B+|x-\rangle_A|x-\rangle_B)ϕ=12(x+AxB+xAx+B)|\phi^-\rangle=\frac{1}{\sqrt{2}}(|x+\rangle_A|x-\rangle_B+|x-\rangle_A|x+\rangle_B)ψ+=12(x+Ax+BxAxB)|\psi^+\rangle=\frac{1}{\sqrt{2}}(|x+\rangle_A|x+\rangle_B-|x-\rangle_A|x-\rangle_B)ψ+=12(xAx+Bx+AxB)|\psi^+\rangle=\frac{1}{\sqrt{2}}(|x-\rangle_A|x+\rangle_B-|x+\rangle_A|x-\rangle_B)

定义贝尔态的线性组合:
Ψ+12(ϕ+ψ+)|\Psi^+\rangle\equiv\frac{1}{\sqrt{2}}(|\phi^-\rangle+|\psi^+\rangle)=12(z+Ax+B+zAxA)=\frac{1}{\sqrt{2}}(|z+\rangle_A|x+\rangle_B+|z-\rangle_A|x-\rangle_A)=12(x+Az+B+xAzB)=\frac{1}{\sqrt{2}}(|x+\rangle_A|z+\rangle_B+|x-\rangle_A|z-\rangle_B)

对于状态集合ψ+,ϕ,Ψ+,Φ{\psi^+,\phi^-,\Psi^+,\Phi^-}具有如下性质: ψ+ϕ=Ψ+Φ=0\langle\psi^+|\phi^-\rangle=\langle\Psi^+|\Phi^-\rangle=0

从而可以利用这一性质对需要共享的信息做简单的编码.

另外, 来自两个不同集合的状态是非正交的, 即
ψ+Ψ+2=ψ+Φ2=12,ϕΨ+2=ϕ+Φ2=12|\langle\psi^+|\Psi^+\rangle|^2=|\langle\psi^+|\Phi\rangle|^2=\frac{1}{2}, |\langle\phi^-|\Psi^+\rangle|^2=|\langle\phi^+|\Phi^-\rangle|^2=\frac{1}{2}
这一性质是下面给出的基于两粒子纠缠的协议实现窃听检测的关键.

两粒子纠缠秘密共享协议

  • 发送者选择状态0,1ψ+,ϕ{|0\rangle,|1\rangle}\Leftrightarrow{|\psi^+\rangle,|\phi^-\rangle}, 对二进制随机比特串 SS 做编码.
  • Alice和Bob分别接收到一种粒子(光子), 然后随机用 zzxx 基进行测量.
  • 发送者随机选择部分粒子进行窃听检测: Alice和Bob先公开测量结果, 再公开测量基(且先公开结果的后公开基).
  • 发送者根据初始态计算错误率, 如果错误率足够低则继续.
  • Alice和Bob公开其余粒子的测量基, 发送者公开初始基, 以一半的概率, Alice和Bob的测量结果与发送者的初始态具有关联, 因此Alice和Bob合作可以推出发送者的量子态.