8 Search Results for "Mhalla, Mehdi"

Document
DOI: 10.4230/LIPIcs.ESA.2025.51
Quantum Approximate k-Minimum Finding

Authors: Minbo Gao, Zhengfeng Ji, and Qisheng Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum k-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum k-minimum finding algorithm that works with approximate values for all k ≥ 1, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for k = 1. As practical applications, we present efficient quantum algorithms for identifying the k smallest expectation values among multiple observables and for determining the k lowest ground state energies of a Hamiltonian with a known eigenbasis.
Cite as

Minbo Gao, Zhengfeng Ji, and Qisheng Wang. Quantum Approximate k-Minimum Finding. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2025.51,
  author =	{Gao, Minbo and Ji, Zhengfeng and Wang, Qisheng},
  title =	{{Quantum Approximate k-Minimum Finding}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.51},
  URN =		{urn:nbn:de:0030-drops-245192},
  doi =		{10.4230/LIPIcs.ESA.2025.51},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Quantum Minimum Finding}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.13
Quantum Speedup for Sampling Random Spanning Trees

Authors: Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu

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

Abstract
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
Cite as

Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu. Quantum Speedup for Sampling Random Spanning Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ICALP.2025.13,
  author =	{Apers, Simon and Gao, Minbo and Ji, Zhengfeng and Liu, Chenghua},
  title =	{{Quantum Speedup for Sampling Random Spanning Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{13:1--13:21},
  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.13},
  URN =		{urn:nbn:de:0030-drops-233907},
  doi =		{10.4230/LIPIcs.ICALP.2025.13},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Random Spanning Trees}
}
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.2025.54
Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer

Authors: Stacey Jeffery and Galina Pass

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

Abstract
We introduce an object called a subspace graph that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a switching network with arbitrary quantum subroutines, to compute a composed function. As another application, we give a time-efficient implementation of quantum Divide & Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch’s algorithm for directed st-connectivity.
Cite as

Stacey Jeffery and Galina Pass. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.STACS.2025.54,
  author =	{Jeffery, Stacey and Pass, Galina},
  title =	{{Multidimensional Quantum Walks, Recursion, and Quantum Divide \& Conquer}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{54:1--54:16},
  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.54},
  URN =		{urn:nbn:de:0030-drops-228791},
  doi =		{10.4230/LIPIcs.STACS.2025.54},
  annote =	{Keywords: Quantum Divide \& Conquer, Time-Efficient, Subspace Graphs, Quantum Walks, Switching Networks, Directed st-Connectivity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.36
Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems

Authors: Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, and Stéphan Thomassé

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the notion of k-stabilizer universal quantum state, that is, an n-qubit quantum state, such that it is possible to induce any stabilizer state on any k qubits, by using only local operations and classical communications. These states generalize the notion of k-pairable states introduced by Bravyi et al., and can be studied from a combinatorial perspective using graph states and k-vertex-minor universal graphs. First, we demonstrate the existence of k-stabilizer universal graph states that are optimal in size with n = Θ(k²) qubits. We also provide parameters for which a random graph state on Θ(k²) qubits is k-stabilizer universal with high probability. Our second contribution consists of two explicit constructions of k-stabilizer universal graph states on n = O(k⁴) qubits. Both rely upon the incidence graph of the projective plane over a finite field 𝔽_q. This provides a major improvement over the previously known explicit construction of k-pairable graph states with n = O(2^{3k}), bringing forth a new and potentially powerful family of multipartite quantum resources.
Cite as

Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, and Stéphan Thomassé. Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cautres_et_al:LIPIcs.ICALP.2024.36,
  author =	{Cautr\`{e}s, Maxime and Claudet, Nathan and Mhalla, Mehdi and Perdrix, Simon and Savin, Valentin and Thomass\'{e}, St\'{e}phan},
  title =	{{Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.36},
  URN =		{urn:nbn:de:0030-drops-201796},
  doi =		{10.4230/LIPIcs.ICALP.2024.36},
  annote =	{Keywords: Quantum networks, graph states, vertex-minors, k-pairability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.22
Coherent Control and Distinguishability of Quantum Channels via PBS-Diagrams

Authors: Cyril Branciard, Alexandre Clément, Mehdi Mhalla, and Simon Perdrix

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

Abstract
Even though coherent control of quantum operations appears to be achievable in practice, it is still not yet well understood. Among theoretical challenges, standard completely positive trace preserving (CPTP) maps are known not to be appropriate to represent coherently controlled quantum channels. We introduce here a graphical language for coherent control of general quantum channels inspired by practical quantum optical setups involving polarising beam splitters (PBS). We consider different situations of coherent control and disambiguate CPTP maps by considering purified channels, an extension of Stinespring’s dilation. First, we show that in classical control settings, the observational equivalence classes of purified channels correspond to the standard definition of quantum channels (CPTP maps). Then, we propose a refinement of this equivalence class generalising the "half quantum switch" situation, where one is allowed to coherently control which quantum channel is applied; in this case, quantum channel implementations can be distinguished using a so-called transformation matrix. A further refinement characterising observational equivalence with general extended PBS-diagrams as contexts is also obtained. Finally, we propose a refinement that could be used for more general coherent control settings.
Cite as

Cyril Branciard, Alexandre Clément, Mehdi Mhalla, and Simon Perdrix. Coherent Control and Distinguishability of Quantum Channels via PBS-Diagrams. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{branciard_et_al:LIPIcs.MFCS.2021.22,
  author =	{Branciard, Cyril and Cl\'{e}ment, Alexandre and Mhalla, Mehdi and Perdrix, Simon},
  title =	{{Coherent Control and Distinguishability of Quantum Channels via PBS-Diagrams}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{22:1--22:20},
  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.22},
  URN =		{urn:nbn:de:0030-drops-144629},
  doi =		{10.4230/LIPIcs.MFCS.2021.22},
  annote =	{Keywords: Quantum Computing, Diagrammatic Language, Quantum Control, Polarising Beam Splitter, Categorical Quantum Mechanics, Quantum Switch}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.24
PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations

Authors: Alexandre Clément and Simon Perdrix

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We introduce the PBS-calculus to represent and reason on quantum computations involving coherent control of quantum operations. Coherent control, and in particular indefinite causal order, is known to enable multiple computational and communication advantages over classically ordered models like quantum circuits. The PBS-calculus is inspired by quantum optics, in particular the polarising beam splitter (PBS for short). We formalise the syntax and the semantics of the PBS-diagrams, and we equip the language with an equational theory, which is proved to be sound and complete: two diagrams are representing the same quantum evolution if and only if one can be transformed into the other using the rules of the PBS-calculus. Moreover, we show that the equational theory is minimal. Finally, we consider applications like the implementation of controlled permutations and the unrolling of loops.
Cite as

Alexandre Clément and Simon Perdrix. PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{clement_et_al:LIPIcs.MFCS.2020.24,
  author =	{Cl\'{e}ment, Alexandre and Perdrix, Simon},
  title =	{{PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.24},
  URN =		{urn:nbn:de:0030-drops-126921},
  doi =		{10.4230/LIPIcs.MFCS.2020.24},
  annote =	{Keywords: Quantum Computing, Diagrammatic Language, Completeness, Quantum Control, Polarising Beam Splitter, Categorical Quantum Mechanics, Quantum Switch}
}
  • Refine by Type
  • 8 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2024
  • 1 2021
  • 1 2020

  • Refine by Author
  • 5 Perdrix, Simon
  • 3 Claudet, Nathan
  • 2 Clément, Alexandre
  • 2 Gao, Minbo
  • 2 Ji, Zhengfeng
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Quantum computation theory
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Quantum information theory
  • 2 Hardware → Quantum communication and cryptography
  • 2 Hardware → Quantum computation
  • Show More...

  • Refine by Keyword
  • 4 Quantum Computing
  • 2 Categorical Quantum Mechanics
  • 2 Diagrammatic Language
  • 2 Entanglement
  • 2 Graph theory
  • 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