| 失效链接处理 |
|
量子优化算法综述 PDF 下载
本站整理下载：
相关截图：
主要内容：
１． １ Grover 算法与量子随机游走( Groveralgorithm
&quantumrandomwalk )
Grover 算法与量子随机游走已经被应用在许
多领 域,其 中 就 有 离 散 优 化 领 域 ．Grover 算 法 于
１９９６ 年被提出
[ １０ ] ,用于无序数据库搜索,其方法是
通过迭代利用一个可识别搜索目标的黑盒来提高搜
索目标在量子叠加态中的振幅,从而提高测量获得
搜索目标的概率 ． 后续有多个相关的改进结果,如由
清华大学的 Long 提出的 Grover 算法的精确版本 [
１７ ] ．
原始的 Grover 算法需要确切知道搜索空间中目标
的数量才能确定最优的迭代次数,过少的迭代次数
达不到效果,过多的迭代也会降低搜索的成功率,迭
代次数增多并不能保证一直趋向搜索目标 ． 该问题
在文献[
１８ ]中被称为“ souffléproblem ” ． 因此,对于
搜索空间中目标数量未知的情形,算法需要改进,
Grover 和 Mizel 先后对此作过讨论,并给出了随着
迭代次数增加 能一直增 加搜索 成 功 率 的 改 进 版
本 [
１９Ｇ２１ ] ,但这几项工作都一定程度上牺牲了算法效
率 ． 最终 Yoder 等人给出了进一步改进 [
２２ ] ,既保留
了平方加速,也保证了迭代最终会一直趋向搜索目
标 ． 此系列改进工作被称为固定点量子搜索(
fixedＧ
pointquantumsearch ) ． 若搜索前对答案有一定的
先验知识, He 等人给出了相应最优算法 [
２３ ] ．
量子随机游走于 １９９３ 年由新墨西哥大学的
Aharonov 等 ３ 名学者提出
[ ２４ ] ．
不同时期量子随机游
走的工作梳理可参见文献[
２５Ｇ２８ ] ．Grover 算法可以
看作是在一种特殊图上的量子随机游走,因此量子
随机游走是一种更一般化的量子搜索技术,已经成
为一类重要的量子算法设计模型 ．
１． ２ 量子傅里叶变换与量子相位估计算法( quantum
Fouriertransform & quantumphaseestimation
algorithm )
作为量子算法里提供加速的最为核心的 ２ 个基
本工具,量子傅里叶变换最早可追溯到 １９９４ 年 [
２９ ] ,
而量子相位估计算法最早可追溯到 １９９５ 年 [
３０ ] ．
利
用量子解线性方程思想以及量子梯度估计法的量子
优化算法都直接或间接地使用了量子傅里叶变换或
量子相位估计算法 ． 读者可以在任一量子计算教材
中找到这 ２ 个基本工具的详细介绍 [
１４Ｇ１６ ] ．
１． ３ 量子幅值放大 ∕ 幅值估计( quantumamplitude
ampＧlificationandamplitudeestimation )
２００２ 年, Brassard 等 ４ 名学者提出了量子振幅
放大以及量子振幅估计算法 [
３１ ] ．
前者通过一系列的
反射操作,达到放大所需结果概率的目的;而后者则
是在前者的基础上结合量子相位估计算法,从而估
计所需结果的概率 ． 在量子优化算法中,不完美的演
化产生的垃圾信息,以及算法本身产生的无用信息
一般都通过振幅放大过滤掉 ． 该工作与 Grover 算
法 [
１０ ] 以 及 量 子 计 数 [ ３２ ] 有 密 切 联 系 ．Ambainis 于
２０１２ 年提出了量子振幅放大算法的时变版本
[ ３３ ] ,并
用于求解线性代数问题 ． 量子振幅估计算法近期还
有针对非布尔函数的推广 [
３４ ] 以及无需使用量子相
位估计算法的变种 [
３５ ] ．
１． ４ 解线性方程量子算法( quantumlinearsystem
algorithm )
解线性方程量子算法最早在 ２００９ 年由 Harrow ,
Hassidim , Lloyd 三名学者提出
[ １１ ] ,所以也被称为
HHL 算法 ． 解线性方程即给定矩阵 A 与向量 b ,求
满足 Ax ＝ b 的 x ． 此类算法也可以用来处理矩阵与
向量乘积、矩阵求逆等操作,因此也常见于量子优化
技术的迭代算法中 ． 需要注意的是,解线性方程量子
算法求解的是量子版本的问题,即输入输出均为量
子态,无法直接得到解的每一个分量,因此在进一步
应用时需要经过巧妙设计,一般在利用方程解的全
局信息时才能体现量子算法的加速效果 ．Ambainis
于次年提出了改进版本,减少了算法复杂度对矩阵
条件数的依赖 [
３６ ] ．
２０１７ 年, Childs 等 ３ 名学者用其
他思路给出了解线性方程量子算法 [
３７ ] ,减少了计算
复杂度中对精度的依赖 ．
２０１８ 年, Wossnig 等 ３ 名学
者利用量子奇异值估计算法,去除了计算复杂度中
对矩阵稀疏度的依赖 [
３８ ] ．
关于此系列工作的梳理可
以参见文献[
３９ ] ．
１． ５ 量子随机存取存储( quantumrandomaccess
memory )
要在经典问题上使用量子算法,经典数据编码
成量子态是必不可少的重要步骤,量子随机存取存
储(简称 QRAM )则是这一过程的主要辅助技术 ． 同
为实现数据的存储和提取, QRAM 与经典的随机存
储器最大的区别是: QRAM 可以被量子叠加态地址
访问,返回与地址相纠缠的叠加态数据,这为量子优
化算法以及量子机器学习的初态制备提供了有力工
具 ． 在量子优化中使用得较多的为 ２００８ 年 Lloyd 等
３ 名学者提出的 BucketＧBrigade 结构的 QRAM
[ ４０Ｇ４１ ] ,
利用此结构在对数时间复杂度内可实现初态制备 ．
值得注意的是搭建 QRAM 的时间复杂性仍然较高,
整体上会抵消掉量子算法带来的加速, QRAM 搭建
技术仍然需要进一步优化 ．
２０１８ 年, Chakraborty 等
３ 名学者提出了块编码技术,并证明与 BucketＧBrigade
结构在矩阵编码上等价
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
