betaFeedback

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 R∗(S)R^{*}(S) denote the minimum worst-case number of rounds among perfect strategies for a code SS. For irreducible [[n,1]][[n,1]] stabilizer codes, we prove

R∗(S)=min⁡Γ∈G(S)ecc⁡Γ(e).R^{*}(S)=\min_{\Gamma\in\mathcal{G}(S)} \operatorname{ecc}_{\Gamma}(e).

Here the root ee represents the encoded qubit, and G(S)\mathcal{G}(S) is the set of rooted graph representations of the code, which forms a single local-complementation orbit. The root eccentricity ecc⁡(e)\operatorname{ecc}(e) is the largest shortest-path distance from ee 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 [[n,1]][[n,1]] 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 F2\mathbb{F}_2 for the binary field; all vector and matrix arithmetic below is over this field. Pauli words on nn physical qubits, modulo phase, are represented by vectors in V=(F22)nV = (\mathbb{F}_2^2)^n. We use the equivalent notations

v=((x1,z1),…,(xn,zn))≡(x∣z),v = ((x_1,z_1),\ldots,(x_n,z_n)) \equiv(x \mid z),

where x,z∈F2nx,z \in\mathbb{F}_2^n and vi=(xi,zi)∈F22v_i=(x_i,z_i)\in\mathbb{F}_2^2 is the two-bit component at coordinate ii. At one coordinate,

X=(1,0),Z=(0,1),X=(1,0),\quad Z=(0,1),
Y=(1,1),I=(0,0).Y=(1,1),\quad I=(0,0).

Vector addition corresponds to multiplication of Pauli words modulo phase. We write [n]={1,2,…,n}[n]=\{1,2,\ldots,n\}. The support is

supp⁡(v)={i∈[n]:vi≠(0,0)}.\operatorname{supp}(v)=\{i\in[n]:v_i\ne(0,0)\}.

For A⊆[n]A\subseteq[n], let VAV_A be the subspace of vectors that vanish outside AA.

The symplectic form

ω((x,z),(x′,z′))=x⋅z′+z⋅x′\omega((x,z),(x',z'))=x\cdot z'+z\cdot x'

is zero for commuting Pauli words and one for anticommuting words. An [[n,1]][[n,1]] stabilizer code, encoding one logical qubit, is represented by an isotropic subspace S⊂VS\subset V of dimension n−1n-1. Isotropy means ω(s,t)=0\omega(s,t)=0 for all s,t∈Ss,t\in S, expressing commutativity of the stabilizers.

Let N=S⊥VN=S^{\perp_V} 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

[u]=u+S∈N/S(u∈N).[u]=u+S\in N/S\qquad(u\in N).

The quotient N/SN/S is a two-dimensional nondegenerate symplectic space with form

ωˉ([u],[v])=ω(u,v).\bar{\omega}([u],[v])=\omega(u,v).

We call its elements logical Pauli classes; nonzero classes represent nontrivial logical Pauli operators. A physical representative u∈N∖Su\in N\setminus S is a nontrivial logical word, or simply a logical word. Thus uu is a vector in the physical space VV, whereas [u][u] belongs to the quotient.

We call SS irreducible if

dim⁡(S∩VA)<∣A∣(∅≠A⊆[n]).(1)\dim(S\cap V_A)<|A|\qquad(\varnothing\ne A\subseteq[n]). \tag*{(1)}

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 ii denotes a pair containing one photon from each block. Its failure basis is chosen from X,Y,ZX,Y,Z. 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 (FFFF).

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 Πperf(S)\Pi_{\mathrm{perf}}(S) be the set of perfect fusion strategies for SS, and let B(π)\mathcal{B}(\pi) be the set of outcome branches of a strategy π\pi. Write Rπ(b)R_{\pi}(b) for the number of nonempty batches executed on branch b∈B(π)b \in\mathcal{B}(\pi). We minimize the worst-case number of rounds:

R∗(S)=min⁡π∈Πperf(S)max⁡b∈B(π)Rπ(b).(2)R^{*}(S)=\min_{\pi\in\Pi_{\mathrm{perf}}(S)}\max_{b\in\mathcal{B}(\pi)}R_{\pi}(b). \tag*{(2)}

Set R∗(S)=∞R^{*}(S)=\infty if no perfect strategy exists.

One round requires no FF; RR rounds use at most R−1R-1 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 Γ\Gamma be a simple graph on the fixed labeled vertex set {e}⊔[n]\{e\}\sqcup[n], with ee nonisolated. Use the same symbol for its binary adjacency matrix. The graph-state stabilizer subspace is

WΓ={(a,Γa):a∈F2n+1},W_{\Gamma}=\{(a,\Gamma a):a\in\mathbb{F}_{2}^{n+1}\},

generated by hv=Xv∏u∈NΓ(v)Zuh_v=X_v\prod_{u\in N_{\Gamma}(v)}Z_u, where NΓ(v)N_{\Gamma}(v) is the neighborhood of vv. The corresponding graph code is

SΓ={w∣[n]:w∈WΓ, we=0}.(3)S_{\Gamma}=\{w|_{[n]}:w\in W_{\Gamma},\ w_e=0\}. \tag*{(3)}

The root ee 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 X,Y,ZX,Y,Z at each physical coordinate. Let G(S)\mathcal{G}(S) be the set of rooted graphs whose graph codes are related to SS by such maps. This set is nonempty and is exactly one local-complementation orbit, as explained in § 5.1. Local complementation at a vertex vv toggles the edges between distinct neighbors of vv. Local complementation at the root is allowed, but vertex permutations are not included in the operations generating this orbit. The root eccentricity is

ecc⁡Γ(e)=max⁡i∈[n]dist⁡Γ(e,i).\operatorname{ecc}_{\Gamma}(e)=\max_{i\in[n]}\operatorname{dist}_{\Gamma}(e,i).

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 [[n,1]][[n,1]] code with n≥1n\ge1 satisfies

R∗(S)=min⁡Γ∈G(S)ecc⁡Γ(e).(4)R^{*}(S)=\min_{\Gamma\in\mathcal{G}(S)}\operatorname{ecc}_{\Gamma}(e). \tag*{(4)}

Reducible codes admit no perfect strategy in this model.

In particular, the one-round case is

R∗(S)=1⟺∃Γ∈G(S):NΓ(e)=[n].R^{*}(S)=1\quad\Longleftrightarrow\quad\exists\Gamma\in\mathcal{G}(S):\mathcal{N}_{\Gamma}(e)=[n].

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 S∩Fq={0}S\cap F_q=\{0\} 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.

Main dependencies in the proof

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 D⊆[n]D\subseteq[n] be the failed coordinates on a branch, and write r=(ri)i∈D\mathbf{r}=(r_i)_{i\in D} for their chosen failure bases. At each i∈Di\in D, the Pauli rir_i is measured individually in each block. Represent these operators by phase-free vectors. We call the binary linear subspace they generate,

Fr={∑i∈Dciυi(ri):ci∈F2},(5)F_{\mathbf{r}}=\left\{\sum_{i\in D}c_i\upsilon_i(r_i):c_i\in\mathbb{F}_2\right\}, \tag*{(5)}

the failure-basis span. Here υi\upsilon_i embeds a one-coordinate vector into coordinate ii of VV:

υi(p)=(0,…,0,p,0,…,0).\upsilon_i(p)=(0,\ldots,0,p,0,\ldots,0).

Each coefficient cic_i specifies whether the Pauli rir_i occurs in the product. Thus a word in FrF_{\mathbf{r}} has letter 0 or rir_i at each i∈Di\in D 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 u∈Fru\in F_{\mathbf{r}}, 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 J=[n]∖DJ=[n]\setminus D be the successful coordinates. The physical measurement outcomes determine the inter-block parity associated with every Pauli word in

M=VJ+Fr.M=V_J+F_r.

For words in FrF_r, 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 MM that belong to NN and identify words that differ by a stabilizer. The recoverable logical Bell parities are described by

B=(N∩M)+S⊆N,Q=B/S⊆N/S.(6)\begin{aligned} B&=(N\cap M)+S\subseteq N,\\ Q&=B/S\subseteq N/S. \tag*{(6)} \end{aligned}

Here BB is a space of physical representatives, whereas QQ is a space of logical Pauli classes; they belong to different ambient spaces. The measured signs ±1\pm1 give the parity values, while the subspace QQ specifies which parities are recoverable. Logical Bell measurement succeeds exactly when Q=N/SQ=N/S. 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 Fr⊆VF_r\subseteq V contains a logical word, that is, a physical representative in N∖SN\setminus S. 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

Fr∩N⊆S.(7)F_r\cap N\subseteq S. \tag*{(7)}

Equivalently, FrF_r contains no element of N∖SN\setminus S.

This condition means that products of the Paulis directly measured at failed coordinates cannot form a nontrivial logical word.

Proof. Rather than test Q=N/SQ=N/S directly, we compute the orthogonal complement of QQ in the logical quotient. Every orthogonal complement with subscript VV below is taken in the physical space VV. At a single coordinate, the symplectic orthogonal complement of F22\mathbb{F}_2^2 is {0}\{0\}, corresponding to the identity Pauli II, while that of any one-dimensional subspace is the subspace itself. The local subspace of MM is F22\mathbb{F}_2^2 at each successful coordinate and F2riF_{2r_i} at each failed coordinate, so

M⊥V=Fr.M^{\perp_V}=F_r.

The identities for subspaces A,C⊆VA,C\subseteq V,

(A+C)⊥V=A⊥V∩C⊥V,(A∩C)⊥V=A⊥V+C⊥V,\begin{aligned} (A+C)^{\perp_V}&=A^{\perp_V}\cap C^{\perp_V},\\ (A\cap C)^{\perp_V}&=A^{\perp_V}+C^{\perp_V}, \end{aligned}

together with N⊥V=SN^{\perp_V}=S, give

B⊥V=((N∩M)+S)⊥V=(S+Fr)∩N=S+(Fr∩N).(8)\begin{aligned} B^{\perp_V} &=((N\cap M)+S)^{\perp_V}\\ &=(S+F_r)\cap N\\ &=S+(F_r\cap N). \tag*{(8)} \end{aligned}

The last equality uses S⊆NS\subseteq N. Moreover, S⊆B⊆NS\subseteq B\subseteq N implies S⊆B⊥V⊆NS\subseteq B^{\perp_V}\subseteq N. Hence the orthogonal complement in the logical quotient N/SN/S is

Q⊥ωˉ=B⊥V/S.Q^{\perp_{\bar{\omega}}}=B^{\perp_V}/S.

Since the form on N/SN/S is nondegenerate,

Q=N/S⟺Q⊥ωˉ=0⟺B⊥V=S.\begin{aligned} Q=N/S&\Longleftrightarrow Q^{\perp_{\bar{\omega}}}=0\\ &\Longleftrightarrow B^{\perp_V}=S. \end{aligned}

By Eq. (8), the last condition is equivalent to Fr∩N⊆SF_r\cap N\subseteq S. □\square

Next, independently of the actual success or failure outcomes, consider an assignment q=(qi)i∈[n]q=(q_i)_{i\in[n]} of one Pauli basis to every coordinate. The associated failure-basis span FqF_q is Eq. (5) with D=[n]D=[n]. It is a maximal isotropic, or Lagrangian, subspace satisfying

dim⁡Fq=n,Fq⊥V=Fq.\dim F_q=n,\qquad F_q^{\perp_V}=F_q.

Here qq 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 FqF_q.

The next lemma is the k=1k=1 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 qq of bases to all coordinates,

dim⁡(Fq∩N)=1+dim⁡(Fq∩S).(9)\dim(F_q \cap N) = 1 + \dim(F_q \cap S). \tag*{(9)}

In particular, Fq∩(N∖S)≠∅F_q \cap(N \setminus S) \ne\varnothing.

Thus, for any full basis assignment, the products of the assigned Paulis include a nontrivial logical word.

Proof. Since FqF_q is a Lagrangian subspace of dimension nn,

(Fq+S)⊥V=Fq∩N.(F_q + S)^{\perp_V} = F_q \cap N.

Applying the dimension formulas for a sum and an orthogonal complement gives

dim⁡(Fq+S)=2n−1−dim⁡(Fq∩S),\dim(F_q + S) = 2n - 1 - \dim(F_q \cap S),
dim⁡(Fq∩N)=2n−dim⁡(Fq+S)=1+dim⁡(Fq∩S).\begin{aligned} \dim(F_q \cap N) &= 2n - \dim(F_q + S) \\ &= 1 + \dim(F_q \cap S). \end{aligned}

If Fq∩NF_q \cap N were contained in SS, then Fq∩N=Fq∩SF_q \cap N = F_q \cap S, contradicting the difference of one in their dimensions. □\square

On an all-failure branch, a logical word in FqF_q 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 1/21/2, the success probability is 1−2−n1 - 2^{-n}. 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 ii succeeds. Let rr be the chosen failure bases on [n]∖{i}[n] \setminus\{i\} and FrF_r the corresponding failure-basis span. If some s∈Ss \in S satisfies

si≠0,s−ιi(si)∈Fr,s_i \ne0,\qquad s - \iota_i(s_i) \in F_r,

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 FrF_r supported away from the successful coordinate.

Proof. Extend rr to an assignment r′r' on all coordinates by choosing basis sis_i at coordinate ii. Lemma 3 gives w∈Fr′∩(N∖S)w \in F_{r'} \cap(N \setminus S). If wi=0w_i = 0, then w∈Frw \in F_r already. Otherwise wi=siw_i = s_i, so adding the stabilizer ss gives

(w+s)i=si+si=0,(w + s)_i = s_i + s_i = 0,
[w+s]=[w]≠0.[w + s] = [w] \ne0.

The other components remain aligned with the bases rr, hence w+s∈Fr∩(N∖S)w + s \in F_r \cap(N \setminus S). In either case, FrF_r contains a nontrivial logical word, and Lemma 2 implies logical failure. □\square

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 qq denote the bases used on it. If FqF_q 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 qq be the basis assignment on any all-failure branch of a perfect strategy. The corresponding failure-basis span FqF_q satisfies

S∩Fq={0}.(10)S \cap F_q = \{0\}. \tag*{(10)}

Thus products of the Paulis directly measured on an all-failure branch of a perfect strategy cannot form a nonzero stabilizer.

Proof. Suppose 0≠s∈S∩Fq0 \ne s \in S \cap F_q. Along this all-failure branch, let TkT_k be the last batch meeting supp⁡s\operatorname{supp}s, and choose i∈Tk∩supp⁡si \in T_k \cap\operatorname{supp}s. Follow the same preceding history, including its measured values, make ii the only success in TkT_k, 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 supp⁡s∖{i}\operatorname{supp}s \setminus\{i\} has already been fused by the end of TkT_k. Its failure basis is the same as on the original all-failure branch: the preceding history is unchanged, and all bases in TkT_k were fixed before the outcomes of that round were known. Thus, writing rr for the final failure-basis assignment on the new branch,

s−ιi(si)∈Fr.s-\iota_i(s_i) \in F_r.

By Lemma 4, the new branch fails logically despite the success at coordinate ii. This contradicts perfection.

Combining Lemmas 3 and 5, we obtain dim⁡(Fq∩N)=1\dim(F_q \cap N)=1 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 supp⁡s\operatorname{supp}s ensures that any later changes of basis cannot affect coordinates in the support of ss. 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 πe:WΓ→Ve\pi_e: W_\Gamma\to V_e extract the Pauli component at the root. By Eq. (3), SΓS_\Gamma is obtained by restricting ker⁡πe\ker\pi_e, the graph-state stabilizers acting trivially at the root, to the physical coordinates. Since every element of ker⁡πe\ker\pi_e has zero root component, this restriction is injective and preserves isotropy. In particular, dim⁡SΓ=dim⁡ker⁡πe\dim S_\Gamma=\dim\ker\pi_e.

If the root is not isolated, πe\pi_e is surjective: heh_e has root component X, while hvh_v for any neighbor vv has root component Z. Since dim⁡WΓ=n+1\dim W_\Gamma=n+1 and dim⁡Ve=2\dim V_e=2, the rank-nullity theorem gives

dim⁡SΓ=dim⁡ker⁡πe=(n+1)−2=n−1.\dim S_\Gamma=\dim\ker\pi_e=(n+1)-2=n-1.

To obtain such a representation for a general code SS, introduce a reference qubit ee. Choose physical representatives LX,LZ∈NL_X,L_Z\in N of logical Pauli classes with ω(LX,LZ)=1\omega(L_X,L_Z)=1, and define, in V~:=Ve⊕V\widetilde V:=V_e\oplus V,

W=(0⊕S)+span⁡{(X,LX),(Z,LZ)}.(11)W=(0\oplus S)+\operatorname{span}\{(X,L_X),(Z,L_Z)\}. \tag*{(11)}

The space WW 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:

ωV~((X,LX),(Z,LZ))=1+1=0.\omega_{\widetilde V}((X,L_X),(Z,L_Z))=1+1=0.

They also commute with 0⊕S0\oplus S because LX,LZ∈NL_X,L_Z\in N. Thus

dim⁡W=n+1,W=W⊥V~,\dim W=n+1,\qquad W=W^{\perp_{\widetilde V}},
W∩(0⊕V)=0⊕S.W\cap(0\oplus V)=0\oplus S.

We call this construction a purification of SS. By the graph-state normal-form theorem, coordinate-wise symplectic maps take WW 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 SS.

Graph representations and the local-complementation orbit. The root projection of a purification WW has kernel 0⊕S0\oplus S and image VeV_e. Each root component p∈Vep\in V_e therefore determines a unique logical Pauli class [L]∈N/S[L]\in N/S of the physical component. Indeed,

(p,L1),(p,L2)∈W⟹(0,L1+L2)∈0⊕S(p,L_1),(p,L_2)\in W \Longrightarrow(0,L_1+L_2)\in0\oplus S
⟹[L1]=[L2].\Longrightarrow[L_1]=[L_2].

Identifying the quotient naturally with a subspace of Ve⊕(N/S)V_e \oplus(N/S) gives

W/(0⊕S)={(p,ϕ(p)):p∈Ve},W/(0 \oplus S) = \{(p,\phi(p)) : p \in V_e\},
ϕ:Ve→≅N/S.\phi: V_e \xrightarrow{\cong} N/S.

Here ≅\cong denotes a symplectic isomorphism: ϕ\phi associates the root Pauli operator pp with the code’s logical Pauli class ϕ(p)\phi(p). Indeed, isotropy of WW gives ω‾(ϕ(p),ϕ(p′))=ωe(p,p′)\overline{\omega}(\phi(p),\phi(p')) = \omega_e(p,p'). If ϕ1,ϕ2\phi_1,\phi_2 are the isomorphisms for two purifications, the root map ϕ2−1ϕ1\phi_2^{-1}\phi_1 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 G(S)\mathcal{G}(S) 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 SΓS_\Gamma is irreducible if and only if Γ\Gamma is connected.

Thus graph connectivity characterizes the absence of a pure stabilizer subsystem detached from the logical qubit.

Proof. Let ∅≠A⊆[n]\varnothing\ne A \subseteq[n], and let AcA^c denote its complement in the full vertex set {e}⊔[n]\{e\}\sqcup[n], including the root. Here aAa_A denotes the restriction of aa to AA, and ΓAc,A\Gamma_{A^c,A} is the submatrix of the adjacency matrix Γ\Gamma with rows indexed by AcA^c and columns indexed by AA, describing the edges between these two sets.

Every element of WΓW_\Gamma has the form (a,Γa)(a,\Gamma a). For its support to lie entirely within AA, both its XX and ZZ components must vanish outside AA. Thus aAc=0a_{A^c}=0 and (Γa)Ac=0(\Gamma a)_{A^c}=0. Since aAc=0a_{A^c}=0, the latter condition reduces to (Γa)Ac=ΓAc,AaA=0(\Gamma a)_{A^c}=\Gamma_{A^c,A}a_A=0. Hence,

supp⁡(a,Γa)⊆A⟺{aAc=0,ΓAc,AaA=0.\operatorname{supp}(a,\Gamma a) \subseteq A \Longleftrightarrow \begin{cases} a_{A^c}=0,\\ \Gamma_{A^c,A}a_A=0. \end{cases}

Since AA does not contain the root, every such element has zero root component. Its restriction to the physical coordinates therefore lies in SΓ∩VAS_\Gamma\cap V_A.

Conversely, every element of SΓ∩VAS_\Gamma\cap V_A uniquely lifts to an element of WΓW_\Gamma satisfying these conditions by restoring the zero root component. Thus SΓ∩VAS_\Gamma\cap V_A is in one-to-one correspondence with ker⁡ΓAc,A\ker\Gamma_{A^c,A}, giving

dim⁡(SΓ∩VA)=∣A∣−rank⁡F2ΓAc,A.(12)\dim(S_\Gamma\cap V_A) = |A| - \operatorname{rank}_{\mathbb{F}_2}\Gamma_{A^c,A}. \tag*{(12)}

Since ΓAc,A=0\Gamma_{A^c,A}=0 exactly when no edge joins AA to AcA^c,

dim⁡(SΓ∩VA)=∣A∣\dim(S_\Gamma\cap V_A)=|A|
⟺no edge joins A to Ac.\Longleftrightarrow\quad\text{no edge joins } A \text{ to } A^c.

If Γ\Gamma is disconnected, choose a nonempty connected component not containing the root as AA. Then dim⁡(SΓ∩VA)=∣A∣\dim(S_\Gamma\cap V_A)=|A|, violating irreducibility. Conversely, if Γ\Gamma is connected, every nonempty A⊆[n]A\subseteq[n] has an edge to AcA^c, so dim⁡(SΓ∩VA)<∣A∣\dim(S_\Gamma\cap V_A)<|A|. This is precisely the irreducibility condition. □\square

Coordinatewise invertible maps preserve supports and dim⁡(S∩VA)\dim(S\cap V_A). 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 ZZ.

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 ZZ [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 q=(qi)i∈[n]q=(q_i)_{i\in[n]} satisfies S∩Fq={0}S\cap F_q=\{0\}. Then there exist Γ∈G(S)\Gamma\in\mathcal{G}(S) and a coordinatewise symplectic map that takes SS to SΓS_\Gamma and simultaneously takes every qiq_i to ZZ.

The all-failure branch of any perfect fusion strategy can thus be represented as a graph-code strategy whose failure bases are all ZZ.

Proof. For W⊆V~W \subseteq\widetilde{V} in Eq. (11), set U=Ve⊕FqU = V_e \oplus F_q. In UU, the physical failure bases are fixed by qq, while the root component is unrestricted. Since Fq⊥Ve=FqF_q^{\perp_{V_e}} = F_q and S∩Fq={0}S \cap F_q = \{0\},

U⊥V~=0⊕Fq,U^{\perp_{\widetilde{V}}} = 0 \oplus F_q,
W∩U⊥V~=(0⊕S)∩(0⊕Fq)={0},W \cap U^{\perp_{\widetilde{V}}} = (0 \oplus S) \cap(0 \oplus F_q) = \{0\},
(W+U)⊥V~=W∩U⊥V~={0}.(W + U)^{\perp_{\widetilde{V}}} = W \cap U^{\perp_{\widetilde{V}}} = \{0\}.

The last line uses W⊥V~=WW^{\perp_{\widetilde{V}}} = W. Hence W+U=V~W + U = \widetilde{V}, and

dim⁡(W∩U)=dim⁡W+dim⁡U−dim⁡V~=(n+1)+(n+2)−(2n+2)=1.\begin{aligned} \dim(W \cap U) = \dim W + \dim U - \dim\widetilde{V} \\ &= (n + 1) + (n + 2) - (2n + 2) = 1. \end{aligned}

Write this one-dimensional space as W∩U=F2(p,L)W \cap U = \mathbb{F}_2(p,L). The root component pp of its nonzero element is nonzero: otherwise L∈S∩Fq={0}L \in S \cap F_q = \{0\}. Choose

qe∈F22∖{0,p},F~=F2qe⊕Fq⊆U.q_e \in\mathbb{F}_2^2 \setminus\{0,p\}, \qquad\widetilde{F} = \mathbb{F}_2q_e \oplus F_q \subseteq U.

This choice will allow us to obtain a graph-state representation while keeping all specified bases mapped to ZZ.

W∩F~⊆W∩U={(0,0),(p,L)}.W \cap\widetilde{F} \subseteq W \cap U = \{(0,0),(p,L)\}.

Since (p,L)∉F~(p,L) \notin\widetilde{F}, we obtain W∩F~={0}W \cap\widetilde{F} = \{0\}. For the specified nonzero Pauli qvq_v at each coordinate, choose tvt_v with ω(qv,tv)=1\omega(q_v,t_v)=1. The linear map TvT_v taking the basis qv,tvq_v,t_v to Z,XZ,X is invertible and symplectic. Set T=⨁v∈{e}⊔[n]TvT = \bigoplus_{v\in\{e\}\sqcup[n]} T_v and

W^=T(W),\widehat{W} = T(W),
Z=T(F~)={(0,z):z∈F2n+1}.\mathcal{Z} = T(\widetilde{F}) = \{(0,z):z \in\mathbb{F}_2^{n+1}\}.

Because the same invertible map acts on both WW and F~\widetilde{F},

W^∩Z=T(W)∩T(F~)=T(W∩F~)={0}.\begin{aligned} \widehat{W} \cap\mathcal{Z} = T(W) \cap T(\widetilde{F}) \\ &= T(W \cap\widetilde{F}) = \{0\}. \end{aligned}

For the projection πx:W^→F2n+1\pi_x:\widehat{W}\to\mathbb{F}_2^{n+1} onto the xx component,

ker⁡πx=W^∩Z={0},\ker\pi_x = \widehat{W} \cap\mathcal{Z} = \{0\},
dim⁡W^=dim⁡F2n+1=n+1.\dim\widehat{W} = \dim\mathbb{F}_2^{n+1} = n+1.

Thus πx\pi_x is an isomorphism. Writing GG for the matrix of the linear map πzπx−1\pi_z\pi_x^{-1} gives

W^={(a,Ga):a∈F2n+1}.\widehat{W} = \{(a,Ga):a \in\mathbb{F}_2^{n+1}\}.

Isotropy of W^\widehat{W} implies, for every a,b∈F2n+1a,b \in\mathbb{F}_2^{n+1},

0=ω((a,Ga),(b,Gb))=aT(G+GT)b,\begin{aligned} 0 = \omega((a,Ga),(b,Gb)) \\ &= a^{\mathsf{T}}(G+G^{\mathsf{T}})b, \end{aligned}

and hence G=GTG=G^{\mathsf{T}}. Since the adjacency matrix of a simple graph must have zero diagonal, we remove the diagonal of GG. Set DG=diag⁡(Gvv)D_G=\operatorname{diag}(G_{vv}) and apply the coordinatewise map

C:(x,z)⟼(x,z+DGx).C:(x,z)\longmapsto(x,z+D_Gx).

Since DG=DGTD_G=D_G^{\mathsf{T}}, this map is symplectic, and it fixes every element of Z\mathcal{Z}. At each coordinate with Gvv=1G_{vv}=1, it simply applies the shear (xv,zv)⟼(xv,zv+xv)(x_v,z_v)\longmapsto(x_v,z_v+x_v), which leaves the specified basis ZZ unchanged. Consequently,

C(W^)={(a,Γa):a∈F2n+1}=WΓ,C(\widehat{W})=\{(a,\Gamma a):a\in\mathbb{F}_2^{n+1}\}=W_\Gamma,
Γ=G+DG.\Gamma=G+D_G.

The matrix Γ\Gamma 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 0⊕S0\oplus S to 0⊕SΓ0\oplus S_\Gamma. The restriction of CTCT 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 XX 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 Γ\Gamma. Suppose that all previous failure bases were Z, coordinate ii has succeeded, and there is an induced path

P=(e=v0,v1,…,vℓ=i)P = (e = v_0, v_1, \ldots, v_\ell= i)

of length ℓ\ell (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 PP 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 N=SΓ⊥N = S_{\Gamma}^{\perp}. Sum the graph-state generators hvjh_{v_j} separately over the even and odd positions along the path:

wev=∑0≤j≤ℓj evenhvj,w_{\mathrm{ev}} = \sum_{\substack{0 \le j \le\ell\\ j\ \mathrm{even}}} h_{v_j},
wodd=∑0≤j≤ℓj oddhvj.w_{\mathrm{odd}} = \sum_{\substack{0 \le j \le\ell\\ j\ \mathrm{odd}}} h_{v_j}.

The two path neighbors of each internal vertex contribute to the same sum, where their Z + Z = 0 contributions cancel the internal zz component. Because the path is induced, more distant path vertices contribute no additional Z there. The components along the path are therefore

Coordinatewevw_{\mathrm{ev}}woddw_{\mathrm{odd}}
e=v0e = v_0XZ
vjv_j (0<j<ℓ0 < j < \ell, jj even)X0
vjv_j (0<j<ℓ0 < j < \ell, jj odd)0X
i=vℓi = v_\ell (ℓ\ell even)XZ
i=vℓi = v_\ell (ℓ\ell odd)ZX

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 Lev=wev∣[n]L_{\mathrm{ev}} = w_{\mathrm{ev}}|_{[n]} and Lodd=wodd∣[n]L_{\mathrm{odd}} = w_{\mathrm{odd}}|_{[n]} be the restrictions to the physical coordinates. For every s∈SΓs \in S_{\Gamma}, we have (0,s)∈WΓ(0,s) \in W_{\Gamma}, so isotropy gives

ω(Lev,s)=ω(Lodd,s)=0,\omega(L_{\mathrm{ev}},s) = \omega(L_{\mathrm{odd}},s) = 0,
Lev,Lodd∈N.L_{\mathrm{ev}},L_{\mathrm{odd}} \in N.

The two graph-state stabilizers commute, but their root components anticommute:

0=ωΓ~(wev,wodd)=ωe(X,Z)+ω(Lev,Lodd),0 = \omega_{\widetilde{\Gamma}}(w_{\mathrm{ev}},w_{\mathrm{odd}}) = \omega_e(X,Z) + \omega(L_{\mathrm{ev}},L_{\mathrm{odd}}),
ω(Lev,Lodd)=1.\omega(L_{\mathrm{ev}},L_{\mathrm{odd}}) = 1.

Hence [Lev][L_{\mathrm{ev}}], [Lodd][L_{\mathrm{odd}}] form a basis of the two-dimensional space N/SΓN/S_{\Gamma}. It is these logical Pauli classes that are independent; Lev,LoddL_{\mathrm{ev}}, L_{\mathrm{odd}} are their physical representatives.

Let FrF_r be the final failure-basis span. For f∈Frf \in F_r, the component table above shows that ff commutes with both LevL_{\mathrm{ev}} and LoddL_{\mathrm{odd}} at every physical coordinate: at internal path vertices, only 0 and X occur; at the successful coordinate ii, we have fi=0f_i = 0; and outside the path, only 0 and Z occur. Hence

ω(f,Lev)=ω(f,Lodd)=0.\omega(f,L_{\mathrm{ev}}) = \omega(f,L_{\mathrm{odd}}) = 0.

If also f∈Nf \in N, its logical Pauli class is orthogonal to both elements of a basis of N/SΓN/S_{\Gamma}:

ω‾([f],[Lev])=ω‾([f],[Lodd])=0\overline{\omega}([f],[L_{\mathrm{ev}}]) = \overline{\omega}([f],[L_{\mathrm{odd}}]) = 0
⟹[f]=0.\Longrightarrow\quad[f] = 0.

Thus Fr∩N⊆SΓF_r \cap N \subseteq S_{\Gamma}, and logical fusion succeeds by Lemma 2.

For example, on the length-two path ee–aa–ii, take wev=he+hiw_{\mathrm{ev}} = h_e + h_i and wodd=haw_{\mathrm{odd}} = h_a. The two Z contributions at aa cancel, giving (wev)a=0(w_{\mathrm{ev}})_a = 0 and (wodd)a=X(w_{\mathrm{odd}})_a = \mathrm{X}. 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 ii or in the last round. Each additional success merely sets the corresponding component of FrF_r to zero and therefore preserves the orthogonality. If no coordinates remain unfused, the same inclusion already holds for the available FrF_r.

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 [n][n] into nonempty batches T1,…,TrT_1,\ldots,T_r, and write

T>k=Tk+1∪⋯∪Tr.T_{>k}=T_{k+1}\cup\cdots\cup T_r.

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.

  1. There exists a perfect strategy with an all-failure branch whose batches are T1,…,TrT_1,\ldots,T_r, in that order.

  1. There exists Γ∈G(S)\Gamma\in\mathcal{G}(S) such that, for every kk and every i∈Tki\in T_k,

NΓ(i)∩({e}∪T>k)≠∅.(13)N_{\Gamma}(i)\cap\left(\{e\}\cup T_{>k}\right)\ne\varnothing. \tag*{(13)}

When these conditions hold, there exists a perfect strategy with the specified all-failure batch sequence that uses at most rr 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 qq 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 qq to Z. Suppose that condition (13) fails for some i∈Tki\in T_k. Then ii is not adjacent to ee, so the restriction s=hi∣[n]s=h_i|_{[n]} belongs to SΓS_\Gamma.

Follow the same history, including the measured values, until just before batch TkT_k. Consider a branch on which only ii succeeds in that batch and every subsequent fusion fails.

Since condition (13) fails, all neighbors of ii belong to T1∪⋯∪TkT_1\cup\cdots\cup T_k and have therefore been fused by the end of round kk. Their failure bases are all Z, since the preceding history is unchanged and the bases within TkT_k were fixed before its outcomes were known.

Let r′r' be the final failure-basis assignment on this branch. Then

si=X,s−ιi(X)∈Fr′.s_i=X,\qquad s-\iota_i(X)\in F_{r'}.

By Lemma 4, logical fusion fails despite the physical success at ii, contradicting perfection.

Sufficiency. In graph coordinates satisfying (13), fuse the batches T1,T2,…T_1,T_2,\ldots in failure basis Z until the first round containing a success. Let this be round kk, and choose one successful coordinate i∈Tki\in T_k.

Within the subgraph induced by {e,i}∪T>k\{e,i\}\cup T_{>k}, start at ii 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 ee. Choose a shortest path from ee to ii in this induced subgraph. It is also an induced path in Γ\Gamma, and all its internal vertices lie in T>kT_{>k} and have not yet been fused. Lemma 8 completes fusion in at most one additional round. If k<rk<r, the total is at most k+1≤rk+1\le r rounds. If k=rk=r, condition (13) makes ii adjacent to ee, and no coordinates remain. The same lemma then gives success in rr rounds without an additional round. The all-failure branch follows the prescribed rr batches. Undoing the maps on the physical coordinates gives a perfect strategy for SS. □

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 RR rounds, and choose an all-failure branch with r≤Rr \le R batches. Proposition 9 gives a graph Γ∈G(S)\Gamma\in\mathcal{G}(S) satisfying (13). From any i∈Tki \in T_k, following neighbors in later batches reaches ee in at most r−k+1r-k+1 edges. Thus

min⁡Γ′∈G(S)ecc⁡Γ′(e)≤ecc⁡Γ(e)≤r≤R.\min_{\Gamma' \in\mathcal{G}(S)} \operatorname{ecc}_{\Gamma'}(e) \le\operatorname{ecc}_{\Gamma}(e) \le r \le R.

Minimizing the worst-case round count RR over perfect strategies proves the lower bound.

Upper bound. If SS is irreducible, Lemma 6 implies that every graph in G(S)\mathcal{G}(S) is connected. Choose one with root eccentricity hh. For 1≤k≤h1 \le k \le h, define the batches from the outermost distance layer inward:

Tk={i:dist⁡Γ(e,i)=h−k+1}.(14)T_k = \{i : \operatorname{dist}_{\Gamma}(e,i) = h-k+1\}. \tag*{(14)}

These batches partition [n][n]. A shortest path to a vertex at distance hh visits every distance 1,…,h1,\ldots,h, 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 ee. Hence condition (13) holds, and Proposition 9 gives a perfect strategy using at most hh rounds. Minimizing hh over G(S)\mathcal{G}(S) gives

R∗(S)≤min⁡Γ∈G(S)ecc⁡Γ(e).R^*(S) \le\min_{\Gamma\in\mathcal{G}(S)} \operatorname{ecc}_{\Gamma}(e).

Together with the lower bound, this yields equality in (4).

Reducible codes. Suppose that a reducible SS 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 ee, 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 ∣00⟩\lvert00\rangle, ∣11⟩\lvert11\rangle, ∣Ψ+⟩\lvert\Psi^+\rangle, and ∣Ψ−⟩\lvert\Psi^-\rangle, where ∣Ψ±⟩=(∣01⟩±∣10⟩)/2\lvert\Psi^\pm\rangle= (\lvert01\rangle\pm\lvert10\rangle)/\sqrt{2}. The first two outcomes are fusion failures, reporting equal individual ZZ 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 (∣0ˉ0ˉ⟩±∣1ˉ1ˉ⟩)/2(\lvert\bar{0}\bar{0}\rangle\pm\lvert\bar{1}\bar{1}\rangle)/\sqrt{2} and (∣0ˉ1ˉ⟩±∣1ˉ0ˉ⟩)/2(\lvert\bar{0}\bar{1}\rangle\pm\lvert\bar{1}\bar{0}\rangle)/\sqrt{2} with equal probability, where ∣0ˉ⟩,∣1ˉ⟩\lvert\bar{0}\rangle,\lvert\bar{1}\rangle 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 ρS⊗ρS\rho_S \otimes\rho_S, with ρS=ΠS/2\rho_S = \Pi_S/2 and ΠS\Pi_S the projector onto the code space. In graph coordinates, every failure basis along the all-failure branch of the distance-layer strategy is ZZ. A graph code has no nonidentity purely ZZ-type stabilizer, so the complete ZZ-outcome string x∈{+1,−1}nx \in\{+1,-1\}^n of each block is uniformly distributed, with p(x)=2−np(x) = 2^{-n}. The two blocks are independent under ρS⊗ρS\rho_S \otimes\rho_S, and all fusions fail precisely when their ZZ-outcome strings agree. Consequently,

Pr⁡(all fail)=∑xp(x)2=2−n.\Pr(\text{all fail}) = \sum_x p(x)^2 = 2^{-n}.

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 qq, Lemma 3 gives a nontrivial logical Pauli w∈(Fq∩N)∖Sw \in(F_q \cap N) \setminus S. 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 1−2−n1-2^{-n}. 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 ee–1–2–3. Its root eccentricity is three, giving the distance-layer batches {3}\{3\}, {2}\{2\}, {1}\{1\}. 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 R∗=1R^{*}=1. 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.

Three graph representations of the same code

Figure 2. Three graph representations of the same code. The operation ∗v\ast_v denotes local complementation at vertex vv. 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 K2,2,2K_{2,2,2} with parts {e,c}\{e,c\}, {a,b}\{a,b\}, {d,f}\{d,f\} and root ee. It is connected, so the corresponding five-qubit code is irreducible. In physical-coordinate order (c,a,b,d,f)(c,a,b,d,f), its stabilizer subspace is

S=span⁡{XZZZZ,IXXII,IYZYZ,IYZZY}.S = \operatorname{span}\{XZZZZ, IXXII, IYZYZ, IYZZY\}.

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 ecc⁡Γ(e)=2\operatorname{ecc}_{\Gamma}(e)=2, since cc is the only physical vertex not adjacent to ee. To rule out eccentricity one, start from K2,2,2K_{2,2,2} 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 min⁡Γ′∈G(S)ecc⁡Γ′(e)=2\min_{\Gamma' \in\mathcal{G}(S)}\operatorname{ecc}_{\Gamma'}(e)=2, and Theorem 1 gives R∗(S)=2R^{*}(S)=2.

Explicit strategy. First fuse cc in failure basis Z, and choose the second round according to its outcome.

  • If cc fails, fuse a,b,d,fa,b,d,f 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 cc succeeds, use the induced path ee–aa–cc and fuse aa in failure basis X and b,d,fb,d,f 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 R∗=2R^{*}=2 given by Theorem 1; one feed-forward step between fusion rounds is necessary in our model.

Conclusion

For an irreducible [[n,1]][[n,1]] 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. [1]S. Bartolucci et al., Fusion-based quantum computation, Nature Communications 14, 912 (2023). doi:10.1038/s41467-023-36493-1.DOI
  2. [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. [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. [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. [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. [6]K. Goodenough, What are local complementations, really? arXiv:2611.08620v1 (2026). doi:10.48550/arXiv.2611.08620.DOI

Paper details

vlnc:W_7w5knyey
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude, Codex

View statement
Looking for related papers…
Contents