Logical information localisation in stabiliser codes via single-qubit measurements

AI summary

Overview

Research area: Quantum error correction and quantum communication — specifically, stabiliser codes, qubit loss, and measurement-based localisation of logical information.

Technical level: Advanced. The paper assumes familiarity with stabiliser codes, the Pauli group, symplectic representations, graph codes and surface codes; Section 2 is written to be accessible with only basic stabiliser-code knowledge, but the proofs rely on percolation theory.

Scope (one sentence): The paper provides a theoretical and computational study of stabiliser path finding (SPF) — the task of localising logical information in a stabiliser code after qubit loss using a single round of single-qubit measurements — including a new relaxed variant called g-SPF, a proof of a localisation threshold of p = 1/2 for the planar surface code, and two fast algorithms (D-LoFi and H-LoFi) for solving the problem.

What This Paper Is About

When photons are lost from a stabiliser code, the encoded logical information can sometimes still be recovered by measuring logical representatives qubit-by-qubit, pushing the information onto a small number of surviving target qubits. The prior method for finding such measurement patterns, stabiliser path finding, worked by exhaustively listing logical representatives, which becomes infeasible beyond small codes and offered no analytical guarantee at larger sizes. This paper asks whether localisation has a genuine threshold, and builds fast, scalable algorithms to find localisation patterns in codes far larger than previously studied.

Key Contributions

1. A relaxed problem definition, g-SPF. The authors generalise SPF — which requires the logical X and Z representatives to anti-commute qubit-wise on one pre-specified target qubit — to g-SPF, where the pair must anti-commute on at most g arbitrary (unspecified) target qubits. This removes the assumption that a particular target qubit is the right one, and recovers Target-SPF when g = 1.

2. An analytical localisation threshold for the planar surface code. Using percolation theory and a new lemma bounding the minimum intersection size of disjoint representative sets (Lemma 2: min intersection ≤ n/(Δ_X Δ_Z)), the authors prove that for i.i.d. loss with p < 1/2 and constant g, g-SPF succeeds with probability converging to one on sufficiently large planar surface codes, while for p > 1/2 the success rate converges to zero — making p = 1/2 the exact threshold.

3. Two new algorithms. D-LoFi (Deterministic Localisation Finder) encodes Target-SPF and g-SPF exactly as constrained quadratic optimisation problems, formulated as integer linear programs, and additionally minimises the total support of the SPF pair so the number of required single-qubit measurements is minimal. H-LoFi (Heuristic Localisation Finder) instead casts g-SPF as a most-likely-error decoding problem solved in two stages: first finding a short Z representative, then finding an X representative that anti-commutes with it on few qubits.

4. A large numerical validation and runtime comparison. Both algorithms numerically reproduce the predicted threshold on the rotated surface code with g = 1, and D-LoFi is benchmarked against the earlier SPF algorithm of Morley-Short et al. on the "crazy graph" code, showing orders-of-magnitude speedups and access to substantially larger codes.

Main Findings

• Threshold at p = 1/2 for the planar surface code. For any p < 1/2 there exists a constant g such that, for large enough code size n, a g-SPF pair exists with probability converging to one; for any p > 1/2 the success rate converges to zero. The threshold coincides with the standard erasure threshold of the surface code, which the authors note is not trivially obvious since localisation and erasure decoding are not necessarily equivalent.

• Numerics suggest the stronger statement g = 1. Simulations on the rotated surface code with g = 1 show threshold behaviour consistent with Theorem 1, indicating that g may be settable to one — but the authors state that an analytical proof is needed to make a definite claim.

• H-LoFi closely approximates the exact algorithm. D-LoFi is exact (it always finds a g-SPF pair when one exists). Figure 1(b) shows H-LoFi closely matching D-LoFi's success rates, while Figure 2(a) shows H-LoFi is orders of magnitude faster at fixed loss probability p = 0.1. Figure 2(b), at fixed p = 0.15, shows the support-size penalty of the heuristic is small: H-LoFi's solutions require only slightly more single-qubit measurements than D-LoFi's minimal ones.

• Substantial speedup over the previous state of the art. On the crazy graph code (qubit number n = l² + 2), the algorithm from Ref. [33] exceeded the imposed wall-time limit of 60,000 seconds (about 16 hours and 40 minutes) for l > 4, i.e. n > 18. D-LoFi remained tractable and was orders of magnitude faster, enabling study of graph codes significantly larger than those in Ref. [33] and far beyond the twelve-qubit graphs that prior work (Ref. [6]) could search on a computing cluster.

• Simulation scale. For each loss probability, at least 5000 Monte Carlo loss configurations were sampled to estimate the g-SPF success rate; runtimes were averaged over 5000 Monte Carlo samples taken at p = 0.1. For the runtime comparison, all possible loss configurations were sampled for small codes and 1000 unique ones for each lattice parameter.

• Generality beyond graph codes. Because the algorithms use the stabiliser tableau representation and linear algebra on symplectic spaces, they do not require any particular code structure and can analyse stabiliser codes beyond graph codes.

Methodology in Plain English

The task is to find two logical operators (an X-type and a Z-type) that avoid all lost qubits and that anti-commute on only a few target qubits. The authors exploit the fact that stabiliser codes are linear objects: adding a stabiliser to a logical operator gives another equally valid representative of the same logical operator. This redundancy is what makes loss recovery possible at all.

For the theory, they picture the surface code's logical X representatives as left-to-right paths on a lattice and logical Z representatives as top-to-bottom paths on the dual lattice. Standard percolation theory then says that below p = 1/2 a macroscopic number of disjoint surviving paths exists. A combinatorial lemma (Lemma 2) converts many disjoint X and Z representatives into a guarantee that some pair must intersect in only a constant number of qubits — which is precisely what g-SPF needs.

For the algorithms, they first update the stabiliser tableau to describe the code remaining after loss, then either (a) express the search for a minimum-support SPF pair as an integer linear program and solve it exactly, or (b) express the search as a decoding problem and solve it with a decoder, which is much faster but not guaranteed optimal. They then run these on rotated surface codes across many randomly sampled loss configurations to map out success rates versus loss probability, and benchmark runtimes against the earlier exhaustive-listing approach.

Why This Matters

Impact on research. This is described as a first theoretical and numerical analysis of localisation via SPF in this form. It converts a purely numerical, small-scale search into a problem with a provable threshold and with algorithms fast enough to study large codes, and it links localisation to percolation and to the standard erasure threshold of the surface code — a connection the authors highlight as non-obvious.

Real-world applications (as framed by the paper):

• Fault-tolerant teleportation, where logical information must be moved onto specific surviving qubits over a lossy link.
• Efficient logical fusion, and in particular the adaptive fusions proposed for fusion-based quantum computation that tolerate fusion failures and qubit loss.
• Photonic quantum communication and quantum repeater schemes, where photon loss is the dominant error channel.
• Measurement-based quantum computation, where computation proceeds by adaptive single-qubit measurements on an entangled resource state — the same primitive used here.

Industry relevance. Photonic hardware is highlighted as a promising route to scalable, fast and energy-efficient quantum computation, and photons are the natural resource for fusion-based quantum computation and communication. Because the method needs only one round of single-qubit measurements and no two-qubit operations during readout, it is directly relevant to hardware with limited resources and flying qubits, and to teams designing graph codes and resource states for photonic architectures.

Future Directions

• Prove that g = 1 suffices. The numerics indicate the threshold holds even when localisation is onto a single unspecified qubit, but the authors state an analytical proof is needed for a definite statement.
• Systematic code search at scale. The speedup enables searching for codes suitable for fault-tolerant schemes in regimes that were previously computationally out of reach; extending such searches beyond graph codes is a natural step.
• Understanding the source of hardness. The authors note that localisation to a specified target can be found in polynomial time in the loss-free setting (Ref. [43]) and suspect that the hardness of this task stems from qubit loss — a question worth pinning down.
• Closing the modelling assumptions. Prior SPF work assumed the target (and input) qubit is never lost, which the authors flag as possibly unrealistic; g-SPF relaxes the target assumption, while a fully loss-tolerant treatment of the input qubit remains an open practical issue.

Target Audience

Quantum error correction researchers working on stabiliser and topological codes; photonic quantum computing and fusion-based quantum computation teams concerned with photon loss; quantum communication and repeater architects; and graduate students or researchers comfortable with the stabiliser formalism who want a rigorous, algorithmically practical treatment of loss-tolerant logical readout. Readers without background in symplectic representations and percolation theory will find the informal results section accessible but the proofs demanding.

Authors’ abstract

Stabiliser path finding (SPF) has previously been introduced as a method to localise logical information in a stabiliser code undergoing loss onto a single pre-specified target qubit, using only one round of single-qubit measurements. When working with limited resources and flying qubits, this fast read-out of logical information is a helpful tool for fault-tolerant communication. In this work, we provide a broad analytical and computational study of localisation via SPF. We introduce $g$-SPF, where the task is to localise the logical information onto a set of at most $g$ unspecified target qubits. Through analytical arguments based on percolation theory and the disjointness of stabiliser codes, we prove that for i.i.d. qubit loss with probability $p&lt;1/2$ and sufficiently large planar surface codes, localisation via $g$-SPF for constant $g$ succeeds with a probability converging to one, which establishes a localisation threshold. Furthermore, we propose and implement two algorithms to solve SPF. The first is exact and formulates SPF as an integer linear program, whereas the second is heuristic and formulates SPF as a decoding problem. We validate both algorithms by numerically reproducing the localisation threshold for the surface code and demonstrate that the heuristic algorithm is considerably faster. Our work significantly reduces the time required to solve SPF compared to current state-of-the-art algorithms, allowing us to study localisation in substantially larger stabiliser codes than previously considered in the literature. Together, these theoretical and computational results open the door to various applications, such as fault-tolerant teleportation and efficient logical fusion.