Technical Summary: Automated Logical Clifford Gadgets for Heterogeneous Architectures via Chain Maps

1. Problem Statement

Current large-scale fault-tolerant quantum computing proposals increasingly rely on heterogeneous architectures, where distinct Quantum Error Correcting Codes (QECCs) are tailored for specific tasks (e.g., memory, Clifford computation, or magic state preparation). While transversal CNOT gates provide a natural mechanism for entangling logical qubits within identical CSS code blocks, extending these operations to arbitrary pairs of distinct CSS codes remains a significant challenge.

Existing methods for inter-code logical operations are largely restricted to:

• Structurally related code families (e.g., 2D to 3D codes, or codes and their punctured subcodes).
• Symmetry-preserving operations between identical blocks.
• Universal adapters, which require joint logical Pauli measurements. These adapters often incur substantial spacetime overheads, scaling as $\tilde{O}(td)$ ancilla qubits and $O(d)$ measurement rounds to achieve fault tolerance.

There is a lack of a systematic, automated framework for synthesizing low-overhead logical CNOT circuits between arbitrary CSS codes that preserves the product codespace and induces a well-defined logical action.

2. Methodology

The authors introduce a linear-algebraic framework based on chain maps between the chain complexes representing CSS codes. The methodology proceeds in three stages:

2.1 Formalism: Chain Maps and Hom-Spaces

CSS codes are represented as length-3 chain complexes over $\mathbb{F}_2$. A degree-1 chain map $\gamma_1: C^B_1 \to C^A_1$ specifies a pattern of physical CNOT gates from code $B$ to code $A$.

• Chain Map Conditions: The map must satisfy commutative diagram conditions with the boundary maps (parity-check matrices), ensuring that stabilizers are mapped to stabilizers and the product codespace is preserved.
• Hom-Space: The set of all valid degree-1 maps, denoted $\text{Hom}_1(B, A)$, forms a linear subspace. The authors show this space is isomorphic to the kernel of an explicit binary matrix constructed from the parity-check matrices of the two codes.

2.2 Logical Targeting as Affine Constraints

To achieve a specific logical operation (e.g., a CNOT between specific logical qubits), the authors impose constraints on the induced logical action.

• Induced Action: A chain map $\gamma_1$ induces linear maps on the homology groups (logical operators), denoted $\Gamma_Z(\gamma_1)$ and $\Gamma_X(\gamma_1)$.
• Affine Subspace: Specifying a target logical action (e.g., $\Gamma_Z = \Gamma_{\text{tgt}}$) restricts the linear space $\text{Hom}_1(B, A)$ to an affine subspace. This transforms the problem from finding any valid map to finding a specific representative within a constrained affine family.

2.3 Optimization via CP-SAT

The search for physically efficient gadgets (low-depth, sparse circuits) within this affine subspace is formulated as a discrete optimization problem.

• Objective: Minimize circuit depth (defined by the maximum degree of the bipartite interaction graph) and/or the number of physical CNOT gates (weight).
• Solver: The authors employ a CP-SAT (Constraint Programming - Satisfiability) solver.
• Heuristics: To improve solver performance, they introduce a sparse basis replacement heuristic. This replaces dense generators of the null space with structured, sparse rank-1 matrices derived from the parity-check structure (e.g., coupling a qubit to a specific stabilizer support), effectively decomposing the search space.

2.4 Fault Tolerance and Flagging

While the chain map conditions guarantee logical correctness, they do not automatically guarantee fault tolerance (distance preservation).

• Partially Fault-Tolerant Solutions: The optimizer often finds circuits that are not fully distance-preserving.
• Flagging: The authors demonstrate that these partially fault-tolerant circuits can be promoted to full fault tolerance by adding a small number of flag qubits and single-shot stabilizer measurements. This approach recovers the full code distance with minimal time overhead compared to general surgery methods.

3. Key Contributions

1. Automated Synthesis Framework: A fully automated pipeline that takes parity-check matrices of two arbitrary CSS codes and a desired logical CNOT network, outputting a physical CNOT circuit.
2. Affine Characterization: A rigorous characterization of the space of inter-code couplings as an affine subspace defined by logical targeting constraints.
3. Sparse Basis Heuristic: A novel method for re-parametrizing the search space to improve the efficiency of discrete optimizers (CP-SAT) in finding low-depth solutions.
4. Flagged Circuit Construction: A practical demonstration that "imperfect" chain maps can be made fully fault-tolerant with a modest number of flags, avoiding the heavy overhead of universal adapters.

4. Results and Benchmarks

The framework was benchmarked on a range of heterogeneous CSS code pairs, including surface codes, color codes, bivariate bicycle (BB) codes, and many-hypercubes codes.

• Recovery of Known Constructions: The method successfully recovers known transversal constructions for structurally related codes.
• New Low-Depth Solutions: For arbitrary pairs, the optimizer finds new circuits with favorable spacetime tradeoffs.
  • Magic State Injection: The method identifies maps for magic state injection that avoid the expensive universal adapters, offering significant overhead reductions.
  • Inter-Block CNOTs: For the [[16, 4, 4]] many-hypercubes code, the method finds depth-2 circuits for targeted inter-block CNOTs, compared to depth-6 for the ConiQ AHA scheme (a 4.5$\times$ reduction in spacetime overhead).
  • Pauli Product Measurements (PPMs): The framework enables efficient PPMs for qLDPC codes. For example, measuring seed operators on a [[62, 10, 6]] GB code using a color code ancilla requires fewer ancilla qubits than previous surgery-based approaches.
  • Grid PPMs: For HGP codes, bespoke chain maps can measure specific logical qubits using a single ancilla block, removing the need for secondary ancillas required by Grid Pauli Product Measurements (GPPM), while maintaining depth-2.
• Performance Simulations: Numerical simulations using the Stim simulator show that the resulting homomorphic CNOT gates have logical error rates comparable to idling memory baselines and transversal CNOTs of the respective codes.
  • Flagged Circuits: Simulations of flagged homomorphic CNOTs (e.g., between a distance-7 surface code and a [[72, 12, 6]] BB code) demonstrate that adding a small number of flags (e.g., 5) restores the full code distance, achieving performance on par with transversal gates.

5. Significance and Claims

The paper claims that this framework provides a flexible and systematic tool for designing logical operations tailored to heterogeneous architectures.

• Generality: Unlike previous methods restricted to specific code families, this approach applies to arbitrary CSS code pairs.
• Efficiency: It offers a path to inter-code entanglement with spacetime overheads closer to transversal gates than universal adapters, while maintaining fault tolerance through flagging.
• Scalability: The method is computationally feasible for moderate-sized codes relevant to current architecture proposals (e.g., BB codes, surface codes).
• Extensibility: The authors note that the framework naturally extends to other logical gates, such as logical CZ gates, and can be adapted for other primitives like GHZ state preparation or multi-block Clifford gadgets.

The authors remain modest regarding the computational complexity, acknowledging that the optimization over the affine space is a discrete problem without a known polynomial-time solution in the general case, and that the current results serve as proof-of-principle demonstrations for moderate-scale instances. They emphasize that the affine space inherently contains many partially fault-tolerant candidates that can be promoted to full fault tolerance, offering a practical route for near-term heterogeneous architectures.