杀(树)手(新)级(风)应用-Shor算法

初等数论记号

• a整除N记作$a\mid N\Leftrightarrow N=k\cdot a, k\in \mathbb{Z}$
• a同余于b模N记作$a\equiv b\pmod N\Leftrightarrow a-b\mid N$
• a与b的最大公约数记作$\gcd(a,b)$（辗转相除法¹）

RSA公钥系统¹

Alice随机产生大质数$p,q$，$N=p\cdot q$

• 公开发布公钥$(N,e)$。$e<r=\phi(N)=(p-1)(q-1)$
• 自己保存私钥$(N,d)$。$e\cdot d\equiv 1\pmod r$

1. Bob发送消息$m$，使用公钥加密为$c\equiv m^e\pmod N$
2. Alice收到密文$c$，根据Euler定理²使用私钥解密$c^d\equiv m^{e\cdot d}=m^{1+k\cdot r}=m(m^r)^k\equiv m\pmod N$

RSA例子¹

$p=11,q=13,e=23,m=69$(‘E’)

大数分解

破解私钥d需要对N进行整数分解

位数$n=\log(N)$，分解算法的时间复杂度

• 试除法：$\sqrt{N}=e^{n/2}$
• 普通数域筛选法（GNFS）¹：$O(e^{(\frac{64}{9}n)^{1/3}\log^{2/3}{n}})$
• Shor算法^2,3：$O(n^3)$

台式机破解RSA-2048需要$6.4\times 10^{15}$年⁴

模阶方法

1. 随机取$a<N$，若$\gcd(a,N)\neq 1$，则$\gcd(a,N)$是N的非平凡因子
2. 否则求a的阶r，即$f(x)=a^x\pmod N$的周期。应有$a^r\equiv 1\pmod N$
3. 若r为奇数，或$a^{r/2}\equiv -1\pmod N$，返回第一步
4. 因为$N\|a^r-1=(a^{r/2}-1)(a^{r/2}+1)$，$N\nmid a^{r/2}\pm 1$，所以$\gcd(a^{r/2}\pm 1,N)$都是N的非平凡因子

模阶方法例子¹

$N=143,a=2,r=60\rightarrow 143=11\times 13$

量子态记号¹

本征态内积$\langle 0|0\rangle=\langle 1|1\rangle=1, \langle 0|1\rangle=0$

量子态	复向量	$\lvert\psi_0\rangle=\frac{1}{\sqrt{2}}\left(\lvert 0\rangle+i\lvert 1 \rangle\right)=\frac{1}{\sqrt{2}}\left(\begin{matrix}1 \\\\ i\end{matrix}\right)$
测量概率	系数模方	$P(\lvert 0\rangle)=P(\lvert 1\rangle)=\frac{1}{2}$
量子门	复矩阵	$\hat{U}=\frac{1}{\sqrt{2}}\left(\begin{matrix}1 & -i\\\\ i & -1\end{matrix}\right)$
态操作	矩阵乘	$\lvert\psi_1\rangle=\hat{U}\cdot\lvert\psi_0\rangle=\left(\begin{matrix}1 \\\\ 0\end{matrix}\right)=\lvert 0 \rangle$

多量子比特

• 3比特（未归一化）直积态表示为Kronecker积¹$(\lvert 0\rangle-\lvert 1\rangle)\otimes \lvert 0\rangle \otimes(\lvert 0\rangle+\lvert 1\rangle)$=$\left(\begin{matrix}1 \\\\ -1\end{matrix}\right)\otimes \left(\begin{matrix}1 \\\\ 0\end{matrix}\right)\otimes \left(\begin{matrix}1 \\\\ 1\end{matrix}\right)$
• $$\lvert 000\rangle +\lvert 001\rangle-\lvert 100\rangle-\lvert 101\rangle=(1,1,0,0,-1,-1,0,0)'$$
• 纠缠态$\lvert 000\rangle+\lvert 111\rangle=(1,0,0,0,0,0,0,1)'=\lvert 0\rangle+\lvert 7\rangle$
• 部分量子测量²相当于密度矩阵$\rho=\lvert\psi\rangle\langle\psi\rvert$求偏迹³

量子Fourier变换

两个q量子比特寄存器，$N^2\le Q=2^q< 2N^2$，初态：$|(0\cdots 0)_q\rangle\otimes|(0\cdots 0)_q\rangle$

1. 并行的q个Hadamard门作用于寄存器1：$Q^{-1/2}\sum_{k=(0\cdots 0)_q}^{(1\cdots 1)_q}\lvert k\rangle\otimes\lvert 0=(0\cdots 0)_q\rangle$
2. 模幂门$f(\lvert k\rangle\otimes\lvert 0\rangle)=\lvert k\rangle\otimes\lvert a^k\pmod N\rangle$作用于寄存器1,2：$Q^{-1/2}\sum_{k=0}^{Q-1}\lvert k\rangle\otimes\lvert a^k\pmod N\rangle$
3. 测量寄存器2，不妨设其坍缩到$\lvert m\rangle$态：$Q^{-1/2}\sum_{k\in A_m=\lbrace k\lvert a^k\equiv m\pmod N\rbrace}\lvert k\rangle\otimes\lvert m\rangle$
4. 设$\omega$为Q次原根，量子Fourier变换作用于寄存器1：$Q^{-1}\sum\_{k\in A\_m}\sum_{n=0}^{Q-1}\omega^{kn}\lvert n\rangle\otimes\lvert m\rangle$

相位估计

• 测量寄存器1，不妨设测量到$\lvert n\rangle$态，测量概率$P\_n=\lvert Q^{-1}\sum_{k\in A_m}\omega^{nk}\rvert^2$

设a的模阶为$r$，则$A_m=\lbrace k_m+br\|0\le b\le b_m=\lfloor(Q-1-k_m)/r\rfloor\rbrace$，$P_n=Q^{-2}\lvert\sum_be^{\frac{2\pi i}{Q}n(k_m+br)}\rvert^2=Q^{-2}\lvert\sum_be^{b\frac{nr}{Q}2\pi i}\rvert^2$

• 设$t=\frac{nr}{Q}$，若t为整数，则$P_n=Q^{-2}(b_m+1)^2$

• 否则$P_n=\frac{\sin^2{(b_m+1)\pi t}}{Q^2\sin^2{\pi t}}$，$t$越接近整数，$P_n$越大

• 设$c$是最接近$t=\frac{nr}{Q}$整数，则$\frac{c}{r}$是$\frac{n}{Q}$的有理数近似

连分式展开

• 例如$0.234375=\frac{15}{64}=\frac{1}{4+\frac{4}{15}}=\frac{1}{4+\frac{1}{3+\frac{3}{4}}}=\frac{1}{4+\frac{1}{3+\frac{1}{1+\frac{1}{3}}}}$

• 各级连分数$[4]=\frac{1}{4}=0.25$，$[4,3]=\frac{1}{4+\frac{1}{3}}=\frac{3}{13}\approx 0.231$，$[4,3,1]=\frac{1}{4+\frac{1}{3+\frac{1}{1}}}=\frac{4}{17}\approx 0.235$，均为$\frac{15}{64}$的有理数近似

若$\frac{d}{s}$是$\frac{n}{Q}$的有理数近似，且满足$s<N,\lvert\frac{d}{s}-\frac{n}{Q}\rvert<\frac{1}{2Q}$，则有很大概率$s=r$或$s\|r$

Shor算法例子¹

$N=35,a=2\rightarrow 35=5\times 7$

ShorJS¹

Quantum Playground¹

进阶思考

• 量子电路描述语言：QASM
• IBM量子云计算：IBM Q
• NMR量子云计算：NMR Quantum Cloud
• 模幂量子门/QFT如何实现
• Shor算法改进（减少算法步骤，减少qubit个数）
• 如何学习量子计算（量子计算机模拟器）

量子模拟——Ising模型

铁磁性与居里点相变

经典计算方法

量子模拟方案

组成原理

量子门¹

• 量子门U为酉阵²：$\langle \psi_1\mid \psi_1\rangle=\langle \psi_0\mid U^\dagger U\mid \psi_0\rangle=1\Rightarrow U^\dagger U=I$
• 存在自共轭(Hermite³)矩阵H使得$U=e^{iH}$
• 哈密顿量(Hamiltonian⁴)不含时的Schrödinger方程⁵${\hat {H}}|\psi (t)\rangle =i\hbar {\frac {\partial }{\partial t}}|\psi (t)\rangle$的解为$\lvert\psi(t)\rangle=\hat{U}(t)\lvert\psi(0) \rangle,\hat{U}(t)=e^{-i\hat{H}t/\hbar}$
• 一般分解为基本操作（通用量子门^{6 7}）序列$U\approxeq U_n\cdots U_1=e^{-i H_n t_n/\hbar}\cdots e^{-i H_1 t_1/\hbar}$
• 部分操作通过有效哈密顿量⁸或绝热演化⁹实现

单比特量子门

Pauli矩阵¹$\sigma_x=\left(\begin{matrix}0 & 1 \\\\ 1 & 0\end{matrix}\right),\sigma_y=\left(\begin{matrix}0 & -i \\\\ i & 0\end{matrix}\right),\sigma_z=\left(\begin{matrix}1 & 0 \\\\ 0 & -1\end{matrix}\right)$

• 一般形式的2阶酉阵² $U=e^{i\phi}\left(\begin{matrix}e^{i\phi_1}\cos{\theta} & e^{i\phi_2}\sin{\theta} \\\\ -e^{-i\phi_2}\sin{\theta} & e^{-i\phi_1}\cos{\theta}\end{matrix}\right)$
• 设$\phi_1=\delta_1+\delta_2,\phi_2=\delta_1-\delta_2$则 $\begin{align}U &= e^{i\phi}\left(\begin{matrix}e^{i\delta_1} & 0 \\\\ 0 & e^{-i\delta_1}\end{matrix}\right)\left(\begin{matrix}\cos{\theta} & \sin{\theta} \\\\ -\sin{\theta} & \cos{\theta}\end{matrix}\right)\left(\begin{matrix}e^{i\delta_2} & 0 \\\\ 0 & e^{-i\delta_2}\end{matrix}\right) \\\\ &= e^{i\phi}e^{i \sigma_z \delta_1}e^{i \sigma_y \theta}e^{i \sigma_z \delta_2}\end{align}$

偶极跃迁

电偶极跃迁$\hat{H}=-\hat{\overrightarrow{d}}\cdot \overrightarrow{E}$，磁偶极跃迁$\hat{H}=-\hat{\overrightarrow{\mu}}\cdot \overrightarrow{B}$

• 以电偶极跃迁为例 $\hat{H}=-q\hat{\overrightarrow{r}}\cdot \overrightarrow{E}=-q(E_x\hat{x}+E_y\hat{y}+E_z\hat{z})$
• $\hat{H}$本征态$\mid\psi\rangle$具有确定的宇称，$x$为奇函数，$\hat{x}\mid\psi\rangle与\mid\psi\rangle$宇称相反，因此$\langle\psi\mid\hat{x}\mid\psi\rangle=0$
• $\hat{H}$对角元为0，在二能级系统中可表示为 $\hat{H}=\left(\begin{matrix}0 & \hbar\Omega^* \\\\ \hbar\Omega & 0\end{matrix}\right)\rightarrow \hbar\lvert \Omega \rvert\left(\begin{matrix}0 & 1 \\\\ 1 & 0\end{matrix}\right), \lvert \Omega \rvert \propto \lvert E \rvert$
• $$\hat{H}^{(e)}=\hbar\Omega\cos(\nu t+\phi-\overrightarrow{k}\cdot \hat{\overrightarrow{r}})\hat{\sigma}_x=\frac{1}{2}\hbar\Omega e^{i (\nu t+\phi-\overrightarrow{k}\cdot \hat{\overrightarrow{r}})}\hat{\sigma}_x+h.c.$$

相互作用绘景¹

• 设$\hat{H}=\hat{H}_0 + \hat{H}_1$，取$\hbar=1$，令$\hat{H}_I=e^{i\hat{H}_0 t}\hat{H_1}e^{-i\hat{H}_0 t}$

• 设$$

  \psi_I (t)\rangle=e^{i\hat{H}_0 t}

  \psi (t)\rangle$，则$\hat{H}_I

  \psi_I (t)\rangle=e^{i\hat{H}_0 t}\hat{H_1}

  \psi (t)\rangle$$

• $$i {\frac {\partial }{\partial t}}|\psi_I (t)\rangle = (-\hat{H}_0 e^{i\hat{H}_0 t})|\psi (t)\rangle+ e^{i\hat{H}_0 t} (i {\frac {\partial }{\partial t}}|\psi (t)\rangle)$$
• $$-e^{i\hat{H}_0 t}\hat{H}_0|\psi (t)\rangle+e^{i\hat{H}_0 t}\hat{H}|\psi (t)\rangle = {\hat {H}_I}|\psi_I (t)\rangle$$

Bloch球

旋转

universal gates

Pauli/Hadamard/Toffoli

Digital模拟

DiVincenzo判据

主流系统

Paul阱

电磁囚禁

Mathieu

势场求解

FEM/BEM

运动模拟

Euler/RungeKutta

背景撞击

真空系统

冷阱

Yb离子

电离

冷却

态制备

探测

激光

激光原理

二极管、ECDL

PDH稳频

气体吸收峰

Iodine 740nm

窄线宽激光

超稳腔

脉冲激光

脉冲Raman操作

电路

基尔霍夫定律

麦克斯韦->KCL/KVL

常见运放电路

PID

MOSFET/Inverter

整流器

滤波器

集成芯片(IC)

DDS/Lock-In

控制芯片

单片机/FPGA 时序发生 脉冲计数

光路

光学知识

几何光学、高斯光学

反射镜

增反膜(AR coating)

透镜

成像、像差、缩束

偏振元件

AOM/EOM