DROPS

Document

DOI: 10.4230/LIPIcs.CP.2024.16

A New Optimization Model for Multiple-Control Toffoli Quantum Circuit Design

Authors: Jihye Jung, Kevin Dalmeijer, and Pascal Van Hentenryck

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

As quantum technology is advancing, the efficient design of quantum circuits has become an important area of research. This paper provides an introduction to the MCT quantum circuit design problem for reversible Boolean functions without assuming a prior background in quantum computing. While this is a well-studied problem, optimization models that minimize the true objective have only been explored recently. This paper introduces a new optimization model and symmetry-breaking constraints that improve solving time by up to two orders of magnitude compared to earlier work when a Constraint Programming solver is used. Experiments with up to seven qubits and using up to 15 quantum gates result in several new best-known circuits, obtained by any method, for well-known benchmarks. Finally, an extensive comparison with other approaches shows that optimization models may require more time but can provide superior circuits with optimality guarantees.

Cite as

Jihye Jung, Kevin Dalmeijer, and Pascal Van Hentenryck. A New Optimization Model for Multiple-Control Toffoli Quantum Circuit Design. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jung_et_al:LIPIcs.CP.2024.16,
  author =	{Jung, Jihye and Dalmeijer, Kevin and Van Hentenryck, Pascal},
  title =	{{A New Optimization Model for Multiple-Control Toffoli Quantum Circuit Design}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.16},
  URN =		{urn:nbn:de:0030-drops-207010},
  doi =		{10.4230/LIPIcs.CP.2024.16},
  annote =	{Keywords: Constraint Programming, Quantum Circuit Design, Reversible Circuits}
}

Search Results

Documents authored by Jung, Jihye

A New Optimization Model for Multiple-Control Toffoli Quantum Circuit Design

Abstract

Cite as

Thanks for your feedback!

Could not send message