2 Search Results for "Storjohann, Arne"

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/DagSemProc.06271.12
Notes on computing minimal approximant bases

Authors: Arne Storjohann

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

Abstract
We show how to transform the problem of computing solutions to a classical Hermite Pade approximation problem for an input vector of dimension $m imes 1$, arbitrary degree constraints $(n_1,n_2,ldots,n_m)$, and order $N := (n_1 + 1) + cdots + (n_m + 1) - 1$, to that of computing a minimal approximant basis for a matrix of dimension $O(m) imes O(m)$, uniform degree constraint $Theta(N/m)$, and order $Theta(N/m)$.
Cite as

Arne Storjohann. Notes on computing minimal approximant bases. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{storjohann:DagSemProc.06271.12,
  author =	{Storjohann, Arne},
  title =	{{Notes on computing minimal approximant bases}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  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.12},
  URN =		{urn:nbn:de:0030-drops-7763},
  doi =		{10.4230/DagSemProc.06271.12},
  annote =	{Keywords: Hermite Pade approximation, minimal approximant bases}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2006

  • Refine by Author
  • 1 Claudet, Nathan
  • 1 Perdrix, Simon
  • 1 Storjohann, Arne

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 1 Entanglement
  • 1 Graph theory
  • 1 Hermite Pade approximation
  • 1 Local complementation
  • 1 Quantum computing
  • 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