《量子算法与量子密码导论》全套教学课件

量子算法与量子密码导论第1章

量子线路模型第2章

量子力学基础第3章

量子线路模型第4章Shor算法及其应用第5章

量子搜索算法及其应用第6章

量子线路模型全套可编辑PPT课件

量子算法与量子密码导论量子线路模型

一古典密码二现代密码三量子计算对现代密码的影响四后量子时代密码本章内容

本课件是可编辑的正常PPT课件1.1古典密码古典密码学设计主要有两大基本方法，分别为置换和代换。置换：将明文字母保持不变，但顺序被打乱。典型的置换密码是移位密码，将原文中的所有明文字母都在字母表上向后（或向前）按照一个固定数目进行偏移后得出密文。“恺撒密码”就是典型的移位密码。代换：明文字母被替换，但顺序保持不变。代换密码又可进一步分为单表代换、多表代换和多字母代换。典型的代换密码包括维吉尼亚密码、普莱费尔密码等。古典密码设计本课件是可编辑的正常PPT课件1.1古典密码频率分析在密码学中，频率分析是指研究字母或者字母组合在文本中出现的频率。无论在何种自然语言体系当中，不同的文字单位都有其特定的出现频率，这个特征一般表现在长篇幅、有意义的文字序列中。以英文为例，出现频率最高的字母是e，其次是t、a、o…..找到出现频率最高的符号，假设为e并将原符号替换

找到含有e的单词，根据语言学基础尝试判断其是否可能为明文中一个合理的单词将得到新的假设重复类似步骤2的操作，直至密码破译。如果步骤2-3无法实施，则考虑将出现频率最高的符号假设为t（按照频率表从高到低依次假设），重复步骤2、3直至密码破译。本课件是可编辑的正常PPT课件1.1古典密码完善保密系统（一次一密）本课件是可编辑的正常PPT课件1.2现代密码私钥密码学

序列密码：对数据流进行连续处理的一类密码，通过密钥序列生成器产生与明文消息相同长度的密钥流序列，通过密钥流序列与明文消息流序列的异或操作完成加解密。典型序列密码包括：RC4算法、A5算法、ZUC算法等分组密码：将明文消息序列划分成固定长度的组，每组分别在密钥的控制下变换成等长的密文序列。分组密码的设计原则主要包括混淆与扩散。典型分组密码包括：AES、SM4等

杂凑函数的定义：将任意长的消息M映射为较短的、固定长度的一个值H(M)。杂凑函数H一般是公开的，需要满足单向性、抗碰撞性和抗第二原像碰撞性。典型杂凑函数包括：MD5、SHA-1、SHA-3等本课件是可编辑的正常PPT课件1.2现代密码公钥密码学明文消息密文消息密文消息公钥私钥公钥加密算法本课件是可编辑的正常PPT课件1.2现代密码公钥密码学Diffie-Hellman(DH)密钥交换协议本课件是可编辑的正常PPT课件1.2现代密码公钥密码学密钥封装机制本课件是可编辑的正常PPT课件1.2现代密码公钥密码学数字签名方案本课件是可编辑的正常PPT课件1.2现代密码公钥密码学

安全协议是建立在密码算法基础之上的高互通协议，为计算机网络和通信系统的安全需求提供直接的解决方案,是构建安全信息系统的基本要素,也是信息与网络安全的关键技术。常用的安全协议包括TLS、IKE、SSH等。本课件是可编辑的正常PPT课件1.3量子计算对现代密码的影响Shor量子算法Grover量子算法Simon算法BHT算法本课件是可编辑的正常PPT课件1.3量子计算对现代密码的影响密码算法类型功能量子计算的影响AES对称密码学加密更长的密钥SHA-2，SHA-3对称密码学杂凑函数更长的摘要输出RSA公钥密码学签名密钥建立不再安全ECDSA,ECDH（椭圆曲线密码学）公钥密码学签名密钥建立不再安全DSA（有限域密码学）公钥密码学签名密钥建立不再安全本课件是可编辑的正常PPT课件1.4后量子时代密码基于量子力学基本原理的密码学量子密钥分发量子随机数发生器基于数学问题的密码学格密码基于纠错码密码多变量密码学基于杂凑函数的密码学本课件是可编辑的正常PPT课件谢谢量子算法与量子密码导论量子力学基础一量子力学革命二量子力学数学基础三量子力学基本假设四量子力学基本现象本章内容

本课件是可编辑的正常PPT课件2.1量子力学革命1两次量子力学革命上世纪末以来，第二次量子科技革命在信息技术领域兴起，如今已接近产业化阶段在上世纪40年代兴起第一次量子科技革命，催生了原子弹、半导体晶体管、激光器等重要成果本课件是可编辑的正常PPT课件2.1量子力学革命2黑体辐射—量子的诞生马克斯·普朗克于1900年建立了黑体辐射定律的公式

为普朗克常数本课件是可编辑的正常PPT课件2.1量子力学革命1光电效应—发现光量子爱因斯坦于1905年对光电效应给出解释光束描述为一群离散的量子，现称为“光子”。从普朗克黑体辐射定律，组成光束的每一个光子所拥有的能量等于频率乘以一个常数，即普朗克常数本课件是可编辑的正常PPT课件2.1量子力学革命2氢原子—分立能级玻尔于1913年提出了氢原子的量子理论：1）原子核外的电子只能处于一些分立的稳态上，E1,E2,E3,···；2）如果电子要从能量较低的稳态跃迁到能量更高的稳态，它必须吸收一个光子；如果要从高能态跃迁低能态，它必须放出一个光子。吸收或释放的光子能量等于两个稳态间的能量差，即本课件是可编辑的正常PPT课件2.1量子力学革命2波粒二象性—波&粒子德·布罗意于1923年提出微观粒子都具有波粒二象性这个关系式后来就叫做德·布罗意公式，德·布罗意预言的电子同样具有波粒二象性后来得到了实验的证实本课件是可编辑的正常PPT课件2.1量子力学革命2波动力学—薛定谔方程薛定谔于1926年提出了薛定谔波动方程是约化普朗克常数，这个公式能够正确地描述波函数的量子行为本课件是可编辑的正常PPT课件2.1量子力学革命2矩阵力学——与波动力学统一用线性代数中的矩阵可完全描述量子力学，给出了量子力学理论简单而优美的数学语言形式上与波动力学完全等价，是量子力学的两种表现形式本课件是可编辑的正常PPT课件2.2量子力学数学基础1线性空间—狄拉克符号其共轭行向量为

其中左矢

读作bra，a*和

b*分别为

a和

b的共轭复数左矢和右矢连起来就是英文单词bra(c)ket

任意一个二维列向量子态记作

其中

a和

b都是复数，且符号

为狄拉克符号的右矢，读作ket本课件是可编辑的正常PPT课件2.2量子力学数学基础1线性空间—内积内积在量子力学中，对于向量

和

，它们内积形式如下：其结果是一个复数反过来，向量

和

的内积为

几何意义：表征两个向量之间的夹角，以及一个向量在另一向量方向上的投影

本课件是可编辑的正常PPT课件2.2量子力学数学基础1内积的性质内积当两个向量的内积是一个实数时，有特别的，当两个向量的内积为0时，即称这两个向量正交本课件是可编辑的正常PPT课件2.2量子力学数学基础1内积的性质内积向量与它自身的内积为其结果的平方根

称为向量的模，几何上表示向量的长度本课件是可编辑的正常PPT课件2.2量子力学数学基础1线性空间—希尔伯特空间线性空间：也称向量空间，常记为V，定义在某个数域K中，其元素为向量，对向量加法和标量乘法封闭内积空间：具有内积运算的线性空间希尔伯特空间：完备的内积空间，有距离和角的概念量子态由希尔伯特空间中的单位向量来描述本课件是可编辑的正常PPT课件2.2量子力学数学基础1线性空间—标准正交基希尔伯特空间中模长为1且两两正交的向量，如二维空间中的一组向量或可以表示空间中任意向量本课件是可编辑的正常PPT课件2.2量子力学数学基础2线性算子—定义n维线性空间上的线性算子可以表示成一个

n×n的矩阵定义：若映射

A:V

V保持向量加法运算和标量乘法运算，即对于

，有

则称A为线性空间V上的线性算子本课件是可编辑的正常PPT课件2.2量子力学数学基础2线性算子—厄米算子与幺正算子泡利算子：厄米算子：其转置复共轭等于它本身，即幺正算子：其转置共轭等于它的逆，即显然，四个泡利算子也都是幺正算子本课件是可编辑的正常PPT课件2.2量子力学数学基础2线性算子—外积在量子力学中有一种非常有用的表示线性算子的方法，即外积表示法。对于向量

和

，其外积为其结果是一个线性算子可用于构造测量算子，尤其是投影算子本课件是可编辑的正常PPT课件2.2量子力学数学基础3本征值与本征态当线性算子A对线性空间

V中向量

v的作用是v的倍数时，

则称

为的

A本征值，v为

A对应于本征值

的本征态由本征值与本征态的定义可得

有非平凡解的充要条件，即本征值方程为

本课件是可编辑的正常PPT课件2.2量子力学数学基础3本征值与本征态例.求泡利算子

的本征值和本征态

解：

本征方程为本征方程

解得本征值为

本课件是可编辑的正常PPT课件2.2量子力学数学基础3本征值与本征态同理可得：

因此，归一化后得：

令

为对应于本征值

的本征态，则

本课件是可编辑的正常PPT课件2.2量子力学数学基础3正规算子定理：若

A是正规算子，则其对应不同本征值的本征态是正交的定义：若算子A满足

，则称

A为正规算子

简并：对应于同一本征值的多个不同的本征态称为简并态本课件是可编辑的正常PPT课件2.2量子力学数学基础3谱分解定理及推论谱分解定理：A是一个正规算子，其本征值及相对应的本征态分别为

和

，则

A可以分解为

推论：对于正规算子A，有

若算子A可逆，则有

对于任意自然数n都成立本课件是可编辑的正常PPT课件2.2量子力学数学基础3正规算子函数

A是正规算子，f(x)为任意的解析函数，则称

f(A)为正规算子函数，且有

例如

，求解：本课件是可编辑的正常PPT课件2.2量子力学数学基础4张量积特别的，若

、

分别是V、W中的正交基，则

是

中的正交基，通常简记为

或定义

：设V、W分别是

n维和

m

维的线性空间，v、w分别是V、W中的向量，A、B分别是V、W中的线性算子，则

是由张量积

构成的nm维线性空间，张量积

是在空间

上的线性算子，有本课件是可编辑的正常PPT课件2.2量子力学数学基础4张量积的计算假定线性算子A、B在空间V、W中n×n、m×m的矩阵，则

例如，本课件是可编辑的正常PPT课件2.3量子力学基本假设1波函数假设微观物理系统的状态由一个波函数完全描述。

如果一个微观系统包含若干个粒子，而这些粒子又是按照量子力学的规律运动的话，则称此系统处于某种量子状态，简称量子态。波函数是粒子位置和时间的复函数，当一个微观系统的波函数确定时，该系统的全部性质都可以由此得出，即波函数表征了系统的量子态。本课件是可编辑的正常PPT课件2.3量子力学基本假设2量子态演化假设封闭量子系统量子态的演化由薛定谔方程描述

本课件是可编辑的正常PPT课件2.3量子力学基本假设3算子假设量子力学中的可观测量由厄米算子来表示。这里的可观测量是指可通过物理实验得到测量结果的量，它对应于经典理论中的力学量。如果算子描述对应于力学量，那么当系统处于某个本征态时，则力学量有确定值，即该本征态所对应的本征值。

本课件是可编辑的正常PPT课件2.3量子力学基本假设4测量假设若算子F为量子力学中的一个力学量，其正交归一化本征函数为，对应的概率为cn，则任一量子态可表示为：当对一个量子体系进行某一力学量的测量时，测量结果一定为该力学量算子的本征值当中的某一个，测量结果为的概率为，当测量完成后，该量子体系塌缩至量子态。

本课件是可编辑的正常PPT课件2.3量子力学基本假设5全同粒子假设在量子系统中，存在内禀属性完全相同的粒子，对任意两个这样的粒子进行交换，不会改变系统的状态。这表明在量子力学中，交换任意两个全同粒子，不会导致任何可被观测到的现象出现，也即微观粒子是不能被标识的，无法在两个电子之间做出区分，这与经典世界的情况是不同的。本课件是可编辑的正常PPT课件2.4量子力学基本现象1基本原理不可克隆原理:量子力学中对任意一个未知的量子态进行完全相同的复制的过程是不可实现的。本课件是可编辑的正常PPT课件2.4量子力学基本现象1基本原理不确定性原理:对于一个微观粒子，其位置与动量不能同时具有确定值。其位置信息的准确度越高，则同时能够获得的其动量信息的准确度越低，位置的不确定性与动量的不确定性遵守不等式本课件是可编辑的正常PPT课件2.4量子力学基本现象1基本原理不可区分原理:非正交的量子态不可能被同时精确测量。本课件是可编辑的正常PPT课件2.4量子力学基本现象2量子纠缠在量子力学里，当几个粒子在彼此相互作用后，由于各个粒子所拥有的特性已综合成为整体性质，无法单独描述各个粒子的性质，只能描述整体系统的性质，称这种现象为量子纠缠（Quantumentanglement）。纠缠是一种纯粹发生于量子系统的现象，在经典力学里找不到类似的现象。本课件是可编辑的正常PPT课件2.4量子力学基本现象3贝尔不等式1964年，约翰·贝尔在其论文中根据定域性隐变量理论提出了贝尔不等式，对于两个分隔的粒子同时被测量时其结果的可能关联程度建立了一个严格的限制关系。而量子力学预言，在某些分离系统之间关联的程度可以突破任何“定域实在性”理论中的限制，这表明量子力学是违背贝尔不等式的。本课件是可编辑的正常PPT课件量子算法与量子密码导论量子线路模型一单比特量子门二两比特量子门三量子通用门组四简单量子算法本章内容

本课件是可编辑的正常PPT课件3.1单比特量子门1单比特量子门表示常见的单比特量子门：单比特量子门即作用在单个量子比特上的幺正矩阵，在线路图中通常表示为本课件是可编辑的正常PPT课件3.1单比特量子门1单比特量子门表示其他常见单比特门：相应的，将量子线路中的U分别换成Y、Z、H、T、S即可。本课件是可编辑的正常PPT课件3.1单比特量子门1单比特量子门表示单比特旋转门：本课件是可编辑的正常PPT课件3.1单比特量子门1单比特量子门表示单比特旋转门：

本课件是可编辑的正常PPT课件3.2两比特量子门1一般两比特量子门两比特量子门，即只涉及两量子比特的幺正变换。例如两比特交换门：本课件是可编辑的正常PPT课件3.2两比特量子门2C-U两比特量子门

本课件是可编辑的正常PPT课件3.2两比特量子门2C-U两比特量子门

其他控制两比特门：本课件是可编辑的正常PPT课件3.3量子通用门组1多比特量子门

本课件是可编辑的正常PPT课件3.3量子通用门组1多比特量子门常见的Toffoli门思考：Toffoli门能用两比特门表示吗？本课件是可编辑的正常PPT课件3.3量子通用门组1多比特量子门Toffoli门等价线路

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

使得其中本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

接下来构造两级幺正矩阵使得本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

接下来构造两级幺正矩阵使得本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

接下来按照上述规则依次构造两级幺正矩阵，使得

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

分解成两级幺正矩阵的乘积。本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

给定两级幺正矩阵

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

由于另外本课件是可编辑的正常PPT课件3.3量子通用门组2量子通用门组

本课件是可编辑的正常PPT课件3.4简单量子算法1量子黑盒

本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法Deutsch算法是首个展示了量子计算优越性的玩具算法，该算法针对的是Deutsch问题设计的量子算法。Deutsch问题：给定函数判断函数是常函数还是对称函数。常函数：对称函数：本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法（1）经过H操作，系统态演化为（2）经过黑盒操作，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法（3）对第一个qubit施加H操作，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法结果分析（i）常函数时（ii）对称函数时本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法Deutsch-Jozsa问题：给定函数

，判断函数是常函数还是对称函数。常函数：或x为任意n比长常二进制串。对称函数：所有n比特长二进制串中，有一半的x，其函数值为：另一半的x，其函数值为：算法所需qubit数：n+1

输入态本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法（1）经过H门操作，系统态演化为（2）经过黑盒操作，系统态演化为（3）对前n个qubit做H操作，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法2D-J算法结果分析（i）常函数时，前n个qubit测量只能得到全0态；（ii）对称函数时，前n个qubit测量测得全0态的概率为0；因此，通过调用一次黑盒，即可判定函数的性质！本课件是可编辑的正常PPT课件3.4简单量子算法3BV算法1992年，Vazirani和Bernstein构造了一种典型的数学问题，并提出了相应的量子算法——BV算法。问题：给定未知二进制串

及函数若要确定

a

，需要调用几次函数f（x）。算法所需qubit数：n+1

输入态本课件是可编辑的正常PPT课件3.4简单量子算法3BV算法（1）经过H门操作，系统态演化为（2）经过黑盒操作，系统态演化为（3）对前n个qubit做H操作，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法3BV算法结果分析（i），中态的概率幅为因此，通过调用一次黑盒，即可通过测量得到a的值！（ii），。因此，。故本课件是可编辑的正常PPT课件3.4简单量子算法4量子傅里叶变换经典上的离散傅里叶变换是将一组复矢量

变换为另外一组复矢量

，其中量子傅里叶变换（QFT，用算子

表示）是经典离散傅里叶变换的量子形式，量子傅里叶变换将量子态

变换为可证明

是幺正变换。本课件是可编辑的正常PPT课件3.4简单量子算法4量子傅里叶变换

本课件是可编辑的正常PPT课件3.4简单量子算法4量子傅里叶变换

本课件是可编辑的正常PPT课件3.4简单量子算法5Simon算法给定函数

。要求：函数是下面两种函数中的一种。（1）函数是一一映射函数，即输入不同，函数值则不同；（2）函数是二对一的周期函数，即函数值相同当且仅当算法所需qubit数：2n

输入态本课件是可编辑的正常PPT课件3.4简单量子算法5Simon算法（1）经过H门操作，系统态演化为（2）经过黑盒操作，系统态演化为（3）对前n个qubit施加H门操作，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法5Simon算法结果分析（i）函数为一一映射时，系统态可以写为测量得到的概率为本课件是可编辑的正常PPT课件3.4简单量子算法5Simon算法结果分析（ii）函数为周期函数时，系统态可以写为测量得到的满足。本课件是可编辑的正常PPT课件3.4简单量子算法6量子相位估计算法

算法所需qubit数：n+m

本课件是可编辑的正常PPT课件3.4简单量子算法6量子相位估计算法（1）制备初始态（2）对前n个比特施加H门操作，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法6量子相位估计算法（3）对第一寄存器和第二寄存器施加黑盒操作本课件是可编辑的正常PPT课件3.4简单量子算法6量子相位估计算法（4）对前n个比特做逆傅里叶变换，系统态演化为本课件是可编辑的正常PPT课件3.4简单量子算法6量子相位估计算法（5）对前n个qubit在计算基矢下测量。结果分析：case1：

。显然有这种情况下会确定性的测量得到case2：

。此时测量得到态

的概率为本课件是可编辑的正常PPT课件谢谢量子算法与量子密码导论Shor算法及其应用一RSA公钥密码算法二Shor算法三DH秘钥交换协议四Shor算法在离散对数问题中的应用本章内容

本课件是可编辑的正常PPT课件4.1RSA公钥密码算法1RSA公钥密码算法1976年，Diffie与Hellman在其划时代的论文《密码学的新方向》一文中提出：可以利用单向函数设计一对密钥，如果公开其中的一个（公钥），并不会危害到另一个（私钥）的秘密性质。1978年，Rivest、Shamir、Adleman三人提出了著名的RSA公钥密码算法。本课件是可编辑的正常PPT课件4.1RSA公钥密码算法1RSA公钥密码算法在RSA算法中，包含了三个子算法：1.秘钥产生算法：

本课件是可编辑的正常PPT课件4.1RSA公钥密码算法1RSA公钥密码算法在RSA算法中，包含了三个子算法：2.加密算法：

并将计算结果c通过公开通信渠道发送给A.本课件是可编辑的正常PPT课件4.1RSA公钥密码算法1RSA公钥密码算法在RSA算法中，包含了三个子算法：3.解密算法：

本课件是可编辑的正常PPT课件4.1RSA公钥密码算法2经典整数分解算法

本课件是可编辑的正常PPT课件4.1RSA公钥密码算法2经典整数分解算法

本课件是可编辑的正常PPT课件4.1RSA公钥密码算法2经典整数分解算法

本课件是可编辑的正常PPT课件4.2Shor算法1Shor算法思想

本课件是可编辑的正常PPT课件4.2Shor算法2Shor算法流程

其中（1）制备初始态本课件是可编辑的正常PPT课件4.2Shor算法2Shor算法流程

（3）对两个寄存器施加量子模幂操作

，系统态演化为本课件是可编辑的正常PPT课件4.2Shor算法2Shor算法流程

（5）对第一、第二寄存器施加计算基矢下的测量操作，由量子力学的测量假设可知，此时系统以一定概率塌缩为某个态。本课件是可编辑的正常PPT课件4.2Shor算法2Shor算法流程分析：系统塌缩为态

的概率是可以证明：

本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现思路：

通过量子加法器作为基本构件构造量子模加器，再由量子模加器作为基本构件构造控制量子模乘器，最后由控制量子模乘器作为基本构件构造量子模幂操作1量子加法器非进位加法模块本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现1量子加法器进位模块CARRY的线路如下图本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现1量子加法器本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现3量子模加器练习：写出后续量子态演化过程。本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现3量子控制模乘操作量子控制模乘操作实现以下功能本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现3量子控制模乘操作练习：写出量子模乘操作中态的演化过程。本课件是可编辑的正常PPT课件4.2Shor算法3模幂的量子线路实现4量子模幂操作其中：前三条线表示x，下面两部分初始时刻是1、0。本课件是可编辑的正常PPT课件4.3DH秘钥交换协议1离散对数问题

本课件是可编辑的正常PPT课件4.3DH秘钥交换协议2DH秘钥交换协议DH秘钥交换协议由Diffie和Hellman于1976年在其合作发表的论文《NewdirectionsinCryptography》中首先提出，同时这篇文章的发表也意味着公钥密码学思想的诞生。如何在公开信道中进行安全的秘钥分发？本课件是可编辑的正常PPT课件4.3DH秘钥交换协议2DH秘钥交换协议DH秘钥交换协议流程：

本课件是可编辑的正常PPT课件4.3DH秘钥交换协议2DH秘钥交换协议DH秘钥交换协议流程：

A和B的秘钥是一样的吗？秘钥是安全的吗？本课件是可编辑的正常PPT课件4.3DH秘钥交换协议3经典离散对数问题求解算法

本课件是可编辑的正常PPT课件4.3DH秘钥交换协议3经典离散对数问题求解算法（2）大步小步算法：

本课件是可编辑的正常PPT课件4.3DH秘钥交换协议3经典离散对数问题求解算法

本课件是可编辑的正常PPT课件4.4Shor算法在离散对数问题中的应用1思想

本课件是可编辑的正常PPT课件4.4Shor算法在离散对数问题中的应用2算法流程

（0）制备初始态

本课件是可编辑的正常PPT课件4.4Shor算法在离散对数问题中的应用2算法流程

（3）对第一、第二寄存器分别施加量子傅里叶变换

，其中因此，系统状态为本课件是可编辑的正常PPT课件4.4Shor算法在离散对数问题中的应用2算法流程（4）对第一、第二、第三寄存器施加计算基矢下的测量操作。系统塌缩为态

的概率为可以证明，满足

本课件是可编辑的正常PPT课件谢谢量子算法与量子密码导论量子搜索算法及其应用

一搜索算法原理及框架二搜索算法分析及示例三Grover算法与可满足性问题四Grover算法求解代数方程组Grover算法与密钥搜索本章内容

本课件是可编辑的正常PPT课件5.1搜索算法原理及框架1背景搜索问题是一个基础性问题，在计算机科学、密码学等许多领域中，很多问题的求解均可规约为搜索问题，如路径搜索、密钥搜索、碰撞搜索等。理论上来说，一般的NP问题均可用搜索的思路进行求解。对于特定问题来说，搜索不一定是最有效的方法。很多问题自身存在特殊结构，如果能够充分利用问题特征，则可能得到更高效的求解方法。对于无结构的搜索问题，如无序数据库搜索，暴力穷举可能是最优的方法。本课件是可编辑的正常PPT课件5.1搜索算法原理及框架1量子Oracle与搜索问题给定一个输出为0或1的函数可以将函数值存入一个辅助寄存器，构造一个量子Oracle，即本课件是可编辑的正常PPT课件5.1搜索算法原理及框架1量子Oracle与搜索问题根据量子Oracle，可以给出搜索问题的形式化描述。搜索问题：给定计算未知函数的量子Oracle，找到满足条件

的输入。本课件是可编辑的正常PPT课件5.1搜索算法原理及框架2Grover搜索算法框架如果满足要求的目标文件地址为z，则可以定义函数其中可以给出量子Oracle为本课件是可编辑的正常PPT课件5.1搜索算法原理及框架2Grover搜索算法框架将量子Oracle作用于量子态则只考虑地址寄存器，量子Oracle的作用可视为本课件是可编辑的正常PPT课件5.1搜索算法原理及框架2Grover搜索算法框架与一般的量子算法类似，制备初始等概率叠加态对应Grover算法框架如图本课件是可编辑的正常PPT课件5.1搜索算法原理及框架2Grover搜索算法框架在Grover算法中，核心的部分是Grover迭代过程，其线路实现如图5.2所示。本课件是可编辑的正常PPT课件5.1搜索算法原理及框架3搜索算法的图形描述量子Oracle的作用是在目标文件地址上翻转相位，实现标记目标文件地址的功能。本课件是可编辑的正常PPT课件5.2搜索算法分析及示例1搜索算法的复杂度算法初始态为第一次迭代后，逆时针旋转角，对应量子态变为进行k次迭代后，量子态变为本课件是可编辑的正常PPT课件5.2搜索算法分析及示例1搜索算法的复杂度

这是迭代的终极目标本课件是可编辑的正常PPT课件5.2搜索算法分析及示例2搜索算法示例根据Grover算法流程，可以给出针对4个数据的Grover算法线路图以k=3时的量子Oracle为例，目标数据编码为11，则量子Oracle可以直接用一个Toffoli门实现。本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题1概述在计算机科学、密码学等许多领域中，布尔可满足性问题的求解具有重要的理论和现实意义。此类问题的核心是确定是否存在赋值满足给定的布尔公式。换句话说，对于给定布尔公式的变量，确定是否存在一种赋值方式，使得公式计算结果为True。如果存在，则该公式称为可满足的；如果不存在，也就是公式对于所有可能的赋值的计算结果都是False，则该公式称为不可满足的。这可以看作一个搜索问题，目标是在布尔公式的各种赋值中寻找赋值计算结果为True的方案。本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题1概述Grover算法可用于加速任何NP完全问题的求解，但是如果对应的NP完全问题包含内部结构，则直接利用Grover算法可能无法实现有效加速。虽然在3-SAT问题上直接利用Grover算法穷举没有意义，但相关方法可以应用于更一般的情况（如k-SAT问题），对于某些特定问题，Grover算法可以胜过最优经典算法。此外，理论上Grover算法可以与经典算法进行深度融合，以获得比最优经典算法更好的加速效果。本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题Exactly-13-SATproblem：找到一个真值指派，使得每个Clause中恰好有一个literal赋值为1，且函数值为1。f(x1,x2,x3)=(x1∨x2∨¬x3)∧(¬x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)x1x2x3f0001第二Clause中3个literal为10010函数值为00101第一Clause中2个literal为10111第三Clause中3个literal为11000函数值为01011Y1101第一Clause中3个literal为11110函数值为0本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题先构造子模块：考虑函数f的每个Clause取值为1，且恰好一个literal赋值为1；组合所有Clause。例：(x1∨¬x2∨x3)考虑y=x1

¬x2

x3

(x1

¬x2

x3)本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题(x1∨x2∨¬x3)

(¬x1∨¬x2∨¬x3)

(¬x1∨x2∨x3)y1=

x1

x2

¬x3

(x1

x2

¬x3)y2=

¬x1

¬x2

¬x3

(¬x1

¬x2

¬x3)y3=

¬x1

x2

x3

(¬x1

x2

x3)初始化子句1子句2子句3本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题退计算q4本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题本课件是可编辑的正常PPT课件5.3Grover算法与可满足性问题2SAT问题本课件是可编辑的正常PPT课件5.4Grover算法求解代数方程组1代数方程组问题代数攻击在公钥密码、分组密码和序列密码分析领域，甚至在杂凑函数碰撞攻击领域都有成功应用，已经发展成为一种重要的通用密码分析方法。代数攻击通过分析密码算法的内部结构，构建多变元高次代数方程组，利用求解方程组开展密码分析。代数方程组的求解是一个困难问题，利用Grover算法可以暴力穷举求解代数方程组。当然，这种方法并非最优方法，这里只是以代数方程组为例，探索量子搜索算法如何直接应用于密码分析中的基础数学问题。本课件是可编辑的正常PPT课件5.4Grover算法求解代数方程组1代数方程组问题以二元域上的代数方程组为例，给定如下方程组这是一个四变元的方程组，如果采用穷举搜索算法求解，相当于在0000,…,1111这16个四比特的序列中找到同时满足4个方程的解。利用Grover算法搜索方程组的解，核心是构造一个能够标记方程组正确解的量子Oracle。本课件是可编辑的正常PPT课件5.4Grover算法求解代数方程组1代数方程组问题以第二个方程

为例，可以用量子线路实现，如图所示。本课件是可编辑的正常PPT课件5.4Grover算法求解代数方程组1代数方程组问题类似地，可以给出整个方程组的可逆线路本课件是可编辑的正常PPT课件5.4Grover算法求解代数方程组2搜索方程组解的量子线路本课件是可编辑的正常PPT课件5.4Grover算法求解代数方程组2搜索方程组解的量子线路单次迭代输出结果如图所示，从图中可以看出，对于单次迭代算法，执行1024

次后，得到正确解0110的次数约为480次，也就是说，成功概率约为0.469。本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索1AES算法AES（AdvancedEncryptionStandard，高级加密标准）是一种典型的对称密码算法。AES是一种面向字节的算法，以AES-128为例，其以128位的明文块和128位的密钥块作为输入，并生成相同大小的密文块。AES-128的状态（State）可以用一个4×4的矩阵描述，矩阵每个元素代表1字节（8位）。本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索1AES算法AES的每一轮加密可以分为SubBytes（字节代换）、ShiftRows（行移位）、MixColumns（列混合）及AddRoundKey（轮密钥加）4个步骤，其中，前3个步骤分别以字节、行和列为单位进行数据处理，可并行计算。本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索2Grover算法搜索AES密钥框架密钥搜索的目标是通过给定的明密文对，寻找用于加密的密钥。从Grover算法框架来看，相位翻转等模块是基本固定的。因此，利用Grover算法搜索AES密钥，核心是给出能够标记正确密钥的量子Oracle，本质上需要设计AES加密（解密）算法的量子线路。先考虑简化情况，对于AES-128，其量子Oracle实现框架如图所示。本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索2Grover算法搜索AES密钥框架从量子Oracle的功能结构可以看出，为实现标记正确密钥的功能，关键是要给出AES加密过程的可逆实现，也就是在量子线路模型下，实现AES的加密过程。这样能够对叠加态的密钥进行并行处理，从而加速密钥搜索过程。结合AES算法的流程可以看出，最为关键的是给出SubBytes、ShiftRows、MixColumns及AddRoundKey这4个步骤在量子线路上的可逆实现。本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索3AES算法的可逆实现利用Grover算法搜索AES密钥，核心是AES的可逆实现，主要资源消耗是SubBytes操作，本质问题是有效的求有限域上元素的逆元。

需要构造有限域上元素模平方运算量子线路本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索3AES算法的可逆实现

本课件是可编辑的正常PPT课件5.5Grover算法与密钥搜索3AES算法的可逆实现图中每一个虚线框的编号，恰好对应矩阵分解式中主对角线之外非零元所在的行，含几个非零元就执行几个CNOT门操作。前6个虚线框对应上三角矩阵操作，后2

个虚线框则对应下三角矩阵操作。从图中可以看出，利用12个CNOT门，不需要辅助比特，即可实现有限域上元素的平方运算。本课件是可编辑的正常PPT课件谢谢量子算法与量子密码导论量子密钥分发技术

一量子信息论基础二QKD协议三QKD协议理论安全性四QKD系统组成及实际安全性本章内容

本课件是可编辑的正常PPT课件6.1量子信息论基础1背景量子信息技术除了可用于量子计算进行密码分析之外，还可以用于进行信息加密。有别于传统的加密技术，量子加密技术不在依赖于计算困难的数学问题，其利用量子力学基本原理对信息进行加密，从物理机制上保障信息的安全性。在诸多量子加密技术中，量子密钥分发（quantumkeydistribution，QKD）技术受到关注最多也最为成熟。QKD理论上实现密钥在远距离通信双方之间的安全分配，结合“一次一密”加密方法，理论上可以实现无条件安全的信息传递。因此，自1984年首次提出以来，经过了30多年的发展，QKD理论及实验得到了长足的进步。多种多样的QKD协议层出不穷，相应的安全性分析也不断完善。与此同时，QKD实验发展迅速，通信距离也在不断增大。量子网络及量子卫星相继出现，标志着QKD技术逐渐走出实验室，向着实用化方向迈进。本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础经典香农熵本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础经典香农熵性质本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础经典相对熵本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础经典联合熵本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础经典条件熵本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础互信息本课件是可编辑的正常PPT课件6.1量子信息论基础1经典信息论基础维恩图：互信息和各种熵之间的关系本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础量子冯·诺伊曼熵本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础量子联合熵本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础量子相对熵本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础量子互信息本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础Holevo界本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础信道模型——比特翻转信道本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础信道模型——退极化信道本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础信道模型——幅值阻尼信道本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础信道模型——幅值阻尼信道本课件是可编辑的正常PPT课件6.1量子信息论基础1量子信息论基础信道模型——相位阻尼信道本课件是可编辑的正常PPT课件6.2量子密钥分发协议1协议框架QKD发送设备QKD接收设备经典信道量子信道（a）基于制备测量QKD方案信道示意图AliceBob纠缠源量子信道量子信道经典信道（b）基于纠缠QKD方案信道示意图几乎所有QKD协议框架中，均存在量子信道和经典信道两种信道，其中量子信道用于传输量子信息，经典信道用于传输量子态制备、测量所选择基矢等信息。经典信道中传输的信息完全公开，任何人都可以随意获取。本课件是可编辑的正常PPT课件6.2量子密钥分发协议1协议分类按照使用的物理资源分类，QKD协议可以大致分为纠缠光子QKD协议、单光子QKD协议和连续变量QKD协议三类。1.纠缠光子QKD协议。

该类协议利用量子纠缠和经典通信实现高安全性密钥生成与分发，主要代表为Ekert在1991年提出的E91协议；2.单光子QKD协议。

该类协议利用单光子的偏振或相位传递密钥信息，主要包括1984年Bennett和Brassard共同提出的BB84协议、1992年Bennett提出了B92协议、六态协议及SARG04协议等；3.连续变量QKD协议。

该类协议主要包括基于高斯调制的压缩态协议和基于相干态的平衡零拍