Paper published in a book (Scientific congresses and symposiums)
A Parallel Genetic Algorithm for Qubit Mapping on Noisy Intermediate-Scale Quantum Machines
Rouzé, Jérôme; Melab, Nouredine; Tuyttens, Daniel
2025 • In Dorronsoro, Bernabé (Ed.) Optimization and Learning - 7th International Conference, OLA 2024, Revised Selected Papers B. Dorronsoro et al. (Eds.): OLA 2024, CCIS 2311, pp. 305–320, 2025.
[en] Quantum computers are getting increasingly large and available thanks to some major technological advancements, but they remain in the realm of NISQ (Noisy Intermediate Scale Quantum) devices. On such devices, due to the limited connectivity of the physical qubits, most quantum circuit-based programs cannot be executed without transpilation. This latter includes an important step, referred to as qubit mapping, which consists in converting the quantum circuit into another one which best matches the graph of physical qubits taking into account its limited connectivity constraint. In this paper, we propose a Parallel Genetic Algorithm to Qubit Mapping (PGA-QM). The challenge is to minimize the depth of the transformed circuit and the execution time and error rate consequently. PGA-QM has been experimented using various medium-to-large scale circuit benchmarks. It is compared against the SABRE heuristic currently implemented in Qiskit, the IBM’s library for quantum computing. The reported results show that PGA-QM can provide better solutions and with better consistency than its counterpart while parallelism greatly reduces its execution time during the transpilation.
Disciplines :
Computer science
Author, co-author :
Rouzé, Jérôme; Mathematics and Operations Research Department, University of Mons, Mons, Belgium
Melab, Nouredine; Univ. Lille, CNRS, Centrale Lille, Inria, UMR 9189 - CRIStAL - Centre de Recherche en Informatique Signal et Automatique de Lille, Lille, France
Tuyttens, Daniel ; Université de Mons - UMONS > Faculté Polytechnique > Service de Mathématique et Recherche opérationnelle
Language :
English
Title :
A Parallel Genetic Algorithm for Qubit Mapping on Noisy Intermediate-Scale Quantum Machines
Publication date :
2025
Event name :
OLA 2024
Event place :
Dubrovnik, Hrv
Event date :
13-05-2024 => 15-05-2024
Main work title :
Optimization and Learning - 7th International Conference, OLA 2024, Revised Selected Papers B. Dorronsoro et al. (Eds.): OLA 2024, CCIS 2311, pp. 305–320, 2025.
Editor :
Dorronsoro, Bernabé
Publisher :
Springer Science and Business Media Deutschland GmbH
Acampora, G., Schiattarella, R.: Deep neural networks for quantum circuit mapping. Neural Comput. Appl. 33(20), 13723–13743 (2021). https://doi.org/10.1007/s00521-021-06009-3
Balouek, D., et al.: Adding virtualization capabilities to the grid’5000 testbed. In: Ivanov, I.I., van Sinderen, M., Leymann, F., Shan, T. (eds.) CLOSER 2012. CCIS, vol. 367, pp. 3–20. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-04519-1_1
Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995). https://doi.org/10.1103/physreva.52.3457
Cheng, C.Y., Yang, C.Y., Kuo, Y.H., Wang, R.C., Cheng, H.C., Huang, C.Y.R.: Robust qubit mapping algorithm via double-source optimal routing on large quantum circuits (2023)
Dahi, Z.A., Alba, E.: Metaheuristics on quantum computers: inspiration, simulation and real execution. Futur. Gener. Comput. Syst. 130, 164–180 (2022). https://doi.org/10.1016/j.future.2021.12.015
Dahi, Z.A., Chicano, F., Luque, G., Alba, E.: Genetic algorithm for qubits initialisation in noisy intermediate-scale quantum machines: the IBM case study. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 1164–1172. Association for Computing Machinery, New York (2022). https://doi.org/10.1145/3512290.3528830
Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms versus simulated annealing (2002)
Gad, A.F.: Pygad: an intuitive genetic algorithm python library (2021)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 212–219. Association for Computing Machinery, New York (1996). https://doi.org/10.1145/237814.237866
Gyongyosi, L., Imre, S.: A survey on quantum computing technology. Comput. Sci. Rev. 31, 51–71 (2019). https://doi.org/10.1016/j.cosrev.2018.11.002. https://www.sciencedirect.com/science/article/pii/S1574013718301709
Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for nisq-era quantum devices. In: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2019, pp. 1001–1014. Association for Computing Machinery, New York (2019). https://doi.org/10.1145/3297858.3304023
Li, Y., Tian, M., Liu, G., Peng, C., Jiao, L.: Quantum optimization and quantum learning: a survey. IEEE Access 8, 23568–23593 (2020). https://doi.org/10.1109/ACCESS.2020.2970105
Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023). https://doi.org/10.5281/zenodo.2573505
Quetschlich, N., Burgholzer, L., Wille, R.: MQT Bench: Benchmarking software and design automation tools for quantum computing (2022). MQT Bench is available at https://www.cda.cit.tum.de/mqtbench/
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). https://doi.org/10.1137/s0097539795293172
Siraichi, M.Y., Santos, V.F.D., Collange, C., Quintão Pereira, F.M.: Qubit allocation. In: CGO 2018 - International Symposium on Code Generation and Optimization, Vienna, Austria, pp. 1–12 (2018). https://doi.org/10.1145/3168822. https://hal.science/hal-01655951
Zhou, X., Li, S., Feng, Y.: Quantum circuit transformation based on simulated annealing and heuristic search. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 39(12), 4683–4694 (2020). https://doi.org/10.1109/tcad.2020.2969647
