Pith. sign in

REVIEW 3 major objections 6 minor 52 references

Finding trail covers: near-optimal decompositions of graph states as linear fusion networks

T0 review · 3 major / 6 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Building a graph state by fusions is exactly covering it with trails

desk verdict Needs a fix to its central counting definition, but the trail-cover framework and NP-hardness results are real contributions; worth refereeing. read the letter →

arxiv 2508.18375 v1 pith:XRXMGCJG submitted 2025-08-25 quant-ph

William Cashman , Giovanni de Felice , Aleks Kissinger This is my paper
classification quant-ph MSC 05C4505C7068Q1768Q2581P68 PACS 03.67.Lx03.67.Mn
keywords graphstatestrailcoverfusionnetworksmeasurement-basedquantumcomputingphotonicNP-hardnessTravellingSalesmanProblemrewriting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that the quantum compilation problem of building a graph state from linear resource states and fusion measurements is, at its core, a graph-covering problem: each linear resource becomes a trail, each vertex where trails meet costs one X fusion, and each edge not covered by any trail costs one Y fusion. The central identity X+Y=|E|-|V|+|C| shows the total fusion count is fixed once the number of trails is fixed, so minimizing fusions is exactly minimizing the number of trails in a trail cover. The paper proves the bounded versions of this optimization are NP-hard, gives a polynomial-time algorithm for the unbounded X-only case via Eulerian circuits, and provides heuristic algorithms including a reduction to the Travelling Salesman Problem. If the claimed correspondence holds, photonic measurement-based quantum computing gets a concrete, graph-theoretic target for compile-time optimization of probabilistic fusion attempts.

What carries the argument

The key object is the trail cover: a set of edge-disjoint trails that visits every vertex of the target graph G. Its power comes from Theorem 1, X(G,C)+Y(G,C)=|E|-|V|+|C|, which converts physical fusion counts into a graph invariant plus the number of trails in the cover. This identity carries the entire argument: it makes minimizing fusions equivalent to minimizing the trail count, it yields the NP-hardness reductions, and it is the basis for the heuristic algorithms and the TSP reduction.

What would settle it

Take a small graph such as the diamond graph (two triangles sharing an edge) with a length bound L=3, brute-force enumerate all valid trail covers, and compare the minimum fusion count from Theorem 1 with the output of the paper's heuristic; if the heuristic ever exceeds the brute-force minimum on a graph with a few vertices, the near-optimality claim fails on that instance. More fundamentally, on a device where Y fusions have a much higher success probability than X fusions, compare the paper's fusion-minimized network against a network with one extra trail but all-Y coverage; if the all-Y ne

Watch

Extended reading notes

Core claim

Every linear XY fusion network—a protocol that builds a target graph state from line-shaped resource states using X and Y fusions—is claimed to correspond one-to-one to a trail cover of the target graph: trails are resource states, vertices on several trails cost X fusions, edges absent from the cover cost Y fusions. Theorem 1 gives X+Y = |E|-|V|+|C|, so the fusion count depends only on the number of trails. The identity then yields the complexity landscape: unbounded X-only decompositions are polynomial via Eulerian trails; bounded decompositions, bounded covers, and mixed X/Y covers are NP-hard. Heuristics and a TSP reduction follow, benchmarked near a lower bound on error-correcting codes

Load-bearing premise

The equivalence rests on the assumption that every linear resource state is exactly a simple trail in the target graph, that each trail intersection costs exactly one X fusion, each uncovered edge exactly one Y fusion, and that minimizing the number of trails is the right objective; if real devices have different success rates for X versus Y fusions, non-trail-shaped resource states, or routing constraints, the problem solved here may not minimize the true physical cost.

Editorial extensions

If this is right

  • Any algorithm that finds a short trail cover can serve as a compiler for photonic graph states, with the fusion count read off directly from |E|-|V|+|C|.
  • The X-only case is cheap: minimum trail decompositions with |Odd(G)|/2 trails exist and can be built in O(|E|) time, giving a fast baseline for photon-starved resource states.
  • Because bounded resource lengths make the problem NP-hard, practical devices will need heuristics; the paper's algorithms adapt to photon-bounded trails, so the same machinery covers realistic emitter coherence limits.
  • Rewrites based on local complementation and Z-deletion reduce edges and odd vertices while preserving determinism, cutting fusion and photon requirements by about 10% on the benchmark set.
  • Reducing the fusion count directly raises the post-selected success probability of repeat-until-success fusion networks, so near-minimal trail covers translate into higher probabilities of successfully building the target graph state.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural testable extension is to weight X and Y fusions differently: the paper's objective treats them as interchangeable, but real devices may have different success probabilities, so a weighted trail-cover variant could yield physically cheaper networks even when the trail count is not minimal.
  • The paper's worst-case bound for subdividing Eulerian trails suggests the average case is twice as good; a focused numerical study on random graph families could sharpen the expected approximation ratio for practical compilation.
  • The reduction to TSP opens a direct comparison: feeding the same benchmarks through a modern TSP solver may improve on the bespoke heuristics, or at least confirm their near-optimality on larger graphs.
  • The paper separates graph rewrites from fusion planning; interleaving local complementation between fusion operations could find additional savings on small graphs, and a generalized notion of trail cover would be needed to capture that setting.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper formalizes the compilation of graph states into photonic fusion networks as a graph-theoretic trail-cover problem. It defines XY-fusion networks, associates linear resource states with trails, and claims an exact identity (Theorem 1) relating the number of X and Y fusions to |E| - |V| + |C| for a trail cover C. On this basis it defines MinTrailCover, MinPathCover, MinTrailDecomposition, and bounded/photon-bounded variants, proves NP-hardness for most of them, gives a polynomial algorithm for minimum trail decomposition, proposes approximation heuristics with a TSP reduction, introduces graph-rewrite strategies that preserve gflow, and benchmarks the resulting fusion counts on quantum error-correcting codes and QASMBench circuits against a lower bound derived from the same identity.

Significance. If the stated identity and bounds are corrected, the paper makes a useful contribution: it connects a practically motivated photonic compilation problem to classical trail-cover problems, gives several nontrivial NP-hardness reductions, provides an exact polynomial algorithm for the unbounded trail-decomposition case, and reduces the trail-cover problem to TSP so that mature TSP solvers can be applied. The lower bound used in the benchmarks is derived analytically rather than fitted, and the benchmark comparisons are a genuine strength. The rewrite heuristics are plausible and their limitations (e.g., the Appendix C counterexample for bounded decompositions) are openly documented. However, two load-bearing mathematical points are currently wrong: the definition/proof of Theorem 1 is inconsistent with itself, and Proposition 4's bound is derived through an invalid ceiling inequality and becomes negative for L in {3,4}. These issues must be fixed before the paper's central claims can be accepted as stated.

major comments (3)
  1. [Section 2, Definition 2 and proof of Theorem 1] X(G,C) is defined as the number of intersections between trails, with k trails through a vertex contributing k-1. The proof of Theorem 1 uses the identity sum_T V(T) = |V| + X(G,C), which requires counting repeated occurrences of a vertex within a single trail. These two notions disagree. Concretely, take V={a,b,x,y,z}, E={a-x, x-y, y-z, z-x, x-b} and C={T: a-x-y-z-x-b}. Then every edge is covered (Y=0), and since only one trail is used, Definition 2 gives X=0, so the left-hand side of Theorem 1 is 0, while |E|-|V|+|C| = 5-5+1 = 1. Physically, the trail contains two x-labelled qubits and requires one X fusion, so the correct left-hand side is 1. The identity is salvageable by defining X(G,C) = sum_v (r_v - 1), where r_v is the total number of occurrences of v over all trails, but this must be stated explicitly and used consistently.
  2. [Section 4.1, Proposition 4] The proof of Proposition 4 contains a ceiling manipulation with the wrong direction. Writing A = sum_i (P_i - 2)/(L - 2) and B = (2K - 2)/(L - 2), the proof implicitly uses -ceil(A+B) <= -ceil(A) - ceil(B), but the valid inequality is the reverse up to an additive +1 correction. Consequently the stated bound 1/2|Odd(G)|(1 - 3/(L-2)) + 1 is not established. For L=3 it equals 1 - 2K and for L=4 it equals 1 - K/2, which are negative for sufficiently large K; since K = 1/2|Odd(G)|, this would imply a polynomial-time exact algorithm for an NP-hard problem. The proposition, and its restatement in the conclusion, need to be corrected or removed.
  3. [Section 3.3, Proposition 2 and connectedness assumptions] Proposition 2 is false for disconnected graphs. If G is the disjoint union of two edges, then |E|=2 and ceil(|E|/2)=1, but no single trail can cover edges in different connected components, so the minimum 2-trail decomposition has size 2. The proof invokes Sumner's theorem on line graphs, which requires connectedness. Similar connectedness assumptions are missing elsewhere: for example, Proposition 3 uses K=1 when |Odd(G)|=0, which is only valid for connected graphs; a disjoint union of cycles has one trail per component. Please add explicit connectedness hypotheses or formulate component-wise statements for all affected results.
minor comments (6)
  1. [Section 2, Definition 2] After correcting Theorem 1, please clarify that trails may revisit vertices and that X-fusions count every repeated occurrence of a logical vertex across all resource states, including repetitions within a single trail.
  2. [Conclusion] The conclusion restates Proposition 4 as 1/2|Odd(G)|(1 - 3/L) + 1, omitting the denominator L-2. Align the final statement with the corrected proposition.
  3. [Lemma 3] The sentence 'Loop i has w_j edges' is a typo; it should refer to cycle j.
  4. [Proposition 5] The phrase 'on average' is not formally defined. Specify the probability distribution over graphs or over minimum trail decompositions that is being averaged.
  5. [Table 1 and Section 6.2] There are garbled phrases: 'increas by more than 50%' and 'the action in accept by our algorithm'. Please proofread.
  6. [References] References [12] and [46] appear to be the same work, and [30] and [52] also appear to duplicate; merge to avoid duplicate entries.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: trail-cover identities, NP-hardness reductions, and lower bounds are derived from standard graph theory and benchmarks, not fitted or self-imported.

full rationale

The central compilation identity X+Y=|E|-|V|+|C| (Thm 1) is presented as a theorem proved by elementary counting from the definition of a trail (V(T)=E(T)+1). Even with the known ambiguity about self-intersections — Definition 2 phrases X as intersections 'between trails' while the proof implicitly counts total repeated vertex traversals — this is an internal consistency issue, not a circular step: the theorem is not forced by a fitted parameter or by defining X to be the RHS. Complexity results reduce from bin packing and Hamiltonian path, standard external NP-complete problems. The benchmark lower bound (Lemma 8) is obtained by applying Theorem 1 and photon accounting to a hypothetical single resource state; it is not fitted to the reported heuristic outputs. Self-citations [17] (fusion-network formalism) and [21] (rewriting theory) provide background/definitions, but the trail-cover equivalence, maximal-cover characterization, Algorithm 1/2/3, TSP reduction, and approximation bounds are derived in this paper from Euler's theorem and elementary counting, not imported. There is no uniqueness theorem or ansatz from prior work of the authors that constrains the conclusions. The X(G,C) wording should be corrected to count all repeated occurrences (or Theorem 1's proof amended), but that correction would preserve the formula and does not make the paper's derivation circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central results rest on standard graph theory (Eulerian trails, NP-completeness of Hamiltonian path and bin packing) plus domain assumptions mapping physical fusion operations to trails. No free parameters are fitted to data; the heuristic algorithms' parameters (time limits, annealing iterations) are implementation choices, not fitted constants.

assumptions (5)
  • standard math Euler's theorem: a connected graph has an Eulerian circuit iff all vertices have even degree (Lemma 1, Section 3.2).
    Used to prove minimum trail decomposition size is |Odd(G)|/2 (Theorem 2).
  • standard math NP-completeness of Hamiltonian path in cubic graphs and of bin packing (cited [42], [41]).
    Used for reductions in Theorems 4 and 7.
  • domain assumption Linear XY-fusion networks are in one-to-one correspondence with trail covers; X fusions merge trail intersections and Y fusions implement uncovered edges (Section 2, Definitions 1-2).
    Bridges the physical compilation problem to graph theory; without this, the optimization target is not the trail cover problem.
  • domain assumption Local complementation and Z-deletion preserve gflow and are sufficient to transform any two labeled open graphs with gflow and the same linear map (cited [22]).
    Justifies that rewrite strategies in Section 5 preserve the implemented MBQC pattern.
  • domain assumption Resource states are linear (1D) chains of photons; each fusion consumes one photon from each of two qubits; minimizing fusion count is the primary objective.
    Underlies the trail model and the focus on fusion count rather than other costs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding trail covers: near-optimal decompositions of graph states as linear fusion networks." pith.science (2026). https://pith.science/paper/XRXMGCJG

@misc{pith2026250818375,
  author       = {Pith},
  title        = {Pith review of: Finding trail covers: near-optimal decompositions of graph states as linear fusion networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XRXMGCJG}},
  note         = {Machine review of arXiv:2508.18375}
}
read the original abstract

Quantum compilation requires the development of new algorithms that optimise the cost of implementing quantum computations on physical hardware. Often this gives rise to problems which are asymptotically hard to solve classically, and for which heuristics and reductions to known problems are of great practical use. In this paper, we study three graph-theoretic problems which can be seen as generalisations of the Eulerian and Hamiltonian path problems. These arise in photonic implementations of measurement-based quantum computing, where graph states are constructed by fusing bounded-length linear resource states. Since the fusion operation succeeds with probability smaller than one, we wish to minimise the number of fusions required to build a particular graph state and this corresponds to finding a minimal path or trail cover of the graph. We show that these covering problems are NP-hard in most cases and give heuristic algorithms for finding trail covers in graphs including a reduction to the travelling salesman problem. We propose new rewrite strategies for graph states that reduce the number of fusions required to build a given graph. Finally, we apply these algorithms to the compilation of photonic fusion networks and provide a series of benchmarks showing the performance of our algorithms on common error-correcting codes and circuits from the QASMBench set.

Figures

Figures reproduced from arXiv: 2508.18375 by the authors.

Figure 1
Figure 1. An X fusion (or Type-II) corresponds to adding a node in the graph measured in the X basis. := Y = π 2 π 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. A Y fusion (or CZ) corresponds to adding a node in the graph measured in the Y basis, and rotating the target qubits with a Z phase of π 2 . Given additional resource entanglement, both fu￾sion operations admit protocols to increase the prob￾ability of success pS [13], although X fusion is some￾times preferred as its boosting protocol does not re￾quire active switching [15, 16]. Note that X and Y fusions cannot be r… view at source ↗
Figure 3
Figure 3. An example of a graph that whose mini￾mum L-trail decomposition contains more than |E|/L or 1 2 |Odd(G)| trails. For L = 3, the minimum 3-trail decom￾position requires 3 trails but |E|/3 = 2 and 1 2 |Odd(G)| = 2. The minimum 1-trail decomposition is simply the edge set E. There also exists an efficient algorithm for computing a minimum 2-trail decomposition by converting it to a matching problem. Proposition 2. Let … view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: Example reaching the bound in Proposition 3. To find a minimum 2-trail decomposition for graph (A), we first find a minimum trail decomposition (B) and subdivide it into four 2-trails (C). However, the minimum 2-trail decomposition has size 3 (D). This achieves the max…
Figure 6
Figure 6. Figure 6: Example of the reduction from the multi-visit TSP to the TSP. The main limitation of this reduction from multi￾visit TSP to standard TSP is that the number of edges in the new graph increases with complexity O(|V | 2 + |E|). Further work could aim at estab￾lishing a mo…
Figure 5
Figure 5. Figure 5: Finding a minimum trail cover by solving the multi-TSP problem. The original graph (1) is transformed into a new graph (2) by adding a vertex v and edges be￾tween v and odd vertices of the original graph. A solution to the multi-visit TSP (3) is transformed into a solu…
Figure 7
Figure 7. Figure 7: The cycle graph state is transformed into a lin￾ear graph state requiring fewer fusions through a series of local complementation. However, any local complementa￾tion applied to the cycle will increase the number of edges in the graph state and so Rewrite 1 would not f…
Figure 9
Figure 9. Figure 9: Complementing the triangle never increases the number of fusions. Solid black lines represent edges belonging to the path cover and blue dashed lines are Y fusions. This technique easily generalizes to cliques of ar￾bitrary size. For cliques of size four or greater, it…
Figure 8
Figure 8. Figure 8: Complementing a triangle by first adding a new node connected to the triangle vertices and locally comple￾menting it. Complementing the triangle keeps the number of edges unchanged but increases the number of vertices by one. Therefore by (2), it decreases the number o…
Figure 10
Figure 10. Figure 10: illustrates a graph where local comple￾mentation of the vertex v leaves the number of edges unchanged but reduces the number of odd edges by four. The new graph can therefore be implemented with two X fusions, whereas the original graph re￾quires at least four XY fusi…
Figure 11
Figure 11. Figure 11: shows the performance of our algorithms for the different fusion types alongside the lower bound from Lemma 8, and illustrates two key insights. First, we are almost always able to find X fusion networks that require fewer fusions than Y fusion net￾works, with the dif…
Figure 12
Figure 12. Figure 12: Number of fusions and resource states required to implement the Shor(2,2) encoded 6-ring graph state us￾ing the algorithms from Section 4 for different resource state lengths. The number of fusions and resource states are linearly dependent from Theorem 1. every verte…
Figure 13
Figure 13. Figure 13: Post-selected probability of successfully imple￾menting selected graphs against the photon loss probability for resource states with 10 and 20 photons. The plot for resource states with at most 10 photons appears sparse as most graphs have a near-zero probability of s…
Figure 14
Figure 14. Figure 14: Average probability of success for the QASM￾Bench benchmark set comparing post-selected and error￾corrected probabilities of success for different photon lengths [PITH_FULL_IMAGE:figures/full_fig_p016_14.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

52 extracted references · 44 canonical work pages

  1. [1]

    A One-Way Quantum Computer

    Robert Raussendorf and Hans J. Briegel. “A One-Way Quantum Computer”. Physical Review Letters 86, 5188–5191 (2001)

    work page 2001

  2. [2]

    Generating Entanglement with Linear Optics

    Stasja Stanisic, Noah Linden, Ashley Montanaro, and Peter S. Turner. “Generating Entanglement with Linear Optics”. Physical Review A 96, 043861 (2017)

    work page 2017

  3. [3]

    Resource-efficient linear optical quantum com- putation

    Daniel E. Browne and Terry Rudolph. “Resource-efficient linear optical quantum com- putation”. Physical Review Letters 95 (2005)

    work page 2005

  4. [4]

    Fusion-based quantum computation

    Sara Bartolucci, Patrick Birchall, Hector Bomb ´ ın, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kiel- ing, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Terry Rudolph, and Chris Sparrow. 17 “Fusion-based quantum computation”. Nature Communications 14, 912 (2023)

    work page 2023

  5. [5]

    Fault tolerant quantum computation with nondeterministic gates

    Ying Li, Sean D. Barrett, Thomas M. Stace, and Simon C. Benjamin. “Fault tolerant quantum computation with nondeterministic gates”. Phys. Rev. Lett. 105, 250502 (2010)

    work page 2010

  6. [6]

    All- photonic architecture for scalable quantum com- puting with greenberger-horne-zeilinger states

    Srikrishna Omkar, Seok-Hyung Lee, Yong Siah Teo, Seung-Woo Lee, and Hyunseok Jeong. “All- photonic architecture for scalable quantum com- puting with greenberger-horne-zeilinger states”. PRX Quantum 3, 030309 (2022)

    work page 2022

  7. [7]

    Extracting GHZ states from linear cluster states

    J. de Jong, F. Hahn, N. Tcholtchev, M. Hauswirth, and A. Pappa. “Extracting GHZ states from linear cluster states”. Physical Review Research 6, 013330 (2024)

    work page 2024

  8. [8]

    Observation of entanglement be- tween a single trapped atom and a single pho- ton

    B. B. Blinov, D. L. Moehring, L.-M. Duan, and C. Monroe. “Observation of entanglement be- tween a single trapped atom and a single pho- ton”. Nature 428, 153–157 (2004)

    work page 2004

Show all 52 references
  1. [10]

    High-rate entanglement between a semiconduc- tor spin and indistinguishable photons

    N. Coste, D. A. Fioretto, N. Belabas, S. C. Wein, P. Hilaire, R. Frantzeskakis, M. Gundin, B. Goes, N. Somaschi, M. Morassi, A. Lema ˆ ıtre, I. Sagnes, A. Harouri, S. E. Economou, A. Auf- feves, O. Krebs, L. Lanco, and P. Senellart. “High-rate entanglement between a semiconduc...

    2023

  2. [11]

    Creation of Entangled Photonic States Using Linear Op- tics

    Sara Bartolucci, Patrick M. Birchall, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Mihir Pant, Terry Rudolph, Jake Smith, Chris Sparrow, and Mihai D. Vidrighin. “Creation of Entangled Photonic States Using Linear Op- tics” (2021). arXiv:2106.13825

    2021 arXiv

  3. [13]

    Repeat-Until-Success Linear Optics Dis- tributed Quantum Computing

    Yuan Liang Lim, Almut Beige, and Leong Chuan Kwek. “Repeat-Until-Success Linear Optics Dis- tributed Quantum Computing”. Physical Review Letters 95, 030505 (2005)

    2005

  4. [14]

    A Spin-Optical Quantum Computing Architec- ture

    Gr´ egoire de Gliniasty, Paul Hilaire, Pierre- Emmanuel Emeriau, Stephen C. Wein, Alexia Salavrakos, and Shane Mansfield. “A Spin-Optical Quantum Computing Architec- ture” (2024). arXiv:2311.05605

    2024 arXiv

  5. [15]

    Nearly deterministic Bell measurement with multiphoton entanglement for efficient quantum-information processing

    Seung-Woo Lee, Kimin Park, Timothy C. Ralph, and Hyunseok Jeong. “Nearly deterministic Bell measurement with multiphoton entanglement for efficient quantum-information processing”. Phys- ical Review A 92, 052324 (2015)

    2015

  6. [16]

    Enhanced Fault-tolerance in Photonic Quantum Comput- ing: Floquet Code Outperforms Surface Code in Tailored Architecture

    Paul Hilaire, Th´ eo Dessertaine, Boris Bourdon- cle, Aur´ elie Denys, Gr´ egoire de Gliniasty, Gerard Valent ´ ı-Rojas, and Shane Mansfield. “Enhanced Fault-tolerance in Photonic Quantum Comput- ing: Floquet Code Outperforms Surface Code in Tailored Architecture” (2024). arXi...

    2024

  7. [17]

    Fusion and flow: for- mal protocols to reliably build photonic graph states

    Giovanni de Felice, Boldizs´ ar Po´ or, Lia Yeh, and William Cashman. “Fusion and flow: for- mal protocols to reliably build photonic graph states” (2024). arXiv:2409.13541

    2024 arXiv

  8. [18]

    Rewrit- ing Measurement-Based Quantum Computations with Generalised Flow

    Ross Duncan and Simon Perdrix. “Rewrit- ing Measurement-Based Quantum Computations with Generalised Flow”. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Klein- berg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Ran- gan, Bernhard Steffe...

    2010

  9. [19]

    Graph-theoretic Simplification of Quantum Circuits with the ZX- calculus

    Ross Duncan, Aleks Kissinger, Simon Pedrix, and John van de Wetering. “Graph-theoretic Simplification of Quantum Circuits with the ZX- calculus” (2019). url: http://arxiv.org/abs/ 1902.03178

    2019 arXiv

  10. [20]

    Generalized flow and determinism in measurement-based quan- tum computation

    Daniel E. Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. “Generalized flow and determinism in measurement-based quan- tum computation”. New Journal of Physics 9, 250 (2007)

    2007

  11. [21]

    There and back again: A circuit ex- traction tale

    Miriam Backens, Hector Miller-Bakewell, Gio- vanni de Felice, Leo Lobski, and John van de Wetering. “There and back again: A circuit ex- traction tale”. Quantum 5, 421 (2021)

    2021

  12. [22]

    Complete flow-preserving rewrite rules for mbqc patterns with pauli measurements

    Tommy McElvanney and Miriam Backens. “Complete flow-preserving rewrite rules for mbqc patterns with pauli measurements”. Electronic Proceedings in Theoretical Computer Science 394, 66–82 (2023)

    2023

  13. [23]

    Graph- theoretical optimization of fusion-based graph state generation

    Seok-Hyung Lee and Hyunseok Jeong. “Graph- theoretical optimization of fusion-based graph state generation”. Quantum 7, 1212 (2023)

    2023

  14. [24]

    Qasmbench: A low-level qasm benchmark suite for nisq evaluation and simula- tion

    Ang Li, Samuel Stein, Sriram Krishnamoorthy, and James Ang. “Qasmbench: A low-level qasm benchmark suite for nisq evaluation and simula- tion” (2022). arXiv:2005.13018

    2022 arXiv

  15. [25]

    Minimizing resource overhead in 18 fusion-based quantum computation us- ing hybrid spin-photon devices

    Stephen C. Wein, Timoth´ ee Goubault de Brugi` ere, Luka Music, Pascale Senel- lart, Boris Bourdoncle, and Shane Mans- field. “Minimizing resource overhead in 18 fusion-based quantum computation us- ing hybrid spin-photon devices” (2024). url: https://arxiv.org/abs/2412.08611v1

    2024

  16. [26]

    A compiler for universal pho- tonic quantum computers

    Felix Zilk, Korbinian Staudacher, Tobias Gugge- mos, Karl F¨ urlinger, Dieter Kranzlm¨ uller, and Philip Walther. “A compiler for universal pho- tonic quantum computers”. In 2022 IEEE/ACM Third International Workshop on Quantum Computing Software (QCS). IEEE (2022)

    2022

  17. [27]

    Repeat-until-success linear optics dis- tributed quantum computing

    Yuan Liang Lim, Almut Beige, and Leong Chuan Kwek. “Repeat-until-success linear optics dis- tributed quantum computing”. Physical Review Letters95 (2005)

    2005

  18. [28]

    Experimental generation of an eight- photon greenberger–horne–zeilinger state

    Yun-Feng Huang, Bi-Heng Liu, Liang Peng, Yu- Hu Li, Li Li, Chuan-Feng Li, and Guang-Can Guo. “Experimental generation of an eight- photon greenberger–horne–zeilinger state”. Na- ture Communications 2, 546 (2011)

    2011

  19. [29]

    Deterministic and re- configurable graph state generation with a single solid-state quantum emitter

    H. Huet, P. R. Ramesh, S. C. Wein, N. Coste, P. Hilaire, N. Somaschi, M. Morassi, A. Lema ˆ ıtre, I. Sagnes, M. F. Doty, O. Krebs, L. Lanco, D. A. Fioretto, and P. Senellart. “Deterministic and re- configurable graph state generation with a single solid-state quantum emitter”....

    2025

  20. [31]

    Deterministic and reconfigurable graph state generation with a single solid-state quantum emitter

    H. Huet, P. R. Ramesh, S. C. Wein, N. Coste, P. Hilaire, N. Somaschi, M. Morassi, A. Lema ˆ ıtre, I. Sagnes, M. F. Doty, O. Krebs, L. Lanco, D. A. Fioretto, and P. Senellart. “Deterministic and reconfigurable graph state generation with a single solid-state quantum emitter” (2...

    2025 arXiv

  21. [32]

    Reducibility among combi- natorial problems

    Richard M. Karp. “Reducibility among combi- natorial problems”. Pages 85–103. Springer US. Boston, MA (1972)

    1972

  22. [33]

    List of graphs for which the hamilto- nian path problem is in p

    “List of graphs for which the hamilto- nian path problem is in p”. url: https: //www.graphclasses.org/classes/problem_ Hamiltonian_path.html

  23. [34]

    Approximation algorithms for cover- ing a graph by vertex-disjoint paths of max- imum total weight

    Shlomo Moran, Ilan Newman, and Yaron Wolf- sthal. “Approximation algorithms for cover- ing a graph by vertex-disjoint paths of max- imum total weight”. Networks 20, 55– 64 (1990). url: https://api.semanticscholar. org/CorpusID:8146642

    1990

  24. [35]

    Path cover problems with length cost

    Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, and Tsuyoshi Yagita. “Path cover problems with length cost”. Algorithmica 85, 3348–3375 (2023)

    2023

  25. [36]

    Graph theory 1736-1936

    Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson. “Graph theory 1736-1936”. Claren- don Press. (1976). url: https://api. semanticscholar.org/CorpusID:118963253

    1936

  26. [37]

    Graphs and their uses

    Oystein Ore and Robin J. Wilson. “Graphs and their uses”. Anneli Lax New Mathematical Library. Mathematical Association of America. (1990)

    1990

  27. [38]

    Eulerian graphs and re- lated topics: Part 1, volume 2

    Herbert Fleischner. “Eulerian graphs and re- lated topics: Part 1, volume 2”. Annals of Dis- crete Mathematics. (1991). url: https://api. semanticscholar.org/CorpusID:118183786

    1991

  28. [39]

    Graphs with 1-factors

    David P. Sumner. “Graphs with 1-factors”. Pro- ceedings of the American Mathematical Society 42, 8–12 (1974). url: http://www.jstor.org/ stable/2039666

    1974

  29. [40]

    An o(v—v— c —e—) algoithm for finding maximum matching in general graphs

    Silvio Micali and Vijay V. Vazirani. “An o(v—v— c —e—) algoithm for finding maximum matching in general graphs”. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). Pages 17–27. (1980)

    1980

  30. [41]

    Approximation algorithms

    Vijay V. Vazirani. “Approximation algorithms”. Page 380. Springer Berlin, Heidelberg. (2001)

    2001

  31. [42]

    The planar hamiltonian circuit problem is np-complete

    M. R. Garey, D. S. Johnson, and R. En- dre Tarjan. “The planar hamiltonian circuit problem is np-complete”. SIAM Journal on Computing 5, 704–714 (1976). arXiv:https://doi.org/10.1137/0205049

    1976 doi

  32. [43]

    A new benchmark set for traveling salesman prob- lem and hamiltonian cycle problem

    Pouya Baniasadi, Vladimir Ejov, Michael Haythorpe, and Serguei Rossomakhine. “A new benchmark set for traveling salesman prob- lem and hamiltonian cycle problem” (2018). arXiv:1806.09285

    2018 arXiv

  33. [44]

    Complexity of graph-state preparation by clifford circuits

    Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura. “Complexity of graph-state preparation by clifford circuits” (2024). arXiv:2402.05874

    2024 arXiv

  34. [45]

    Rank-width and vertex-minors

    Sang il Oum. “Rank-width and vertex-minors”. Journal of Combinatorial Theory, Series B 95, 79–100 (2005)

    2005

  35. [46]

    Fusion-based quantum computation

    Sara Bartolucci, Patrick Birchall, Hector Bombin, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kiel- ing, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Terry Rudolph, and Chris Sparrow. “Fusion-based quantum computation” (2021). arXiv:2101.09310

    2021 arXiv

  36. [47]

    Measurement-based quantum computation on cluster states

    Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. “Measurement-based quantum computation on cluster states”. Phys. Rev. A68, 022312 (2003)

    2003

  37. [48]

    All-photonic quantum repeaters

    Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo. “All-photonic quantum repeaters”. Nature Communications 6, 6787 (2015)

    2015

  38. [49]

    Resource costs for fault-tolerant linear optical quantum comput- ing

    Ying Li, Peter C. Humphreys, Gabriel J. Men- doza, and Simon C. Benjamin. “Resource costs for fault-tolerant linear optical quantum comput- ing”. Phys. Rev. X 5, 041007 (2015). 19

    2015

  39. [50]

    Loss tolerance in one-way quan- tum computation via counterfactual error correc- tion

    Michael Varnava, Daniel E. Browne, and Terry Rudolph. “Loss tolerance in one-way quan- tum computation via counterfactual error correc- tion”. Phys. Rev. Lett. 97, 120501 (2006)

    2006

  40. [51]

    Pyzx: Large scale automated diagrammatic rea- soning

    Aleks Kissinger and John van de Wetering. “Pyzx: Large scale automated diagrammatic rea- soning”. Electronic Proceedings in Theoretical Computer Science 318, 229–241 (2020)

    2020

  41. [52]

    Sequential generation of linear cluster states from a single photon emitter

    D. Istrati, Y. Pilnyak, J. C. Loredo, C. Ant´ on, N. Somaschi, P. Hilaire, H. Ollivier, M. Esmann, L. Cohen, L. Vidro, C. Millet, A. Lema ˆ ıtre, I. Sagnes, A. Harouri, L. Lanco, P. Senellart, and H. S. Eisenberg. “Sequential generation of linear cluster states from a single p...

    2020

  42. [53]

    Generating graph states with a single quantum emitter and the minimum number of fusions

    Matthias C. L¨ obl, Love A. Pettersson, Andrew Jena, Luca Dellantonio, Stefano Paesani, and Anders S. Sørensen. “Generating graph states with a single quantum emitter and the minimum number of fusions” (2025). arXiv:2412.04587 [quant-ph]

    2025 arXiv

  43. [54]

    Optimizing Graph Codes for Measurement-Based Loss Tolerance

    Thomas J. Bell, Love A. Pettersson, and Ste- fano Paesani. “Optimizing Graph Codes for Measurement-Based Loss Tolerance”. PRX Quantum 4, 020328 (2023)

    2023

  44. [55]

    Loss-tolerant architecture for quantum computing with quantum emitters

    Matthias C. L¨ obl, Stefano Paesani, and An- ders S. Sørensen. “Loss-tolerant architecture for quantum computing with quantum emitters”. Quantum 8, 1302 (2024). A Bounded Trail cover estimations Lemma 9. Let (ti)N i=1 and L be positive integers. Then N∑ i=1 ⌈ti L ⌉ − ⌈N∑ i=1 t...

    2024

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.