5 Search Results for "Grosshans, Nathan"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.59
Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time

Authors: Nathan Claudet and Simon Perdrix

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We describe an algorithm with quasi-polynomial runtime n^{log₂(n)+O(1)} for deciding local unitary (LU) equivalence of graph states. The algorithm builds on a recent graphical characterisation of LU-equivalence via generalised local complementation. By first transforming the corresponding graphs into a standard form using usual local complementations, LU-equivalence reduces to the existence of a single generalised local complementation that maps one graph to the other. We crucially demonstrate that this reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up. As a byproduct, we generalise Bouchet’s algorithm for deciding local Clifford (LC) equivalence of graph states by allowing the addition of arbitrary linear constraints. We also improve existing bounds on the size of graph states that are LU- but not LC-equivalent. While the smallest known examples involve 27 qubits, and it is established that no such examples exist for up to 8 qubits, we refine this bound by proving that LU- and LC-equivalence coincide for graph states involving up to 19 qubits.
Cite as

Nathan Claudet and Simon Perdrix. Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{claudet_et_al:LIPIcs.ICALP.2025.59,
  author =	{Claudet, Nathan and Perdrix, Simon},
  title =	{{Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{59:1--59:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.59},
  URN =		{urn:nbn:de:0030-drops-234367},
  doi =		{10.4230/LIPIcs.ICALP.2025.59},
  annote =	{Keywords: Quantum computing, Graph theory, Entanglement, Local complementation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.27
Local Equivalence of Stabilizer States: A Graphical Characterisation

Authors: Nathan Claudet and Simon Perdrix

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Stabilizer states form a ubiquitous family of quantum states that can be graphically represented through the graph state formalism. A fundamental property of graph states is that applying a local complementation - a well-known and extensively studied graph transformation - results in a graph that represents the same entanglement as the original. In other words, the corresponding graph states are LU-equivalent. This property served as the cornerstone for capturing non-trivial quantum properties in a simple graphical manner, in the study of quantum entanglement but also for developing protocols and models based on graph states and stabilizer states, such as measurement-based quantum computing, secret sharing, error correction, entanglement distribution... However, local complementation fails short to fully characterise entanglement: there exist pairs of graph states that are LU-equivalent but cannot be transformed one into the other using local complementations. Only few is known about the equivalence of graph states beyond local complementation. We introduce a generalisation of local complementation which graphically characterises the LU-equivalence of graph states. We use this characterisation to show the existence of a strict infinite hierarchy of equivalences of graph states. Our approach is based on minimal local sets, which are subsets of vertices that are known to cover any graph, and to be invariant under local complementation and even LU-equivalence. We use these structures to provide a type to each vertex of a graph, leading to a natural standard form in which the LU-equivalence can be exhibited and captured by means of generalised local complementation.
Cite as

Nathan Claudet and Simon Perdrix. Local Equivalence of Stabilizer States: A Graphical Characterisation. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{claudet_et_al:LIPIcs.STACS.2025.27,
  author =	{Claudet, Nathan and Perdrix, Simon},
  title =	{{Local Equivalence of Stabilizer States: A Graphical Characterisation}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.27},
  URN =		{urn:nbn:de:0030-drops-228527},
  doi =		{10.4230/LIPIcs.STACS.2025.27},
  annote =	{Keywords: Quantum computing, Graph theory, Entanglement, Local complementation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.38
The AC⁰-Complexity of Visibly Pushdown Languages

Authors: Stefan Göller and Nathan Grosshans

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We study the question of which visibly pushdown languages (VPLs) are in the complexity class AC⁰ and how to effectively decide this question. Our contribution is to introduce a particular subclass of one-turn VPLs, called intermediate VPLs, for which the raised question is entirely unclear: to the best of our knowledge our research community is unaware of containment or non-containment in AC⁰ for any language in our newly introduced class. Our main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs exactly one of the following: that its language L is in AC⁰, some m ≥ 2 such that MODₘ (the words over {0,1} having a number of 1’s divisible by m) is constant-depth reducible to L (implying that L is not in AC⁰), or a finite disjoint union of intermediate VPLs that L is constant-depth equivalent to. In the latter of the three cases one can moreover effectively compute k,l ∈ ℕ_{> 0} with k≠l such that the concrete intermediate VPL L(S → ε ∣ ac^{k-1}Sb₁ ∣ ac^{l-1}Sb₂) is constant-depth reducible to the language L. Due to their particular nature we conjecture that either all intermediate VPLs are in AC⁰ or all are not. As a corollary of our main result we obtain that in case the input language is a visibly counter language our algorithm can effectively determine if it is in AC⁰ - hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter language is in AC⁰ (when restricted to well-matched words). For our proofs we revisit so-called Ext-algebras (introduced by Czarnetzki et al.), which are closely related to forest algebras (introduced by Bojańczyk and Walukiewicz), and use Green’s relations.
Cite as

Stefan Göller and Nathan Grosshans. The AC⁰-Complexity of Visibly Pushdown Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goller_et_al:LIPIcs.STACS.2024.38,
  author =	{G\"{o}ller, Stefan and Grosshans, Nathan},
  title =	{{The AC⁰-Complexity of Visibly Pushdown Languages}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.38},
  URN =		{urn:nbn:de:0030-drops-197483},
  doi =		{10.4230/LIPIcs.STACS.2024.38},
  annote =	{Keywords: Visibly pushdown languages, Circuit Complexity, AC0}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.51
A Note on the Join of Varieties of Monoids with LI

Authors: Nathan Grosshans

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In this note, we give a characterisation in terms of identities of the join of V with the variety of finite locally trivial semigroups LI for several well-known varieties of finite monoids V by using classical algebraic-automata-theoretic techniques. To achieve this, we use the new notion of essentially-V stamps defined by Grosshans, McKenzie and Segoufin and show that it actually coincides with the join of V and LI precisely when some natural condition on the variety of languages corresponding to V is verified. This work is a kind of rediscovery of the work of J. C. Costa around 20 years ago from a rather different angle, since Costa’s work relies on the use of advanced developments in profinite topology, whereas what is presented here essentially uses an algebraic, language-based approach.
Cite as

Nathan Grosshans. A Note on the Join of Varieties of Monoids with LI. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grosshans:LIPIcs.MFCS.2021.51,
  author =	{Grosshans, Nathan},
  title =	{{A Note on the Join of Varieties of Monoids with LI}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.51},
  URN =		{urn:nbn:de:0030-drops-144918},
  doi =		{10.4230/LIPIcs.MFCS.2021.51},
  annote =	{Keywords: Varieties of monoids, join, LI}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.2
The Power of Programs over Monoids in DA

Authors: Nathan Grosshans, Pierre McKenzie, and Luc Segoufin

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class NC^1. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame and we exhibit a regular language, recognized by a program over a monoid from J, yet not recognizable classically by morphisms from the class QJ. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.
Cite as

Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{grosshans_et_al:LIPIcs.MFCS.2017.2,
  author =	{Grosshans, Nathan and McKenzie, Pierre and Segoufin, Luc},
  title =	{{The Power of Programs over Monoids in DA}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.2},
  URN =		{urn:nbn:de:0030-drops-80909},
  doi =		{10.4230/LIPIcs.MFCS.2017.2},
  annote =	{Keywords: Programs over monoids, DA, lower-bounds}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 1 2021
  • 1 2017

  • Refine by Author
  • 3 Grosshans, Nathan
  • 2 Claudet, Nathan
  • 2 Perdrix, Simon
  • 1 Göller, Stefan
  • 1 McKenzie, Pierre
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Quantum information theory
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algebraic language theory
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Formal languages and automata theory
  • Show More...

  • Refine by Keyword
  • 2 Entanglement
  • 2 Graph theory
  • 2 Local complementation
  • 2 Quantum computing
  • 1 AC0
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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