Experimental Progress on Quantum Computing with Atomic Qubits (Part 1)

26 January 2018

张翔

中国人民大学物理系 离子量子科学实验室

2018.01.26

Why

经典计算面临的困难

摩尔定律发展趋势

Moore's Law

量子计算的发展

Shor算法分解速度

Time To Factor

Nat. Chem. 7, 361–363 (2015)

Quantum Chemistry

What

Quantum v.s. Classical

Quantum Classical

量子门电路(代数模型)

量子态记号1

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

     
量子态 复向量
测量概率 系数模方
量子门 复矩阵
态操作 矩阵乘

量子寄存器

量子门1

How

DiVincenzo判据1

IBM科学家DiVincenzo提出量子计算机物理实现标准

  1. 系统必须能够包含充分多、准确定义的量子比特
  2. 系统必须能够将所有量子比特准确地初始化到一个简单的初态
  3. 系统中的量子比特保持相干性的时间要足够长,应当远长于量子门操作的时间
  4. 在系统中应当能实现一组“通用量子门”,即通过这些门的排列组合,可以逼近任何一个量子门
  5. 可以准确的测量任何一个量子比特,被测量后即被准确的投影到可观测量的一个本征态,而其它未被测量的量子比特则不受影响

物理实现

Physical Systems

主流实现对比及应用场景

耦合与量子门实现

实验序列分解(单比特)

Pauli矩阵1$\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)$

容错量子计算

可能需要上万个物理qubit实现一个逻辑qubit

认识误区

我们能做什么

进阶阅读

Shor算法

初等数论记号

RSA公钥系统1

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

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

RSA例子1

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

大数分解

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

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

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

模阶方法

  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的非平凡因子

模阶方法例子1

量子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$

相位估计

设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$

连分式展开

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

Shor算法例子1

ShorJS1

Quantum Playground1