量子算法与量子密码导论 课件 第5、6章 量子搜索算法及其应用；量子密钥分发技术.pptx
量子算法与量子密码导论
量子搜索算法及其应用
●搜索算法原理及框架
●搜索算法分析及示例
·Grover算法与可满足性问题
·Grover算法求解代数方程组
·Grover算法与密钥搜索
口本章内容
三二
而
搜索问题是一个基础性问题，在计算机科学、密码学等许多领域中，很多问题的求解均可规约为搜索问题，如路径搜索、密钥搜索、碰撞搜索等。
理论上来说，一般的NP问题均可用搜索的思路进行求解。
对于特定问题来说，搜索不一定是最有效的方法。很多问题自身存在特殊结构，如果能够充分利用问题特征，则可能得到更高效的求解方法。对于无结构的搜索问题，如无序数据库搜索，暴力穷举可能是最优的方法。
5.1搜索算法原理及框架
背景
5.1搜索算法原理及框架
量子Oracle与搜索问题
给定一个输出为0或1的函数f(x)
可以将函数值存入一个辅助寄存器，构造一个量子Oracle,即
0:|x)|y)→x)|y田f(x)
5.1搜索算法原理及框架
量子Oracle与搜索问题
根据量子Oracle,可以给出搜索问题的形式化描述。
搜索问题：给定计算未知函数f:{0,1}→{0,1}的量子Oracle,找到满足条件f(x)=1的输入。
5.1搜索算法原理及框架
Grover搜索算法框架
如果满足要求的目标文件地址为z,则可以定义函数
f:S→{0,1}
其中
可以给出量子Oracle为
0:|x,y)→|x,y田f(x)〉
5.1搜索算法原理及框架
Grover搜索算法框架
只考虑地址寄存器，量子Oracle的作用可视为
0f|x)→(-1)f)|x)
将量子Oracle作用于量子态
则
5.1搜索算法原理及框架
Grover搜索算法框架
与一般的量子算法类似，制备初始等概率叠加态
对应Grover算法框架如图
比特|0输入
H×n
G
5.1搜索算法原理及框架
Grover搜索算法框架
在Grover算法中，核心的部分是Grover迭代过程，其线路实现如图
5.2所示。
n量子比特输入
量子Oracle辅助比特
条件相移|0→|0〉|x→-|x〉
H×n
量子Oracle的作用是在目标文件地址上翻转相位，实现标记目标文件地址的功能。
搜索算法的图形描述
5.1搜索算法原理及框架
5.2搜索算法分析及示例
搜索算法的复杂度
算法初始态为
第一次迭代后，逆时针旋转角，对应量子态变为
进行k次迭代后，量子态变为
5.2搜索算法分析及示例
搜索算法的复杂度
这是迭代的终极目标
以k=3时的量子Oracle为例，目标数据编码为11,则量子Oracle可以直接用一个Toffoli门实现。
5.2搜索算法分析及示例
根据Grover算法流程，可以给出针对4个数据的Grover算法线路图
搜索算法示例
X
XH
10
10)
10-
量子Oracle
H
H
H
H
H
H
H
H
H
X
H
H
H
H
H
10
10
X
+
+
在计算机科学、密码学等许多领域中，布尔可满足性问题的求解具
有重要的理论和现实意义。此类问题的核心是确定是否存在赋值满足给定的布尔公式。换句话说，对于给定布尔公式的变量，确定是否存在一种赋值方式，使得公式计算结果为True。如果存在，则该公式称为可满足的；如果不存在，也就是公式对于所有可能的赋值的计算结果都是False,则该公式称为不可满足的。这可以看作一个搜索问题，目标是在布尔公式的各种赋值中寻找赋值计算结果为
True的方案。
5.3Grover算法与可满足性问题
概述
Grover算法可用于加速任何NP完全问题的求解，但是如果对应的
NP完全问题包含内部结构，则直接利用Grover算法可能无法实现有
效加速。
虽然在3-SAT问题上直接利用Grover算法穷举没有意义，但相关方法可以应用于更一般的情况(如k-SAT问题),对于某些特定问题，Grover算法可以胜过最优经典算法。此外，理论上Grover算法可以与经典算法进行深度融合，以获得比最优经典算法更好的加速效果
o
5.3Grover算法与可满足性问题
概述
x1
x₂
x₃
f
0
0
0
1
第二Clause中3个literal为1
0
0
1
0
函数值为0
0
1
0
1
第一Clause中2个literal为1
0
1
1
1
第三Clause中3个literal为1
1
0
0
0
函数值为0
1
0
1
1
Y
1
1
0
1
第一Clause中3个literal为1
1
1
1
0
函数值为0
Exac