pith. sign in

arxiv: 2606.23809 · v1 · pith:6AMWRIJKnew · submitted 2026-06-22 · 🪐 quant-ph

Efficient Graph State Purification with Factorized Graph-Preserving Operations across Local Clifford Orbits

Mingyuan Wang , Guus Avis , Kenneth Goodenough , Stefan Krastanov This is my paper

Pith reviewed 2026-06-26 07:53 UTC · model grok-4.3

classification 🪐 quant-ph
keywords graph statesentanglement distillationClifford operationslocal complementationquantum purificationmultipartite entanglementstabilizer states
0
0 comments X

The pith

Factorized graph-preserving Clifford operations enable optimized purification circuits for graph states that outperform recurrence-based protocols under realistic noise.

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

The paper shows that factorized graph-preserving Clifford operations map products of graph-basis states to other such products and can be described compactly by graph features, allowing their action to be treated as label permutations. These operations are further organized over local-complementation orbits via minimum-edge representatives so that a single circuit works for all locally equivalent graphs after a basis change. The reduced simulation cost after precomputation then lets the authors optimize finite-size distillation circuits for several graph families. Numerical tests under gate and measurement noise indicate that the resulting circuits beat standard recurrence protocols. This matters because the design space for multipartite graph-state purification grows quickly with party number, limiting practical use in networks and measurement-based computation.

Core claim

Factorized graph-preserving Clifford operations, when enumerated over local-complementation orbits using minimum-edge representatives, permit efficient optimization of noisy finite-size multipartite distillation circuits that apply to all locally equivalent graph states and that numerically outperform recurrence-based purification protocols under realistic gate and measurement noise.

What carries the argument

Factorized graph-preserving Clifford operations that map products of graph-basis states to products of graph-basis states and admit a compact description from simple graph-theoretic features, organized over local-complementation orbits with minimum-edge representatives.

If this is right

  • A single optimized circuit applies to every graph state in a given local-complementation orbit after a suitable basis change.
  • Gate simulation complexity drops sharply once the initial cached precomputation is complete.
  • The same framework supplies a graph-based heuristic for locating transversal gates.
  • Purification circuits can be tailored to specific graph topologies and hardware noise models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach might extend to distillation of other stabilizer states whose graph representations are not obvious.
  • Orbit organization could reduce the search space when designing error-correction circuits for graph codes.
  • Applying the method to graphs with more vertices would test whether the performance advantage persists at larger sizes.

Load-bearing premise

The enumerated factorized graph-preserving operations over local-complementation orbits with minimum-edge representatives are expressive enough to reach circuits competitive with or superior to the full space of purification protocols for the tested graph families.

What would settle it

A simulation in which the optimized graph-preserving circuits fail to outperform recurrence protocols for the tested graph families under the paper's noise model would falsify the performance claim.

Figures

Figures reproduced from arXiv: 2606.23809 by Guus Avis, Kenneth Goodenough, Mingyuan Wang, Stefan Krastanov.

Figure 2
Figure 2. Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6 [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7 [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8 [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9 [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10 [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11. Two non-isomorphic [PITH_FULL_IMAGE:figures/full_fig_p019_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: FIG. 12 [PITH_FULL_IMAGE:figures/full_fig_p021_12.png] view at source ↗
read the original abstract

Graph states form a broad class of multipartite entangled states underlying measurement-based quantum computation, quantum networks, and stabilizer codes. However, systematic entanglement distillation for arbitrary graph states remains challenging because the circuit design space grows rapidly with the number of parties. We introduce a group of Clifford operations that we call "factorized graph-preserving". It enables us to efficiently enumerate and optimize graph-state purification circuits at finite size for realistic noisy hardware. These operations map products of graph-basis states to products of graph-basis states, so their action can be represented as permutations of graph-basis labels. Moreover, this useful gate set admits a compact factorized description determined by simple graph-theoretic features. This structure also allows, after some initial cached precomputation, drastically lower computational complexity for simulating a gate. We further organize these operations over local-complementation (LC) orbits using minimum-edge representatives (MERs), which let us design purification circuits that apply to all locally equivalent graph states (up to a basis change). Using this framework, we optimize noisy finite-size multipartite distillation circuits for several graph-state families. Numerical results show that the resulting graph-preserving circuits can outperform standard recurrence-based purification protocols under realistic gate and measurement noise. Our results establish LC-orbit structure and factorized graph-preserving operations as practical tools for scalable, topology-aware and hardware-constrained graph-state distillation protocol design. Our work can also be interpreted as a graph-based heuristic for finding transversal gates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces a class of 'factorized graph-preserving' Clifford operations that map products of graph-basis states to products of graph-basis states, admitting a compact factorized description based on graph-theoretic features. These operations are organized over local-complementation (LC) orbits using minimum-edge representatives (MERs) to design purification circuits applicable to all locally equivalent graph states. The framework enables efficient enumeration and optimization of finite-size multipartite distillation circuits, with numerical results claiming outperformance over standard recurrence-based protocols under realistic gate and measurement noise for several graph-state families. The work positions this as a practical, topology-aware tool for graph-state distillation and a heuristic for transversal gates.

Significance. If the central numerical claims hold after addressing the issues below, the framework supplies a graph-theoretic method for scalable protocol design in a domain where the circuit space grows rapidly with party number. The factorized representation, cached precomputation for simulation, and LC-orbit organization are concrete strengths that could reduce computational cost for hardware-constrained distillation. The approach also supplies an explicit graph-based heuristic for identifying transversal gates in stabilizer codes.

major comments (2)
  1. [Abstract / numerical-results section] Abstract and numerical-results section: the headline claim that the optimized circuits 'can outperform standard recurrence-based purification protocols under realistic gate and measurement noise' is asserted without any description of the concrete noise models (e.g., depolarizing rates, measurement error probabilities), circuit sizes tested, optimization procedure (search algorithm, objective function, convergence criteria), or statistical significance of the reported advantage. This information is load-bearing for the central claim and must be supplied before the outperformance result can be evaluated.
  2. [Framework / operation-set sections] Framework and operation-set sections: the restriction to factorized graph-preserving operations enumerated over LC orbits with MERs is presented as sufficient to discover competitive circuits, yet no argument, density argument, or explicit check is given that this restricted set is expressive enough to reach (or surpass) the performance attainable in the unrestricted Clifford+measurement space for the tested graph families. If key non-factorized or orbit-crossing operations are excluded, any reported advantage risks being an artifact of comparing an optimized heuristic against unoptimized baselines rather than a genuine improvement; this expressiveness question directly affects the validity of the numerical claim.
minor comments (2)
  1. [Introduction] The notation for graph-basis labels and the precise definition of 'factorized' should be introduced with an explicit small example (e.g., 3- or 4-vertex graph) early in the manuscript to improve readability.
  2. Several standard references on multipartite entanglement distillation and LC equivalence of graph states appear to be missing; the authors should verify completeness of the citation list.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's detailed feedback on our manuscript. The comments highlight important points regarding the presentation of numerical results and the justification of our operation set. We provide point-by-point responses below and indicate where revisions will be made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract / numerical-results section] Abstract and numerical-results section: the headline claim that the optimized circuits 'can outperform standard recurrence-based purification protocols under realistic gate and measurement noise' is asserted without any description of the concrete noise models (e.g., depolarizing rates, measurement error probabilities), circuit sizes tested, optimization procedure (search algorithm, objective function, convergence criteria), or statistical significance of the reported advantage. This information is load-bearing for the central claim and must be supplied before the outperformance result can be evaluated.

    Authors: We agree that these details are essential for evaluating the claims. In the revised version, we will expand the numerical results section to include: explicit noise models (depolarizing probability p for gates and measurement error q), circuit sizes for the tested graph families (N=3 to 6), the optimization procedure (exhaustive enumeration over the factorized set with objective of output fidelity after fixed rounds), and statistical significance (Monte Carlo runs with error bars). These additions will be placed in a dedicated subsection. revision: yes

  2. Referee: [Framework / operation-set sections] Framework and operation-set sections: the restriction to factorized graph-preserving operations enumerated over LC orbits with MERs is presented as sufficient to discover competitive circuits, yet no argument, density argument, or explicit check is given that this restricted set is expressive enough to reach (or surpass) the performance attainable in the unrestricted Clifford+measurement space for the tested graph families. If key non-factorized or orbit-crossing operations are excluded, any reported advantage risks being an artifact of comparing an optimized heuristic against unoptimized baselines rather than a genuine improvement; this expressiveness question directly affects the validity of the numerical claim.

    Authors: We acknowledge the concern on expressiveness. Our set is chosen for its factorized structure enabling efficient simulation and LC-orbit coverage for local equivalence. We will add a discussion subsection explaining the motivation (natural graph transformations, transversal gate heuristic) and note that for small N we verified no gain from non-factorized ops. We will clarify the heuristic scope and that comparisons are to standard recurrence protocols, not claiming unrestricted optimality. This addresses the artifact risk by scoping the claims appropriately. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained enumeration and optimization

full rationale

The paper defines factorized graph-preserving operations from graph-theoretic properties, organizes them over LC orbits via minimum-edge representatives, enumerates and optimizes circuits within that set, then numerically simulates performance against independent recurrence baselines under noise models. No quoted step reduces a claimed prediction or uniqueness result to a fitted parameter, self-definition, or load-bearing self-citation chain; the central claims rest on explicit enumeration and external comparison rather than tautological re-labeling of inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests primarily on standard quantum information axioms and graph-state properties; the main addition is a newly defined gate set whose utility is demonstrated numerically.

axioms (1)
  • standard math Clifford operations preserve the stabilizer formalism and graph-state structure under local complementation.
    Invoked throughout the description of graph-preserving operations and LC orbits.
invented entities (1)
  • factorized graph-preserving operations no independent evidence
    purpose: To provide a compact, graph-theoretic representation of Clifford gates that map graph-basis products to graph-basis products.
    Newly introduced group whose factorized description is derived from graph features.

pith-pipeline@v0.9.1-grok · 5795 in / 1274 out tokens · 27427 ms · 2026-06-26T07:53:38.206753+00:00 · methodology

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

56 extracted references · 2 linked inside Pith

  1. [1]

    The labeled LC orbitof a graph G, defined as the set of graphs obtained fromG by sequences of local complementations, with vertex labels fixed

  2. [2]

    base case

    Theunlabeled (or isomorphic) LC orbit, defined as the equivalence class of the labeled LC orbit under graph isomorphism. That is, two graphs are iden- tified if they are isomorphic as unlabeled graphs. Graphs that are identical up to a relabeling of their vertices are said to beisomorphic. Distinguishing such isomorphic graphs can be important during anal...

  3. [3]

    Enrico Fermi

    M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest,andH.J.Briegel,Entanglementingraphstatesand its applications, Proceedings of the International School of Physics “Enrico Fermi”162, 115 (2006)

    2006

  4. [4]

    Dür and H

    W. Dür and H. J. Briegel, Entanglement purification and quantum error correction, Reports on Progress in Physics 70, 1381 (2007)

    2007

  5. [5]

    Raussendorf and H

    R. Raussendorf and H. J. Briegel, A one-way quantum 16 computer, Physical Review Letters86, 5188 (2001)

    2001

  6. [6]

    Raussendorf, D

    R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Physical Review A68, 022312 (2003)

    2003

  7. [7]

    Van den Nest, Measurement-based quantum compu- tation, Nature Physics5, 19 (2009)

    H.J.Briegel, D.E.Browne, W.Dür, R.Raussendorf,and M. Van den Nest, Measurement-based quantum compu- tation, Nature Physics5, 19 (2009)

    2009

  8. [8]

    T. N. Kaldenbach and M. Heller, Mapping quantum circuits to shallow depth measurement patterns based on graph states, Quantum Science and Technology10, 015010 (2024)

    2024

  9. [9]

    M. K. Vijayan, A. Paler, J. Gavriel, C. R. Myers, P. P. Rohde, and S. J. Devitt, Compilation of algorithm- specific graph states for quantum circuits, Quantum Sci- ence and Technology9, 025005 (2024)

    2024

  10. [10]

    T. N. Kaldenbach, I. D. Smith, H. P. Nautrup, M. Heller, and H. J. Briegel, Efficient preparation of resource states for hamiltonian simulation and universal quantum com- putation (2025), arXiv:2509.05404 [quant-ph]

    arXiv 2025

  11. [11]

    T. J. Bell, L. A. Pettersson, and S. Paesani, Optimizing graph codes for measurement-based loss tolerance, PRX Quantum 4, 020328 (2023)

    2023

  12. [12]

    Schlingemann and R

    D. Schlingemann and R. F. Werner, Quantum error- correcting codes associated with graphs, Physical Review A 65, 012308 (2001)

    2001

  13. [13]

    C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, Purification of noisy entanglement and faithful teleportation via noisy chan- nels, Physical Review Letters76, 722 (1996)

    1996

  14. [14]

    Borregaard, H

    J. Borregaard, H. Pichler, T. Schröder, M. D. Lukin, P. Lodahl, and A. S. Sørensen, One-way quantum re- peater based on near-deterministic photon-emitter inter- faces, Physical Review X10, 021071 (2020)

    2020

  15. [15]

    Briegel, W

    H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, Quan- tum repeaters: The role of imperfect local operations in quantum communication, Physical Review Letters81, 5932 (1998)

    1998

  16. [16]

    Aschauer, W

    H. Aschauer, W. Dür, and H.-J. Briegel, Multiparticle entanglement purification for two-colorable graph states, Phys. Rev. A71, 012319 (2005)

    2005

  17. [17]

    Kruszynska, A

    C. Kruszynska, A. Miyake, H. J. Briegel, and W. Dür, Entanglement purification protocols for all graph states, Physical Review A74, 052316 (2006)

    2006

  18. [18]

    M. Wang, G. Avis, and S. Krastanov, GHZ-preserving gates and optimized distillation circuits, arXiv preprint (2025), 2510.25854 [quant-ph]

    arXiv 2025

  19. [19]

    Gottesman,Stabilizer Codes and Quantum Error Cor- rection, Ph.D

    D. Gottesman,Stabilizer Codes and Quantum Error Cor- rection, Ph.D. thesis, Caltech (1997), quant-ph/9705052

    Pith/arXiv arXiv 1997

  20. [20]

    Aaronson and D

    S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A70, 052328 (2004)

    2004

  21. [21]

    Van den Nest, J

    M. Van den Nest, J. Dehaene,and B. De Moor, Graphical description of the action of local Clifford transformations on graph states, Physical Review A69, 022316 (2004)

    2004

  22. [22]

    M.VandenNest, J.Dehaene,andB.DeMoor,Localuni- tary versus local Clifford equivalence of stabilizer states, Physical Review A71, 062323 (2005)

    2005

  23. [23]

    J. C. Adcock, S. Morley-Short, A. Dahlberg, and J. W. Silverstone, Mapping graph state orbits under local com- plementation, Quantum4, 305 (2020)

    2020

  24. [24]

    M. Hein, J. Eisert, and H. J. Briegel, Multiparty entan- glement in graph states, Physical Review A69, 062311 (2004)

    2004

  25. [25]

    Cabello, L

    A. Cabello, L. E. Danielsen, A. J. Lopez-Tarrida, and J. R. Portillo, Optimal preparation of graph states, Phys. Rev. A83, 042314 (2011)

    2011

  26. [26]

    Dahlberg, J

    A. Dahlberg, J. Helsen, and S. Wehner, How to trans- form graph states using single-qubit operations: com- putational complexity and algorithms, Quantum Science and Technology5, 045016 (2020)

    2020

  27. [27]

    Dahlberg, J

    A. Dahlberg, J. Helsen, and S. Wehner, The complex- ity of the vertex-minor problem, Information Processing Letters 175, 106222 (2022)

    2022

  28. [28]

    Dahlberg and S

    A. Dahlberg and S. Wehner, Transforming graph states using single-qubit operations, Philosophical Transactions of the Royal Society A376, 20170325 (2018)

    2018

  29. [29]

    Dahlberg, J

    A. Dahlberg, J. Helsen, and S. Wehner, Counting single- qubit Clifford equivalent graph states is #P-complete, Journal of Mathematical Physics61, 022202 (2020)

    2020

  30. [30]

    Bouchet, An efficient algorithm to recognize locally equivalent graphs, Combinatorica11, 315 (1991)

    A. Bouchet, An efficient algorithm to recognize locally equivalent graphs, Combinatorica11, 315 (1991)

    1991

  31. [31]

    Bouchet, Recognizing locally equivalent graphs, Dis- crete Mathematics114, 75 (1993)

    A. Bouchet, Recognizing locally equivalent graphs, Dis- crete Mathematics114, 75 (1993)

    1993

  32. [32]

    Van den Nest, J

    M. Van den Nest, J. Dehaene, and B. De Moor, Efficient algorithm to recognize the local Clifford equivalence of graph states, Phys. Rev. A70, 034302 (2004)

    2004

  33. [33]

    Bravyi and A

    S. Bravyi and A. W. Cross, Doubled color codes, arXiv preprint (2015), arXiv:1509.03239 [quant-ph]

    Pith/arXiv arXiv 2015

  34. [34]

    Goyal, A

    K. Goyal, A. McCauley, and R. Raussendorf, Purification of large bicolorable graph states, Physical Review A74, 032318 (2006)

    2006

  35. [35]

    Glancy, E

    S. Glancy, E. Knill, and H. M. Vasconcelos, Entangle- ment purification of any stabilizer state, Physical Review A 74, 032319 (2006)

    2006

  36. [36]

    M. R. Geller and Z. Zhou, Efficient error models for fault- tolerant architectures and the Pauli twirling approxima- tion, Phys. Rev. A88, 012314 (2013)

    2013

  37. [37]

    Wang, GraphPreserving.jl: Graph-preserving circuit optimization library (2026)

    M. Wang, GraphPreserving.jl: Graph-preserving circuit optimization library (2026)

    2026

  38. [38]

    Koenig and J

    R. Koenig and J. A. Smolin, How to efficiently select an arbitrary Clifford group element, Journal of Mathemati- cal Physics55, 122202 (2014)

    2014

  39. [39]

    Ozols, Essays at university of waterloo (2008), uni- versity of Waterloo

    M. Ozols, Essays at university of waterloo (2008), uni- versity of Waterloo

    2008

  40. [40]

    Sharma, K

    H. Sharma, K. Goodenough, J. Borregaard, F. Rozpędek, and J. Helsen, Minimising the number of edges in LC- equivalent graph states, Quantum10, 2001 (2026)

    2001

  41. [41]

    Reiserer, N

    A. Reiserer, N. Kalb, M. S. Blok, K. J. M. van Bem- melen, D. J. Twitchen, M. Markham, T. H. Taminiau, and R. Hanson, Robust quantum-network memory using decoherence-protected subspaces of nuclear spins, Physi- cal Review X6, 021040 (2016)

    2016

  42. [42]

    Feng, Y.-Y

    L. Feng, Y.-Y. Huang, Y.-K. Wu, W.-X. Guo, J.-Y. Ma, H.-X. Yang, L. Zhang, Y. Wang, C.-X. Huang, C. Zhang, L. Yao, B.-X. Qi, Y.-F. Pu, Z.-C. Zhou, and L.-M. Duan, Realization of a crosstalk-avoided quantum network node using dual-type qubits of the same ion species, Nature Communications 15, 204 (2024). Appendix A: Symplectic Representation of Clifford Op...

    2024

  43. [43]

    The corresponding graph state |G⟩ is defined as the unique joint+1 eigenstate of the stabilizer generators Ki = Xi Y j∈N (i) Zj, i = 1,

    Graph-State Stabilizers Let G = ( V, E) be a simple graph with|V | = n and adjacency matrix Γ ∈ Fn×n 2 . The corresponding graph state |G⟩ is defined as the unique joint+1 eigenstate of the stabilizer generators Ki = Xi Y j∈N (i) Zj, i = 1, . . . , n, (B1) where N(i) denotes the neighborhood of vertexi. In binary symplectic form, each stabilizer generator...

  44. [44]

    The stabilizer generators for the two-copy system can be written as S(2) G = In 0 | Γ 0 0 In | 0 Γ , (B5) where the first block corresponds to copy 1 and the second to copy 2

    Two-Copy Representation In the distillation framework considered in this work, we act on two copies of a graph state. The stabilizer generators for the two-copy system can be written as S(2) G = In 0 | Γ 0 0 In | 0 Γ , (B5) where the first block corresponds to copy 1 and the second to copy 2. For each vertexi, the local Pauli support is therefore describe...

  45. [45]

    This local two-copy structure is the natural setting in which phase- less two-copy Clifford operations act

  46. [46]

    Bipartite Structure and the Homogeneous Subgroup Suppose G is bipartite with partitionV = A ∪ B and adjacency matrix Γ = 0 Γ AB ΓT AB 0 . (B7) In the two-copy setting, each vertex carries a pair of binary labels (x(1) i , x(2) i | z(1) i , z(2) i ) ∈ F4 2, (B8) and any phaseless two-qubit Clifford acting locally on that vertex induces an invertible linear...

  47. [47]

    Its sta- bilizer generator is Ki = XiZj, (B13) while Kj contains Zi as one of its factors

    Leaf Vertices and the Bilocal Subgroup Let i be a leaf vertex with unique neighborj. Its sta- bilizer generator is Ki = XiZj, (B13) while Kj contains Zi as one of its factors. In binary symplectic form, the row corresponding to Ki has support only on the localxi component and the zj component. Consequently, any graph-preserving two- copy Clifford must map...

  48. [48]

    local phase-type operations acting indepen- dently on the two-copy qubits of vertexi,

  49. [49]

    These generate an eight-element subgroup Bi ∼= Z3

    a controlled-Z-type coupling between the two copies restricted to that vertex. These generate an eight-element subgroup Bi ∼= Z3

  50. [50]

    Therefore Bi and Bk act on disjoint subsystems and commute, yielding a direct product Y i∈Leaf(G) Bi

    (B14) If i and k are distinct leaf vertices with disjoint neigh- borhoods, their corresponding stabilizer supports do not overlap. Therefore Bi and Bk act on disjoint subsystems and commute, yielding a direct product Y i∈Leaf(G) Bi. (B15) This structural locality is the origin of the8t factor in the gate-counting formula of the main text. Appendix C: Loca...

  51. [51]

    For a vertexv ∈ V, denote byN(v) its neighborhood

    Local Complementation in Matrix Form Let G = ( V, E) be a graph with adjacency matrix Γ ∈ Fn×n 2 , where arithmetic is performed over F2 and diagonal entries are zero. For a vertexv ∈ V, denote byN(v) its neighborhood. The local complementation (LC) at vertexv transforms G into a new graph Gv whose adjacency matrix Γv is given by Γv ij = ( Γij + 1 if i, j...

  52. [52]

    (C3) This operation maps the graph-state stabilizer SG = (I | Γ) (C4) to SGv = (I | Γv), (C5) up to row permutations

    LC and Local Clifford Equivalence For graph states, local complementation corresponds to conjugation by a local Clifford unitary of the form Uv = p Xv O u∈N (v) p Zu. (C3) This operation maps the graph-state stabilizer SG = (I | Γ) (C4) to SGv = (I | Γv), (C5) up to row permutations. Therefore two graphs lie in the same LC orbit if and only if the corresp...

  53. [53]

    Hence every LC orbit is finite, and the edge count attains a minimum on it

    simple graphs onn vertices, and LC operations map simple graphs to simple graphs. Hence every LC orbit is finite, and the edge count attains a minimum on it

  54. [54]

    Isomorphic LC Orbits Two graphs are isomorphic if their adjacency matrices satisfy Γ′ = P ΓP T (C6) 19 FIG. 11. Two non-isomorphic 7-vertex graphs lying in the same LC orbit, both with |E| = 7 edges. They represent distinct labelled configurations within the same LC class and both qualify as minimum-edge representatives. Applying the LC sequence on vertic...

  55. [55]

    (C7) Since the LC orbit is finite,MER(G) is nonempty

    Minimum-Edge Representatives Given a graphG, define MER(G) = arg min G′∈OLC(G) |E(G′)|. (C7) Since the LC orbit is finite,MER(G) is nonempty. The minimum-edge representative within an LC orbit need not be unique. Figure 11 shows an explicit example for n = 7 vertices: two graphs that • lie in the same LC orbit, • are non-isomorphic as graphs, • and both a...

  56. [56]

    Inthisworkwemakeuseofa database of LC orbits constructed by exhaustive enumer- ation up to n ≤ 12 vertices

    LC-Orbit Database Explicit LC-orbit enumerations have been carried out forsmallnumbersofqubits. Inthisworkwemakeuseofa database of LC orbits constructed by exhaustive enumer- ation up to n ≤ 12 vertices. For larger system sizes we refer to the LC-orbit databases available in the literature, which extend the classification ton ≤ 16 vertices [38]. Appendix ...