License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.43
URN: urn:nbn:de:0030-drops-190805
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19080/
Go to the corresponding LIPIcs Volume Portal

Booth, Kyle E. C.

Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing (Short Paper)

pdf-format:
LIPIcs-CP-2023-43.pdf (0.6 MB)

Abstract

Due to the limited connectivity of gate model quantum devices, logical quantum circuits must be compiled to target hardware before they can be executed. Often, this process involves the insertion of SWAP gates into the logical circuit, usually increasing the depth of the circuit, achieved by solving a so-called qubit assignment and routing problem. Recently, a number of integer linear programming (ILP) models have been proposed for solving the qubit assignment and routing problem to proven optimality. These models encode the objective function and constraints of the problem, and leverage the use of automated solver technology to find hardware-compliant quantum circuits. In this work, we propose constraint programming (CP) models for this problem and compare their performance against ILP for circuit depth minimization for both linear and two-dimensional grid lattice device topologies on a set of randomly generated instances. Our empirical analysis indicates that the proposed CP approaches outperform the ILP models both in terms of solution quality and runtime.

BibTeX - Entry

@InProceedings{booth:LIPIcs.CP.2023.43,
  author =	{Booth, Kyle E. C.},
  title =	{{Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{43:1--43:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19080},
  URN =		{urn:nbn:de:0030-drops-190805},
  doi =		{10.4230/LIPIcs.CP.2023.43},
  annote =	{Keywords: Qubit routing, quantum computing, constraint programming, combinatorial optimization}
}

Keywords: Qubit routing, quantum computing, constraint programming, combinatorial optimization
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI