量子计算笔记Week4(coursera)

第四周将学习shor算法

官方笔记我放在最后

前言

本章全是数学推导, 所以本文会没什么内容, 官方笔记已经很详细了

对于RSA算法部分, 看wiki的RSA加密算法理解起来更快

官方在讲量子傅里叶(Quantum Fourier transform)变换时, 课件以及pdf笔记中的QFT是反的, 所以原来的x0会变成y2, wiki的Quantum Fourier transform是正的, x0变换后是y0, 最后的shor算法例子中的QFT也是正的

官方笔记错误

公式(8)下面文字下的那一行公式左边e的指数少了一个负号(下文图片中我已修复)

个人思考

在公式(22)下面证明r的唯一性那个地方我感觉有点不太对, 有公式(20)可知good y与k是一一对应的, 若存在不同的r, 式子应写成$$\left| \frac{k}{r_1} - \frac{k}{r_2}\right| = \frac{k|r_2-r_1|}{r_1 * r_2} \geq \frac{1}{r_1 * r_2} = \frac{1}{N}$$从而证明了r的唯一性

对于官方笔记的证明方法, 如果$a = 3, r_1=10, b=6, r_2=20$不就为0了?

第三页证明

关于第三页, 我用自己的话重新讲一遍证明过程, 官方笔记和课件感觉有点难理解

官方笔记第三页对a的概率证明应该是本章最难的东西了

数学知识预备

Multiplicative order

Multiplicative order

比如对于下面这句话的理解(第三页第三行)

$r_1$ and $r_2$ are the orders of $a_1$ and $a_2$ in the rings $\mathbb{Z_p}$ and $\mathbb{Z_q}$.

即, 使$a_1^{r} \equiv 1 (mod\ n)$成立的最小的正整数为$r_1$, r2同理

Fermat’s little theorem

费马小定理

看上面链接公式就可以理解第三页倒数第二行中间的话了(The order of b is $2^{k_p}s_p$)

Primitive root modulo n

Primitive root modulo n

比如对于下面这句话的理解(第三页倒数第三行)

Let $b$ be the primitive element of the field $\mathbb{Z_p}$

即当$b^{m_p}$中的${m_p}$从1到$p-1$取一遍时, 那么$b^{m_p}(mod\ p)$的值也从1到$p-1$取一遍, 顺序会乱(想要直观一点可以直接看上面wiki链接里的例子)

问题描述

当我们随机取一个a时, 满足下列条件(3)(4)的概率是多少?

$$r = 0(2) \tag{3}$$

$$(a^{r/2}+1)\neq0(N) \tag{4}$$

过程

下面证明中用$(p)$表示$(mod\ p)$, $r\mid s$表示s能整除r

现在我们已经随机选择了a

已知

r is the order of the element a in the ring $\mathbb{Z_n}$

$$a^r = 1(N)\tag{1}$$

$$N=pq$$

开始求概率

$$a_1 = a(p)\tag{2}$$

$$a_2 = a(q)$$

$r_1$ and $r_2$ are the orders of $a_1$ and $a_2$ in the rings $\mathbb{Z_p}$ and $\mathbb{Z_q}$.

$$a_1^{r_1}(p) = 1\tag{3x}$$

$$a_2^{r_2}(q) = 1$$

由(1)可知, $a^r(p) = 1$

由(2)可知, $a = pk_1 + a_1$, 将其带入上一行的式子

$$(pk_1+a_1)^r(p) = 1 \Longrightarrow a_1^r(p) = 1$$

又因为$r_1$和$r_2$是order, 故r是$r_1$的倍数, 同理r是$r_2$的倍数

构造$s = kr_1r_2$

$$a^s(p) = (pk_1 + a_1)^s(p) = a_1^{kr_1r_2}(p) = (a^{r_1})^{kr_2}(p)$$

又因为(3x)

所以$a^s(p) = 1$, 等价于

$$a^s = pk_1+1 \tag{5}$$

同理

$$a^s = qk_2+1 \tag{6}$$

(5)(6)左边相等, 所以右边相等, 即

$$pk_1 = qk_2 \tag{7}$$

p,q 互质, 所以k1一定是q的倍数

将(5)改写为

$$a^s = pq\frac{k_1}{q} + 1 \Longrightarrow a^s = 1(pq) \Longrightarrow r\mid s$$

即对于任意s都能整除r, 又因为s和r都是$r_1$和$r_2$的倍数, 且对任意s成立, 所以

$$r = LCM(r_1, r_2)$$

我们接下来把$r_1$和$r_2$进行分解(把里面的2提出来, 比如$5 = 2^05$, $28 = 2^27$)

$$r_1 = 2^{c_1}odd_1, c_1\geq0 \tag{8}$$

$$r_2 = 2^{c_2}odd_2, c_2\geq0 \tag{9}$$

如果$c_1 \neq c_2$(比如$c_1 > c_2$), 则同时满足了(3)(4)

$$r = 2r_2int$$

$$a^{r/2}=a^{r_2int}=1(q) \Longrightarrow a^{r/2}\neq-1(q) \Longrightarrow a^{r/2}\neq-1(pq)$$

$c_1$和$c_2$取决与a, 下面让我们来计算$c_1 \neq c_2$的概率

首先将p用另外一种形式表达

$$p=2^{k_p}s_p+1,\ \ s_p=1(2)$$

令$b$ be the primitive element of the field $\mathbb{Z_p}$, 由上面的Primitive root modulo n知, 可将$a_1$用另外一种方法表示出来

$$a_1 = b^{m_p}(p),\ \ m_p \in {1,\cdots,2^{k_p}s_p}$$

将上面这个式子带入(3x)

$$b^{m_pr_1} = 1(p)$$

由费马小定理可知

$$b^{p-1} \equiv 1(p) \Longrightarrow b^{2^{k_p}s_p} \equiv 1(p)$$

再根据Primitive root modulo n可知$2^{k_p}s_p$是order(因为只有当指数为p-1时才为1, 其余时为其他数字, 而p-1就是最小的正整数, 即为order)

故$m_pr_1 = 0(2^{k_p}s_p)$

同理可得$m_qr_2 = 0(2^{k_q}s_q)$

$$\begin{cases}
m_pr_1 = k_12^{k_p}s_p\\
m_qr_2 = k_22^{k_q}s_q\\
\end{cases}
$$

回忆一下, 我们只是想知道(8)(9)中含有不同的2个数的概率

最糟糕的情况, 也就是$r_1$和$r_2$有相同2个数的概率最大时候, 此时右边$k_1 = k_2 = k_q = k_p = 1$, 即右边只有一个2, 如果右边有很多个2, 那么$r_1$和$r_2$有相同2个数的概率会非常小

在最糟糕的情况下, $r_1$和$r_2$都分到2和$r_1$和$r_2$都没分到时$c_1$和$c_2$相等, $m_p$和$r_2$分到或$m_q$和$r_1$分到时$c_1$和$c_2$不相等

最糟糕的情况下概率为1/2

为什么$k_p$或$k_q$不能为0?

如果为0, 即p或q为2, 不用量子计算机也能快速分解, 所以$k_p \geq 1$, $k_q \geq 1$

官方笔记