遗传启发映射策略在量子电路优化中的应用

doi:10.3778/j.issn.1002-8331.2408-0285

摘要/Abstract

摘要： 现行的量子位映射策略大多是确定性的，导致生成的量子电路映射缺乏多样性，难以在质量和多样性之间取得平衡，且无法灵活适应不同的量子计算任务。基于此，设计了一种基于遗传启发的量子电路映射策略（genetic-inspired quantum circuit mapping strategy，GQCMS）。该策略引入了多样化的交叉和突变操作，通过在更广阔的解空间中进行搜索，使得算法执行过程中不断生成多样化的候选解，避免陷入局部最优解，从而增加找到全局最优解的机会，提高了电路映射的整体质量。此外，为了克服传统映射策略中常见的量子比特距离较远导致的SWAP操作频繁问题，提出了一种基于邻近门的初始化方法，通过优先考虑最近邻量子位，减少需要进行SWAP操作的次数，降低电路的复杂性，缩短映射过程中的计算时间。实验结果表明，GQCMS在t|ket>和Qiskit编译器中的表现显著优于2QAN，分别平均减少了44.8%和62.5%的SWAP门数量，并在t|ket>中平均减少了42.9%的映射运行时间。

关键词: 量子电路, 量子位映射, 遗传算法, 遗传启发量子电路映射策略, 适应度函数

Abstract: The current qubit mapping strategies are predominantly deterministic, leading to quantum circuit mappings that lack diversity, making it challenging to balance quality and diversity while being inflexible to various quantum computing tasks. To address this issue, a genetic-inspired quantum circuit mapping strategy (GQCMS) has been developed. This strategy introduces diversified crossover and mutation operations, enabling the algorithm to continually generate diverse candidate solutions through broader search spaces, thereby avoiding local optima and increasing the likelihood of identifying global optima, which ultimately enhances the overall quality of circuit mapping. Additionally, to overcome the frequent SWAP operations caused by distant qubit placements in traditional mapping strategies, a proximity-gate-based initialization method is proposed. By prioritizing nearest-neighbor qubits, this method reduces the need for SWAP operations, decreases circuit complexity, and shortens computation time during the mapping process. Experimental results indicate that GQCMS significantly outperforms 2QAN in the t|ket> and Qiskit compilers, with an average reduction of 44.8% and 62.5% in SWAP gate count, respectively, and a 42.9% average reduction in mapping runtime in t|ket>.

Key words: quantum circuit, qubit mapping, genetic algorithm, genetic-inspired quantum circuit mapping strategy (GQCMS), fitness function

韩子傲, 李晖, 卢凯, 刘述娟, 鞠明媚. 遗传启发映射策略在量子电路优化中的应用[J]. 计算机工程与应用, 2025, 61(5): 94-103.

HAN Zi’ao , LI Hui, LU Kai, LIU Shujuan, JU Mingmei. Application of Genetic-Inspired Mapping Strategy in Quantum Circuit Optimization[J]. Computer Engineering and Applications, 2025, 61(5): 94-103.

参考文献

[1] PIRANDOLA S, ANDERSEN U L, BANCHI L, et al. Advances in quantum cryptography[J]. Advances in Optics and Photonics, 2020, 12(4): 1012-1236.
[2] KHUMALO M T, CHIEZA H A, PRAG K, et al. An investigation of IBM quantum computing device performance on combinatorial optimisation problems[J]. arXiv:2107.03638, 2021.
[3] CAVA R, LEON D N, XIE W. Introduction: quantum materials[J]. Chemical Reviews, 2021, 121(5): 2777-2779.
[4] WILLE R, VAN METER R, NAVEH Y. IBM’s Qiskit tool chain: working with and developing for real quantum computers[C]//Proceedings of the 2019 Design, Automation & Test in Europe Conference & Exhibition, 2019: 1234-1240.
[5] Google. Shor’s algorithm: Cirq. Google quantum AI[EB/OL]. [2024-02-18]. https://quantumai.google/cirq/experiments/shor.
[6] ItOKO T, RAYMOND R, IMAMICHI T, et al. Optimization of quantum circuit mapping using gate transformation and commutation[J]. Integration, 2020, 70: 43-50.
[7] LAO L, ALMUDEVER C G. Fault-tolerant quantum error correction on near-term quantum processors using flag and bridge qubits[J]. Physical Review A, 2020, 101(3): 32333.
[8] STEINBERG M A, FELD S, ALMUDEVER C G, et al. Topological-graph dependencies and scaling properties of a heuristic qubit-assignment algorithm[J]. IEEE Transactions on Quantum Engineering, 2022, 3: 1-14.
[9] PALER A, SASU L, FLOREA A C, et al. Machine learning optimization of quantum circuit layouts[J]. ACM Transactions on Quantum Computing, 2023, 4(2): 1-25.
[10] DAI S. On the quantum circuit implementation of modus ponens[J]. Scientific Reports, 2024, 14(1): 14245.
[11] SüNKEL L, MARTYNIUK D, MATTERN D, et al. GA4QCO: genetic algorithm for quantum circuit optimization[J]. arXiv:2302.01303, 2023.
[12] HE J, XU H, FENG S, et al. [Retracted] heuristic reordering strategy for quantum circuit mapping on LNN architectures[J]. Computational Intelligence and Neuroscience, 2022, 2022(1): 1765955.
[13] BAE J H, ALSING P M, AHN D, et al. Quantum circuit optimization using quantum Karnaugh map[J]. Scientific Reports, 2020, 10(1): 15651.
[14] AROCHE R R, GARCíA O Y M, MARTíNEZ A M A, et al. DNA as a perfect quantum computer based on the quantum physics principles[J]. Scientific Reports, 2024, 14(1): 11636.
[15] 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.
[16] ZHU P, GUAN Z, CHENG X. A dynamic look-ahead heuristic for the qubit mapping problem of NISQ computers[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4721-4735.
[17] 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.
[18] 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.
[19] 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.
[20] SIVARAJAH S, DILKES S, COWTAN A, et al. t|ket＞: a retargetable compiler for NISQ devices[J]. Quantum Science and Technology, 2020, 6(1): 14003.
[21] JAVADI-ABHARI A, TREINISH M, KRSULICH K, et al. Quantum computing with Qiskit[J]. arXiv:2405.08810, 2024.