A computer⁃aided⁃design methodology for quantum circuit 
mapping based on stochastic optimization model

doi:10.3969/j.issn.1007-5461.2023.06.015

Abstract

Abstract: The limited connectivity between physical qubits is one of the most important constraints for noisy intermediate-scale quantum (NISQ) computing devices. Quantum circuit mapping makes all qubits in quantum circuits exchange mutually by inserting SWAP gates to satisfy the restricted connectivity constraints of physical devices. In a noisy computing environment, reducing the number of inserted SWAP gates is of great significance to improve the success rate of quantum computing. In order to minimize the number of SWAP gates, a heuristic quantum circuit mapping algorithm is proposed, and then based on the heuristic algorithm and the random search technology, a multi-iterative stochastic optimization model for quantum circuit mapping is proposed. The experimental results show that the method can greatly reduce the number of quantum gates inserted during the quantum circuit mapping process, and effectively reduce the dependence of the resulting physical circuit on the initial mapping.

Key words: quantum computing, quantum circuit mapping, noisy intermediate-scale quantum computing, limited connectivity, stochastic optimization

CLC Number:

TP302.2

WEI Lihua , ZHU Pengcheng, GUAN Zhijin. A computer⁃aided⁃design methodology for quantum circuit mapping based on stochastic optimization model[J]. Chinese Journal of Quantum Electronics, 2023, 40(6): 952-962.

References

[1] IBM Quantum. IBM Quantum computer systems define the future of computing, [OL]. [2021-03-08]. https://www.ibm.com/quantum-computing/.
[2] Arute F, Arya K, Babbush R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, 2019, 574(7779): 505-510.
[3] Zhong H S, Wang H, Deng Y H, et al. Quantum computational advantage using photons[J]. Science, 2020, 370(6523): 1460-1463.
[4] Wu Y, Bao W S, Cao S, et al. Strong quantum computational advantage using a superconducting quantum processor[J]. Physical review letters, 2021, 127(18): 180501.
[5] Preskill J. Quantum Computing in the NISQ era and beyond[J]. Quantum, 2018, 2: 79-98.
[6] Wille R, Fowler A, Naveh Y. Computer-aided design for quantum computation[C]//Proceedings of IEEE/ACM International Conf. on Computer-Aided Design (ICCAD). San Diego, CA :IEEE, 2018: 1-6.
[7] Amy M, Maslov D, Mosca M, et al. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(6): 818-830.
[8] Miller D M, Wille R, Sasanian Z. Elementary quantum gate realizations for multiple-control Toffoli gates[C]//Proceedings of of 41st IEEE International Symposium on Multiple-Valued Logic. Tuusula, Finland: IEEE, 2011: 288-293.
[9] H?ner T, Steiger D S, Svore K, et al. A software methodology for compiling quantum programs[J]. Quantum Science and Technology, 2018, 3(2): 020501.
[10] Cheng XY, Guan ZJ, Xu H, et al. The Nearest Neighbor Arrangement of Quantum Circuits Based on MCT Reversible Circuits[J]. Acta Electronica Sinica, 2018,46(08):1891-1897(in Chinese) .
程学云, 管致锦, 徐海, 等. 基于MCT可逆线路的量子线路近邻化排布[J]. 电子学报, 2018, 46(08): 1891-1897.
[11] Lu Y, Guan ZJ, Cheng XY, et al. Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix[J]. Acta Electronica Sinica, 2018, 46(03): 688-694(in Chinese) .
鹿玉, 管致锦, 程学云, 等. 基于矩阵变换的线性最近邻量子线路综合与优化[J]. 电子学报, 2018, 46(03): 688-694.
[12] Wille R, Lye A, Drechsler R. Exact Reordering of Circuit Lines for Nearest Neighbor Quantum Architectures [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(12): 1818-1831.
[13] Siraichi M Y, Santos V F, Collange S, et al. Qubit allocation[C]//Proceedings of International Symposium on Code Generation and Optimization. New York, NY: ACM, 2018: 113-125.
[14] Botea A, Kishimoto A, Marinescu R. On the complexity of quantum circuit compilation[C]//Proceedings of 11th Annual Symposium on Combinatorial Search. Palo Alto, CA :AAAI, 2018: 138–142.
[15] Ding J, Yamashita S. Exact Synthesis of Nearest Neighbor Compliant Quantum Circuits in 2-D Architecture and Its Application to Large-Scale Circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(5): 1045-1058.
[16] Booth K, Do M, Beck J, et al. Comparing and integrating constraint programming and temporal planning for quantum circuit compilation[C]//Proceedings of International Conference on Automated Planning and Scheduling. Delft, Netherlands: TUDelft, 2018, 28(1):366-374.
[17] Venturelli D, Do M, Rieffel E G, et al. Temporal Planning for Compilation of Quantum Approximate Optimization Circuits[C]//Proceedings of 26th International Joint Conference on Artificial Intelligence IJCAI. Melbourne, Australia: IJCAI, 2017: 4440-4446.
[18] De Almeida A A A, Dueck G W, Da Silva A C R. Finding optimal qubit permutations for IBM's quantum computer architectures[C]//Proceedings of of 32nd Symposium on Integrated Circuits and Systems Design. S?o Paulo, Brazil: IEEE, 2019: 1-6.
[19] Wille R, Burgholzer L, Zulehner A. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations[C]//Proceedings of 56th ACM/IEEE Design Automation Conference. New York, NY: IEEE, 2019: 1-6.
[20] Wu B, He X, Yang S, et al. Optimization of CNOT circuits on topological superconducting processors[J]. arXiv:1910.14478, 2019, https://arxiv.org/abs/1910.14478.
[21] Nash B, Gheorghiu V, Mosca M. Quantum circuit optimizations for NISQ architectures[J]. Quantum Science and Technology, 2020, 5(2): 025010.
[22] Kissinger A, de Griend A M. CNOT circuit extraction for topologically-constrained quantum memories[J]. arXiv:1904.00633, 2019, https://arxiv.org/abs/1904.00633.
[23] 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.
[24] Li S, Zhou X, Feng Y. Qubit mapping based on subgraph isomorphism and filtered depth-limited search[J]. IEEE Transactions on Computers, 2020, Early Access, https://ieeexplore.ieee.org/abstract/document/9194320.
[25] 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.
[26] Kole A, Hillmich S, Datta K, et al. Improved mapping of quantum circuits to IBM QX architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(10): 2375-2383.
[27] 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.
[28] 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. New York, NY: ACM 2019: 1001-1014.
[29] 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.
[30] Finigan W, Cubeddu M, Lively T, et al. Qubit allocation for noisy intermediate-scale quantum computers[J]. arXiv:1810.08291, 2018, https://arxiv.org/abs/1810.08291.
[31] Paler A. On the influence of initial qubit placement during NISQ circuit compilation[C]//Proceedings of International Workshop on Quantum Technology and Optimization Problems. Munich, Germany: Springer, 2019: 207-217.
[32] Nishio S, Pan Y, Satoh T, et al. Extracting success from IBM’s 20-qubit machines using error-aware compilation[J]. ACM Journal on Emerging Technologies in Computing Systems, 2020, 16(3): 1-25.
[33] Murali P, Baker J M, Javadi-Abhari A, et al. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers[C]//Proceedings of 24th International Conference on Architectural Support for Programming Languages and Operating Systems. New York, NY: ACM, 2019: 1015-1029.
[34] Tan B, Cong J. Optimality study of existing quantum computing layout synthesis tools[J]. IEEE Transactions on Computers, 2020, Early Access, https://ieeexplore.ieee.org/abstract/document/9140293.
[35] M. A. Nielsen and I. L. Chuang, Quantum Circuits[M]//Quantum Computation and Quantum Information, 10th ed. New York, NY: Cambridge Univ. Press, 2010:171-215.

A computer⁃aided⁃design methodology for quantum circuit mapping based on stochastic optimization model

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

Comments

[1]	. A Conversion Method for Improving Fidelity of QuantumCircuits [J]. Chinese Journal of Quantum Electronics, 2024, 41(1): 161-169.
[2]	. Research progress of distributed quantum computing [J]. Chinese Journal of Quantum Electronics, 2024, 41(1): 1-25.
[3]	LI Zhiqiang, HU Jiajia, ZHANG Wei, PAN Suhan, DAI Juan, YANG Donghan, WU Xi. A fast method for solving unitary matrix of quantum logic circuits [J]. Chinese Journal of Quantum Electronics, 2020, 37(2): 222-228.
[4]	CHEN Jinlian, LI Dongfen, ZHOU Qin, YANG Yanhan. Quantum teleportation for an unknown six-qubit entangled state and principle verification [J]. Chinese Journal of Quantum Electronics, 2019, 36(4): 456-463.
[5]	Wang Xin-Liang, Yang Qian-Hui, Jin Xiang. Periodic communication detection of botnet based on quantum computing [J]. J4, 2016, 33(2): 182-187.