PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal adapters between quantum LDPC codes

Esha Swaroop, Tomas Jochym-O'Connor, Theodore J. Yoder

arXiv:2410.03628v4quant-ph

TL;DR

Quantum LDPC codes need a general way to perform joint logical operations while retaining low-density checks and practical fault-tolerant overhead. The paper introduces a universal repetition-code adapter, supported by relative expansion and SkipTree, to connect arbitrary code surgeries. It achieves O(d) time with tilde O(td) additional resources generally, O(td) for specified geometrically local codes, and also constructs a toric-code adapter for logical CNOT gates.

  • Problem

    General quantum LDPC codes lack a universal way to connect auxiliary graph surgeries for joint logical Pauli measurements across arbitrary codes and logical operators.

    Source: §I · pp. 1–2

  • Method

    The paper uses a repetition-code adapter, relative expansion, and the SkipTree sparse basis transformation to connect auxiliary graphs while preserving the required LDPC structure.

    Source: §I · p. 2, §VIII · p. 28

  • Results

    Joint measurement of t weight-O(d) logical operators requires O(d) time and tilde O(td) additional qubits and checks, with O(td) overhead for some geometrically local codes.

    Source: §I · p. 2, §VIII · p. 28

  • Takeaways & Limitations

    The universal adapter provides a low-overhead primitive for logical Clifford computation and for connecting different LDPC codes in multi-code architectures.

    Source: §VIII · p. 28

    The toric-code adapter is asymptotically inefficient, using O(d2) additional qubits, despite potential finite-size interface advantages.

    Source: §VIII · p. 28

Abstract

from arXiv · show

We propose the repetition code adapter as a way to perform joint logical Pauli measurements within a quantum low-density parity check (LDPC) codeblock or between separate such codeblocks, thus providing a flexible tool for fault-tolerant computation with quantum LDPC codes. This adapter is universal in the sense that it works regardless of the LDPC codes involved and the logical Paulis being measured. The construction achieves joint logical Pauli measurement of $t$ weight $O(d)$ operators using $O(d)$ time and $\tilde O(td)$ additional qubits and checks, up to a factor polylogarithmic in $d$. As a special case, for some geometrically-local codes in fixed $D\ge2$ dimensions, only $O(td)$ additional qubits and checks are required instead. By extending the adapter in the case $t=2$, we also construct a toric code adapter that uses $O(d^2)$ additional qubits and checks to perform addressable logical CNOT gates on arbitrary LDPC codes via Dehn twists. To obtain these results, we develop a novel weaker form of graph edge expansion and the $\mathsf{SkipTree}$ algorithm, which ensures a sparse transformation between different weight-2 check bases for the classical repetition code.

I. INTRODUCTION

The paper develops universal adapters for fault-tolerant joint logical Pauli measurements in arbitrary quantum LDPC codes, addressing the difficulty of combining code-specific auxiliary graph surgeries while preserving LDPC structure and distance. It introduces relative expansion and the SkipTree algorithm as the graph-theoretic tools underlying these constructions.

I. INTRODUCTION

  • The construction uses auxiliary graph surgery, where ancilla qubits occupy graph edges and vertex or cycle checks turn a high-weight logical measurement into low-weight stabilizer measurements.The auxiliary graph must satisfy properties including suitable matchings, a sparse cycle basis, and expansion to avoid losing LDPC structure or code distance.Source: §I · pp. 1–2

Related Work

  • The SkipTree algorithm supplies a sparse basis transformation between weight-2 check bases of the classical repetition code, enabling adapters between different auxiliary graphs.The paper also develops relative expansion as a weaker requirement than global edge expansion, and in some cases removes the expansion requirement entirely.Source: Figure 1 · p. 2, Related Work · p. 3, B. Graphs and expansion · p. 5

I. INTRODUCTION

  • Joint logical Pauli measurements can combine operators within one codeblock or across separate codeblocks, but general auxiliary graphs cannot be connected directly while preserving the needed code properties.The construction targets products of logical operators without measuring each operator individually and assumes locally compatible Pauli types when operators overlap.Source: §I · p. 2
  • The universal adapter connects arbitrary auxiliary graphs through adapter edges, preserving LDPC structure and code distance regardless of the codes or logical operators involved.This extends bridge-system ideas by guaranteeing that the resulting deformed code remains practical for product measurements.Source: §I · p. 2, Related Work · p. 3
  • O(td log3 d) additional qubits support joint measurement of t weight-O(d) operators in O(d) time, while geometrically local codes can reduce the auxiliary-qubit overhead to O(td).The general overhead improves quadratically over the previous O(d2) method for arbitrary quantum LDPC codes; the log3 d factor comes from decongestion for a sparse cycle basis.Source: §I · p. 2
  • The adapter also couples arbitrary LDPC codes to toric-code ancillas for addressable logical gates, including a logical CNOT implemented through a Dehn-twist-inspired construction.This toric-code adapter uses O(d2) additional qubits asymptotically but can have smaller finite-size interfaces than existing LDPC–surface-code interfaces.Source: §I · pp. 2–3

A. Stabilizer codes and Tanner graphs

  • The paper formalizes stabilizer and CSS codes with Tanner graphs, where qubit–check incidence and Pauli labels encode the sparse parity-check structure.For CSS codes, checks are separated into X- and Z-type sets; LDPC sparsity bounds both check weights and the number of checks incident on each qubit.Source: A. Stabilizer codes and Tanner graphs · p. 4

B. Graphs and expansion

  • Relative expansion is defined with respect to a vertex subset and threshold, allowing the constructions to guarantee sufficient local expansion without requiring large global expansion.Relative expansion is always at least the corresponding global expansion and can increase under Cartesian-product thickening even when global expansion cannot.Source: B. Graphs and expansion · p. 5

C. Auxiliary graph LDPC surgery

Auxiliary graph surgery deforms a quantum code by attaching an auxiliary graph to the support of a logical operator, then measuring vertex and cycle checks so the target operator enters the deformed stabilizer group. The construction preserves LDPC structure and code distance under graph conditions that can be achieved with polylogarithmic overhead.

Construction

  • Auxiliary graph surgery attaches an injectively ported graph to the support L of a logical operator and introduces edge qubits, vertex checks, and cycle checks.Each graph edge represents one additional qubit; vertices define Z checks, while basis cycles define X checks.Source: C. Auxiliary graph LDPC surgery · p. 6
  • Original checks with X-type support on L are repaired by adding edge support along perfect matchings connecting their port vertices.Pairing the even set f(Ls) and adding matching paths removes the resulting anticommutation with the new vertex checks.Source: C. Auxiliary graph LDPC surgery · p. 6

Logical effect

  • The deformed code has one fewer logical qubit and contains the target logical operator Z(L) in its stabilizer group when the auxiliary graph is connected.This is the core logical effect of the surgery.Source: C. Auxiliary graph LDPC surgery · p. 6

Graph conditions

  • LDPC preservation requires constant graph degree, bounded matching congestion, and a bounded-congestion constant-length cycle basis.These conditions keep the relevant rows and columns of the surgery check matrices at constant weight.Source: C. Auxiliary graph LDPC surgery · pp. 6–7
  • Maintaining distance at least d requires relative expansion β_d(G, imf) ≥ 1, a weaker condition than the global expansion requirement used in prior work [24].The port function only needs to be injective for this distance argument, and relative expansion can be obtained by graph augmentation or thickening.Source: C. Auxiliary graph LDPC surgery · p. 7

Graph construction

  • A graph satisfying the full desiderata can be constructed by thickening and cellulating an initial graph, increasing vertices and edges by only O(log^3 |V0|).Decongestion supplies a controlled cycle basis, while cellulation replaces long basis cycles with constant-length cycles without more-than-constant degree growth.Source: C. Auxiliary graph LDPC surgery · p. 7

Protocol and fault distance

  • The spacetime protocol initializes edge qubits in |+⟩, repeats deformed-code checks for at least d rounds, measures edge qubits in the X basis, and applies a path-dependent Pauli correction.The resulting phenomenological fault distance equals the original code distance d when measurement-circuit noise beyond the stated model is excluded.Source: C. Auxiliary graph LDPC surgery · pp. 7–8

III. THE SkipTree BASIS TRANSFORMATION

This section develops basis transformations and graph constructions that support LDPC adapters for jointly measuring multiple logical operators. The methods preserve sparse cycle bases, expansion-related graph properties, and bounded check weights and qubit degrees.

III. THE SkipTree BASIS TRANSFORMATION

  • Theorem 7 guarantees, for any connected graph, matrices T and P satisfying TGP = HC, with T (3,2)-sparse and both matrices constructible in O(n + m) time.The construction works for high-degree graphs and returns T and P as sparse matrices with O(n) nonzero entries.Source: §III · pp. 8–9
  • SkipTree labels a spanning tree so consecutive labels are connected by paths of length at most three, then uses those paths to define the sparse basis transformation.Each transformation row records a tree path, while each spanning-tree edge appears in exactly two paths, yielding the constant sparsity required by the theorem.Source: §III · p. 9
  • For irreducible logical Z support in a CSS LDPC code, auxiliary graph surgery converts higher-weight checks into a graph incidence matrix, enabling Theorem 7’s canonical repetition-code basis change.This construction is used to connect LDPC-code deformations with repetition-code and toric-code adapters while preserving commuting checks and LDPC structure.Source: §III · p. 10

IV. THE REPETITION CODE ADAPTER FOR JOINT LOGICAL MEASUREMENTS

  • Adapters join two graphs through matched port subsets, enabling joint measurement of Z_lZ_r without measuring Z_l or Z_r individually while retaining the graphs’ structural desiderata.The graphs may represent separate codeblocks or overlapping logical operators within one codeblock, provided the operators do not locally anticommute.Source: §IV · p. 11, Figure 7 · p. 12
  • If each graph has relative expansion at least 1 and the adapter has size at least d, the adapted graph retains relative expansion at least 1 at t = d; SkipTree also bounds cycle-basis degradation by γ′ ≤ max(γ, 8) and δ′ ≤ δ + 2.The adapter-size condition is feasible because the logical-operator ports already have size at least d, while applying SkipTree to induced port subgraphs controls newly created cycles.Source: §IV · pp. 11–12

III. THE SkipTree BASIS TRANSFORMATION

  • The adapted cycle basis is complete and remains (γ′, δ′)-sparse, with γ′ ≤ max(γ, 8) and δ′ ≤ δ + 2.The construction adds A edges and A − 1 independent cycles, and sparsity follows from the (3, 2)-sparse transformations T_l and T_r.Source: §IV · p. 12

IV. THE REPETITION CODE ADAPTER FOR JOINT LOGICAL MEASUREMENTS

  • Theorem 11 constructs an auxiliary graph for the product Z_0Z_1...Z_{t−1} of nontrivial, sparsely overlapping logical operators, preserving LDPC check weights, qubit degrees independent of t, and distance d.The logical operators must be simultaneously made Z-type by single-qubit Cliffords, and the individual auxiliary graphs must satisfy Theorem 5’s graph desiderata.Source: §IV · p. 12
  • The proof is simplest for pairwise disjoint logical supports, while the general sparsely overlapping case requires set-valued port functions developed in Appendix VIII.Set-valued ports allow qubits to connect to multiple vertex checks.Source: §IV · p. 13
  • Adapters are iteratively inserted between connected port subsets of the individual auxiliary graphs to form a single graph for the joint logical product.The combined port function maps each qubit in L_0 ∪ L_1 ∪ · · · ∪ L_{t−1} through its original graph, while the resulting graph inherits desiderata 0–2, gains desideratum 3 from Lemma 10, and satisfies desideratum 4 via β_d(G, P) ≥ 1.Source: §IV · p. 13
  • A limitation is that adapting edges attach directly to ports, and extending the construction to higher levels of thickened auxiliary graphs may require expansion relative to several ports simultaneously.The text contrasts this with constructions for products of same-type logical operators in Ref. [21].Source: §IV · p. 13
  • For practical instances, the construction may be used without explicit relative-expansion guarantees, followed by direct verification that the joint deformed code has distance d.Concrete finite-sized examples are provided in Section VII.Source: §IV · p. 13

V. LEVERAGING CODE PROPERTIES TO SIMPLIFY AUXILIARY GRAPH LDPC SURGERY

This section examines which auxiliary-graph requirements can be avoided when simplifying LDPC surgery.

V. LEVERAGING CODE PROPERTIES TO SIMPLIFY AUXILIARY GRAPH LDPC SURGERY

  • The section focuses on determining whether all graph desiderata are necessary for auxiliary-graph surgery.The graph desiderata theorem provides a checklist of properties intended to preserve code distance and check sparsity.Source: §V · p. 13
  • The graph desiderata theorem supplies the baseline requirements for measuring a chosen logical operator.These requirements concern preserving code distance and sparsity of checks.Source: §V · p. 13
  • The section explores the extent to which auxiliary-graph constructions can avoid some of those requirements.Its stated goal is to assess which checklist properties are essential rather than automatically retaining every one.Source: §V · p. 13

A. Expansion is unnecessary for measuring some joint logical operators

For some joint logical measurements, the auxiliary graph need not satisfy the usual expansion requirement: alternative conditions can preserve the deformed code’s distance. Theorem 12 gives a single-operator-pair construction, while Theorem 13 extends this to simultaneous ZlZr and XlXr measurements under stronger left-code conditions.

Conditions replacing expansion

  • The construction replaces expansion with conditions on the measured operators, including a port-function ordering that makes the left port set contain the right port set.The resulting port vertices have constant degree, and thickening yields O(D log^3 D) total vertices and edges.Source: A. Expansion is unnecessary for… · pp. 13–14

Theorem 12

  • Theorem 12 constructs an LDPC auxiliary graph of size O(D log^3 D) for measuring only ZlZr, with deformed-code distance at least dl + dr − D under condition (a), and at least min(dl, dr) when condition (b) also holds.Here D = max(|Zl|, |Zr|).Source: A. Expansion is unnecessary for… · p. 14

Distance preservation

  • Under condition (a), the deformed-code distance is at least dl + dr − max(|Zl|, |Zr|), and condition (b) reduces this bound to d = min(dl, dr).Condition (b) requires the larger-weight measured operator to be minimum weight in its code, with only one needing that property when the weights are equal.Source: A. Expansion is unnecessary for… · pp. 13, 15

Theorem 13

  • Theorem 13 constructs two O(dl log^3 dl)-size auxiliary graphs that simultaneously measure ZlZr and XlXr while preserving LDPC structure and distance at least dr.The left code must encode two logical qubits and satisfy a weight condition on ZlXl; the toric code is an example.Source: A. Expansion is unnecessary for… · pp. 15–16

Scope

  • The paper studies only two scenarios where expansion can be replaced and suspects the requirement is overkill in many practical settings.This is presented as an open scope boundary rather than a general replacement theorem.Source: A. Expansion is unnecessary for… · p. 16

B. Decongestion is unnecessary for geometrically local codes

For geometrically local codes, Delaunay-triangulation graphs provide bounded-degree, low-congestion auxiliary structures, eliminating the general thickening overhead in fixed dimensions. The same adapters support multi-code logical gates, including gate teleportation, CNOT protocols, and a toric-code construction for addressable CNOTs.

B. Decongestion is unnecessary for geometrically local codes

  • For geometrically local codes in fixed D ≥ 2, a Delaunay-triangulation construction gives a cycle basis with constant edge participation, so thickening is unnecessary and the extra log^3 d overhead can be removed.The constant depends on dimension but not code size.Source: B. Decongestion is unnecessary for… · pp. 16–17
  • The construction uses local logical-operator geometry and unique Delaunay triangulations; disjoint logical operators can instead be handled by separate graphs connected with a repetition-code adapter.The local-code assumptions include constant qubit density and stabilizer radius R_S.Source: B. Decongestion is unnecessary for… · p. 16
  • Theorem 15 guarantees that the Delaunay graph is connected, has system-size-independent bounded degree, and supports bounded-length matchings for local stabilizers.The matching search recursively subdivides pairs using interior points and terminates after O(R_S^D) edges.Source: B. Decongestion is unnecessary for… · pp. 17–18

A. Logical gates by joint-measurements and symmetries

B. Toric code adapter for addressable CNOT

  • The toric code adapter connects auxiliary graphs for irreducible logical Z and X supports to a toric-code ancilla through SkipTree-derived adapter matrices.The toric code’s repetition-like overlap permits direct connection to the base LDPC auxiliary graphs.Source: B. Toric code adapter for addressable… · p. 19
  • The toric-code construction uses Dehn-twist-like operations to implement addressable CNOTs between arbitrary multi-qubit LDPC codeblocks while preserving code distance and sparsity.The auxiliary graphs interfacing with the toric code use O(d log^3 d) qubits, compared with O(d^2)-scale naive ancillas in prior approaches.Source: B. Toric code adapter for addressable… · p. 19, Figure 13 · p. 20

1. Outline of protocol using toric code adapter

The toric code adapter merges an LDPC code with a toric ancilla, performs a Dehn-twist CNOT, and then disentangles the ancilla. The merged code preserves the original logical-qubit count and distance while enabling the logical CNOT through transversal physical gates and permutations.

1. Outline of protocol using toric code adapter

  • The protocol merges the LDPC code with a prepared toric ancilla, applies a toric-code logical CNOT, measures out the ancilla, and applies Pauli corrections.The final circuit implements CNOT between the original control and target logical qubits.Source: §1 · p. 20

2. Parameters of the deformed code

  • The merged code encodes the same number of logical qubits as the original LDPC code.This follows from the stabilizer-rank analysis of the deformed code.Source: §2 · p. 20
  • The deformation moves representatives of the original logical operators into the toric ancilla while preserving their support weight and logical information.Equivalent representatives can be shifted between layers using vertex checks, effectively entangling the LDPC logical information with the ancilla.Source: §2 · pp. 20–21
  • The merged code retains distance d when the auxiliary graphs satisfy the required graph conditions.Thus code deformation preserves the original LDPC code’s error-correcting distance under the stated graph assumptions.Source: §2 · p. 21, §3 · p. 22

3. Toric code CNOT using a Dehn twist

  • Universal-adapter code switching extends the toric-code Dehn-twist construction to arbitrary quantum LDPC codes.The construction combines the toric adapter with the original LDPC code while preserving the original code distance.Source: §3 · pp. 21–22
  • The toric-code CNOT uses transversal physical CNOTs within layers followed by cyclic permutations that preserve the toric-code codespace.These operations realize a Dehn twist and implement the logical CNOT between the toric code’s logical qubits.Source: §3 · pp. 21–22

VII. EXAMPLES

The examples apply the construction to high-rate bivariate bicyclic and lifted product codes, including inter-code and intra-code logical measurements. Individually measured logicals retain code distance with concrete auxiliary-graph overheads, while universal adapters connect graphs despite differing structure or overlapping supports.

VII. EXAMPLES

  • The examples study logical-parity measurements in a [[98, 6, 12]] bivariate bicyclic code and a [[200, 20, 10]] lifted product code.They include measurements between different codeblocks and between distinct logicals within the same BB1 codeblock.Source: §VII · pp. 22–23
  • Universal adapters connect auxiliary graphs for multi-code and within-code measurements, including cases with different logical structure or overlapping supports.The within-code case requires generalizing beyond an injective port function.Source: §VII · p. 22

A. Auxiliary graphs for individual logical measurements

  • All three example auxiliary graphs preserve code distance without adding edge qubits after cellulation to boost relative expansion.The LP2 graph’s cycle basis is bounded by weight 7, matching the original LP2 stabilizer weight.Source: A. Auxiliary graphs for individual… · pp. 23, 25, Table II · p. 24
  • 47 extra physical qubits measure BB1 logical Z1, corresponding to 37.7% additional space over the original BB1 codeblock.The final auxiliary graph uses 23 edge qubits, 14 Z-check ancillas, and 10 X-check ancillas.Source: A. Auxiliary graphs for individual… · pp. 23–24
  • 41 additional physical qubits measure LP2 logical Z2, about 10.5% overhead, while the deformed code remains [[220, 19, 10]].The construction adds 20 data qubits, 14 Z-check ancillas, and 7 X-check ancillas, and preserves distance 10.Source: A. Auxiliary graphs for individual… · p. 25
  • 35 additional physical qubits measure BB1 logical Z3, fewer than for Z1 because Z3 has lower weight.Using a full-rank X-stabilizer basis requires 16 edge qubits during perfect matching, compared with 18 in the canonical basis.Source: A. Auxiliary graphs for individual… · p. 25

B. BB-LP inter-code joint logical measurements using a universal adapter

The universal repetition-code adapter connects auxiliary graphs for joint logical measurements across codeblocks and within one codeblock, while preserving sparse checks and supporting modular reuse. Demonstrations show bounded adapter overhead, preserved distance, and trade-offs against specialized constructions.

B. BB-LP inter-code joint logical measurements using a universal adapter

  • SkipTree transforms each auxiliary graph into the canonical repetition-code basis with (3, 2)-sparse transformations, enabling sparse inter-code adapters.For G1 and G2, T1G1P1 = HR(14) and T2G2P2 = HR(14).Source: B. BB-LP inter-code joint logical… · p. 26
  • The adapter connects corresponding vertices of separate auxiliary graphs through repetition-code checks, requiring 14 added edges and physical data qubits in the BB-LP example.SkipTree supplies matched vertex labels and the adapter X-check matrix uses HR(14).Source: B. BB-LP inter-code joint logical… · p. 26
  • The BB-LP merged code has parameters [[355, 25, 10]], retaining the minimum input distance while measuring one fewer logical qubit than the two codeblocks initially contain.The BB1 and LP2 codeblocks contain 6 and 20 logical qubits, respectively, while the merged code contains 25.Source: B. BB-LP inter-code joint logical… · p. 27
  • The inter-code adapter uses w extra qubits and w−1 checks, costing 27 physical qubits for w = 14, while new adapter X checks have weight at most 8.A representative random spanning-tree run gives check weights from 4 through 8.Source: B. BB-LP inter-code joint logical… · pp. 26–27

C. BB-BB intra-code joint logical measurements

  • For intra-code BB1 measurements, overlapping logical supports are handled with a set-valued port function, and the adapter uses repetition-code distance 12 for unequal logical weights.Shared physical qubits receive two vertex checks, whose product cancels the overlap and leaves support on Z1Z3.Source: C. BB-BB intra-code joint logical… · pp. 27–28
  • The modular BB1 adapter for Z1Z3 costs 23 adapter qubits, whereas a specialized graph uses fewer total qubits but lacks reusable components across measurements.The modular construction yields [[150, 5, 12]] and 295 total physical qubits; the specialized construction yields [[137, 5, 12]] and 269 total physical qubits.Source: Table IV · p. 27, C. BB-BB intra-code joint logical… · p. 28

VIII. DISCUSSION

  • The overall scheme targets O(d log^3 d) space overhead for joint Pauli measurements and fault-tolerant Clifford gates on and between arbitrary quantum LDPC codes.The discussion identifies the universal adapter as a primitive for connecting LDPC codes in multi-code architectures.Source: §VIII · p. 28
  • SkipTree provides rigorous LDPC guarantees, with a universal adapter costing 2d extra qubits and checks and additional checks of weight at most 8.The paper notes that these constants may support near-term fault-tolerant use.Source: §VIII · p. 28

Appendix A: Proofs for Theorem 5

This appendix establishes the theorem by proving that auxiliary graph surgery measures the target logical while preserving code distance under relative-expansion conditions. It verifies the adapter’s structural properties and extends the construction to set-valued ports and joint measurements of sparsely overlapping logical operators.

1. Codespace of the deformed code in auxiliary graph surgery

  • For connected G, graph surgery removes one logical qubit and places the measured operator Z = Z(L) in the deformed code’s stabilizer group.The proof constructs the remaining logical basis using perfect matchings and cycle-basis X-type stabilizers.Source: §1 · p. 31

2. Code distance of the deformed code in auxiliary graph surgery

  • If βd(G, im f) ≥1, the deformed code retains distance at least d, using relative expansion to prevent logical operators from becoming lighter.The argument cleans Z-type support from auxiliary edge qubits and lower-bounds all vertex-check modifications by d.Source: §2 · pp. 31–32

Appendix B: A set-valued port function and the general proof of Theorem 11

  • For set-valued port functions, requiring |f(q)| odd on measured qubits L and even on Q \ L preserves a code distance at least d when βd(G, im f) ≥ 1.Under this generalization, qubit q’s degree in the original code increases by |f(q)|.Source: Appendix B · p. 33
  • Theorem 11 extends the construction to t sparsely overlapping logicals: their product can be measured with an LDPC deformed code whose check weights, qubit degrees, and distance d are independent of t.The combined graph uses the set-valued port f(q) = ⋃i fi(q) and joins the individual auxiliary graphs through adapters.Source: Appendix B · p. 34
  • The product of all vertex checks equals Z(L), where L is the symmetric difference of the logical supports L_i and exactly the qubits with odd incidence lie in L.The support is L = L_0 △ L_1 △ ⋯ △ L_{t−1}, and |f(q)| is odd precisely for q ∈ L.Source: Appendix B · p. 34
  • The adapted graphs preserve the desiderata by increasing vertex degree only constantly and maintaining sparse logical overlap and sparse perfect-matchings.Only constantly many original matchings contribute for each constant-size stabilizer, so their union remains sparse in the adapted graph.Source: Appendix B · p. 34
  • Lemma 10 supplies adapters satisfying desideratum 3, while Lemma 9 guarantees β_d(G, P) ≥ 1 for desideratum 4.Source: Appendix B · p. 34

Appendix C: Thickening to increase relative expansion

Thickening a graph by taking its Cartesian product with a path can increase relative expansion. Sufficient thickening allows an initially inadequate graph to meet the expansion requirement used by the construction.

Appendix C: Thickening to increase relative expansion

  • Thickening any connected graph G0 with subset U by a sufficiently large path-product factor increases relative expansion to the required threshold.The stated bound is L ≥ 1/β_t(G0,U).Source: Appendix C · pp. 34–35
  • The repetition-code check matrix used in the construction is the L−1 by L matrix obtained by omitting the final row of the full check matrix.This identifies the repetition-code structure appearing in the thickening proof.Source: Appendix C · p. 34
  • The proof analyzes vertex restrictions across copies of G0 and uses the assumption Lβ_t(G0,U) ≥ 1 to establish the expansion bound in the thickened graph.The argument applies triangle inequalities and a minimizing copy index.Source: Appendix C · pp. 34–35
  • Using an injective port function on each layer of the thickened graph satisfies the auxiliary-graph expansion desideratum even when the initial graph is insufficiently expanding.The port function maps logical-support locations into corresponding vertices across the path-product layers.Source: Appendix C · pp. 34–35

Appendix D: Support lemma for irreducible logical operators

The appendix establishes a support lemma for irreducible logical operators, develops SkipTree for sparse repetition-code transformations, and proves a two-graph construction for measuring paired logical products.

Appendix D: Support lemma for irreducible logical operators

  • For an irreducible Z-type logical operator, the restricted X-check matrix generates the classical repetition code, so commuting X operators can be adjusted to avoid its support.In CSS codes, the adjustment can be chosen X-type and remove the overlap entirely.Source: Appendix D · p. 35

Appendix E: SkipTree for the full-rank check matrix of the repetition code

  • SkipTree adds branch skipping to solve TGP = HR with sparser transformations, achieving the optimal solution for the path-graph example.The algorithm constructs a permutation and sparse matrix transformation from a spanning tree.Source: Appendix E · p. 35

Appendix F: Proof of Theorem 13

  • Theorem 13 constructs two auxiliary graphs of size O(dl log^3 dl) that simultaneously measure ZlZr and XlXr for arbitrary non-overlapping logical operators under stated left-code assumptions.The construction uses a left code with distance at least the right operators’ weights and produces an LDPC deformed code.Source: Appendix F · p. 36
  • The resulting deformed code retains distance at least dr when the left logical operators have weight dl.The proof concludes this bound using |Zl| = |Xl| = dl.Source: Appendix F · p. 36

Appendix G: Proofs on the toric code adapter

The appendix proves that the merged construction preserves the original number of logical qubits by counting independent stabilizers and their redundancies.

1. Proof that merged code has k logical qubits

  • The merged code encodes k logical qubits whenever the original LDPC code encodes k qubits.The proof tracks the rank contributions of original checks, gauge-fixing checks, and deformation-layer checks.Source: §1 · pp. 36, 38
  • The proof assumes disjoint irreducible logical representatives can be chosen after stabilizer multiplication, using the support corollary to clean overlaps.This provides the support decomposition used in the merged-code rank argument.Source: §1 · p. 36
  • Ancilla single-qubit stabilizers do not add logical qubits because their count matches the introduced ancilla qubits and their supports are distinct.The construction uses a one-to-one correspondence between introduced qubits and new checks, up to permutation.Source: §1 · p. 37
  • The rank calculation separates original X checks, cycle-based gauge-fixing checks, and layer checks whose supports remain linearly independent.For a connected graph, the cycle contribution is determined by its cyclomatic number.Source: §1 · p. 38

a. Initial code deformation step

The initial deformation must initialize edge and toric-code ancillas so stabilizer measurements remain compatible with the original code and preserve the merged code’s distance.

a. Initial code deformation step

  • Edge qubits are initialized as |+⟩ on EZ and |0⟩ on EX so their stabilizers commute with the overlapping original-code checks.Opposite initialization choices make measurement outcomes nondeterministic and lose prior stabilizer information.Source: a. Initial code deformation step · pp. 38–39
  • Initializing toric-code layer qubits with single-qubit stabilizers can clean logical representatives and reduce the merged code distance.The issue arises for Z stabilizers on QZ and X stabilizers on QX.Source: a. Initial code deformation step · p. 39
  • The asymptotic construction uses the entangled toric-code state |+0⟩, while product-state initialization can lack a threshold because of anticommuting gauge operators.The toric-code state is prepared as a simultaneous logical eigenspace and then reset after the split step.Source: a. Initial code deformation step · p. 39

a. Notation on permutations

  • For Tanner-matrix permutations, check permutations act by left multiplication and qubit permutations by right multiplication, giving A → π^T A σ.These paired transformations preserve check structure and syndrome.Source: a. Notation on permutations · p. 40

b. Tracking stabilizer evolution

The stabilizer-tracking analysis combines transversal CNOTs with layer-dependent permutations so the merged Tanner graph and codespace remain invariant while implementing shifted targets.

b. Tracking stabilizer evolution

  • Transversal CNOTs introduce cyclic shifts in Tanner-graph edges, which are compensated by permutations of checks and qubits.The matrix rule A → π^T A σ specifies how these compensating permutations preserve the edge structure.Source: b. Tracking stabilizer evolution · p. 40
  • The required dual-layer qubit permutations follow the closed form σi = C^(-i−1), with corresponding check permutations in each layer.This solves the recurrence generated by successive transversal CNOT shifts.Source: b. Tracking stabilizer evolution · pp. 40–41
  • After compensation, the physical gates preserve the stabilizer space and keep the construction within the merged code’s codespace.The required permutations for all layer qubit and check sets are summarized in Figure 15.Source: b. Tracking stabilizer evolution · pp. 40–41
  • In layer i, transversal CNOT targets are shifted by i, coupling control qubit j to target qubit j+i modulo d.Thus the target alignment changes systematically across successive layers.Source: b. Tracking stabilizer evolution · p. 41

3. Logical action of the Dehn twist

The Dehn-twist circuit implements the toric code’s logical CNOT action and transfers that action to arbitrary LDPC-code logical qubits through the merged adapter.

a. CNOT via a Dehn twist on the toric code

  • The circuit combines layerwise permutations with transversal CNOT gates between ordered primal and dual qubit sets.The permutations restore the merged Tanner-graph structure after the physical CNOTs.Source: a. CNOT via a Dehn twist on the toric… · pp. 41–42
  • The toric-code Dehn twist maps X̄(1) → X̄(1)X̄(2) and Z̄(2) → Z̄(1)Z̄(2), while leaving the other logicals unchanged.These transformations are verified by tracking transversal CNOTs, cyclic permutations, and stabilizer multiplication across the d layers.Source: a. CNOT via a Dehn twist on the toric… · pp. 41–42
  • The toric-code action yields an addressable logical CNOT between arbitrary LDPC logical qubits c and t after merging with auxiliary graphs GZ and GX.The reduction identifies the desired LDPC operation with the toric-code operation CNOT12.Source: a. CNOT via a Dehn twist on the toric… · pp. 42–43
  • The construction assumes disjoint representatives for Z̄(c) and X̄(t), and the adapter can merge an arbitrary LDPC code with the toric code along two disjoint logical supports.This supplies the interface needed for addressable gates on generic LDPC codes.Source: a. CNOT via a Dehn twist on the toric… · p. 42
  • The merged-code representatives of X̄(c) and Z̄(t) acquire toric-code supports that transform into X̄(c)X̄(t) and Z̄(c)Z̄(t), respectively.These maps are the required Pauli conjugations for the targeted CNOT from c to t.Source: a. CNOT via a Dehn twist on the toric… · p. 43

c. Code Distance of the merged LDPC-toric code

The merged LDPC–toric code preserves distance d under sufficient auxiliary-graph conditions, with the toric-code logical supports supplying the key distance bound.

c. Code Distance of the merged LDPC-toric code

  • The merged code has distance d when the original code has distance d and auxiliary graphs GZ and GX satisfy Theorem 5’s graph desiderata 0–3.This is the stated distance-preservation theorem for the merged construction.Source: c. Code Distance of the merged… · p. 43
  • Distance preservation can be established without requiring expansion in the auxiliary graphs of the LDPC logicals.The alternate sufficient condition analyzes the toric-code side and prevents low-weight reductions of relevant logical products.Source: c. Code Distance of the merged… · p. 43
  • The non-overlapping toric-code logical representatives have weight d, and their product has weight 2d.This 2d support supplies the required lower bound in the sufficient condition.Source: c. Code Distance of the merged… · p. 43
  • The toric code should ideally be chosen with distance max(wt(Z̄(c)), wt(X̄(t))) for the protocol.This choice matches the relevant LDPC logical-operator weights.Source: c. Code Distance of the merged… · p. 43

d. Distance preservation during the logical gate

With d toric-code layers, the Dehn-twist circuit has fault distance d: any d−1 or fewer faulty CNOTs produce only stabilizer-equivalent or detectable errors.

d. Distance preservation during the logical gate

  • The Dehn-twist circuit’s fault distance equals the original code distance d when the toric-code adapter has l=d layers.Fault distance counts the largest number of faults guaranteed to result in detectable errors.Source: d. Distance preservation during the… · pp. 43–44
  • The upper bound d is attained when the first CNOT in every layer fails, producing an undetectable representative of X̄1.Those d faults map the state to another codespace state with trivial syndrome but a nontrivial logical error.Source: d. Distance preservation during the… · p. 44
  • Each physical CNOT acts between opposite-type qubits and can introduce at most one error in each participating primal or dual layer.Thus d−1 failed gates generate at most d−1 errors in each layer family, although correlated two-qubit errors may occur.Source: d. Distance preservation during the… · p. 44
  • At most d−1 faulty CNOTs create errors that cannot equal the weight-d logical operators, so every nontrivial resulting error is detectable.The argument separately bounds errors across primal and dual layers and uses their logical-support requirements.Source: d. Distance preservation during the… · p. 44
Loading 2410.03628v4…