2 Search Results for "Nielsen, Frank"

Document
DOI: 10.4230/LIPIcs.SAT.2024.26
Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits

Authors: Irfansha Shaik and Jaco van de Pol

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.
Cite as

Irfansha Shaik and Jaco van de Pol. Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shaik_et_al:LIPIcs.SAT.2024.26,
  author =	{Shaik, Irfansha and van de Pol, Jaco},
  title =	{{Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.26},
  URN =		{urn:nbn:de:0030-drops-205487},
  doi =		{10.4230/LIPIcs.SAT.2024.26},
  annote =	{Keywords: Layout Synthesis, Transpiling, Qubit Mapping and Routing, Quantum Circuits, Propositional Satisfiability, Parallel Plans}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.67
On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution)

Authors: Frank Nielsen and Laetitia Shao

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Hilbert geometry is a metric geometry that extends the hyperbolic Cayley-Klein geometry. In this video, we explain the shape of balls and their properties in a convex polygonal Hilbert geometry. First, we study the combinatorial properties of Hilbert balls, showing that the shapes of Hilbert polygonal balls depend both on the center location and on the complexity of the Hilbert domain but not on their radii. We give an explicit description of the Hilbert ball for any given center and radius. We then study the intersection of two Hilbert balls. In particular, we consider the cases of empty intersection and internal/external tangencies.
Cite as

Frank Nielsen and Laetitia Shao. On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 67:1-67:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nielsen_et_al:LIPIcs.SoCG.2017.67,
  author =	{Nielsen, Frank and Shao, Laetitia},
  title =	{{On Balls in a Hilbert Polygonal Geometry}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{67:1--67:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.67},
  URN =		{urn:nbn:de:0030-drops-72443},
  doi =		{10.4230/LIPIcs.SoCG.2017.67},
  annote =	{Keywords: Projective geometry, Hilbert geometry, balls}
}
  • Refine by Author
  • 1 Nielsen, Frank
  • 1 Shaik, Irfansha
  • 1 Shao, Laetitia
  • 1 van de Pol, Jaco

  • Refine by Classification

  • Refine by Keyword
  • 1 Hilbert geometry
  • 1 Layout Synthesis
  • 1 Parallel Plans
  • 1 Projective geometry
  • 1 Propositional Satisfiability
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 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 About DROPS Imprint Privacy Contact