量子优化算法综述

何键浩; 李绿周

doi:10.7544/issn1000-1239.2021.20210276

量子优化算法综述

(中山大学计算机学院广州 510006) (hejh9@mail2.sysu.edu.cn)

基金项目: 国家自然科学基金项目(61772565);广东省基础与应用基础研究基金项目(2020B1515020050);广东省重点研发项目(2018B030325001)

详细信息

中图分类号: TP3-0; O224
计量
- 文章访问数: 1906
- HTML全文浏览量: 20
- PDF下载量: 1117
出版历程
- 发布日期: 2021-08-31

An Overview of Quantum Optimization

(School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006)

Funds: This work was supported by the National Natural Science Foundation of China (61772565), the Basic and Applied Basic Research Foundation of Guangdong Province (2020B1515020050), and the Key Research and Development Project of Guangdong Province (2018B030325001).

摘要

摘要: 量子优化是量子计算领域近年来颇受关注的一个研究分支，主要研究如何利用量子计算加速优化问题的求解.根据优化问题的变量是否连续分类梳理量子优化算法，侧重介绍连续变量优化算法.通过对现存工作的调研梳理得到一些观察：1)5~20年前的研究主要集中在离散变量的量子优化技术，近5年的研究则更关注连续变量的量子优化技术；2)量子优化使用的主要基础技术都是10~20年前提出的，在基础技术方面需要进一步革新；3)量子优化算法相比于对应的经典算法通常在理论上有加速优势，既有体现在时间复杂度的加速，也有体现在查询复杂度的加速，但仍然有待更为严格的理论分析；4)优化领域依然存在许多值得量子计算研究人员探索的问题，特别是非凸优化领域，亦即经典计算上认为较难的优化问题.
- 量子计算 /
- 量子优化 /
- 数学规划 /
- 离散变量优化 /
- 连续变量优化
Abstract: Quantum optimization has attracted much attention in recent years. It mainly studies how to accelerate the solution of optimization problems with quantum computing. This overview will classify the quantum optimization algorithm according to whether the optimization variable is continuous, and focus on introducing the continuous variable optimization algorithm. Through the investigation of existing work, this article obtains the following observations: 1)The works of discrete variable quantum optimization were distributed five years ago, while the works of continuous variable quantum optimization has attracted more attention in the last five years; 2)The main basic technologies used in quantum optimization were mainly proposed ten to twenty years ago, and basic innovations are needed; 3)In most works of quantum optimization, theoretical acceleration of time complexity or query complexity is achieved, but more rigorous theoretical analysis is still needed; 4)There are still many problems worthy of exploration by quantum computing researchers in the optimization field, especially in the field of non-convex optimization, which is considered to be difficult in classical computing.
- quantum computing /
- quantum optimization /
- mathematical programming /
- discrete variable optimization /
- continuous variable optimization

HTML全文

参考文献(0)

施引文献(13)

期刊类型引用(8)

1.	郭玲玲，李志强，段孟环. 量子近似优化算法在精确覆盖问题中的应用. 计算机应用. 2024(03): 849-854 . 百度学术
2.	章刚，陈庆奎. 基于工业算力网络的算力接入服务器部署算法. 计算机集成制造系统. 2024(12): 4446-4458 . 百度学术
3.	周鑫鑫，袁林旺，吴长彬，韩佩佩，黄敬，俞肇元. 面向设施配置空间优化的量子进化算法. 测绘学报. 2023(01): 142-154 . 百度学术
4.	丁元明，夏清雨，张然，李森. 蝴蝶优化算法研究综述. 科学技术与工程. 2023(07): 2705-2716 . 百度学术
5.	申元霞，汪小燕，张学锋. 求解高维优化问题的新型平衡优化器算法. 小型微型计算机系统. 2023(05): 969-973 . 百度学术
6.	毕忠勤，杨小婷，王宝楠，张丹，鞠琳，刘哲. 基于量子退火算法的配电网故障定位. 科学技术与工程. 2023(31): 13394-13406 . 百度学术
7.	朱伟浩，徐妙语，高毫林. 基于量子优化算法的交通视频结构化分析. 信息技术与信息化. 2022(03): 214-216+220 . 百度学术
8.	王晓晗. 非线性混沌网络系统的分散性能量子优化算法. 吉林大学学报(信息科学版). 2022(03): 424-430 . 百度学术