AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Qubit Mapping Based on Tabu Search

Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China
Show Author Information

Abstract

The goal of qubit mapping is to map a logical circuit to a physical device by introducing additional gates as few as possible in an acceptable amount of time. We present an effective approach called Tabu Search Based Adjustment (TSA) algorithm to construct the mappings. It consists of two key steps: one is making use of a combined subgraph isomorphism and completion to initialize some candidate mappings, and the other is dynamically modifying the mappings by TSA. Our experiments show that, compared with state-of-the-art methods, TSA can generate mappings with a smaller number of additional gates and have better scalability for large-scale circuits.

Keywords

quantum computingqubit mappinginitial mappingtabu searchlogical circuit

Electronic Supplementary Material

Download File(s)
JCST-2112-12121-Highlights.pdf (130.9 KB)

References

[1]
Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. the 35th Annual Symposium on Foundations of Computer Science, Nov. 1994, pp.124–134. DOI: 10.1109/SFCS.1994.365700.
Crossref
[2]
Grover L K. A fast quantum mechanical algorithm for database search. In Proc. the 28th Annual ACM Symposium on the Theory of Computing, Jul. 1996, pp.212–219. DOI: 10.1145/237814.237866.
Crossref
[3]

Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Physical Review Letters , 2009, 103(15): 150502. DOI: 10.1103/PhysRevLett.103.1505 02.
Crossref Google Scholar
[4]

Arute F, Arya K, Babbush R et al. Quantum supremacy using a programmable superconducting processor. Nature , 2019, 574(7779): 505–510. DOI: 10.1038/s41586-019-1666-5.
Crossref Google Scholar
[5]
Almudever C G, Lao L L, Wille R, Guerreschi G G. Realizing quantum algorithms on real quantum computing devices. In Proc. the 23rd Conference on Design, Automation and Test in Europe, Mar. 2020, pp.864–872. DOI: 10.23919/DATE48585.2020.9116240.
Crossref
[6]

Reagor M, Pfaff W, Axline C et al. Quantum memory with millisecond coherence in circuit QED. Physical Review B , 2016, 94(1): 014506. DOI: 10.1103/PhysRevB.94.014506.
Crossref Google Scholar
[7]
Sun S X, Luo Q. In-memory subgraph matching: An in-depth study. In Proc. the 2020 ACM SIGMOD International Conference on Management of Data, Jun. 2020, pp.1083–1098. DOI: 10.1145/3318464.3380581.
Crossref
[8]
Siraichi M Y, dos Santos V F, Collange C, Pereira F M Q. Qubit allocation. In Proc. the 2018 International Symposium on Code Generation and Optimization, Feb. 2018, pp.113–125. DOI: 10.1145/3168822.
Crossref
[9]

Glover F. Tabu search-part II. ORSA Journal on Computing , 1990, 2(1): 4–32. DOI: 10.1287/ijoc.2.1.4.
Crossref Google Scholar
[10]

Zulehner A, Paler A, Wille R. An efficient methodology for mapping quantum circuits to the IBM QX architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2019, 38(7): 1226–1236. DOI: 10.1109/TCAD.2018.2846658.
Crossref Google Scholar
[11]
Li G S, Ding Y F, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.1001–1014. DOI: 10.1145/3297858.3304023.
Crossref
[12]

Li S J, Zhou X Z, Feng Y. Qubit mapping based on subgraph isomorphism and filtered depth-limited search. IEEE Transactions on Computers , 2021, 70(11): 1777–1788. DOI: 10.1109/TC.2020.3023247.
Crossref Google Scholar
[13]

Zhu P C, Guan Z J, Cheng X Y. A dynamic look-ahead heuristic for the qubit mapping problem of NISQ computers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2020, 39(12): 4721–4735. DOI: 10.1109/TCAD.2020.2970594.
Crossref Google Scholar
[14]

Cai S W, Su K L. Local search for Boolean Satisfiability with configuration checking and subscore. Artificial Intelligence , 2013, 204: 75–98. DOI: 10.1016/j.artint.2013.09.001.
Crossref Google Scholar
[15]
Paler A. On the influence of initial qubit placement during NISQ circuit compilation. In Proc. the 1st International Workshop on Quantum Technology and Optimization Problems, Mar. 2019, pp.207–217. DOI: 10.1007/978-3-030-14082-3_18.
Crossref
[16]

Kissinger A, van de Griend A M. CNOT circuit extraction for topologically-constrained quantum memories. Quantum Information and Computation , 2020, 20(7/8): 581–596. DOI: 10.26421/QIC20.7-8-4.
Crossref Google Scholar
[17]

Nash B, Gheorghiu V, Mosca M. Quantum circuit optimizations for NISQ architectures. Quantum Science and Technology , 2020, 5(2): 025010. DOI: 10.1088/2058-9565/ab79b1.
Crossref Google Scholar
[18]
Venturelli D, Do M, Rieffel E, Frank J. Temporal planning for compilation of quantum approximate optimization circuits. In Proc. the 26th International Joint Conference on Artificial Intelligence, Aug. 2017, pp.4440–4446.
Crossref
[19]
Bernal D E, Booth K E C, Dridi R, Alghassi H, Tayur S, Venturelli D. Integer programming techniques for minor-embedding in quantum annealers. In Proc. the 17th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Sept. 2020, pp.112–129. DOI: 10.1007/978-3-030-58942-4_8.
Crossref
[20]
de Almeida A A A, Dueck G W, da Silva A C R. Finding optimal qubit permutations for IBM’s quantum computer architectures. In Proc. the 32nd Symposium on Integrated Circuits and Systems Design, 2019, Article No. 13. DOI: 10.1145/3338852.3339829.
Crossref
[21]
Wille R, Burgholzer L, Zulehner A. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In Proc. the 56th Annual Design Automation Conference 2019, Jun. 2019, Article No. 142. DOI: 10.1145/3316781.3317859.
Crossref
[22]
Shafaei A, Saeedi M, Pedram M. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In Proc. the 50th Annual Design Automation Conference, May 2013, Article No. 41. DOI: 10.1145/2463209.2488785.
Crossref
[23]

Guerreschi G G, Park J. Two-step approach to scheduling quantum circuits. Quantum Science and Technology , 2018, 3(4): 045003. DOI: 10.1088/2058-9565/aacf0b.
Crossref Google Scholar
[24]
Matsuo A, Yamashita S. An efficient method for quantum circuit placement problem on a 2-D grid. In Proc. the 11th International Conference on Reversible Computation, Jun. 2019, pp.162–168. DOI: 10.1007/978-3-030-21500-2_10.
Crossref
[25]
Cowtan A, Dilkes S, Duncan R, Krajenbrink A, Simmons W, Sivarajah S. On the qubit routing problem. In Proc. the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography, May 2019, Article No. 5. DOI: 10.4230/LIPIcs.TQC.2019.5.
[26]

Zhou X Z, Li S J, Feng Y. Quantum circuit transformation based on simulated annealing and heuristic search. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2020, 39(12): 4683–4694. DOI: 10.1109/TCAD.2020.2969647.
Crossref Google Scholar
[27]
Tannu S S, Qureshi M K. Not all qubits are created equal: A case for variability-aware policies for NISQ-era quantum computers. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.987–999. DOI: 10.1145/3297858.3304007.
Crossref
[28]

Lao L L, van Someren H, Ashraf I, Almudever C G. Timing and resource-aware mapping of quantum circuits to superconducting processors. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2022, 41(2): 359–371. DOI: 10.1109/TCAD.2021.3057583.
Crossref Google Scholar
[29]
Guerreschi G G. Scheduler of quantum circuits based on dynamical pattern improvement and its application to hardware design. arXiv: 1912.00035, 2019. https://arxiv.org/abs/1912.00035, Mar. 2024.
[30]
Nielsen M A, Chuang I L. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
[31]

Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A, Weinfurter H. Elementary gates for quantum computation. Physical Review A , 1995, 52(5): 3457–3467. DOI: 10.1103/PhysRevA.52.3457.
Crossref Google Scholar
[32]
Mottonen M, Vartiainen J J. Decompositions of general quantum gates. Frontiers in Artificial Intelligence and Applications, 2005, 57(8): 1263–1270. DOI: 10.1103/PhysRevLett.93.130502.
Crossref
[33]

Cross A, Javadi-Abhari A, Alexander T et al. OpenQASM 3: A broader and deeper quantum assembly language. ACM Transactions on Quantum Computing , 2022, 3(3): 12. DOI: 10.1145/3505636.
Crossref Google Scholar
[34]

Floyd R W. Algorithm 97: Shortest path. Communications of the ACM , 1962, 5(6): 345. DOI: 10.1145/367766.368168.
Crossref Google Scholar
[35]
Wille R, Große D, Teuber L, Dueck G W, Drechsler R. Revlib: An online resource for reversible functions and reversible circuits. In Proc. the 38th International Symposium on Multiple Valued Logic, May 2008, pp.220–225. DOI: 10.1109/ISMVL.2008.43.
Crossref
Journal of Computer Science and Technology
Volume 39 Issue 2,
March 2024
Pages 421-433
DOI: 10.1007/s11390-023-2121-5
Cite this article:
Jiang H, Deng Y-X, Xu M. Qubit Mapping Based on Tabu Search. Journal of Computer Science and Technology, 2024, 39(2): 421-433. https://doi.org/10.1007/s11390-023-2121-5

201

Views

0

Crossref

1

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 29 December 2021
Accepted: 31 August 2023
Published: 30 March 2024
© Institute of Computing Technology, Chinese Academy of Sciences 2024
Return