WorksPhysics and Astronomy
Optimal Measurement Rounds for Perfect Encoded Fusion
Abstract
Encoded fusion combines probabilistic physical fusions to perform a logical Bell measurement. Adaptive choices depend on earlier measurement outcomes and therefore require multiple measurement rounds. We determine the minimum worst-case number of rounds for perfect fusion of two blocks of an irreducible [[n,1]] stabilizer code. A strategy is perfect if the logical Bell measurement succeeds on every branch containing at least one successful physical fusion. Even after fixing the past history, including measurement values, we consider all success/failure branches, including those with zero probability for a particular input state or measurement device. In a lossless model with fixed coordinate pairing, arbitrary Pauli failure bases, and each pair fused exactly once, the optimum equals the minimum root eccentricity over the local complementation orbit of rooted graphs representing the code. The lower bound applies to arbitrary perfect strategies that choose batches and bases using previous outcomes. We also characterize the batch sequences that can occur on an all-failure branch of a perfect strategy by a necessary and sufficient graph adjacency condition. A matching strategy fuses distance layers from the outside in and, after the first success, completes the remaining fusions in at most one further round by changing the failure bases along an induced path.
Introduction
Fusion-based quantum computation connects small photonic resource states through measurements [1]. Physical fusion is probabilistic: success reveals two Bell parities, whereas failure measures the two photons individually in a chosen Pauli basis. Encoding can make a logical Bell measurement succeed even when some physical fusions fail. In adaptive fusion, feed-forward (FF) lets earlier outcomes determine subsequent batches and failure bases. Acquiring and processing these outcomes may require delaying unmeasured photons, increasing latency and exposure to loss. Fewer rounds therefore reduce sequential control requirements.
This leads to a question about measurement rounds. For a fixed code, what is the minimum worst-case number of rounds needed for logical fusion to succeed on every branch containing at least one physical success? We call a strategy satisfying this condition perfect.
Let denote the minimum worst-case number of rounds among perfect strategies for a code . For irreducible stabilizer codes, we prove
Here the root represents the encoded qubit, and is the set of rooted graph representations of the code, which forms a single local-complementation orbit. The root eccentricity is the largest shortest-path distance from to a physical vertex. The optimization therefore ranges over graph representations as well as measurement orders within a fixed graph.
Goodenough et al. established recoverability criteria and characterized perfect nonadaptive fusion [2]. Reiß and van Loock gave adaptive strategies, including layer constructions for tree codes [3]; a sequential construction for connected graph codes appears in a machine-generated Lean proof made public before this work [4]. We characterize the minimum worst-case round count over arbitrary perfect adaptive strategies for irreducible codes in the full outcome-tree model, proving a matching lower bound and graph-based construction, together with a necessary and sufficient condition on all-failure batch sequences.
Section § 2 defines the model and states the main theorem. § 3 and § 4 develop the recovery criterion and necessary conditions for perfect strategies. § 5 provides the graph representations and induced-path completion used in § 6 to prove the batch characterization and the main theorem. § 7 illustrates optimization over graph representations and a code that requires two rounds. § 8 concludes.
Model and Main Result
We define the code and fusion strategy model, then introduce rooted graph representations and state the optimal-round theorem with its proof roadmap.
Stabilizer Codes and Adaptive Fusion
Write for the binary field; all vector and matrix arithmetic below is over this field. Pauli words on physical qubits, modulo phase, are represented by vectors in . We use the equivalent notations
where and is the two-bit component at coordinate . At one coordinate,
Vector addition corresponds to multiplication of Pauli words modulo phase. We write . The support is
For , let be the subspace of vectors that vanish outside .
The symplectic form
is zero for commuting Pauli words and one for anticommuting words. An stabilizer code, encoding one logical qubit, is represented by an isotropic subspace of dimension . Isotropy means for all , expressing commutativity of the stabilizers.
Let be the space of Pauli words commuting with every stabilizer. Physical Pauli words that differ by a stabilizer represent the same logical operator. Their classes are
The quotient is a two-dimensional nondegenerate symplectic space with form
We call its elements logical Pauli classes; nonzero classes represent nontrivial logical Pauli operators. A physical representative is a nontrivial logical word, or simply a logical word. Thus is a vector in the physical space , whereas belongs to the quotient.
We call irreducible if
This excludes a detached subsystem in a pure stabilizer state that is independent of the logical information.
We fuse two blocks of the same code with fixed coordinate pairing. Coordinate denotes a pair containing one photon from each block. Its failure basis is chosen from . A successful physical fusion reveals two Bell parities; on failure, the photons are measured individually in the failure basis. Photon loss is excluded.
In each round a fusion strategy chooses a nonempty batch of previously unfused coordinates and a failure basis for each. A batch is the set of coordinates fused in the same round. These choices are fixed before any outcome of that round is known. All earlier outcomes, including individual measurement values, may be used. We call such outcome-dependent choices adaptive fusion, and the use of outcomes from earlier rounds to select subsequent measurements feed-forward ().
Every coordinate is fused exactly once on every branch; a strategy does not stop early even if the logical information is already recoverable. The pairing is fixed. Ancillary photons, single-photon measurements used to complete fusion, and operations that boost the physical fusion success probability are not allowed.
We now specify the outcome branches on which a fusion strategy is required to succeed. We use the full outcome-tree model: after fixing the past history, including measurement values, every success/failure assignment in the next batch is included as a branch. A perfect fusion strategy, or perfect strategy, recovers both logical Bell parities on every such branch containing at least one successful physical fusion. Branches with zero probability for a particular input state and measurement device are not excluded. Measurement values may affect control choices, but not the recovery criterion in § 3. Phase-free vectors specify which parities are recoverable; their measured signs are tracked separately by classical processing.
Let be the set of perfect fusion strategies for , and let be the set of outcome branches of a strategy . Write for the number of nonempty batches executed on branch . We minimize the worst-case number of rounds:
Set if no perfect strategy exists.
One round requires no FF; rounds use at most inter-round FF steps. It suffices to consider deterministic strategies: fixing the internal random choices of a strategy that is perfect on every branch preserves perfection and cannot increase the worst-case number of rounds.
Rooted Graphs and Optimal Measurement Rounds
Graph representations allow rounds to be constructed from distances to a root. Let be a simple graph on the fixed labeled vertex set , with nonisolated. Use the same symbol for its binary adjacency matrix. The graph-state stabilizer subspace is
generated by , where is the neighborhood of . The corresponding graph code is
The root represents the encoded qubit and is not a physical fusion coordinate. Equation (3) selects the graph-state words that are trivial at the root and restricts them to the physical coordinates.
Coordinatewise symplectic maps independently permute at each physical coordinate. Let be the set of rooted graphs whose graph codes are related to by such maps. This set is nonempty and is exactly one local-complementation orbit, as explained in § 5.1. Local complementation at a vertex toggles the edges between distinct neighbors of . Local complementation at the root is allowed, but vertex permutations are not included in the operations generating this orbit. The root eccentricity is
the largest shortest-path distance from the root to a physical vertex.
Main Theorem and Proof Roadmap
Theorem 1 (Optimal measurement rounds). In the full outcome-tree model of § 2.1, every irreducible code with satisfies
Reducible codes admit no perfect strategy in this model.
In particular, the one-round case is
This recovers the characterization of perfect nonadaptive fusion in Ref. [2 Corollary 3.5 and Theorem 4.3].
The theorem optimizes both the graph representation of the code and the measurement order. Its proof relies on the characterization of all-failure batch sequences in Proposition 9.
Proof roadmap. Lemmas 2 and 3 express recoverable logical Bell parities in linear-algebraic terms. From this common starting point, we separate the lower bound from the construction attaining it.
Lower bound. The obstruction to logical success with a single physical success (Lemma 4) implies on every all-failure branch of a perfect strategy (Lemma 5). A graph representation adapted to these specified bases (Lemma 7) then forces each vertex to be adjacent either to the root or to a vertex in a later batch. This is the necessity direction of Proposition 9 and yields a lower bound for arbitrary perfect strategies.
Upper bound. The adjacency condition provides an induced path from a successful coordinate in the first round containing a success to the root, with only unfused internal vertices. Lemma 8 completes the remaining fusions in at most one further round, proving sufficiency in Proposition 9. Irreducibility is equivalent to connectivity (Lemma 6); fusing distance layers from the outside in then gives the main theorem’s upper bound. Figure 1 summarizes these dependencies.

Figure 1. Main dependencies in the proof. The left side gives necessary conditions for arbitrary perfect strategies; the right side constructs strategies. Connectivity is used for the distance-layer upper bound and for nonexistence for reducible codes.
Logical Fusion and Recoverability
We determine which logical Bell parities can be recovered from the physical fusion outcomes on a branch. We first represent these outcomes by a space of Pauli words, then characterize logical fusion success by whether the failure-basis span contains a logical word.
Recoverable Logical Bell Parities
Let be the failed coordinates on a branch, and write for their chosen failure bases. At each , the Pauli is measured individually in each block. Represent these operators by phase-free vectors. We call the binary linear subspace they generate,
the failure-basis span. Here embeds a one-coordinate vector into coordinate of :
Each coefficient specifies whether the Pauli occurs in the product. Thus a word in has letter 0 or at each and vanishes outside $D. This space includes products of the directly measured Pauli words. The definition does not add words inferred using known stabilizer values.
For , the value of the corresponding Pauli word is known separately in each block. Multiplying these two values gives the inter-block parity for that word. A successful fusion instead gives two independent Bell parities, without giving the individual Pauli values in each block. Let be the successful coordinates. The physical measurement outcomes determine the inter-block parity associated with every Pauli word in
For words in , the Pauli measurement outcomes are also known separately for each block.
We now pass from physical words to logical Pauli classes. We retain the words in that belong to and identify words that differ by a stabilizer. The recoverable logical Bell parities are described by
Here is a space of physical representatives, whereas is a space of logical Pauli classes; they belong to different ambient spaces. The measured signs give the parity values, while the subspace specifies which parities are recoverable. Logical Bell measurement succeeds exactly when . Two independent logical Pauli classes need not commute on one block, but their corresponding inter-block parity operators do commute.
Conditions for Logical Fusion Success
To decide success, it suffices to check whether the failure-basis span contains a logical word, that is, a physical representative in . The following criterion is Proposition 3.1 of Goodenough et al. [2], expressed in the present notation.
Lemma 2 (Failure-basis span criterion). Logical fusion succeeds on a branch if and only if
Equivalently, contains no element of .
This condition means that products of the Paulis directly measured at failed coordinates cannot form a nontrivial logical word.
Proof. Rather than test directly, we compute the orthogonal complement of in the logical quotient. Every orthogonal complement with subscript below is taken in the physical space . At a single coordinate, the symplectic orthogonal complement of is , corresponding to the identity Pauli , while that of any one-dimensional subspace is the subspace itself. The local subspace of is at each successful coordinate and at each failed coordinate, so
The identities for subspaces ,
together with , give
The last equality uses . Moreover, implies . Hence the orthogonal complement in the logical quotient is
Since the form on is nondegenerate,
By Eq. (8), the last condition is equivalent to .
Next, independently of the actual success or failure outcomes, consider an assignment of one Pauli basis to every coordinate. The associated failure-basis span is Eq. (5) with . It is a maximal isotropic, or Lagrangian, subspace satisfying
Here specifies bases; it does not assert that all physical fusions have actually failed. If an all-failure branch uses these bases, its failure-basis span is .
The next lemma is the case of Lemma 3.2 of Goodenough et al. [2]. We include its short proof to keep the argument self-contained.
Lemma 3 (A logical word for every full basis assignment). For every assignment of bases to all coordinates,
In particular, .
Thus, for any full basis assignment, the products of the assigned Paulis include a nontrivial logical word.
Proof. Since is a Lagrangian subspace of dimension ,
Applying the dimension formulas for a sum and an orthogonal complement gives
If were contained in , then , contradicting the difference of one in their dimensions.
On an all-failure branch, a logical word in violates the success condition of Lemma 2, so logical fusion necessarily fails. A perfect strategy therefore succeeds on precisely the patterns containing at least one successful physical fusion. If the physical fusion flags are independent, with success and failure each having probability , the success probability is . The round-count theorem itself does not use a probability distribution.
Necessary Conditions for Perfect Fusion Strategies
We derive necessary conditions for a perfect strategy by considering branches with exactly one successful physical fusion. We first give a condition under which that success does not suffice for logical fusion. We then constrain the bases on an all-failure branch so that they cannot produce this obstruction.
Logical Fusion Failure Despite a Single Successful Physical Fusion
A single successful physical fusion need not recover both logical Bell parities. The next lemma identifies such a failure from the form of a stabilizer.
Lemma 4 (A condition for logical failure despite one physical success). Suppose only coordinate succeeds. Let be the chosen failure bases on and the corresponding failure-basis span. If some satisfies
then logical fusion fails.
A stabilizer that is nonzero at the successful coordinate and aligned with the failure bases elsewhere lets us construct a logical word in supported away from the successful coordinate.
Proof. Extend to an assignment on all coordinates by choosing basis at coordinate . Lemma 3 gives . If , then already. Otherwise , so adding the stabilizer gives
The other components remain aligned with the bases , hence . In either case, contains a nontrivial logical word, and Lemma 2 implies logical failure.
Constraints on All-Failure Branches
We now derive a necessary condition for a perfect fusion strategy by examining its all-failure branches. Choose such a branch and let denote the bases used on it. If contains a nonzero stabilizer, we show that an alternative outcome branch satisfies the conditions of Lemma 4, contradicting perfection.
Lemma 5 (A necessary condition for a perfect strategy). Let be the basis assignment on any all-failure branch of a perfect strategy. The corresponding failure-basis span satisfies
Thus products of the Paulis directly measured on an all-failure branch of a perfect strategy cannot form a nonzero stabilizer.
Proof. Suppose . Along this all-failure branch, let be the last batch meeting , and choose . Follow the same preceding history, including its measured values, make the only success in , and let every subsequent fusion fail. The full outcome-tree model of § 2.1 includes this continuation in the perfection requirement: every success/failure continuation of a fixed history is included, even if its probability is zero.
Every coordinate in has already been fused by the end of . Its failure basis is the same as on the original all-failure branch: the preceding history is unchanged, and all bases in were fixed before the outcomes of that round were known. Thus, writing for the final failure-basis assignment on the new branch,
By Lemma 4, the new branch fails logically despite the success at coordinate . This contradicts perfection.
Combining Lemmas 3 and 5, we obtain for every all-failure branch of a perfect strategy. Thus, its failure-basis span contains exactly one nonzero logical Pauli word.
Choosing the last batch meeting ensures that any later changes of basis cannot affect coordinates in the support of . The bases chosen after the success need not agree with those on the original all-failure branch. If the controller also uses individual measured values, the same argument applies after fixing those values in the rounds preceding the modified batch.
Graph Representations and Fusion Strategies
This section translates the necessary condition for a perfect fusion strategy derived in § 4 into a condition on graph adjacency. We first describe graph representations of a code and then construct a representation adapted to specified failure bases. Finally, an induced path from a successful coordinate to the root provides a way to complete the remaining fusions.
Graph Codes and Connectivity
Graph codes and the reference qubit. Let extract the Pauli component at the root. By Eq. (3), is obtained by restricting , the graph-state stabilizers acting trivially at the root, to the physical coordinates. Since every element of has zero root component, this restriction is injective and preserves isotropy. In particular, .
If the root is not isolated, is surjective: has root component X, while for any neighbor has root component Z. Since and , the rank-nullity theorem gives
To obtain such a representation for a general code , introduce a reference qubit . Choose physical representatives of logical Pauli classes with , and define, in ,
The space is the phase-free stabilizer subspace of the pure state obtained by placing the logical qubit and the reference qubit in a Bell pair. The root is a reference system used in the analysis; this construction does not add an ancillary photon to the fusion protocol. The two added generators commute because their anticommutation at the root and on the physical coordinates cancels:
They also commute with because . Thus
We call this construction a purification of . By the graph-state normal-form theorem, coordinate-wise symplectic maps take to a graph-state stabilizer subspace [5]. The root projection retains rank two, so the resulting root is not isolated. Taking the root-zero part gives a graph representation of .
Graph representations and the local-complementation orbit. The root projection of a purification has kernel and image . Each root component therefore determines a unique logical Pauli class of the physical component. Indeed,
Identifying the quotient naturally with a subspace of gives
Here denotes a symplectic isomorphism: associates the root Pauli operator with the code’s logical Pauli class . Indeed, isotropy of gives . If are the isomorphisms for two purifications, the root map takes the first purification to the second. Consequently, two graph codes are related by coordinatewise maps on the physical coordinates if and only if their graph states are related by coordinatewise maps including the root. For the reverse implication, take the root-zero part. By the local-Clifford equivalence theorem for graph states [5], this equivalence is generated by sequences of local complementations. This is why the set defined in § 2 forms a single local-complementation orbit. A map acting only on the root changes the logical basis but leaves the code on the physical coordinates unchanged.
Lemma 6 (Irreducibility and connectivity of graph codes). The graph code is irreducible if and only if is connected.
Thus graph connectivity characterizes the absence of a pure stabilizer subsystem detached from the logical qubit.
Proof. Let , and let denote its complement in the full vertex set , including the root. Here denotes the restriction of to , and is the submatrix of the adjacency matrix with rows indexed by and columns indexed by , describing the edges between these two sets.
Every element of has the form . For its support to lie entirely within , both its and components must vanish outside . Thus and . Since , the latter condition reduces to . Hence,
Since does not contain the root, every such element has zero root component. Its restriction to the physical coordinates therefore lies in .
Conversely, every element of uniquely lifts to an element of satisfying these conditions by restoring the zero root component. Thus is in one-to-one correspondence with , giving
Since exactly when no edge joins to ,
If is disconnected, choose a nonempty connected component not containing the root as . Then , violating irreducibility. Conversely, if is connected, every nonempty has an edge to , so . This is precisely the irreducibility condition.
Coordinatewise invertible maps preserve supports and . Every graph representation of an irreducible code is therefore connected.
Strategy-Adapted Graph Representations
To prove a lower bound for an arbitrary perfect fusion strategy, putting the code alone into graph form is not enough. We must also align the bases chosen along its all-failure branch so that the branch can be interpreted on the graph. The next lemma uses the condition from Lemma 5 to construct a graph representation in which all specified failure bases become .
For a pure stabilizer state, a full Pauli assignment whose span intersects the stabilizer subspace only at zero admits a graph representation mapping every assigned Pauli to [6], Definition 2.1 and Theorem 2.11. The proof below also supplies the root-basis choice needed to apply this correspondence to a code purification.
Lemma 7 (Graph form adapted to specified failure bases). Suppose that the full failure-basis assignment satisfies . Then there exist and a coordinatewise symplectic map that takes to and simultaneously takes every to .
The all-failure branch of any perfect fusion strategy can thus be represented as a graph-code strategy whose failure bases are all .
Proof. For in Eq. (11), set . In , the physical failure bases are fixed by , while the root component is unrestricted. Since and ,
The last line uses . Hence , and
Write this one-dimensional space as . The root component of its nonzero element is nonzero: otherwise . Choose
This choice will allow us to obtain a graph-state representation while keeping all specified bases mapped to .
Since , we obtain . For the specified nonzero Pauli at each coordinate, choose with . The linear map taking the basis to is invertible and symplectic. Set and
Because the same invertible map acts on both and ,
For the projection onto the component,
Thus is an isomorphism. Writing for the matrix of the linear map gives
Isotropy of implies, for every ,
and hence . Since the adjacency matrix of a simple graph must have zero diagonal, we remove the diagonal of . Set and apply the coordinatewise map
Since , this map is symplectic, and it fixes every element of . At each coordinate with , it simply applies the shear , which leaves the specified basis unchanged. Consequently,
The matrix is symmetric with zero diagonal and hence is a graph adjacency matrix. The rank of the root projection is preserved by local invertible maps and remains two, so the root is not isolated. The root-zero part is also carried from to . The restriction of to the physical coordinates is therefore the required map, transforming both the code and the specified bases.
Relabeling the strategy’s bases and measurement outcomes by the same map preserves its batches, number of rounds, and property of being perfect. A necessary condition on the resulting graph can therefore be transferred back to the original strategy.
Completing Logical Fusion via Induced Paths
For the upper bound, we use a procedure that finishes the remaining fusions in at most one round after the first success. An induced path is a path whose vertices induce no edges other than the path edges. If such a path connects a successful coordinate to the root and its internal vertices remain unfused, choosing failure basis at those vertices allows the success to yield recovery of the logical Bell parities. Edges from the path to other vertices are allowed; the graph need not be a tree.
Path-based measurement constructions appear in the tree-code strategy of Reiß and van Loock [3, Sec. V.F and Appendix H.4] and in the publicly available distance-ordered construction for general connected graph codes [4]. The next lemma formulates and proves the related path-completion step in our full outcome-tree model.
Lemma 8 (Completion along an induced path). Consider the graph code of . Suppose that all previous failure bases were Z, coordinate has succeeded, and there is an induced path
of length (the number of edges), whose internal vertices have not yet been fused. Fuse all remaining coordinates in one round, using failure basis X at the internal vertices of and Z elsewhere. Logical fusion succeeds regardless of the outcomes of this last round. If no coordinates remain, logical fusion has already succeeded.
Thus changing the bases inside the path suffices to complete logical fusion without requiring another physical fusion to succeed.
Proof. Throughout this proof, let . Sum the graph-state generators separately over the even and odd positions along the path:
The two path neighbors of each internal vertex contribute to the same sum, where their Z + Z = 0 contributions cancel the internal component. Because the path is induced, more distant path vertices contribute no additional Z there. The components along the path are therefore
| Coordinate | ||
| X | Z | |
| (, even) | X | 0 |
| (, odd) | 0 | X |
| ( even) | X | Z |
| ( odd) | Z | X |
Table 1.
Outside the path, none of the selected generators contributes an X component, so only 0 or Z can appear. Each endpoint has only one path neighbor, so the cancellation at internal vertices does not apply at the endpoints.
Let and be the restrictions to the physical coordinates. For every , we have , so isotropy gives
The two graph-state stabilizers commute, but their root components anticommute:
Hence , form a basis of the two-dimensional space . It is these logical Pauli classes that are independent; are their physical representatives.
Let be the final failure-basis span. For , the component table above shows that commutes with both and at every physical coordinate: at internal path vertices, only 0 and X occur; at the successful coordinate , we have ; and outside the path, only 0 and Z occur. Hence
If also , its logical Pauli class is orthogonal to both elements of a basis of :
Thus , and logical fusion succeeds by Lemma 2.
For example, on the length-two path ––, take and . The two Z contributions at cancel, giving and . This explains the choice of failure basis X at the internal vertex. For a length-one path, the interior is empty and the same proof applies. Other coordinates may succeed in the same batch as or in the last round. Each additional success merely sets the corresponding component of to zero and therefore preserves the orthogonality. If no coordinates remain unfused, the same inclusion already holds for the available .
Optimal Adaptive Fusion Rounds
We characterize the batch sequences that can occur on an all-failure branch and use this characterization to prove the main theorem. For necessity, we extract a graph from an arbitrary perfect strategy; for sufficiency, we construct a strategy using induced paths in that graph. Together, these directions determine the minimum number of rounds.
Characterization of Feasible Batch Sequences
Partition into nonempty batches , and write
We ask when this sequence can occur on an all-failure branch of a perfect strategy. The remaining batches may change after a success.
Proposition 9 (Batch sequences on all-failure branches). The following conditions are equivalent.
There exists a perfect strategy with an all-failure branch whose batches are , in that order.
There exists such that, for every and every ,
When these conditions hold, there exists a perfect strategy with the specified all-failure batch sequence that uses at most rounds on every branch.
Condition (13) requires each coordinate to be adjacent either to the root or to a coordinate fused in a later round. The proposition states that this condition, in a suitable graph representation, is necessary and sufficient for a perfect strategy with the specified all-failure batch sequence.
Proof. Necessity. Let be the failure-basis assignment along the specified all-failure branch. Lemmas 5 and 7 put the code in graph form while mapping every basis in to Z. Suppose that condition (13) fails for some . Then is not adjacent to , so the restriction belongs to .
Follow the same history, including the measured values, until just before batch . Consider a branch on which only succeeds in that batch and every subsequent fusion fails.
Since condition (13) fails, all neighbors of belong to and have therefore been fused by the end of round . Their failure bases are all Z, since the preceding history is unchanged and the bases within were fixed before its outcomes were known.
Let be the final failure-basis assignment on this branch. Then
By Lemma 4, logical fusion fails despite the physical success at , contradicting perfection.
Sufficiency. In graph coordinates satisfying (13), fuse the batches in failure basis Z until the first round containing a success. Let this be round , and choose one successful coordinate .
Within the subgraph induced by , start at and repeatedly move to the root or to a neighbor in a later batch. The batch index strictly increases at each step that does not reach the root, so condition (13) ensures that this process reaches . Choose a shortest path from to in this induced subgraph. It is also an induced path in , and all its internal vertices lie in and have not yet been fused. Lemma 8 completes fusion in at most one additional round. If , the total is at most rounds. If , condition (13) makes adjacent to , and no coordinates remain. The same lemma then gives success in rounds without an additional round. The all-failure branch follows the prescribed batches. Undoing the maps on the physical coordinates gives a perfect strategy for . □
Proof of the Main Theorem
We use Proposition 9 to prove the two inequalities in Theorem 1. A graph extracted from an arbitrary perfect strategy gives a lower bound on its number of rounds. Conversely, the distance layers of any graph representation give a strategy and hence an upper bound. We then exclude perfect strategies for reducible codes.
Proof of Theorem 1. Lower bound. Take a perfect strategy using at most rounds, and choose an all-failure branch with batches. Proposition 9 gives a graph satisfying (13). From any , following neighbors in later batches reaches in at most edges. Thus
Minimizing the worst-case round count over perfect strategies proves the lower bound.
Upper bound. If is irreducible, Lemma 6 implies that every graph in is connected. Choose one with root eccentricity . For , define the batches from the outermost distance layer inward:
These batches partition . A shortest path to a vertex at distance visits every distance , so no batch is empty. Every vertex at distance at least two has a neighbor one step closer to the root, in a later batch. Every vertex at distance one is adjacent to . Hence condition (13) holds, and Proposition 9 gives a perfect strategy using at most rounds. Minimizing over gives
Together with the lower bound, this yields equality in (4).
Reducible codes. Suppose that a reducible admitted a perfect strategy. The graph extracted in the lower-bound argument would satisfy (13). Following neighbors in later batches would connect every physical vertex to , making the graph connected. This contradicts Lemma 6, since coordinatewise maps preserve irreducibility.
The distance-layer construction also has a concrete physical interpretation. Consider the four-outcome measurement of a photon pair with rank-one projectors onto , , , and , where . The first two outcomes are fusion failures, reporting equal individual values on both photons; the latter two are successes, reporting two Bell parities. Applying the same single-qubit Clifford change of basis to both photons gives the corresponding measurement for any chosen Pauli failure basis. Thus the physical outcomes supply the Pauli information assumed in § 2.1.
Recovering both logical Bell parities is equivalent to unambiguously distinguishing the four encoded Bell states. To evaluate the logical success probability, choose each of the four encoded Bell inputs and with equal probability, where are an orthonormal logical basis of the code. An outcome branch identifies its input unambiguously if its outcomes have positive Born probability for exactly one of these four Bell states. Their uniform mixture is , with and the projector onto the code space. In graph coordinates, every failure basis along the all-failure branch of the distance-layer strategy is . A graph code has no nonidentity purely -type stabilizer, so the complete -outcome string of each block is uniformly distributed, with . The two blocks are independent under , and all fusions fail precisely when their -outcome strings agree. Consequently,
The distance-layer strategy recovers both logical Bell parities on every branch containing a physical success, by the perfection already proved above. On an all-failure branch with failure-basis assignment , Lemma 3 gives a nontrivial logical Pauli . The corresponding Pauli operator on the first block commutes with every measured projector, while mapping each encoded Bell state to a different one. Thus the branch has the same probability for two distinct Bell inputs and cannot identify the logical Bell state. Hence, for the four encoded Bell inputs chosen uniformly, the average probability of unambiguously identifying the logical Bell state is exactly . Thus the round-optimal distance-layer strategy of Theorem 1 is physically realizable with this fusion measurement and attains this success probability. The theorem’s round-count lower bound concerns perfect strategies in the full outcome-tree model of § 2.1.
Examples
Two codes illustrate what the main theorem optimizes. The first shows how changing the graph representation reduces the number of rounds in a strategy built from distance layers. The second requires at least two rounds for any perfect strategy in our full outcome-tree model.
Optimization over Graph Representations
Consider the path –1–2–3. Its root eccentricity is three, giving the distance-layer batches , , . For example, if coordinate 3 succeeds first, fuse the remaining coordinates 1, 2 in one round with failure basis X. If the first two rounds fail and coordinate 1 succeeds in the third, the success at a neighbor of the root completes logical fusion.
This three-round construction is not optimal for the code. Local complementation at vertex 2 adds edge 13, reducing the root eccentricity to two. Local complementation at vertex 1 then adds edges e2, e3 and removes edge 23. The root is now adjacent to all three physical vertices (Figure 2). This representation has root eccentricity one, so the same code has . The failure bases for the one-round strategy on the original code are obtained by undoing the coordinatewise maps. Thus the strategy from the original graph uses three rounds in the worst case, whereas optimization over the graph orbit gives a single round without feed-forward.

Figure 2. Three graph representations of the same code. The operation denotes local complementation at vertex . The root eccentricity decreases from three to two to one. Although the original path has three nonempty distance layers, the theorem gives a perfect one-round strategy.
A Code Requiring Two Fusion Rounds
Consider the octahedral graph with parts , , and root . It is connected, so the corresponding five-qubit code is irreducible. In physical-coordinate order , its stabilizer subspace is
This code is locally Clifford equivalent to the five-qubit example in Ref. [2 Section 5] that admits no perfect nonadaptive fusion strategy. We use it to illustrate Theorem 1 by determining the minimum root eccentricity over its graph orbit.
Root eccentricity. This graph has , since is the only physical vertex not adjacent to . To rule out eccentricity one, start from and repeatedly apply local complementation at each of the six labeled vertices, retaining each distinct graph until the orbit is closed. The orbit contains 40 labeled graphs; their root degrees are 1, 2, 3, 4 with respective multiplicities 10, 8, 12, 10. In particular, the root is never adjacent to all five physical vertices. Thus , and Theorem 1 gives .
Explicit strategy. First fuse in failure basis Z, and choose the second round according to its outcome.
If fails, fuse in failure basis Z. All four vertices are adjacent to the root. If any one succeeds, the length-one path from that coordinate to the root satisfies Lemma 8, so logical fusion succeeds.
If succeeds, use the induced path –– and fuse in failure basis X and in failure basis Z. Lemma 8 gives recovery for every combination of successes and failures in the second round.
This strategy fuses all coordinates in two rounds on every branch, and logical fusion succeeds whenever at least one physical fusion succeeds. It realizes the optimum given by Theorem 1; one feed-forward step between fusion rounds is necessary in our model.
Conclusion
For an irreducible stabilizer code, we have shown that the minimum worst-case number of measurement rounds for perfect fusion equals the minimum root eccentricity over its rooted graph representations. The lower bound applies to arbitrary perfect strategies that adapt their batches and failure bases to previous outcomes. We also give a necessary and sufficient graph adjacency condition for a batch sequence to occur on an all-failure branch of a perfect strategy.
These results determine the optimal number of measurement rounds for fusion strategies that allow FF and provide both a strategy attaining that number and a proof that fewer rounds cannot be perfect. They do not directly optimize hardware latency: measurement times, FF processing times, and storage costs between rounds are not specified.
The results apply to the full outcome-tree model of § 2.1, which includes zero-probability branches. Restricting to positive-probability branches for a particular input state and measurement device gives a different optimization problem.
Acknowledgments
This work was supported in part by JST Moonshot R&D Grant Number JPMJMS256F and in part by the MITOU Target Program of the Information-technology Promotion Agency, Japan (IPA).
Author Contributions
Seita Tsuboi led the research. Takuya Kasamura, Leo Itoh, Motoharu Tsuboi, and Tomohiro Hatori contributed to research discussions and to reviewing and verifying the mathematical arguments. Junichiro Kadomoto supervised the research.
Large language models were used for mathematical exploration and checking, assistance with code and calculations, literature checking, drafting and revising the manuscript, and preparing LaTeX and figures. The tools used include Claude and OpenAI Codex.
References
References
- [1]S. Bartolucci et al., Fusion-based quantum computation, Nature Communications 14, 912 (2023). doi:10.1038/s41467-023-36493-1.DOI
- [2]K. Goodenough, A. Landahl, J. Lee, A. Russo, and K. Thompson, Optimal fusion strategies for quantum computation, arXiv:2609.02559v2 (2026). doi:10.48550/arXiv.2609.02559.DOI
- [3]S. D. Reiß and P. van Loock, Optimal logical Bell measurements on stabilizer codes with linear optics, Physical Review A 114, 032421 (2026); arXiv:2601.08820v1. doi:10.1103/qj8s-j274.
- [4]the-omega-institute/trueturing, GitHub pull request #13260, merged October 5, 2026. Machine-generated Lean proof of a perfect sequential adaptive fusion construction for connected graph codes; not peer reviewed. Pinned merge commit: 28bd2b5. See declarations claim and result in Connected ProgenitorPerfectAdaptiveFusion.lean under D5/S3/Quantum/Measurements.
- [5]M. Van den Nest, J. Dehaene, and B. De Moor, Graphical description of the action of local Clifford transformations on graph states, Physical Review A 69, 022316 (2004). doi:10.1103/PhysRevA.69.022316.DOI
- [6]K. Goodenough, What are local complementations, really? arXiv:2611.08620v1 (2026). doi:10.48550/arXiv.2611.08620.DOI