2 Search Results for "Golubitsky, Oleg"

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}
}
Document
DOI: 10.4230/DagSemProc.06271.4
Bounds and algebraic algorithms in differential algebra: the ordinary case

Authors: Marc Moreno Maza, Oleg Golubitsky, Marina V. Kondratieva, and Alexey Ovchinnikov

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
Consider the Rosenfeld-Groebner algorithm for computing a regular decomposition of a radical differential ideal generated by a set of ordinary differential polynomials. This algorithm inputs a system of differential polynomials and a ranking on derivatives and constructs finitely many regular systems equivalent to the original one. The property of regularity allows to check consistency of the systems and membership to the corresponding differential ideals. We propose a bound on the orders of derivatives occurring in all intermediate and final systems computed by the Rosenfeld-Groebner algorithm and outline its proof. We also reduce the problem of conversion of a regular decomposition of a radical differential ideal from one ranking to another to a purely algebraic problem.
Cite as

Marc Moreno Maza, Oleg Golubitsky, Marina V. Kondratieva, and Alexey Ovchinnikov. Bounds and algebraic algorithms in differential algebra: the ordinary case. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{morenomaza_et_al:DagSemProc.06271.4,
  author =	{Moreno Maza, Marc and Golubitsky, Oleg and Kondratieva, Marina V. and Ovchinnikov, Alexey},
  title =	{{Bounds and algebraic algorithms in differential algebra: the ordinary case}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.4},
  URN =		{urn:nbn:de:0030-drops-10219},
  doi =		{10.4230/DagSemProc.06271.4},
  annote =	{Keywords: Differential algebra, Rosenfeld Groebner Algorithm}
}
  • Refine by Author
  • 1 Dalmeijer, Kevin
  • 1 Golubitsky, Oleg
  • 1 Jung, Jihye
  • 1 Kondratieva, Marina V.
  • 1 Moreno Maza, Marc
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 Constraint Programming
  • 1 Differential algebra
  • 1 Quantum Circuit Design
  • 1 Reversible Circuits
  • 1 Rosenfeld Groebner Algorithm

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2007
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact