多策略量子麻雀搜索算法在NISQ量子比特映射中的应用
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

黑龙江省自然科学基金 (LH2024F042); 黑龙江省普通本科高等学校青年创新人才培养计划 (UNPYSCT-2020212); 哈尔滨商业大学“青年科研创新人才”培育计划 (2023-KYYWF-0983)


Application of Multi-strategy Quantum Sparrow Search Algorithm in NISQ Qubit Mapping
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    在噪声中等规模量子(noisy intermediate-scale quantum, NISQ)时代, 由于硬件耦合约束, CNOT门往往无法直接执行, 需要引入额外的SWAP门将逻辑量子比特映射至合适的物理位置, 以确保电路的可执行性. 为了减少传统量子比特映射过程中由于 SWAP 操作引起的额外开销, 提出多策略量子麻雀搜索算法(multi-strategy quantum sparrow search algorithm, MQSSA), 并应用于量子比特映射中. 基于作用于同一量子比特对的非近邻(non-nearest neighbour, non-NN) CNOT门的个数, 定义量子比特联动次数; 结合CNOT门物理间距, 定义联动量子门集; 根据量子比特联动次数以及SWAP门数量构建适应度函数; 同时将适应度最优的个体定义为发现者, 通过引入量子叠加态机制, 使发现者具备并行搜索能力, 可以同时探索多个位置, 扩大搜索空间. 此外, 为了避免陷入局部最优, MQSSA引入高斯噪声作为跟随者位置更新扰动机制, 增强跳出局部最优能力; 设置警戒者机制维持搜索多样性. 实验结果表明, 在t|ket 和Qiskit编译器中, MQSSA的 SWAP 门数量分别平均减少37.5%和46.6%, 硬件开销分别平均减少13.3%和13.2%. 这表明算法在量子比特映射中的表现更加高效, 提升了优化结果质量.

    Abstract:

    In the noisy intermediate-scale quantum (NISQ) era, due to hardware coupling constraints, CNOT gates often cannot be executed directly. Additional SWAP gates need to be introduced to map logical qubits to suitable physical locations for ensuring circuit executability. To reduce the additional overhead caused by SWAP operations during traditional qubit mapping, this study proposes the multi-strategy quantum sparrow search algorithm (MQSSA) and applies it to qubit mapping. The qubit linkage count is defined based on the number of non-nearest neighbour (non-NN) CNOT gates acting on the same qubit pair. Combined with the physical spacing of CNOT gates, a linked quantum gate set is defined, and a fitness function is constructed based on the qubit linkage count and SWAP gate number. Simultaneously, the individual with the optimal fitness is defined as the discoverer. A quantum superposition state mechanism is introduced to equip the discoverer with parallel search capabilities, enabling the simultaneous exploration of multiple positions to expand the search space. Furthermore, to avoid falling into local optima, MQSSA introduces Gaussian noise as a follower position update perturbation mechanism, enhancing the ability to jump out of local optima. Additionally, the sentinel mechanism is implemented to maintain search diversity. Experimental results demonstrate that within the t|ket and Qiskit compilers, MQSSA achieves average reductions of 37.5% and 46.6% in SWAP gate counts respectively, alongside average hardware overhead reductions of 13.3% and 13.2% respectively. This indicates the proposed algorithm has more efficient performance in qubit mapping, thereby improving the quality of optimization outcomes.

    参考文献
    相似文献
    引证文献
引用本文

刘述娟,韩雪娜,李晖,王杰鹏,姬迎松.多策略量子麻雀搜索算法在NISQ量子比特映射中的应用.计算机系统应用,2026,35(2):237-247

复制
分享
相关视频

文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-07-30
  • 最后修改日期:2025-09-15
  • 录用日期:
  • 在线发布日期: 2025-12-29
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62661041 传真: Email:csa@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号