基于动态分区的多量子线路自适应映射

Adaptive multi-programming mapping based on dynamic partitioning

摘要

将逻辑量子线路映射至连通受限且有噪声的量子设备上，是量子计算的关键瓶颈。在量子设备上并行执行多条线路虽提升量子比特利用率，但也加剧了映射的复杂性。为了减少 SWAP 开销并提高保真度，提出基于动态分区的多量子线路自适应映射。通过预处理机制在映射前过滤高错误率的量子比特与物理连接，采用综合质量指标指导的动态分区策略，利用自适应映射策略生成高质量映射。在 IBMQ Toronto 上进行实验，平均保真度可达 52.39%，与现有方法相比提升 2.17%；映射开销上，平均插入 26.25 个额外 CNOT 门，SWAP 开销较其他方法降低 1.5 个 CNOT 门。该方法具有较好的保真度和较低的映射开销，为多量子线路映射提供更优方案。

Abstract

Mapping logical quantum circuits onto quantum devices with constrained connectivity and noise is a critical bottleneck for quantum computing. Executing multiple circuits in parallel on quantum hardware can increase qubit utilization, but it will also exacerbate mapping complexity. To reduce SWAP gate overhead and improve fidelity, an adaptive multi-programming mapping approach based on dynamic partitioning is proposed. A preprocessing mechanism filters out qubits with high error rates from physical connections prior to mapping. A dynamic partitioning strategy guided by a comprehensive quality metric is employed, and adaptive mapping is applied to generate high-quality mappings. Experiments on IBM Quantum Toronto achieved an average fidelity of 52.39%, representing a 2.17% improvement over existing methods. Regarding mapping overhead, an average of 26.25 additional CNOT (controlled NOT) gates were inserted, while SWAP gate overhead was reduced by 1.5 CNOT gates compared to other methods. The proposed method provides an optimized solution for multi-programming mapping, demonstrating the merits of both high fidelity and low mapping overhead.

关键词

量子计算 / 多量子线路映射 / 保真度 / SWAP 开销

Key words

quantum computing / multi-programming mapping / fidelity / SWAP overhead

参考文献

[1] Preskill J. Quantum computing 40 years later[M]//Hey T.Feynman lectures on computation. Boca Raton: CRC Press, 2023: 193-244.

[2] Preskill J. Quantum computing in the NISQ era and beyond[J].Quantum, 2018, 2: 79.

[3] IBM. IBM unveils 400 qubit-plus quantum processor and next-generation IBM quantum system two[EB/OL]. (2022-11-09)[2025-07-03].https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two.

[4] 张辰逸, 尚涛, 刘建伟 . 基于交换门的前瞻启发式量子线路映射算法[J].电子科技大学学报, 2023, 52(4): 489-497.

[5] Zhang Chenyi, Shang Tao, Liu Jianwei . SWAP-based prospective heuristic quantum circuit mapping algorithm[J].Journal of University of Electronic Science and Technology of China, 2023, 52(4): 489-497. (in Chinese)

[6] Tan Bochen, Cong J. Optimal layout synthesis for quantum computing[C]//Proceedings of the 2020 IEEE/ACM International Conference on Computer-Aided Design. San Diego: IEEE, 2020: 1-9.

[7] Das P, Tannu S S, Nair P J, et al. A case for multi-programming quantum computers[C]//Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture. Columbus: IEEE, 2019: 291-303.

[8] Liu Lei, Dou Xinglei. QuCloud: A new qubit mapping mechanism for multi-programming quantum computing in cloud environment[C]//2021 IEEE International Symposium on High-Performance Computer Architecture. Seoul: IEEE, 2021: 167-178.

[9] Liu Lei, Dou Xinglei. QuCloud+: A holistic qubit mapping scheme for single/multi-programming on 2D/3D NISQ quantum computers[J].ACM Transactions on Architecture and Code Optimization, 2024, 21(1): 9.

[10] Ohkura Y, Satoh T, Van Meter R. Simultaneous execution of quantum circuits on current and near-future NISQ systems[J].IEEE Transactions on Quantum Engineering, 2022, 3: 2500210.

[11] Harper B, Tonekaboni B, Goldozian B, et al. Crosstalk attacks and defence in a shared quantum computing environment[J].Advanced Quantum Technologies, 2025, 8(10): e2500009.

[12] Upadhyay S, Ghosh S. SHARE: Secure hardware allocation and resource efficiency in quantum systems[C]//2024 IEEE International Conference on Quantum Computing and Engineering. Montreal: IEEE, 2024: 1109-1119.

[13] Lao Lingling, van Someren H, Ashraf I, et al. Timing and resource-aware mapping of quantum circuits to superconducting processors[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(2): 359-371.

[14] Tan Bochen, Cong J. Optimal qubit mapping with simultaneous gate absorption[C]//2021 IEEE/ACM International Conference on Computer Aided Design. Munich: IEEE, 2021: 1-8.

[15] Nannicini G, Bishop L S, Günlük Ö, et al. Optimal qubit assignment and routing via integer programming[J].ACM Transactions on Quantum Computing, 2023, 4(1): 7.

[16] Molavi A, Xu A, Diges M, et al. Qubit mapping and routing via MaxSAT[C]//2022 55th IEEE/ACM International Symposium on Microarchitecture. Chicago: IEEE, 2022: 1078-1091.

[17] Li Gushu, Ding Yufei, Xie Yuan. 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. Providence: ACM, 2019.

[18] Liu Ji, Li Peiyi, Zhou Huiyang. Not all SWAPs have the same cost: A case for optimization-aware qubit routing[C]//2022 IEEE International Symposium on High-Performance Computer Architecture. Seoul: IEEE, 2022: 709-725.

[19] Gheorghiu V, Huang Jiaxin, Li S M, et al. Reducing the CNOT count for Clifford+T circuits on NISQ architectures[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(6): 1873-1884.

[20] IBM. IBM quantum platform[EB/OL]. [2025-07-03].https://quantum.ibm.com/.

[21] Iverson J K, Preskill J. Coherence in logical quantum channels[J].New Journal of Physics, 2020, 22(7): 073066.

[22] Magesan E, Gambetta J M, Johnson B R, et al. Efficient measurement of quantum gate error by interleaved randomized benchmarking[J].Physical Review Letters, 2012, 109(8): 080505.

[23] Nation P D, Kang H, Sundaresan N, et al. Scalable mitigation of measurement errors on quantum computers[J].PRX Quantum, 2021, 2(4): 040326.

[24] Niu Siyuan, Todri-Sanial A. Analyzing crosstalk error in the NISQ era[C]//2021 IEEE Computer Society Annual Symposium on VLSI. Tampa: IEEE, 2021: 428-430.

[25] Gambetta J M, Córcoles A D, Merkel S T, et al. Characterization of addressability by simultaneous randomized benchmarking[J].Physical Review Letters, 2012, 109(24): 240504.

[26] Kurniawan H, Rodríguez-Soriano L, Cuomo D, et al. On the use of calibration data in error-aware compilation techniques for NISQ devices[C]//2024 IEEE International Conference on Quantum Computing and Engineering. Montreal: IEEE, 2024: 338-348.

[27] Itoko T, Raymond R, Imamichi T, et al. Optimization of quantum circuit mapping using gate transformation and commutation[J].Integration, 2020, 70: 43-50.

[28] Niu Siyuan, Todri-Sanial A. Enabling multi-programming mechanism for quantum computing in the NISQ era[J].Quantum, 2023, 7: 925.

[29] IBM. Qiskit: An open-source framework for quantum computing[EB/OL]. [2025-07-03].https://www.ibm.com/quantum/qiskit.

[30] Ash-Saki A, Alam M, Ghosh S. Experimental characterization, modeling, and analysis of crosstalk in a quantum computer[J].IEEE Transactions on Quantum Engineering, 2020, 1: 3101406.

[31] RevLib. An online resource for reversible benchmarks[EB/OL]. [2025-07-03].https://www.revlib.org/.

[32] QASMBench Benchmark Suite. A low-level OpenQASM benchmark suite for NISQ evaluation and simulation[EB/OL]. [2025-07-03].https://github.com/pnnl/QASMBench/tree/master.

基金资助

国家自然科学基金面上项目(62072259)

江苏省自然科学基金(BK20221411)

南通市自然科学基金(JC2024100)

南通大学博士启动基金(23B03)