Architecture aware compilation of quantum circuits via lazy synthesis

Simon Martiel1 and Timothée Goubault de Brugière1,2,3

1Atos Quantum Lab. Les Clayes-sous-bois, France
2Laboratoire de Recherche en Informatique (LRI), Orsay, France
3Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Nancy, France

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Qubit routing is a key problem for quantum circuit compilation. It consists in rewriting a quantum circuit by adding the least possible number of instructions to make the circuit compliant with some architecture's connectivity constraints. Usually, this problem is tackled via either SWAP insertion techniques or re-synthesis of portions of the circuit using architecture aware synthesis algorithms. In this work, we propose a meta-heuristic that couples the iterative approach of SWAP insertion techniques with greedy architecture-aware synthesis routines. We propose two new compilation algorithms based on this meta-heuristic and compare their performances to state-of-the-art quantum circuit compilation techniques for several standard classes of quantum circuits and show significant reduction in the entangling gate overhead due to compilation.

► BibTeX data

► References

[1] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. On the controlled-not complexity of controlled-not–phase circuits. Quantum Science and Technology, 4(1):015002, 2018. doi:10.1088/​2058-9565/​aad8ca.
https:/​/​doi.org/​10.1088/​2058-9565/​aad8ca

[2] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5), Nov 2004. doi:10.1103/​physreva.70.052328.
https:/​/​doi.org/​10.1103/​physreva.70.052328

[3] Matthew Amy and Vlad Gheorghiu. staq—a full-stack quantum processing toolkit. Quantum Science and Technology, 5(3):034016, jun 2020. doi:10.1088/​2058-9565/​ab9359.
https:/​/​doi.org/​10.1088/​2058-9565/​ab9359

[4] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group. arXiv preprint arXiv:2003.09412, 2020. doi:10.1109/​TIT.2021.3081415.
https:/​/​doi.org/​10.1109/​TIT.2021.3081415
arXiv:2003.09412

[5] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the qubit routing problem. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. doi:10.4230/​LIPIcs.TQC.2019.5.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2019.5

[6] Andrew M. Childs, E. Schoute, and Cem M. Unsal. Circuit transformations for quantum architectures. ArXiv, abs/​1902.09102, 2019. doi:10.4230/​LIPIcs.TQC.2019.3.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2019.3

[7] Niel de Beaudrap. A linearized stabilizer formalism for systems of finite dimension. 2011. doi:10.5555/​2481591.2481597.
https:/​/​doi.org/​10.5555/​2481591.2481597

[8] Timothée Goubault de Brugière, Marc Baboulin, Benoı̂t Valiron, Simon Martiel, and Cyril Allouche. Quantum cnot circuits synthesis for nisq architectures using the syndrome decoding problem. In International Conference on Reversible Computation, pages 189–205. Springer, 2020. doi:10.1007/​978-3-030-52482-1_11.
https:/​/​doi.org/​10.1007/​978-3-030-52482-1_11

[9] Vlad Gheorghiu, Sarah Meng Li, Michele Mosca, and Priyanka Mukhopadhyay. Reducing the cnot count for clifford+t circuits on nisq architectures, 2020. arXiv:2011.12191.
arXiv:2011.12191

[10] Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quantum Information & Computation, 11(1&2):142–166, 2011. doi:10.26421/​QIC11.1-2-10.
https:/​/​doi.org/​10.26421/​QIC11.1-2-10

[11] Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 464(2100):3089–3106, Jul 2008. doi:10.1098/​rspa.2008.0189.
https:/​/​doi.org/​10.1098/​rspa.2008.0189

[12] Samuel A Kutin, David Petrie Moulton, and Lawren M Smithline. Computation at a distance. arXiv preprint quant-ph/​0701194, 2007. doi:10.48550/​arXiv.quant-ph/​0701194.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0701194
arXiv:quant-ph/0701194

[13] Aleks Kissinger and Arianne Meijer van de Griend. Cnot circuit extraction for topologically-constrained quantum memories, 2019. doi:10.26421/​QIC20.7-8-4.
https:/​/​doi.org/​10.26421/​QIC20.7-8-4

[14] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices, 2018. doi:10.1145/​3297858.3304023.
https:/​/​doi.org/​10.1145/​3297858.3304023

[15] Daniel Litinski. Magic state distillation: Not as costly as you think. Quantum, 3:205, Dec 2019. doi:10.22331/​q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

[16] Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations for nisq architectures. Quantum Science and Technology, 5(2):025010, Mar 2020. doi:10.1088/​2058-9565/​ab79b1.
https:/​/​doi.org/​10.1088/​2058-9565/​ab79b1

[17] Ketan N Patel, Igor L Markov, and John P Hayes. Optimal synthesis of linear reversible circuits. Quantum Information & Computation, 8(3):282–294, 2008. doi:10.5555/​2011763.2011767.
https:/​/​doi.org/​10.5555/​2011763.2011767

[18] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, Aug 2018. doi:10.22331/​q-2018-08-06-79.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[19] A. Shafaei, M. Saeedi, and M. Pedram. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In 2013 50th ACM/​EDAC/​IEEE Design Automation Conference (DAC), pages 1–6, 2013. doi:10.1145/​2463209.2488785.
https:/​/​doi.org/​10.1145/​2463209.2488785

[20] Hiromitsu Takahashi. An approximate solution for the steiner problem in graphs. Math. Japonica., 6:573–577, 1990.

[21] Ewout van den Berg and Kristan Temme. Circuit optimization of hamiltonian simulation by simultaneous diagonalization of pauli clusters. Quantum, 4:322, Sep 2020. doi:10.22331/​q-2020-09-12-322.
https:/​/​doi.org/​10.22331/​q-2020-09-12-322

[22] Arianne Meijer van de Griend and Ross Duncan. Architecture-aware synthesis of phase polynomials for nisq devices, 2020. doi:10.4204/​EPTCS.
https:/​/​doi.org/​10.4204/​EPTCS

[23] Fang Zhang and Jianxin Chen. Optimizing t gates in clifford+t circuit as $\pi/​4$ rotations around paulis, 2019. arXiv:1903.12456, doi:10.48550/​arXiv.1903.12456.
https:/​/​doi.org/​10.48550/​arXiv.1903.12456
arXiv:1903.12456

[24] Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the ibm qx architectures, 2017. doi:10.1109/​TCAD.2018.2846658.
https:/​/​doi.org/​10.1109/​TCAD.2018.2846658

Cited by

[1] Vivien Vandaele, Simon Martiel, and Timothée Goubault de Brugière, "Phase polynomials synthesis algorithms for NISQ architectures and beyond", Quantum Science and Technology 7 4, 045027 (2022).

[2] P. Besserve and T. Ayral, "Unraveling correlated material properties with noisy quantum computers: Natural orbitalized variational quantum eigensolving of extended impurity models within a slave-boson approach", Physical Review B 105 11, 115108 (2022).

[3] Mohammad Haidar, Marko J. Rančić, Thomas Ayral, Yvon Maday, and Jean-Philip Piquemal, "Open Source Variational Quantum Eigensolver Extension of the Quantum Learning Machine (QLM) for Quantum Chemistry", arXiv:2206.08798.

The above citations are from Crossref's cited-by service (last updated successfully 2022-12-08 03:35:15) and SAO/NASA ADS (last updated successfully 2022-12-08 03:35:16). The list may be incomplete as not all publishers provide suitable and complete citation data.