Research on quantum circuit mapping based on
dynamic look‑ahead depth

doi:10.3969/j.issn.1007-5461.2024.04.007

Abstract

Abstract: With the rapid development of quantum computing technology, it has entered the noisy intermediate scale quantum (NISQ) era. However, due to the limitations of current technology, a qubit can only be directly interacted with adjacent qubits. In order to implement the logical quantum circuit directly on the NISQ device, it is necessary to insert SWAP gates or use bridge gates to make the qubit nearest neighbor. In order to reduce the number of additional quantum gates inserted in quantum circuit mapping, this paper investigates the dynamic look-ahead based circuit mapping method, considering the impact of inserting SWAP gates in the expansion layer and the cost function model is optimized. Then the best lookahead depth is determined when inserting SWAP gates through the simulated annealing algorithm, in order to reduce the number of inserted SWAP gates and thereby reduce the number of CNOT gates. The experimental results show that, compared with the existing mapping method, the proposed algorithm can effectively reduce the number of CNOT gates inserted in circuit mapping, and the average optimization rate reaches to 45.59%.

Key words: quantum computing, quantum mapping, dynamic look-ahead, look-ahead depth

CLC Number:

TP302.2

CAO Kexin, CHEN Xinyu, ZHU Mingqiang, LI Xiang, CHENG Xueyun, GUAN Zhijin. Research on quantum circuit mapping based on dynamic look‑ahead depth[J]. Chinese Journal of Quantum Electronics, 2024, 41(4): 626-637.

References

[1] Shor?P?W.?Polynomialtime?algorithms?for?prime?factorization?and?discrete?logarithms?on?a?quantum?computer[J].?SIAM?review,?1999,?41(2):?303-332.
[2] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 212-219.
[3] Peruzzo A, McClean J, Shadbolt P, et al. A variational eigenvalue solver on a photonic quantum processor[J]. Nature communications, 2014, 5(1): 1-7.
[4] https://quantum-computing.ibm.com/services 2022.4.20
https://www.cnet.com/pictures/take-a-look-at-googles-quantum-computing-technology 2022.4.20
https://www.intel.com/content/www/us/en/research/quantum-computing.html 2022.4.22
https://www.originqc.com.cn 2022.4.22
[5] Cao Y, Romero J, Olson J P, et al. Quantum chemistry in the age of quantum computing[J]. Chemical reviews, 2019, 119(19): 10856-10915.
[6] 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.
[7] Rahman M M, Dueck G W, Chattopadhyay A, et al. Integrated Synthesis of Linear Nearest Neighbor Ancilla-Free MCT Circuits[C]// ISMVL 2016 IEEE International Symposium on Multiple-Valued Logic. IEEE, 2016:144-149.
[8] Ash-Saki A, Alam M, Ghosh S. QURE: Qubit re-allocation in noisy intermediate-scale quantum computers[C]//Proceedings of the 56th Annual Design Automation Conference 2019. 2019: 1-6.
[9] 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.
[10] Guerreschi G G, Park J. Two-step approach to scheduling quantum circuits[J]. Quantum Science and Technology, 2018, 3(4): 045003.
[11] 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.
[12] Miller?D?M,?Soeken?M,?Drechsler?R.?Mapping?NCV?circuits?to?optimized?Clifford+T?circuits[C]//International?Conference?on?Reversible?Computation.?Springer,?Cham,?2014:?163-175.
[13] Li G, Ding Y, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C]//Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 2019: 1001-1014.
[14] Floyd R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345.
[15] 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.

Research on quantum circuit mapping based on dynamic look‑ahead depth

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments

[1]	WU Xian, FENG Shiguang, LI Lyuzhou. Research progress in reversible circuit synthesis and optimization [J]. Chinese Journal of Quantum Electronics, 2024, 41(4): 565-577.
[2]	CHEN Xinyu , CAO Kexin , ZHU Mingqiang , CHENG Xueyun , FENG Shiguang , GUAN Zhijin. A method for optimizing transmission cost in distributed quantum computing [J]. Chinese Journal of Quantum Electronics, 2024, 41(2): 318-329.
[3]	LI Xiang , JIANG Yibo , CAO Kexin , ZHU Mingqiang , CHENG Xueyun , ZHU Pengcheng , GUAN Zhijin. Research on calibration method of quantum circuit output based on SVM [J]. Chinese Journal of Quantum Electronics, 2024, 41(2): 357-366.
[4]	YANG Hui , LI Zhiqiang , PAN Wenjie , YANG Donghan , WU Xi. Application of quantum approximate optimization algorithm in number partition problem [J]. Chinese Journal of Quantum Electronics, 2024, 41(2): 367-377.
[5]	WANG Shengbin , DOU Menghan , WU Yuchun , GUO Guoping , GUO Guangcan . Research progress of distributed quantum computing [J]. Chinese Journal of Quantum Electronics, 2024, 41(1): 1-25.
[6]	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.
[7]	ZHANG Chao , GUAN Zhijin , FENG Shiguang , NIU Yiren , ZHU Mingqiang. A quantum circuit layout and optimization method in two⁃dimensional architecture [J]. Chinese Journal of Quantum Electronics, 2023, 40(4): 570-581.
[8]	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.
[9]	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.
[10]	Wang Xin-Liang, Yang Qian-Hui, Jin Xiang. Periodic communication detection of botnet based on quantum computing [J]. J4, 2016, 33(2): 182-187.