含噪中型量子计算机的量子比特映射算法

doi:10.3778/j.issn.1002-8331.2404-0196

摘要/Abstract

摘要： 由于量子硬件约束，能够实现双量子比特门的物理量子比特对是有限的。大多数量子程序需要插入额外量子门，通过改变逻辑量子比特到物理量子比特的映射关系实现在含噪中型量子计算机上执行。为了提高量子线路初始映射质量，降低算法复杂度及运行时间，提出一种基于交换门的优化双向启发式搜索算法。利用最近邻策略筛选出交换门候选队列，通过改进启发式成本函数评估候选交换门，减少交换门搜索空间和附加门数。结合量子线路结构特性，使用反向遍历方法更新初始映射策略，提高映射质量。该算法还适用于量子比特任意耦合的硬件设备。实验结果表明，与主流的IBM_QX算法、SPBHA算法和SAHA算法相比，该算法分别减少约73%、28%和20%的附加门数，执行时间减少约300%、80%和19%，提高了量子线路映射效率。

关键词: 量子线路, 初始映射, 启发式搜索, 反向遍历

Abstract: Due to constrains of quantum hardware, the physical qubit pairs capable of implementing two-qubit gates are limited. Most quantum algorithms require to insert additional quantum gates to be executed on NISQ (noisy intermediate-scale quantum) computers by altering the mapping relationship between logical qubits and physical qubits. To improve the quality of initial mapping of quantum circuits, and reduce algorithm complexity and execution time, a SWAP-based optimization bidirectional heuristic search algorithm is proposed. The algorithm utilizes a nearest neighbor strategy to filter out a candidate queue of SWAP gates. To reduce the search space and the number of additional gates, the algorithm evaluates candidates of SWAP gates by enhancing the heuristic cost function. Considering the characteristics of the quantum circuit structure, this algorithm uses a reverse traversal method to enhance mapping quality with updating initial mapping strategy. Moreover, this algorithm is applicable to hardware devices with arbitrary coupling of qubits. Experimental results demonstrate that compared to mainstream IBM_QX, SPBHA and SAHA algorithms, this algorithm reduces the number of additional gates by approximately 73%, 28% and 20%, respectively, and decreases execution time by around 300%, 80% and 19%, improving the efficiency of quantum circuit mapping.

Key words: quantum circuit, initial mapping, heuristic search, reverse traversal

黄泓凯, 张雪松. 含噪中型量子计算机的量子比特映射算法[J]. 计算机工程与应用, 2024, 60(24): 110-118.

HUANG Hongkai, ZHANG Xuesong. Qubit Mapping Algorithm for Noisy Intermediate-Scale Quantum Computers[J]. Computer Engineering and Applications, 2024, 60(24): 110-118.

参考文献

[1] CHAITIN G J. Register allocation & spilling via graph coloring[J]. ACM Sigplan Notices, 1982, 17(6): 98-101.
[2] POLETTO M, SARKAR V. Linear scan register allocation[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1999, 21(5): 895-913.
[3] TOMASULO R M. An efficient algorithm for exploiting multiple arithmetic units[J]. IBM Journal of Research and Development, 1967, 11(1): 25-33.
[4] HENNESSY J L, GROSS T. Postpass code optimization of pipeline constraints[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1983, 5(3): 422-448.
[5] CODINA J M, SáNCHEZ J, GONZáLEZ A. A unified modulo scheduling and register allocation technique for clustered processors[C]//Proceedings 2001 International Conference on Parallel Architectures and Compilation Techniques, 2001: 175-184.
[6] MASLOV D, FALCONER S M, MOSCA M. Quantum circuit placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(4): 752-763.
[7] CHAKRABARTI A, SUR-KOLAY S, CHAUDHURY A. Linear nearest neighbor synthesis of reversible circuits by graph partitioning[J]. arXiv:1112.0564, 2011.
[8] SHAFAEI A, SAEEDI M, PEDRAM M. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures[C]//Proceedings of the 50th Annual Design Automation Conference, 2013: 1-6.
[9] SHAFAEI A, SAEEDI M, PEDRAM M. Qubit placement to minimize communication overhead in 2D quantum architectures[C]//Proceedings of the 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC), 2014: 495-500.
[10] WILLE R, LYE A, DRECHSLER R. Optimal SWAP gate insertion for nearest neighbor quantum circuits[C]//Proceedings of the 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC), 2014: 489-494.
[11] ALFAILAKAWI M, AHMAD I, HAMDAN S. LNN reversible circuit realization using fast harmony search based heuristic[C]//Proceedings of the Asia-Pacific Conference on Computer Science and Electrical Engineering, 2014.
[12] SAEEDI M, WILLE R, DRECHSLER R. Synthesis of quantum circuits for linear nearest neighbor architectures[J]. Quantum Information Processing, 2011, 10: 355-377.
[13] LIN C C, SUR-KOLAY S, JHA N K. PAQCS: physical design-aware fault-tolerant quantum circuit synthesis[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014, 23(7): 1221-1234.
[14] HECKEY J, PATIL S, JAVADIABHARI A, et al. Compiler management of communication and parallelism for quantum computation[C]//Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, 2015: 445-456.
[15] JAVADI-ABHARI A, GOKHALE P, HOLMES A, et al. Optimized surface code communication in superconducting quantum computers[C]//Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, 2017: 692-705.
[16] PALER A, POLIAN I, NEMOTO K, et al. Fault-tolerant, high-level quantum circuits: form, compilation and description[J]. Quantum Science and Technology, 2017, 2(2): 025003.
[17] SIRAICHI M Y, SANTOS V F, COLLANGE C, et al. Qubit allocation[C]//Proceedings of the 2018 International Symposium on Code Generation and Optimization, 2018: 113-125.
[18] 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.
[19] WILLE R, KESZOCZE O, WALTER M, et al. Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits[C]//Proceedings of the 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC), 2016: 292-297.
[20] SHRIVASTWA R R, DATTA K, SENGUPTA I. Fast qubit placement in 2D architecture using nearest neighbor realization[C]//Proceedings of the 2015 IEEE International Symposium on Nanoelectronic and Information Systems, 2015: 95-100.
[21] KOLE A, DATTA K, SENGUPTA I. A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using N-gate lookahead[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2016, 6(1): 62-72.
[22] KOLE A, DATTA K, SENGUPTA I. A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(1): 182-192.
[23] BHATTACHARJEE A, BANDYOPADHYAY C, WILLE R, et al. A novel approach for nearest neighbor realization of 2D quantum circuits[C]//Proceedings of the 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2018: 305-310.
[24] CHEN Y, NEILL C, ROUSHAN P, et al. Qubit architecture with high coherence and fast tunable coupling[J]. Physical Review Letters, 2014, 113(22): 220502.
[25] 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.
[26] 张辰逸, 尚涛, 刘建伟. 基于交换门的前瞻启发式量子线路映射算法[J]. 电子科技大学学报, 2023, 52(4): 489-497.
ZHANG C Y, SHANG T, LIU J W. SWAP-based prospective heuristic quantum circuit mapping algorithm[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(4): 489-497.
[27] 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.
[28] FLOYD R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345-345.
[29] WILLE R, GRO?E D, TEUBER L, et al. RevLib: an online resource for reversible functions and reversible circuits[C]//Proceedings of the 38th International Symposium on Multiple Valued Logic (ISMVL 2008), 2008: 220-225.
[30] GREEN A S, LUMSDAINE P L F, ROSS N J, et al. Quipper: a scalable quantum programming language[C]//Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2013: 333-342.
[31] JAVADIABHARI A, PATIL S, KUDROW D, et al. ScaffCC: a framework for compilation and analysis of quantum computing programs[C]//Proceedings of the 11th ACM Conference on Computing Frontiers, 2014: 1-10.