Pith. sign in

REVIEW 4 minor 81 references

A new edit distance for graph states yields XP algorithms and hardness for disentangling clusters with few ancilla qubits.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 02:47 UTC pith:663HS3A3

load-bearing objection Solid XP/W[1] results for a natural rank-based integrity parameter, with a clean quantum-network motivation and an explicit O(n^6) algorithm for k=1.

arxiv 2607.09469 v1 pith:663HS3A3 submitted 2026-07-10 cs.DS cs.DMquant-ph

A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity

Romain Bourneuf , Nathan Claudet , Sang Yoon Kim , Rose McCarty , Blair D. Sullivan , St\'ephan Thomass\'e This is my paper
classification cs.DS cs.DMquant-ph
keywords graph statesintegrityvertex-minorsrank integrityancilla integrityparameterized complexityflipsquantum networks
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a distance between two graph states that counts the fewest ancilla qubits needed so both can be prepared from one shared resource using only one-qubit Clifford gates, Pauli measurements and classical communication. Graphically this is the least number of extra vertices that make both graphs vertex-minors of a common supergraph. The same distance produces quantum-network analogues of classical graph-edit problems. In particular, the k-ancilla integrity of a graph state is the smallest maximum component size obtainable after a distance-k change; up to a factor of two this equals the rank integrity obtained by adding a rank-at-most-k symmetric matrix over GF(2). The authors prove rank integrity is XP in the rank parameter and W[1]-hard, and give an explicit O(n^6) algorithm for the special case of one ancilla. The practical payoff is a classical way to locate the highly entangled clusters inside a distributed quantum network once a few ancilla qubits are allowed.

Core claim

Rank integrity is XP parameterized by k and W[1]-hard parameterized by k; moreover, for every graph G and integer k one has (2k)-rank-integrity(G) ≤ k-ancilla-integrity(|G⟩) ≤ k-rank-integrity(G), and the 1-ancilla-integrity of an n-vertex graph can be computed in O(n^6) time.

What carries the argument

The rank-k perturbation of a graph: adding a symmetric GF(2) matrix of rank at most k to the adjacency matrix (equivalently, a bounded number of flips). This operation is shown to coincide, up to a factor of two, with the ancilla distance defined via vertex-minors, and becomes the search space for the integrity problems.

Load-bearing premise

The claimed factor-of-two link between rank integrity and ancilla integrity rests on two external conversion lemmas between local-complementation sequences and low-rank flips; if those lemmas fail for some graphs the equivalence collapses.

What would settle it

Either exhibit a family of graphs for which the rank-to-ancilla conversion requires more than a factor-of-two change in the parameter, or produce an FPT algorithm (or W[1]-hardness proof that fails) for rank integrity.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper defines a distance between graph states via the minimum number of ancilla qubits from which both can be prepared by one-qubit Clifford gates, Pauli measurements and classical communication, and shows this coincides with a vertex-minor distance. It then studies the resulting integrity parameters: k-ancilla-integrity (minimum, over distance-≤k states, of maximum component size) and the closely related k-rank-integrity (using rank of the GF(2) sum of adjacency matrices). The main results are that rank-integrity is XP parameterized by k (Theorem 1.3), W[1]-hard parameterized by k (Theorem 1.4), that the two integrity notions sandwich each other up to a factor of two in the parameter (Lemma 1.2), and that 1-ancilla-integrity can be computed in O(n^6) time (Theorem 1.5).

Significance. The work cleanly transfers classical edit-distance / integrity ideas into the quantum-network setting of graph states and vertex-minors, yielding both an XP algorithm and matching W[1]-hardness for the natural rank-based formulation. The XP algorithm (Section 4) is self-contained and technically substantial: it introduces typical systems of representatives, strong/weak conflict resolution via crossing solvers, and reduces the multi-component case to weighted list balancing. The hardness reduction (Section 5) is a careful dense analogue of the known order-integrity reduction, using Sylvester-Hadamard graphs to obtain robust connectivity under low-rank perturbations. The explicit O(n^6) algorithm for the k=1 case (Section 6) further demonstrates that the framework is algorithmically usable. Even if the external Campbell et al. conversion lemmas underlying the factor-of-two sandwich are imperfect, the XP/W[1]/O(n^6) statements stand independently inside the rank model.

minor comments (4)
  1. [Lemma 1.2 / Section 3] The factor-of-two sandwich (Lemma 1.2) is stated as an interpretive bridge and relies on two external lemmas from Campbell et al. (2026). A short self-contained sketch or an explicit pointer to the precise statements would make the manuscript more self-contained for readers who only care about the quantum interpretation.
  2. [Section 4.3 / Algorithm 1] In the XP algorithm roadmap (Algorithm 1) and the surrounding claims, the distinction between the guessed typical system and the optimal G* is sometimes only implicit; a one-sentence reminder that correctness is argued only on the branch that guesses the optimal objects would improve readability.
  3. [Section 6 / Lemma 6.4] The O(n^6) bound for 1-ancilla-integrity arises from an n-factor (local complementations) times an O(n^5) triangle enumeration; a brief remark that the triangle step can be replaced by any O(m^{3/2})-time triangle listing algorithm would clarify the dependence on sparsity.
  4. A few minor typographical issues appear (e.g., “conficts” for “conflicts” in a claim heading, occasional missing spaces around math). A light copy-edit pass would remove them.

Circularity Check

1 steps flagged

No significant circularity; only a non-load-bearing self-citation bridges rank-integrity to ancilla-integrity while the XP/W[1]/O(n^6) theorems are proved self-containedly.

specific steps
  1. self citation load bearing [Lemma 1.2 proof (Section 3.1)]
    "First let G' be a rank-k perturbation of G. Then by [16, Lemma 7.1], G' is also a k-perturbation of G. ... Now let G' be a k-perturbation of G. By [16, Lemma 7.2], G' is locally equivalent to a graph which is a rank-2t perturbation of G."

    The factor-of-two equivalence between k-ancilla-integrity and rank-integrity is justified solely by two lemmas from a paper co-authored by one of the present authors (McCarty). While this is a genuine self-citation, it is purely interpretive and is not used in the proofs of the XP algorithm, W[1]-hardness, or the O(n^6) algorithm; those stand independently inside the rank/flip model.

full rationale

The paper's strongest claims (XP algorithm for rank integrity via typical systems of representatives, strong/weak conflict resolution and weighted list balancing in Section 4; W[1]-hardness via Sylvester-Hadamard robust graphs and incidence-matrix rank in Section 5; O(n^6) for 1-ancilla via Bouchet/Fon-Der-Flaass reduction to flip-integrity plus split decomposition in Section 6) are derived from first principles inside the rank/flip model with no fitted parameters, no uniqueness theorems, and no ansatz. Observation 1.1 and the dictionary to vertex-minors rest on external citations (Dahlberg-Wehner, Van den Nest et al.). The sole self-citation appears in the proof of the interpretive sandwich Lemma 1.2 (citing Campbell et al. 2026 Lemmas 7.1-7.2, co-authored by McCarty); those lemmas convert local-complementation sequences to low-rank flips but are never invoked by Theorems 1.3-1.5. Even if the conversion failed, the algorithmic and hardness statements remain intact. No step reduces a claimed prediction or derivation to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The paper is pure theory. It inherits the standard dictionary between graph states and local complementation / vertex-minors, the definition of cut-rank over GF(2), and the existence of linear-time split decompositions. No numerical parameters are fitted; the only new objects are the integrity parameters themselves, which are definitional.

axioms (4)
  • domain assumption A graph H is a vertex-minor of G if and only if the corresponding graph state |G⟩ can be transformed into |H⟩ by one-qubit Clifford gates, one-qubit Pauli measurements and classical communication (Observation 1.1).
    Taken as given from Dahlberg-Wehner and Van den Nest et al.; used to equate the quantum distance with the combinatorial distance.
  • standard math Local complementation and vertex deletion generate all vertex-minors; the three-case lemma of Bouchet / Fon-Der-Flaass characterises the effect of deleting a single extra vertex (Lemma 2.1).
    Classical structural-graph-theory fact used to reduce 1-ancilla integrity to flip integrity.
  • standard math The split decomposition of an n-vertex graph can be computed in linear time and displays all strong splits (Theorems 6.7 and 6.6).
    Used as a black-box subroutine for the most-balanced-split algorithm that solves the two-component case of flip integrity.
  • standard math A binary matrix of rank at most k has at most 2^k distinct columns; the type partition of a rank-k looped graph therefore has size ≤ 2^k (Observation 4.2).
    Elementary linear algebra over GF(2) that bounds the number of guesses in the XP algorithm.
invented entities (2)
  • k-rank-integrity / k-ancilla-integrity no independent evidence
    purpose: Quantify the smallest achievable maximum component size after a rank-k (respectively distance-k) edit of a graph / graph state.
    Definitional parameters introduced to formalise the clustering question; no independent physical prediction is claimed beyond the combinatorial optimisation problems themselves.
  • typical system of representatives and crossing solvers no independent evidence
    purpose: Bounded-size objects that allow the XP algorithm to reconstruct an optimal rank-k perturbation without enumerating all components.
    Technical devices invented for the proof of Theorem 1.3; they have no existence claim outside the algorithm.

pith-pipeline@v1.1.0-grok45 · 46592 in / 2761 out tokens · 31239 ms · 2026-07-13T02:47:19.442981+00:00 · methodology

0 comments
read the original abstract

We introduce a new notion of distance between two graph states $|G\rangle$ and $|G'\rangle$ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state $|\widehat{G}\rangle$ from which both $|G\rangle$ and $|G'\rangle$ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems. Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state $|G\rangle$. The ancilla integrity problem asks, given a graph $G$ and integer $k$, for the minimum -- over all graph states $|G'\rangle$ with distance at most $k$ from $|G\rangle$ -- of the maximum component size of $G'$. Up to a factor of $2$ in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between $G$ and $G'$ is instead the minimum rank of the sum of their adjacency matrices over $\text{GF}(2)$. We prove that rank integrity is XP parameterized by $k$. We also prove the complementary hardness result that rank integrity is W[1]-hard in $k$. Finally, we give an explicit $\mathcal{O}(n^6)$-time algorithm for ancilla integrity when $G$ has $n$ vertices and $k=1$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

81 extracted references · 26 canonical work pages

  1. [1]

    Knuth , title =

    Donald E. Knuth , title =. Commun. 1974 , doi =

    1974

  2. [2]

    Dijkstra , title =

    Edsger W. Dijkstra , title =. Commun. 1968 , doi =

    1968

  3. [3]

    1993 , isbn =

    Jim Gray and Andreas Reuter , title =. 1993 , isbn =

    1993

  4. [4]

    1975 , crossref =

    On Time versus Space and Related Problems , booktitle =. 1975 , crossref =. doi:10.1109/SFCS.1975.23 , timestamp =

    doi:10.1109/sfcs.1975.23 1975

  5. [5]

    1975 , timestamp =

    16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975 , publisher =. 1975 , timestamp =

    1975

  6. [6]

    Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=

    Transforming graph states using single-qubit operations , author=. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=. 2018 , publisher=

    2018

  7. [7]

    Briegel , doi =

    Marc Hein and Jens Eisert and Hans J. Briegel , doi =. Multiparty entanglement in graph states , volume =. quant-ph/0307130 , journal =

    Pith/arXiv arXiv

  8. [8]

    Entanglement in Graph States and its Applications , volume =

    Hein, Marc and D. Entanglement in Graph States and its Applications , volume =. Quantum computers, algorithms and chaos , month =. 2006 , bdsk-url-1 =. doi:10.3254/978-1-61499-018-5-115 , eprint =

    work page doi:10.3254/978-1-61499-018-5-115 2006

  9. [9]

    2020 , issn =

    The average cut-rank of graphs , journal =. 2020 , issn =. doi:https://doi.org/10.1016/j.ejc.2020.103183 , url =

    doi:10.1016/j.ejc.2020.103183 2020

  10. [10]

    Quantum , volume =

    The Foliage Partition: An Easy-to-Compute. Quantum , volume =. 2025 , issn =. doi:https://doi.org/10.22331/q-2025-04-24-1720 , url =

    work page doi:10.22331/q-2025-04-24-1720 2025

  11. [11]

    1997 , publisher=

    Stabilizer codes and quantum error correction , author=. 1997 , publisher=

    1997

  12. [12]

    Graphical description of the action of local

    Maarten Van den Nest and Jeroen Dehaene and Bart De Moor , doi =. Graphical description of the action of local. 2004 , bdsk-url-1 =. quant-ph/0308151 , journal =

    Pith/arXiv arXiv 2004

  13. [13]

    2014 , isbn =

    Leskovec, Jure and Rajaraman, Anand and Ullman, Jeffrey David , title =. 2014 , isbn =

    2014

  14. [14]

    2024 , publisher=

    Graph-theoretic techniques for optimizing NISQ algorithms , author=. 2024 , publisher=

    2024

  15. [15]

    arXiv preprint arXiv:2504.00291 , year=

    Preparing graph states forbidding a vertex-minor , author=. arXiv preprint arXiv:2504.00291 , year=

    Pith/arXiv arXiv

  16. [16]

    arXiv preprint arXiv:2605.31260 , year=

    On first-order definable operations on relational structures , author=. arXiv preprint arXiv:2605.31260 , year=

    Pith/arXiv arXiv

  17. [17]

    Quantum , volume=

    Generating k EPR-pairs from an n -party resource state , author=. Quantum , volume=. 2024 , publisher=

    2024

  18. [18]

    On the Computational Complexity of Vertex Integrity and Component Order Connectivity , journal=

    Drange, P. On the Computational Complexity of Vertex Integrity and Component Order Connectivity , journal=. 2016 , month=. doi:10.1007/s00453-016-0127-x , url=

    doi:10.1007/s00453-016-0127-x 2016

  19. [19]

    Low rank

    Mikołaj Bojańczyk and Michał Pilipczuk and Wojciech Przybyszewski and Marek Sokołowski and Giannos Stamoulis , year=. Low rank. 2502.08476 , archivePrefix=

    Pith/arXiv arXiv

  20. [20]

    , title =

    Lenstra, Jan Karel and Shmoys, David B. , title =

  21. [21]

    Orthogonal representations over finite fields and the chromatic number of graphs , journal=

    Peeters, Ren. Orthogonal representations over finite fields and the chromatic number of graphs , journal=. 1996 , month=. doi:10.1007/BF01261326 , url=

    work page doi:10.1007/bf01261326 1996

  22. [22]

    Campbell, Rutger and Gollin, J Pascal and Hatzel, Meike and Kwon, O-joung and McCarty, Rose and Oum, Sang-il and Wiederrecht, Sebastian , booktitle=. The. 2026 , organization=

    2026

  23. [23]

    2021 , url=

    Local structure for vertex-minors , author=. 2021 , url=

    2021

  24. [24]

    Matrix Factorization over GF(2) and Trace-Orthogonal Bases of GF(2\^

    Lempel, Abraham , journal=. Matrix Factorization over GF(2) and Trace-Orthogonal Bases of GF(2\^. 1975 , publisher=

    1975

  25. [25]

    Pattern Analysis and Applications , volume=

    A survey of graph edit distance , author=. Pattern Analysis and Applications , volume=. 2010 , doi=

    2010

  26. [26]

    Fomin and Petr Golovach , keywords =

    Christophe Crespelle and Pål Grønås Drange and Fedor V. Fomin and Petr Golovach , keywords =. A survey of parameterized algorithms and the complexity of edge modification , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.cosrev.2023.100556 , url =

    doi:10.1016/j.cosrev.2023.100556 2023

  27. [27]

    Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =

    Dahlberg, Axel and Wehner, Stephanie , title =. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =. 2018 , doi =

    2018

  28. [28]

    Bouchet, André , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1994 , NUMBER =. doi:10.1006/jctb.1994.1008 , URL =

    doi:10.1006/jctb.1994.1008 1994

  29. [29]

    2023 , issn =

    The Grid Theorem for vertex-minors , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.jctb.2020.08.004 , url =

    doi:10.1016/j.jctb.2020.08.004 2023

  30. [30]

    Bouchet, André , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1988 , NUMBER =. doi:10.1016/0095-8956(88)90055-X , URL =

    work page doi:10.1016/0095-8956(88)90055-x 1988

  31. [31]

    Robertson, Neil and Seymour, P. D. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2004 , NUMBER =. doi:10.1016/j.jctb.2004.08.001 , URL =

    doi:10.1016/j.jctb.2004.08.001 2004

  32. [32]

    Surveys in combinatorics 2019 , SERIES =

    Moffatt, Iain , TITLE =. Surveys in combinatorics 2019 , SERIES =. 2019 , ISBN =

    2019

  33. [33]

    Bondy, J. A. and Murty, U. S. R. , title =. 2008 , doi =

    2008

  34. [34]

    Sang-il Oum , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2005 , NUMBER =. doi:10.1016/j.jctb.2005.03.003 , URL =

    doi:10.1016/j.jctb.2005.03.003 2005

  35. [35]

    Combinatorial

    Bouchet, André , TITLE =. Combinatorial. 1989 , DOI =

    1989

  36. [36]

    Multipartite Entanglement in Quantum Networks Using Subgraph Complementations , year=

    Sen, Aniruddha and Goodenough, Kenneth and Towsley, Don , booktitle=. Multipartite Entanglement in Quantum Networks Using Subgraph Complementations , year=

  37. [37]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , title =

    Szymon Toru. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , title =. 2023 , volume =. doi:10.1109/FOCS57990.2023.00045 , url =

    doi:10.1109/focs57990.2023.00045 2023

  38. [38]

    50th International Colloquium on Automata, Languages, and Programming (ICALP) , pages =

    Gajarsk. 50th International Colloquium on Automata, Languages, and Programming (ICALP) , pages =. 2023 , volume =

    2023

  39. [39]

    Merge-Width and First-Order Model Checking , year =

    Dreier, Jan and Toru. Merge-Width and First-Order Model Checking , year =. doi:10.1145/3717823.3718259 , booktitle =

    doi:10.1145/3717823.3718259

  40. [40]

    and Golovach, Petr A

    Fomin, Fedor V. and Golovach, Petr A. and Str mme, Torstein J. F. and Thilikos, Dimitrios M. , TITLE =. Algorithmica , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s00453-020-00677-8 , URL =

    work page doi:10.1007/s00453-020-00677-8 2020

  41. [41]

    Antony, Dhanyamol and Garchar, Jay and Pal, Sagartanu and Sandeep, R. B. and Sen, Sagnik and Subashini, R. , TITLE =. Algorithmica , FJOURNAL =. 2022 , NUMBER =. doi:10.1007/s00453-022-00991-3 , URL =

    work page doi:10.1007/s00453-022-00991-3 2022

  42. [42]

    Antony, Dhanyamol and Pal, Sagartanu and Sandeep, R. B. , TITLE =. Inform. Process. Lett. , FJOURNAL =. 2025 , PAGES =. doi:10.1016/j.ipl.2024.106530 , URL =

    work page doi:10.1016/j.ipl.2024.106530 2025

  43. [43]

    Antony, Dhanyamol and Pal, Sagartanu and Sandeep, R. B. and Subashini, R. , TITLE =. J. Graph Theory , FJOURNAL =. 2024 , NUMBER =. doi:10.1002/jgt.23112 , URL =

    work page doi:10.1002/jgt.23112 2024

  44. [44]

    Principles of verification: cycling the probabilistic landscape---essays dedicated to

    Grohe, Martin , TITLE =. Principles of verification: cycling the probabilistic landscape---essays dedicated to. 2025 , ISBN =. doi:10.1007/978-3-031-75783-9\_15 , URL =

    work page doi:10.1007/978-3-031-75783-9 2025

  45. [45]

    Persistent Entanglement in Arrays of Interacting Particles , author =. Phys. Rev. Lett. , volume =. 2001 , month =. doi:10.1103/PhysRevLett.86.910 , url =

    doi:10.1103/physrevlett.86.910 2001

  46. [46]

    Electron

    Buchanan, Calum and Purcell, Christopher and Rombach, Puck , TITLE =. Electron. J. Combin. , FJOURNAL =. 2022 , NUMBER =. doi:10.37236/10383 , URL =

    work page doi:10.37236/10383 2022

  47. [47]

    Lempel, Abraham , TITLE =. SIAM J. Comput. , FJOURNAL =. 1975 , PAGES =. doi:10.1137/0204014 , URL =

    work page doi:10.1137/0204014 1975

  48. [48]

    Classical simulation versus universality in measurement-based quantum computation , author =. Phys. Rev. A , volume =. 2007 , month =. doi:10.1103/PhysRevA.75.012337 , url =

    work page doi:10.1103/physreva.75.012337 2007

  49. [49]

    and Golovach, Petr A

    Fomin, Fedor V. and Golovach, Petr A. and Panolan, Fahad , TITLE =. Data Min. Knowl. Discov. , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s10618-019-00669-5 , URL =

    work page doi:10.1007/s10618-019-00669-5 2020

  50. [50]

    Meesum, S. M. and Misra, Pranabendu and Saurabh, Saket , TITLE =. Theoret. Comput. Sci. , FJOURNAL =. 2016 , PAGES =. doi:10.1016/j.tcs.2016.02.020 , URL =

    work page doi:10.1016/j.tcs.2016.02.020 2016

  51. [51]

    arXiv preprint arXiv2601.06332 , year=

    Bipartitioning of Graph States for Distributed Measurement-Based Quantum Computing , author=. arXiv preprint arXiv2601.06332 , year=

    arXiv

  52. [52]

    and Barnes, Edwin , TITLE =

    Li, Bikun and Economou, Sophia E. and Barnes, Edwin , TITLE =. npj Quantum Information , VOLUME =. 2022 , DOI =

    2022

  53. [53]

    , TITLE =

    Cunningham, William H. , TITLE =. SIAM J. Algebraic Discrete Methods , FJOURNAL =. 1982 , NUMBER =. doi:10.1137/0603021 , URL =

    work page doi:10.1137/0603021 1982

  54. [54]

    Spinrad, Jeremy , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 1989 , NUMBER =. doi:10.1137/0402051 , URL =

    work page doi:10.1137/0402051 1989

  55. [55]

    Charbit, Pierre and de Montgolfier, Fabien and Raffinot, Mathieu , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2012 , NUMBER =. doi:10.1137/10080052X , URL =

    work page doi:10.1137/10080052x 2012

  56. [56]

    2026 , eprint=

    Connectivity augmentation is fixed-parameter tractable , author=. 2026 , eprint=

    2026

  57. [57]

    Johannes Carmesin and M. S. Ramanujan , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611978971.73 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611978971.73 , year =

    doi:10.1137/1.9781611978971.73 2026

  58. [58]

    2026 , eprint=

    Graph classes through the lens of logic , author=. 2026 , eprint=

    2026

  59. [59]

    Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition , journal =

    Elias Dahlhaus , keywords =. Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition , journal =. 2000 , issn =. doi:https://doi.org/10.1006/jagm.2000.1090 , url =

    doi:10.1006/jagm.2000.1090 2000

  60. [60]

    2026 , eprint=

    Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions , author=. 2026 , eprint=

    2026

  61. [61]

    The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement , year =

    Bouland, Adam and Giurgic. The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement , year =. doi:10.1145/3717823.3718118 , booktitle =

    doi:10.1145/3717823.3718118

  62. [62]

    , booktitle =

    Fon-Der-Flaass, Dmitri G. , booktitle =. On local complementations of graphs , volume =

  63. [63]

    and Browne, David E

    Briegel, Hans J. and Browne, David E. and D. Measurement-based quantum computation , doi=. Nature Physics , number =. 2009 , eprint=

    2009

  64. [64]

    , journal =

    Raussendorf, Robert and Briegel, Hans J. , journal =. A one-way quantum computer , doi=

  65. [65]

    and Briegel, Hans J

    Raussendorf, Robert and Browne, Daniel E. and Briegel, Hans J. , journal =. Measurement-based quantum computation on cluster states , eprint=. doi:10.1103/PhysRevA.68.022312 , volume =

    doi:10.1103/physreva.68.022312

  66. [66]

    Limitations of nearest-neighbor quantum networks , author =. Phys. Rev. A , volume =. 2022 , month =. doi:10.1103/PhysRevA.106.L010401 , url =

    work page doi:10.1103/physreva.106.l010401 2022

  67. [67]

    http://dx.doi.org/10.17169/refubium-41101

    Quantum Networks , author=. 2022 , url = "http://dx.doi.org/10.17169/refubium-41101", school =

    work page doi:10.17169/refubium-41101 2022

  68. [68]

    Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems , booktitle =

    Cautr\`. Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems , booktitle =. doi:10.4230/LIPIcs.ICALP.2024.36 , year =

    work page doi:10.4230/lipics.icalp.2024.36 2024

  69. [69]

    , date-added =

    Markham, Damian and Sanders, Barry C. , date-added =. Graph states for quantum secret sharing , doi=. Physical Review A , number =. 2008 , eprint=

    2008

  70. [70]

    Physical Review A , volume =

    Quantum secret sharing with qudit graph states , author =. Physical Review A , volume =. 2010 , month =. doi:10.1103/PhysRevA.82.062315 , eprint=

    work page doi:10.1103/physreva.82.062315 2010

  71. [71]

    New Protocols and Lower Bounds for Quantum Secret Sharing with Graph States

    Javelle, J \'e r \^o me and Mhalla, Mehdi and Perdrix, Simon. New Protocols and Lower Bounds for Quantum Secret Sharing with Graph States. Proceedings of the 7th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2012). 2013. 1109.1487 , doi=

    Pith/arXiv arXiv 2012

  72. [72]

    Quantum secret sharing with graph states , doi=

    Gravier, Sylvain and Javelle, J. Quantum secret sharing with graph states , doi=. Proceedings of the 8th. 2013 , url=

    2013

  73. [73]

    Bell, B. A. and Markham, Damian and Herrera-Mart. Experimental demonstration of graph-state quantum secret sharing , journal=. 2014 , month=. doi:10.1038/ncomms6480 , url=

    work page doi:10.1038/ncomms6480 2014

  74. [74]

    Quantum network routing and local complementation , volume =

    Hahn, Frederik and Pappa, Anna and Eisert, Jens , date-added =. Quantum network routing and local complementation , volume =. npj Quantum Information , number =. 2019 , bdsk-url-1 =. doi:10.1038/s41534-019-0191-6 , eprint =

    work page doi:10.1038/s41534-019-0191-6 2019

  75. [75]

    Distributing graph states over arbitrary quantum networks , volume =

    Meignant, Cl\'ement and Markham, Damian and Grosshans, Fr\'ed\'eric , doi =. Distributing graph states over arbitrary quantum networks , volume =. Physical Review A , month =. 2019 , bdsk-url-1 =. 1811.05445 , issue =

    Pith/arXiv arXiv 2019

  76. [76]

    Distributing graph states across quantum networks , year =

    Fischer, Alex and Towsley, Don , booktitle =. Distributing graph states across quantum networks , year =. doi:10.1109/QCE52317.2021.00049 , eprint =

    doi:10.1109/qce52317.2021.00049 2021

  77. [77]

    Physical Review A , volume =

    Multiparty entanglement routing in quantum networks , author =. Physical Review A , volume =. 2023 , month =. doi:10.1103/PhysRevA.108.062614 , eprint=

    work page doi:10.1103/physreva.108.062614 2023

  78. [78]

    New Journal of Physics , volume=

    Graph state extraction from two-dimensional cluster states , author=. New Journal of Physics , volume=. 2025 , publisher=

    2025

  79. [79]

    Universal Resources for Measurement-Based Quantum Computation , author =. Phys. Rev. Lett. , volume =. 2006 , month =. doi:10.1103/PhysRevLett.97.150504 , url =

    work page doi:10.1103/physrevlett.97.150504 2006

  80. [80]

    On the Minimum Degree Up to Local Complementation: Bounds and Complexity , year =

    J. On the Minimum Degree Up to Local Complementation: Bounds and Complexity , year =. Proceedings of the 38th workshop on Graph Theory (WG 2012) , doi =

    2012

Showing first 80 references.