On Optimal Subarchitectures for Quantum Circuit Mapping

Tom Peham; Lukas Burgholzer; Robert Wille

doi:10.1145/3593594

journal article Jul 25, 2023

On Optimal Subarchitectures for Quantum Circuit Mapping

Tom Peham

Lukas Burgholzer

Robert Wille

ACM Transactions on Quantum Computing Vol. 4 No. 4 pp. 1-20 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3593594

Abstract

Compiling a high-level quantum circuit down to a low-level description that can be executed on state-of-the-art quantum computers is a crucial part of the software stack for quantum computing. One step in compiling a quantum circuit to some device is quantum circuit mapping, where the circuit is transformed such that it complies with the architecture’s limited qubit connectivity. Because the search space in quantum circuit mapping grows exponentially in the number of qubits, it is desirable to consider as few of the device’s physical qubits as possible in the process. Previous work conjectured that it suffices to consider only subarchitectures of a quantum computer composed of as many qubits as used in the circuit. In this work, we refute this conjecture and establish criteria for judging whether considering larger parts of the architecture might yield better solutions to the mapping problem. We show that determining subarchitectures that are of minimal size, i.e., from which no physical qubit can be removed without losing the optimal mapping solution for some quantum circuit, is a very hard problem. Based on a relaxation of the criteria for optimality, we introduce a relaxed consideration that still maintains optimality for practically relevant quantum circuits. Eventually, this results in two methods for computing near-optimal sets of subarchitectures—providing the basis for
efficient
quantum circuit mapping solutions. We demonstrate the benefits of this novel method for state-of-the-art quantum computers by IBM, Google, and Rigetti.

Topics

No keywords indexed for this article. Browse by subject →

References

33

[1]

10.5555/1972505

[2]

M. H. Devoret and R. J. Schoelkopf. 2013. Superconducting circuits for quantum information: An outlook. 339 6124 (2013) 1169–1174. 10.1126/science.1231930

[3]

Mehdi Saeedi Robert Wille and Rolf Drechsler. 2011. Synthesis of quantum circuits for linear nearest neighbor architectures. 10 3 (2011) 355–377. DOI:http://dx.doi.org/10.1007/s11128-010-0201-2 10.1007/s11128-010-0201-2

[4]

Alwin Zulehner Alexandru Paler and Robert Wille. 2019. An efficient methodology for mapping quantum circuits to the IBM QX architectures. 10.23919/date.2018.8342181

[5]

Alwin Zulehner and Robert Wille. 2019. Compiling SU(4) quantum circuits to IBM QX architectures. In Asia and South Pacific Design Automation Conf.185–190. DOI:http://dx.doi.org/10.1145/3287624.3287704

[6]

Stefan Hillmich, Alwin Zulehner, and Robert Wille. 2021. Exploiting quantum teleportation in quantum circuit mapping. In Proceedings of the Design, Automation and Test in Europe Conference(DAT’2021). ACM, 792–797. DOI:http://dx.doi.org/10.1145/3394885.3431604

[7]

Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Caroline Collange, and Fernando Magno Quintao Pereira. 2018. Qubit allocation. In Proceedings of the International Symposium on Code Generation and Optimization. ACM, 113–125. DOI:http://dx.doi.org/10.1145/3168822

[8]

Pengcheng Zhu Xueyun Cheng and Zhijin Guan. 2020. An exact qubit allocation approach for NISQ architectures. 19 11 (2020) 391. 10.1007/s11128-020-02901-4

[9]

Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. 2019. On the qubit routing problem. In Theory of Quantum Computation, Communication and Cryptography, Wim van Dam and Laura Mancinska (Eds.).

[10]

Yunseong Nam Neil J. Ross Yuan Su Andrew M. Childs and Dmitri Maslov. 2018. Automated optimization of large quantum circuits with continuous parameters. NPJ Quantum Information (2018).

[11]

Aleks Kissinger and John van de Wetering. 2020. Reducing T-count with the ZX-calculus. Physical Review A (2020).

[12]

Prakash Murali, Jonathan M. Baker, Ali Javadi-Abhari, Frederic T. Chong, and Margaret Martonosi. 2019. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 1015–1029. DOI:http://dx.doi.org/10.1145/3297858.3304075

[13]

Lukas Burgholzer, Sarah Schneider, and Robert Wille. 2022. Limiting the search space in optimal quantum circuit mapping. In Proceedings of the Asia and South Pacific Design Automation Conf.

[14]

Robert Wille, Lukas Burgholzer, and Alwin Zulehner. 2019. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In Proceedings of the Design Automation Conf.

[15]

A. Botea, A. Kishimoto, and Radu Marinescu. 2018. On the complexity of quantum circuit compilation. In Proceedings of the International Symposium on Combinatorial Search.

[16]

Jay Gambetta. 2020. IBM’s roadmap for scaling quantum technology. Retrieved from https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/.

[17]

Quantum Computing in the NISQ era and beyond

John Preskill

Quantum 10.22331/q-2018-08-06-79

[18]

Adrian Bondy and Uppaluri Siva Ramachandra Murty. 2008. Graph Theory. Springer International Publishing.

[19]

Dmitri Maslov, Sean M. Falconer, and Michele Mosca. 2007. Quantum circuit placement: Optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment. In Proceedings of the Design Automation Conference. 962–965. DOI:http://dx.doi.org/10.1145/1278480.1278717

[20]

B. Tan and J. Cong. 2021. Optimality study of existing quantum computing layout synthesis tools. 70 9 (2021) 1363–1373. DOI:http://dx.doi.org/10.1109/TC.2020.3009140 10.1109/tc.2020.3009140

[21]

Gushu Li, Yufei Ding, and Yuan Xie. 2019. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems.

[22]

Bochen Tan and Jason Cong. 2020. Optimal layout synthesis for quantum computing. In Proceedings of the International Conf. on Computer-Aided Design.

[23]

Animesh Sinha Utkarsh Azad and Harjinder Singh. 2022. Qubit routing using graph neural network aided Monte Carlo tree search. In AAAI Conference on Artificial Intelligence . 10.1609/aaai.v36i9.21231

[24]

Machine Learning Optimization of Quantum Circuit Layouts

Alexandru Paler, Lucian Sasu, Adrian-Cătălin Florea et al.

ACM Transactions on Quantum Computing 10.1145/3565271

[25]

Marco Baioletti, Riccardo Rasconi, and Angelo Oddi. 2021. A novel ant colony optimization strategy for the quantum circuit compilation problem. In Evolutionary Computation in Combinatorial Optimization.

[26]

Matteo G. Pozzi Steven J. Herbert Akash Sengupta and Robert D. Mullins. 2020. Using reinforcement learning to perform qubit routing in quantum compilers. 3 2 (May 2022) 25. Retrieved from https://arxiv.org/abs/2007.15957. 10.1145/3520434

[27]

Arighna Deb Gerhard W. Dueck and Robert Wille. 2021. Exploring the potential benefits of alternative quantum computing architectures. 40 9 (2021) 1825–1835. DOI:http://dx.doi.org/10.1109/TCAD.2020.3032072 10.1109/tcad.2020.3032072

[28]

R. Wille and L. Burgholzer. 2023. MQT QMAP: Efficient quantum circuit mapping. In Proceedings of the International Symposium on Physical Design.

[29]

Matthew Treinish Ivan Carvalho Georgios Tsilimigkounakis and Nahum Sá. 2022. retworkx: A high-performance graph library for python. arxiv:cs/2110.15221. Retrieved from https://arxiv.org/abs/2110.15221.

[30]

A (sub)graph isomorphism algorithm for matching large graphs

L.P. Cordella, P. Foggia, C. Sansone et al.

IEEE Transactions on Pattern Analysis and Machine... 10.1109/tpami.2004.75

[31]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Symposium on Theory of Computing. 151–158.

[32]

Nils Quetschlich Lukas Burgholzer and Robert Wille. 2022. MQT Bench: Benchmarking software and design automation tools for quantum computing. arxiv:2204.13719. Retrieved from https://arxiv.org/abs/2204.13719.

[33]

Paul Nation and Matthew Treinish. (n. d.) mapomatic. Retrieved from https://github.com/Qiskit-Partners/mapomatic.

Metrics

23

Citations

33

References

Details

Published: Jul 25, 2023
Vol/Issue: 4(4)
Pages: 1-20
License: View

Authors

T

Tom Peham

Technical University of Munich, Germany

L

Lukas Burgholzer

Johannes Kepler University, Austria

R

Robert Wille

Technical University of Munich, Germany and Software Competence Center Hagenberg GmbH, Austria

Funding

European Research Council Award: 101001318

German Bundestag

Hightech Agenda Bayern Plus

BMK, BMDW

Cite This Article

Tom Peham, Lukas Burgholzer, Robert Wille (2023). On Optimal Subarchitectures for Quantum Circuit Mapping. ACM Transactions on Quantum Computing, 4(4), 1-20. https://doi.org/10.1145/3593594

On Optimal Subarchitectures for Quantum Circuit Mapping

You May Also Like