DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2025.47

Quantum Programming in Polylogarithmic Time

Authors: Florent Ferrari, Emmanuel Hainry, Romain Péchoux, and Mário Silva

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

Polylogarithmic time delineates a relevant notion of feasibility on several classical computational models such as Boolean circuits or parallel random access machines. As far as the quantum paradigm is concerned, this notion yields the complexity class FBQPOLYLOG of functions approximable in polylogarithmic time with a quantum random access Turing machine. We introduce a quantum programming language with first-order recursive procedures, which provides the first programming language-based characterization of FBQPOLYLOG. Each program computes a function in FBQPOLYLOG (soundness) and, conversely, each function of this complexity class is computed by a program (completeness). We also provide a compilation strategy from programs to uniform families of quantum circuits of polylogarithmic depth and polynomial size, whose set of computed functions is known as qnc, and recover the well-known separation result FBQPOLYLOG ⊊ QNC.

Cite as

Florent Ferrari, Emmanuel Hainry, Romain Péchoux, and Mário Silva. Quantum Programming in Polylogarithmic Time. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ferrari_et_al:LIPIcs.MFCS.2025.47,
  author =	{Ferrari, Florent and Hainry, Emmanuel and P\'{e}choux, Romain and Silva, M\'{a}rio},
  title =	{{Quantum Programming in Polylogarithmic Time}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.47},
  URN =		{urn:nbn:de:0030-drops-241547},
  doi =		{10.4230/LIPIcs.MFCS.2025.47},
  annote =	{Keywords: Quantum programming languages, Polylogarithmic time, Quantum circuits, Implicit computational complexity}
}

Document

DOI: 10.4230/LIPIcs.FSCD.2025.22

Branch Sequentialization in Quantum Polytime

Authors: Emmanuel Hainry, Romain Péchoux, and Mário Silva

Published in: LIPIcs, Volume 337, 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)

Abstract

Quantum algorithms leverage the use of quantumly-controlled data in order to achieve computational advantage. This implies that the programs use constructs depending on quantum data and not just classical data such as measurement outcomes. Current compilation strategies for quantum control flow involve compiling the branches of a quantum conditional, either in-depth or in-width, which in general leads to circuits of exponential size. This problem is coined as the branch sequentialization problem. We introduce and study a compilation technique for avoiding branch sequentialization on a language that is sound and complete for quantum polynomial time, thus, improving on existing polynomial-size-preserving compilation techniques.

Cite as

Emmanuel Hainry, Romain Péchoux, and Mário Silva. Branch Sequentialization in Quantum Polytime. In 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 337, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hainry_et_al:LIPIcs.FSCD.2025.22,
  author =	{Hainry, Emmanuel and P\'{e}choux, Romain and Silva, M\'{a}rio},
  title =	{{Branch Sequentialization in Quantum Polytime}},
  booktitle =	{10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-374-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{337},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.22},
  URN =		{urn:nbn:de:0030-drops-236373},
  doi =		{10.4230/LIPIcs.FSCD.2025.22},
  annote =	{Keywords: Quantum Programs, Implicit Computational Complexity, Quantum Circuits}
}

Search Results

Documents authored by Hainry, Emmanuel

Quantum Programming in Polylogarithmic Time

Abstract

Cite as

Branch Sequentialization in Quantum Polytime

Abstract

Cite as

Thanks for your feedback!

Could not send message