Logical computation with canonical lifted product codes

Source: arXiv:2607.28605 · Published 2026-07-30 · By Han Zheng, Guo Zheng, Liang Jiang, Qian Xu

TL;DR

This paper addresses the major challenge of enabling efficient, fault-tolerant logical computation on high-rate quantum low-density parity-check (qLDPC) codes, which encode many logical qubits with low physical overhead but have complex and dense logical operators. Prior generic methods like code surgery and gate teleportation are code-agnostic and incur prohibitive overhead or complexity when applied without leveraging the underlying code structure. The authors resolve this by co-designing both the code and its logical instruction set for a broad family of canonical lifted-product (LP) codes with cyclic symmetry. They rigorously establish that these LP codes admit a canonical logical basis where conjugate logical operators organize into cyclic rows and columns inherited from the underlying classical base codes. This structural insight enables a universal fault-tolerant logical instruction set including constant-depth automorphism and fold-transversal Clifford gates, low-overhead modular graph-based code surgeries built from a constant number of reusable seed surgery gadgets, highly parallel logical Pauli-product measurements, and parallel magic-state injection protocols.

Through concrete examples like [[1122,148,≤20]] and [[4350,1224,≤20]] LP codes, the authors demonstrate dramatic reductions in logical gadget overhead and ancilla sizes (e.g., only 2 or 4 seed gadgets needed regardless of block length). They construct small canonical extractors for arbitrary high-weight logical measurements, parallelize logical measurements within columns or across columns with minimal syndrome extraction overhead, and provide explicit protocols for high-throughput magic-state injection and distillation with provable fault tolerance. These advances extend and generalize prior hypergraph-product code techniques while achieving better code rate and distance, substantially advancing the practical fault-tolerant quantum computation frontier on ultra-high-rate architectures.

Key findings

• Canonical lifted-product codes admit a canonical logical basis where conjugate logical operators correspond to cyclic orbits organized in an r_A × r_B* grid of logical fibres, each of size l, enabling highly structured logical operations.
• For LP codes like [[1122, 148, ≤20]] and [[4350, 1224, ≤20]], only 2 and 4 reusable seed surgery gadgets are required respectively for arbitrary low-weight logical Pauli-product measurements, independent of the lift size (code length).
• A compact canonical extractor for arbitrary high-weight logical measurements has size smaller than half the data code block for [[1122, 148, ≤20]], far smaller than generic qLDPC extractors.
• Constant-depth automorphism and fold-transversal Clifford gates (Hadamard, S, CZ) implement logical operations by permuting or folding logical fibres with no ancilla overhead.
• Parallel intra-column code surgery supports arbitrary logically disjoint multi-qubit Pauli measurements on a column of logical fibres with ancilla overhead only 2–4× data column size and O(d) time, where d is code distance.
• Parallel inter-column surgery generalizes homomorphic measurement to two-column Pauli measurements with a single auxiliary column, preserving code distance and requiring minimal ancilla.
• A parallel magic-state injection protocol injects all logical |T⟩ states of the LP block from distance-d_s surface codes using transistor codes about 1.5× data block size, preserving fault-tolerance distance ≥7.
• Automorphism logical gates cyclically shift logical qubits across each fibre orbit and require no extra space, operating in one QEC cycle.

Threat model

The threat model targets physical noise on qubits and syndrome measurements according to standard fault-tolerant quantum error correction assumptions. The adversary can cause local errors and measurement faults but cannot violate the logical structure of the code or symmetries assumed. The constructions guarantee fault-tolerance with provable distance preservation against such noise. Adaptive adversaries beyond standard noise models are not explicitly considered.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is implicitly any noise process on the physical qubits subject to standard fault-tolerant quantum error correction assumptions. The construction aims for fault-tolerant logical gates and measurements under local noise and syndrome extraction errors, ensuring provable distance-preserving fault tolerance. The adversary cannot break the underlying qLDPC code assumptions or code symmetries.

2. Data: No empirical dataset is used. Instead, the codes are constructed algebraically as lifted-product (LP) codes over the finite polynomial ring R=F2[x]/(x^l + 1) with odd lift size l. Classical base codes A and B over R with mild algebraic conditions and cyclic symmetry serve as the starting point. Specific example codes like LP3×5_33=[[1122,148, ≤20]] and LP3×7_75=[[4350,1224, ≤20]] are discussed.

3. Architecture/Algorithm: The LP codes are defined by parity check matrices H_Z and H_X constructed via tensor products with the ring R, organizing physical qubits as n_A × m_B and m_A × n_B grids of l-qubit fibres. The canonical logical basis is constructed using algebraic tools (e.g. Künneth formula, semisimple ring theory) to identify logical Z and X operators as tensor products of kernel and cokernel generators of the base classical codes over R. Logical operators form conjugate pairs overlapping on one physical qubit within each fibre, arranged into cyclic orbits by the group action. Fold symmetries (involution τ exchanging rows and columns) give ZX duality allowing transversal Clifford gates. Logical operations include:

• Automorphism gates applying cyclic shifts σ_t to logical qubits.
• Fold-transversal gates implementing Hadamard and S/CZ gates via transversal physical gates combined with folding.
• Graph surgery by bridging a constant number r_A of seed surgery gadgets re-used by symmetry, independent of lift size.
• Canonical extractors for arbitrary logical measurements leveraging the cyclic structure to drastically reduce ancilla size.
• Parallel intra-column and inter-column surgeries exploiting row/column tensor structure.
• Parallel magic-state injection protocols via transistor codes mediating transfers from surface-code patches.

4. Training Regime: N/A as this is a theoretical quantum error correction code construction.

5. Evaluation Protocol: Code parameters [[n, k, d]] are analyzed algebraically; logical gate constructions are evaluated for space (ancilla) overhead and circuit depth (time in QEC cycles). Examples emphasize scaling of overhead independent of blocklength l, and space/time cost of various logical instructions (Table I). Concrete quantified overheads are given for example codes such as numbers of seed surgery gadgets, extractor sizes, and parallel measurement ancilla scaling relative to code parameters.

6. Reproducibility: While full code or software implementations are not released, the paper provides explicit algebraic constructions and proofs, including detailed theorems on logical bases and code symmetries. The framework generalizes established lifted-product and balanced-product code frameworks. Full technical proofs are deferred to appendices, and the methodology relies on explicit algebraic manipulations, enabling future reproduction by experts.

Example End-to-End: Consider the [[1122, 148, ≤20]] LP3×5 code with r_A=2 and lift size l=33. Logical qubits are arranged in a 2×2 grid of logical fibres, each with 33 qubits. Logical Z operators correspond to classical codewords of base matrix A, while logical X correspond to codewords of A*. Cyclic shifts permute qubits within logical fibres, forming canonical logical bases. Low-weight logical Pauli product measurements are performed by bridging only two distinct seed surgery gadgets (one per row), shifted by cyclic permutations for other fibres. For high-weight logical measurements, a canonical extractor smaller than half the data block measures the logical operator fault-tolerantly. Parallel code surgeries can measure multiple logically disjoint Pauli operators within a column using ancilla of size ~2× the data column, in O(d) time. Magic states |T⟩ are injected across all 148 logical qubits in 2 batches from distance-7 surface codes mediated by a transistor LP code about 1.5× the data size, preserving fault tolerance with distance ≥7 throughout injection.

This illustrates the co-design from algebraic logical basis, symmetry exploitation, modular low-overhead gadgets, and highly parallel fault-tolerant logical operations.

Technical innovations

• Identification of a canonical logical basis for lifted-product codes over cyclic group rings that organizes logical operators into cyclic orbits inherited from classical base codes, enabling structured logical gates.
• Development of a modular graph code surgery framework using only a constant number of reusable seed surgery gadgets independent of code size, reducing ancilla overhead.
• Construction of compact canonical extractors for arbitrary high-weight logical measurements smaller than half the data block by exploiting code symmetries.
• Design of highly parallel intra- and inter-column code surgery protocols and parallel magic-state injection enabled by the row/column tensor product and ZX-duality symmetries.

Baselines vs proposed

• HGP codes: limited code distance and parameters vs Canonical LP codes: achieve encoding hundreds to thousands of logical qubits, e.g. [[1122,148,≤20]], with structural logical bases.
• Generic code-agnostic surgery: ancilla overhead scaling near-linearly with logical weight vs Seed surgery gadgets for LP codes: constant number r_A independent of lift size l.
• Generic qLDPC extractors: extractor size very large (> data block) vs Canonical LP extractors: extractor size smaller than half the data block for [[1122,148,≤20]] code.
• Naive logical measurement on high-weight operators: high ancilla overhead vs Parallel intra-column surgery on LP codes: ancilla overhead only 2–4× size of data column and O(d) time.
• Surface-code based magic-state injection: single qubit injection vs Parallel injection into whole LP block: inject 132 logical |T⟩ states for [[1122,148,≤20]] in two batches with fault tolerance ≥7.

Limitations

• The constructions require lifted-product codes defined over cyclic group rings with odd lift size and specific algebraic conditions on base classical codes; not all qLDPC codes fall into this class.
• The current work assumes perfect knowledge of the code symmetries; adversarial or arbitrary noise correlations breaking such symmetries are not explicitly analyzed.
• Performance under realistic circuit-level noise and syndrome extraction errors is left to future empirical or numerical study.
• The extractors and parallel surgeries are smaller than generic ones but still scale polynomially with code size; absolute overheads for very large blocklengths may remain significant.
• The theory is mainly algebraic/formal without software implementations or experimental demonstrations yet.
• Some details of adapting the ZX-duality and fold permutations to physical architectures may require further practical engineering.

Open questions / follow-ons

• How do the proposed logical instruction sets and surgery protocols perform on realistic hardware noise models in simulation or experiment?
• Can the canonical logical basis and instruction sets be generalized beyond cyclic group ring LP codes to broader classes of qLDPC codes, including non-Abelian group lifts?
• What are the trade-offs in qubit connectivity and physical layout when mapping these LP codes with their logical operations onto specific quantum hardware architectures?
• Can the parallel magic-state injection protocols be optimized further to reduce ancilla or time overhead for fault-tolerant distillation?

Why it matters for bot defense

While this paper is focused on fault-tolerant quantum computation rather than classical robot detection, the underlying themes of exploiting algebraic structure and symmetries to reduce overhead and improve modularity are broadly relevant to CAPTCHA and bot-defense design. For complex CAPTCHA protocols or logic, co-designing code structures and logical operations to leverage intrinsic symmetries might similarly enhance efficiency, scalability, and robustness. The parallel and modular gadget design principles developed here could inspire analogous designs in CAPTCHA systems needing scalable, certifiable security primitives. However, the direct technical contributions specialized to quantum codes limit immediate applicability to classical bot-defense but indicate that joint code and logic design is a promising avenue.

Cite

@article{arxiv2607_28605,
  title={ Logical computation with canonical lifted product codes },
  author={ Han Zheng and Guo Zheng and Liang Jiang and Qian Xu },
  journal={arXiv preprint arXiv:2607.28605},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.28605}
}

Read the full paper

• arXiv:2607.28605 (abstract)
• arXiv:2607.28605 (PDF)