改进量子位初始映射的综合SWAP优化策略

doi:10.3778/j.issn.1002-8331.2310-0211

摘要/Abstract

摘要： 在嘈杂的中尺度量子时代，传统的初始映射策略忽略了后续操作中可能出现的邻接性的问题。针对这一挑战，综合考虑量子比特间的距离、交互时间和门操作的错误率，设计了一个多因素交互成本函数，并提出综合SWAP优化策略（comprehensive SWAP optimization strategy，CSOS）。该策略包括最佳SWAP选择和基于SWAP的批量更新策略，用于优化量子电路的局部量子位映射。最佳SWAP选择通过对比SWAP操作的效益，选择最佳收益的SWAP门；批量更新策略在映射阶段考虑即将执行的量子操作序列，预先执行批量的SWAP操作。二者综合可以减少整个电路执行过程中的SWAP数量，以最大程度减少映射开销。实验结果显示，CSOS优化方式可以平均减少38.1%的插入SWAP门数量，并降低约12%的硬件门计数开销。

关键词: 量子计算, 初始映射, 综合SWAP优化策略, 最佳SWAP选择, 批量更新

Abstract: In the noisy intermediate-scale quantum (NISQ) era, traditional initial mapping strategies overlook potential adjacency issues in subsequent operations. To address this challenge, a multi-factor interaction cost function is devised, considering the distance between qubits, the interaction time, and the gate operations error rate. Additionally, the comprehensive SWAP optimization strategy (CSOS) is proposed to address the adjacency problem in quantum circuits, including the optimal SWAP selection and the SWAP-based batch update strategy (BUS) to optimize the local qubit mapping in quantum circuits. Optimal SWAP selection involves SWAP operations choices with the highest benefit by comparing advantages. The BUS considers upcoming quantum operation sequences during the mapping phase and proactively performs SWAP operations batches. These approaches reduce the SWAP operation numbers during the entire circuit execution process, minimizing mapping overhead to the greatest extent. Experimental results demonstrate that the CSOS reduce the average number of inserted SWAP gates by 38.1% and lower hardware gate count expenses by approximately 12%.

Key words: quantum computing, initial mapping, comprehensive SWAP optimization strategy (CSOS), best SWAP choice, batch updating

李晖, 韩子傲, 卢凯, 刘述娟, 鞠明媚. 改进量子位初始映射的综合SWAP优化策略[J]. 计算机工程与应用, DOI: 10.3778/j.issn.1002-8331.2310-0211.

LI Hui, HAN Zi’ao, LU Kai, LIU Shujuan, JU Mingmei. Comprehensive SWAP Optimization Strategy for Improving Initial Qubit Mapping[J]. Computer Engineering and Applications, DOI: 10.3778/j.issn.1002-8331.2310-0211.

参考文献

[1] 於学松. 量子计算在智能金融发展中的应用前景分析[J]. 国际金融, 2020(2): 35-41.
YU X S. Prospects of quantum computing in the development of intelligent finance[J]. International Finance, 2020(2): 35-41.
[2] 朱钦圣, 杨世璐, 刘恒宇, 等. 量子机器学习简介及其在特定场景中的应用[J]. 大学物理, 2023, 42(8): 27-31.
ZHU Q S, YANG S L, LIU H Y, et al. Introduction of quantummachine learning and its application in a certain scenario[J]. University Physics, 2023, 42(8): 27-31.
[3] HARWOOD S, GAMBELLA C, TRENEV D, et al. Formulating and solving routing problems on quantum computers[J]. IEEE Transactions on Quantum Engineering, 2021, 2: 1-17.
[4] 李震宇, 刘杰, 沈祥建, 等. 量子计算化学的挑战和机遇[J]. 中国科学: 化学, 2023, 53(2): 119-128.
LI Z Y, LIU J, SHEN X J, et al. Challenges and opportunities of quantum-computational chemistry[J]. Science in China: Chemistry, 2023, 53(2): 119-128.
[5] NIU S, SUAU A, STAFFELBACH G, et al. A hardware-aware heuristic for the qubit mapping problem in the NISQ era[J]. IEEE Transactions on Quantum Engineering, 2020, 1: 1-14.
[6] TANNU S S, QURESHI M K. A case for variability-aware policies for NISQ-era quantum computers[J]. arXiv:1805. 10224, 2018.
[7] LI S, NGUYEN K D, CLARE Z, et al. Single-qubit gates matter for optimising quantum circuit depth in qubit mapping[J]. arXiv:2308.00876, 2023.
[8] ZULEHNER A, PALER A, WILLE R. An efficient methodology for mapping quantum circuits to the IBM QX architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38(7): 1226-1236.
[9] LI G, DING Y, XIE Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C]//Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, 2019: 1001-1014.
[10] LI S, ZHOU X, FENG Y. Qubit mapping based on subgraph isomorphism and filtered depth-limited search[J]. IEEE Transactions on Computers, 2020, 70(11): 1777-1788.
[11] ZHOU X, LI S, FENG Y. Quantum circuit transformation based on simulated annealing and heuristic search[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4683-4694.
[12] ZHOU X, FENG Y, LI S. A Monte Carlo tree search framework for quantum circuit transformation[C]//Proceedings of the 39th International Conference on Computer-Aided Design, 2020: 1-7.
[13] DOUSTI M J, SHAFAEI A, PEDRAM M. Squash: a scalable quantum mapper considering ancilla sharing[C]//Proceedings of the 24th Edition of the Great Lakes Symposium on VLSI, 2014: 117-122.
[14] BOOTH K, DO M, BECK J, et al. Comparing and integrating constraint programming and temporal planning for quantum circuit compilation[C]//Proceedings of the International Conference on Automated Planning and Scheduling, 2018, 28: 366-374.
[15] BAHREINI T, MOHAMMADZADEH N. An MINLP model for scheduling and placement of quantum circuits with a heuristic solution approach[J]. ACM Journal on Emerging Technologies in Computing Systems, 2015, 12(3): 1-20.
[16] COTTA C, FERNáNDEZ A J. Memetic algorithms in planning, scheduling, and timetabling[M]//Evolutionary scheduling. Heidelberg: Springer, 2007: 1-30.
[17] GU X, KOCKUM A F, MIRANOWICZ A, et al. Microwave photonics with superconducting quantum circuits[J]. Physics Reports, 2017, 718: 1-102.
[18] RASCONI R, ODDI A. An innovative genetic algorithm for the quantum circuit compilation problem[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 7707-7714.
[19] LAO L, VAN WEE B, ASHRAF I, et al. Mapping of lattice surgery-based quantum circuits on surface code architectures[J]. Quantum Science and Technology, 2018, 4(1): 015005.
[20] LAO L, BROWNE D E. 2QAN: a quantum compiler for 2-local qubit hamiltonian simulation algorithms[C]//Proceedings of the 49th Annual International Symposium on Computer Architecture, 2022: 351-365.