量子电子学报 ›› 2024, Vol. 41 ›› Issue (2): 367-377.doi: 10.3969/j.issn.1007-5461.2024.02.019

• 量子光学 • 上一篇    下一篇

量子近似优化算法在数字分区问题中的应用

杨辉 , 李志强* , 潘文杰 , 杨冬晗 , 吴希   

  1. ( 扬州大学信息工程学院, 江苏 扬州 225009 )
  • 收稿日期:2022-03-12 修回日期:2022-06-05 出版日期:2024-03-28 发布日期:2024-03-28
  • 通讯作者: E-mail: yzqqLzq@163.com E-mail:E-mail: yzqqLzq@163.com
  • 作者简介:杨 辉 ( 1998 - ), 江苏淮安人, 研究生, 主要从事量子线路综合方面的研究。E-mail: 245839631@qq.com.
  • 基金资助:
    国家自然科学基金 (62071240), 江苏省高校基金 (10KJB520021)

Application of quantum approximate optimization algorithm in number partition problem

YANG Hui , LI Zhiqiang *, PAN Wenjie , YANG Donghan , WU Xi   

  1. ( College of Information Engineering, Yangzhou University, Yangzhou 225009, China )
  • Received:2022-03-12 Revised:2022-06-05 Published:2024-03-28 Online:2024-03-28

摘要: 量子近似优化算法( QAOA) 是一种近似求解组合优化问题的方法, 它通过反复调整电路参数, 以获取问题 哈密顿量的最大期望值为目的来解决问题, 在组合优化问题领域具有广阔的应用前景。将QAOA 应用于数字分区 问题( 二分区问题), 通过将问题函数转换成对应的哈密顿量, 构造了量子线路, 采用线性近似约束优化 (COBYLA) 方法对电路参数进行了优化, 并使用IBMQ 模拟平台进行了模拟实验。研究发现量子近似优化算法在 数字分区问题中有着良好的性能表现, 可在多项式时间内给出问题的解, 并且降低了问题的时间复杂度。

关键词: 量子计算, 量子线路, 数字分区, 量子近似优化算法

Abstract: Quantum approximate optimization algorithm (QAOA) is a method for approximately solving combinatorial optimization problems, and has broad application prospects in related fields. It solves problems by repeatedly adjusting circuit parameters in order to maximize the expected value of Hamiltonian. In the research, QAOA is applied to the number partition problem (two partition problem). By converting the problem function into the corresponding Hamiltonian, a quantum circuit is constructed. The circuit parameters are optimized using constrained optimization by linear approximation (COBYLA) method, and the simulation experiment is carried out on IBMQ simulation platform. It is found that QAOA has good performance in number partition problems, which can obtain the solutions of the problems in polynomial time and reduce the time complexity of the problems.

Key words: quantum computing, quantum circuit, number partition, quantum approximate optimization algorithm

中图分类号: