摘要
量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)是求解组合优化问题的算法框架,是近期最有可能展示量子计算优势的算法之一.在QAOA框架内,表征解的量子态采取的二进制编码方案导致的对称性限制了QAOA的性能.为了克服这一局限性,本文受Dicke态制备算法的启发,给出了一种新的解编码方案,消除了现有编码方案中的对称性.本文还设计了新的演化算子——星图(Star Graph,SG)算子,及其对应的SG算法,给出了算法求解图分割问题时的量子电路.在IBM Q上的实验结果显示,星图算法比标准QAO算法平均约有25.3%的性能提升.
Quantum approximate optimization algorithm(QAOA)is an algorithm framework for solving combinatorial optimization problems.It is regarded as one of the promising candidates to demonstrate the advantages of quantum computing in the near future.Within the QAOA framework,the symmetries of quantum states induced by the binary encoding scheme restrain the performance of QAOA.Inspired by the Dicke state preparation algorithm,we proposed a new encoding scheme that eliminated the symmetry of quantum states representing solutions.Beyond that,we also proposed a novel evolution operator,star graph(SG)mixer,and its corresponding SG algorithm.The quantum circuit implementation of the SG algorithm on IBM Q showed the SG algorithm has an average performance improvement of about 25.3%over the standard QAOA algorithm in solving the graph partitioning problem.
作者
袁志强
杨思春
阮越
薛希玲
陶陶
YUAN Zhi-qiang;YANG Si-chun;RUAN Yue;XUE Xi-ling;TAO Tao(School of Computer Science and Technology,Anhui University of Technology,Ma’anshan,Anhui 243032,China)
出处
《电子学报》
EI
CAS
CSCD
北大核心
2024年第6期2025-2036,共12页
Acta Electronica Sinica
基金
国家自然科学基金(No.61802002)
安徽省自然科学基金(No.1708085MF162,No.1908085MF212)
安徽省高校自然科学重点项目(No.KJ2020A0233,No.2022AH050319)
安徽省重点研究与开发计划项目(No.201904d07020020)。
关键词
量子近似优化算法
组合优化问题
星图算子
星图算法
图分割
quantum approximate optimization algorithm
combinatorial optimization
star graph mixer
star graph algorithm
graph partitioning
