Home - 量子计算

未来已经到来，只是还不均匀。

# Quantum Key Distribution

# Problem setup

事情是这样子的，有两个人 Alice 和 Bob。

Key Distribution 的目的就是，希望这两个人通过通信，都知道了同一个字符串（经典的字符串）。

然后问题有以下假设：

  1. Alice 和 Bob 之间有两条信道：一个是量子的，一个是经典的。
  2. 有一个小贼 Eve，她可以获得所有 Alice 和 Bob 之间的通信的信息。
  3. Eve 可以对量子信道上的量子态进行任意操作（譬如修改，丢弃，测量等等）。但是对于经典信道 Eve 只能监听和丢弃信息，并不能修改。（这是假设经典的通信已经有成熟的协议保证安全性了）

那该怎么通信，才能在不让 Eve 知道的前提下，使得 Alice 和 Bob 都知道了同一个字符串呢？

尝试 0：Alice 随机生成一个字符串ss，然后通过经典信道发送给 Bob。

显然这很猪，因为 Eve 直接监听到了ss，失败。

尝试 1：Eve 直接把所有接收到的信息都 drop 掉。

这是玉石俱焚的行为。实际上，我们研究的困难点主要是避免下面两种情况：

  1. Alice 和 Bob 都以为自己获得了 key，结果他们的 key 不一样。
  2. Eve 窃取到了 key。

所以不妨假设 Eve 不去 drop 信息。因为 drop 后，Alice 和 Bob 就认为通信失败了，根据协议应该接收到的消息没收到，从而 Alice 和 Bob 就放弃了这条信道，重新建立信道去了。

# 协议 [BB84]

这个协议的内容很简单：

  1. Alice 随机选择4n4n 个随机的 0/1 经典比特，记为aa。

  2. Alice 随机选择4n4n 个随机的 0/1 经典比特，记为bb。

  3. Alice 生成4n4n 个量子比特q1,...,q4nq_1,...,q_{4n}，其中：

    qi={∣0⟩ai=0,bi=0∣1⟩ai=1,bi=0∣+⟩ai=0,bi=1∣−⟩ai=1,bi=1q_i=\begin{cases} |0\rangle &a_i=0,b_i=0\\ |1\rangle &a_i=1,b_i=0\\ |+\rangle &a_i=0,b_i=1\\ |-\rangle &a_i=1,b_i=1 \end{cases}

    然后将它们发送给 Bob。

  4. Bob 收到量子比特后，回复 Alice 自己确认收到。

  5. 然后 Bob 随机生成4n4n 个 0/1 经典比特，记为b′b'。并对收到的量子比特进行测量。若bi′=0b'_i=0，那么就对qiq_i 在{∣0⟩,∣1⟩}\{|0\rangle,|1\rangle\} 下测量，若bi′=1b'_i=1，那么就在{∣+⟩,∣−⟩}\{|+\rangle,|-\rangle\} 下测量。测量结果也是一个长为4n4n 的 0/1 经典比特串，记为a′a'。

  6. Alice 把bb 传输给 Bob。Bob 把b′b' 传输给 Alice。Alice 和 Bob 都丢弃bi≠bi′b_i\neq b'_i 的那些ai,ai′a_i,a_i'。这一步，大概率两人会留下超过2n2n 个经典比特。不妨假设两人留下了2n2n 个经典比特。

  7. Alice 随机 sample 一个大小为nn 的集合S⊆[2n]S\subseteq [2n]，然后告诉 Bob SS 和{ai∣i∈S}\{a_i\mid i\in S\}。Bob 会比较收到的aia_i 和自己的ai′a_i'，如果∀i∈S.  ai=ai′\forall i\in S.\;a_i=a_i'，那 Bob 就回复 Accept。

  8. 如果 Accept，那么 Alice 和 Bob 分别把a1a2...ana_1a_2...a_n 和a1′a2′...an′a'_1a'_2...a'_n 中那些i∈Si\in S 丢弃掉，剩下的nn 个经典比特就是 share 的 key。

我们分析一下这个协议。

首先，第 7，8 步，可以看作一个简单的 sampling test。

这个 test 的目的是保证 agreement，即如果通过这个 test（Bob 回复 Accept），那么 Alice 和 Bob 大概率 share 的 key 是一样的。同样的，如果 Eve 进行了影响 key 的修改，那么大概率就无法通过 test 了。

我们先来说明这件事。

这个可以抽象为：

给定任意两个长度为2n2n 的 0/1 串aa 和bb。（这里的任意，就是假设 Eve 可以随心所欲地修改）

不失一般性，假设a,ba,b 有μn\mu n 位不一样。

那么对于任意一个阈值δ>0\delta>0，我们随机 sample 一个大小为nn 的集合S⊆[2n]S\subseteq[2n]，有直观感觉：

若μ\mu 很大，那么SS 中至少有δn\delta n 位aa 和bb 不一样，是大概率的（和δ,μ,n\delta,\mu,n 有关）。

那么逆反地，若SS 中只有很少的（<δn<\delta n）几位是不一样的，那么我们就认为大概率μ\mu 也是很小的。

形式化地，我们考虑长为2n2n 的串cc，满足ci={1ai≠bi0ai=bic_i=\begin{cases}1&a_i\neq b_i\\0&a_i=b_i\end{cases}。

那么原说法相当于任意给一个cc，我们 sample 一个S⊆[2n]S\subseteq [2n]，那么应该可以得到如下式子：

Prob[∑i∈Sci≤δn]<...\text{Prob}\left [\sum_{i\in S}c_i\leq\delta n\right ]<...

我们考虑ci=1c_i=1 的每一位，随机 sample 一个大小为nn 的集合的话，有：

Prob[i∈S]=C2n−1n−1C2nn=12Prob[i∉S]=C2n−1nC2nn=12\text{Prob}[i\in S]=\frac{C_{2n-1}^{n-1}}{C_{2n}^n}=\frac{1}{2}\\ \text{Prob}[i\notin S]=\frac{C_{2n-1}^n}{C_{2n}^n}=\frac{1}{2}

因此，我们可以记一个随机变量Zi={1i∈S0i∉SZ_i=\begin{cases}1&i\in S\\0&i\notin S\end{cases}。那么就有：

∑i∈Sci=∑i=1,ci=1nZi\sum_{i\in S}c_i=\sum_{i=1,c_i=1}^nZ_i

而ZiZ_i 以12\frac{1}{2} 的概率取00 或11。那么根据 Hoeffding’s inequality，有：

Prob[1μn∑i=1,ci=1n(Zi−E[Zi])≤−t]≤exp(−2μnt2)\text{Prob}\left [\frac{1}{\mu n}\sum_{i=1,c_i=1}^n(Z_i-\mathbb{E}[Z_i])\leq -t\right ]\leq\text{exp}\left (-2\mu nt^2\right )

所以：

Prob[∑i=1,ci=1nZi≤12μn−tμn]≤exp(−2μnt2)\text{Prob}\left [\sum_{i=1,c_i=1}^nZ_i\leq \frac{1}{2}\mu n-t\mu n\right ]\leq\text{exp}\left (-2\mu nt^2\right )

我们令12μn−tμn=δn\frac{1}{2}\mu n-t\mu n=\delta n，那么取t=12−δμt=\frac{1}{2}-\frac{\delta}{\mu}，那么有：

Prob[∑i∈Sci≤δn]≤exp(−2μn(12−δμ)2)≤exp(−2μn(14−δμ))=exp((−12μ+2δ)n)\begin{aligned} \text{Prob}\left [\sum_{i\in S}c_i\leq\delta n\right ]&\leq\text{exp}\left (-2\mu n\left (\frac{1}{2}-\frac{\delta}{\mu}\right )^2\right )\\ &\leq\text{exp}\left (-2\mu n\left (\frac{1}{4}-\frac{\delta}{\mu}\right )\right )\\ &=\text{exp}\left (\left (-\frac{1}{2}\mu +2\delta \right )n\right ) \end{aligned}

我们分析上述不等式，可以得到两个个结论。

对于长为2n2n 的 01 串a,ba,b，若a,ba,b 有μn\mu n 位不一样，那么我们随机 sample 一个大小为nn 的集合S⊆[2n]S\subseteq[2n]：

  1. μ\mu 越大，sample 的集合中至少有δn\delta n 位不一样的概率越大。不容易通过 test。
  2. δ\delta 越大，sample 的集合中至少有δn\delta n 位不一样的概率越小。容易通过 test。

当δ=0\delta=0，即原协议中说的，那么就有 test 不通过的概率：

ProbS⊆[2n],∣S∣=n[∃i∈S.ai≠bi]≥1−exp(−μn/2)\mathop{\text{Prob}}_{S\subseteq [2n],|S|=n}\left [\exists i\in S.a_i\neq b_i\right ]\geq 1-\text{exp}(-\mu n/2)

可以看到，错误越多（μn\mu n 越大），越不容易通过 test。

除了 agreement，我们还需要分析 secrecy。这个就简单很多，也就是 Eve 无法窥探到 key 值。

当 Alice 随机生成量子比特给 Bob 时，可以看作随机从{∣0⟩,∣1⟩,∣+⟩,∣−⟩}\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\} 中，随机重复选择了(4+δ)n(4+\delta)n 个。所以在 Eve 看来这个 qubit 就是和随机没有区别。

（注意，∣0⟩,∣1⟩,∣+⟩,∣−⟩|0\rangle,|1\rangle,|+\rangle,|-\rangle 正好四等分 Bloch 球面上的圆周，也是单光子偏振 45，90，135，180 度的情况，所以无论怎么测量观察，它们都是均匀随机的）

由于不可克隆性，Eve 无法留下 qubit。所以当后续 Alice 发送给 Bob bb 时，Eve 此时已经无法通过测量知道 key 值了。

还有一个小 trick，就是随机生成两个长度为4n4n 的 01 串，大概率至少有2n2n 位是一样的。这留给读者证明 hhh 很简单呐。