Finding trail covers: near-optimal decompositions of graph states as linear fusion networks
William Cashman, Giovanni de Felice, Aleks Kissinger · 2025
Read Finding trail covers: near-optimal decompositions of graph states as linear fusion networks by William Cashman, Giovanni de Felice, Aleks Kissinger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18375.txt.
Introduction
William Cashman, Giovanni de Felice, and Aleks Kissinger reduced the cost of building photonic quantum states in a 2025 paper. In measurement-based quantum computing with light, large graph states are assembled by fusing short linear resource states, and each fusion can fail, so builders want as few fusions as possible. That wish becomes a covering problem: split the graph into the fewest paths or trails, relatives of the classic Eulerian and Hamiltonian problems.
Most variants prove NP-hard, so the team supplies heuristics, including a reduction to the traveling salesman problem, plus rewrite rules that shrink the needed fusions for a given graph state. Applied to photonic compilation tasks, the algorithms cut fusion counts toward the practical minimum.
Catalog record
| CREATOR | William Cashman, Giovanni de Felice, Aleks Kissinger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-18375
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finding trail covers: near-optimal decompositions of graph states as linear fusion networks William Cashman, Giovanni de Felice, Aleks Kissinger 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. 1 Introduction In the measurement-based or “one-way” model [ 1 ] of quantum computing (MBQC), the computation consists of preparing an entangled graph state G over multiple qubits, and performing a sequence of adaptive measurements on the nodes of this graph. A particular feature of MBQC is that every qubit in the resource state is only measured once and interacts only with its nearest neighbours on the graph. This makes it particularly suitable to photonic architectures since photons are destroyed upon measurement. In practice, the large graph G must be built by entangling smaller resource states. However, as entanglement can only be generated probabilistically in linear optics [ 2 ] , the efficient construction of large graph states poses a serious challenge to photonic architectures. Current approaches to photonic graph state generation are based on a particular type of entangling operation, known as fusion measurement [ 3 ] . Many small resource states are produced and are entangled together by a series of multi-qubit fusion operations [ 4 ] . We consider access to a source of photons, producing a constant-size resource state at every time step. Photons from different sources or time-steps are then fused together to construct a given graph G . Usually, the photon source only provides states with limited entanglement — such as star graphs, lines or small polyhedra — and the fusion pattern determines long-range correlations. The information of which qubits from different resource states are to be fused together is called fusion network . We consider linear fusion networks, where the resource states have a one dimensional entanglement structure. These include n-GHZ states, linear cluster states and variations of the two [ 5 , 6 , 7 ] . They can be generated with high probability p_{R}\approx 1 from matter-based photon sources such as ions [ 8 ] and quantum dots [ 9 , 10 ] , or from multiple SPDC sources and linear optics using active multiplexing to boost p_{R} [ 11 ] . Fusion measurements are a more costly operation as they succeed with probability p_{S} smaller than p_{R} . As a consequence, we wish to minimise the number of fusions required to build a given graph state to maximise the probability of successfully executing the MBQC pattern. We use two types of fusion operations which can be implemented on pairs of photonic qubits using linear optics only. The first, known as Type II fusion [ 3 ] and used in [ 12 ] , has the effect of merging two nodes of a graph state into one, as depicted in Figure 1 . We call it X fusion as it corresponds to adding a qubit in the graph, connected to the target nodes, and measuring it in the Pauli X basis. In the success case, this implements a ZZ measurement on the target qubits. The second fusion operation, called Y fusion and depicted in Figure 2 , is used in [ 13 , 14 ] to implement linear optical CZ gates probabilistically. In the success case, it has the effect of performing a CZ gate on the target qubits. Up to local Clifford operations, this corresponds to adding a node in the graph and measuring it in the Pauli Y basis. := X = Figure 1 : An X fusion (or Type-II) corresponds to adding a node in the graph measured in the X basis. := Y = \frac{\pi}{2} \frac{\pi}{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 \frac{\pi}{2} . Given additional resource entanglement, both fusion operations admit protocols to increase the probability of success p_{S} [ 13 ] , although X fusion is sometimes preferred as its boosting protocol does not require active switching [ 15 , 16 ] . Note that X and Y fusions cannot be related by local Clifford operations on the target qubits. They are in fact canonical representatives of entangling stabilizer measurements that can be performed with linear optics. Moreover, any decomposition of an MBQC graph (with flow structure) as a fusion network of X and Y fusions admits a deterministic measurement pattern to implement the target graph [ 17 ] . The above discussion motivates the following compilation problem: given a graph G find a linear fusion network that implements the graph using the minimal number of X or Y fusions. Translating this problem in the language of graph theory, we want to find a set of edge-disjoint trails on the graph, which covers every node of the graph, and minimises the number of intersections and un-covered edges. We call such a collection of trails a trail cover and show in Section 2 that minimising fusions is equivalent to finding a trail cover of the graph with the fewest number of trails. This graph-theoretic formulation of the problem allows us to relate it to other problems whose complexity is known in Section 3 . We consider different variations of the minimum trail cover problem. First by restricting the allowed fusion operations to only X or only Y , we obtain generalisations of the Eulerian trail and Hamiltonian path problems, respectively. We show that the case for X fusions can be solved in polynomial time while the case for Y fusions is NP-hard. We then use these results to show that the case where both X and Y fusions are allowed, corresponding to the minimum trail cover problem, is also NP-hard. In Section 4 we provide efficient algorithms for approximating the solutions of these NP-hard problems. We give a heuristic strategy based on subdividing Eulerian trails for solving the minimum trail decomposition and trail cover problems. We reduce the minimum trail cover problem to the Travelling Salesman Problem (TSP), allowing us to use