Spacetime Layout and Logical Compilation of Color Code

Technical Summary: Spacetime Layout and Logical Compilation of Color Code

Problem Statement
Fault-tolerant quantum computing (FTQC) requires more than the aggregation of logical qubits and gates; it necessitates the systematic compilation of abstract algorithms into carefully orchestrated arrangements of logical primitives. While surface-code architectures have seen significant progress in compilation schemes (e.g., Clifford+T compilation, Pauli-based compilation, and spacetime block diagrams), the logical compilation of the two-dimensional (2D) color code remains largely unexplored. Existing research on the color code has focused on individual primitives—such as transversal gates, magic-state preparations, and lattice-surgery operations—but lacks a framework for the automated synthesis of universal logical computations. This gap hinders the maturation of color-code-based FTQC, as the code's native logical capabilities cannot be effectively coordinated across entire algorithms.

Methodology
The authors establish a systematic framework for the logical compilation of the 2D color code, grounded in its topological structure. The methodology proceeds through three primary stages:

1. Spacetime Block-Diagram Representation:
   The authors introduce a spacetime block-diagram representation where logical patches and operations are encoded as graphs composed of elementary blocks:

   • Prisms: Spacetime traces of triangular patches maintained for a specific duration, with top/bottom faces as Pauli boundaries and lateral faces as color boundaries.
   • Time Pipes: Vertical connections between prisms that persist in time, capable of carrying transparent domain walls to implement single-qubit Clifford gates (H, S) without spacetime overhead.
   • Space Pipes: Horizontal connections between side-adjacent prisms, acting as semi-transparent domain walls that condense a single bosonic anyon, effectively mapping the interior to a surface-code-like structure.
   • Ports: Open endpoints for inputs, outputs, and magic-state injections (specifically $|T\rangle$ states).

   The authors derive strict assembly rules governing connectivity (e.g., no degree-one prisms, no fanout ports) and domain-wall matching (Pauli and color matching). These rules allow for junctions of degree up to five, a structural advantage over the surface code's degree-four limit, which facilitates more compact layouts.

2. ZX-Calculus Correspondence:
   A semantic correspondence is established between the spacetime block diagrams and ZX diagrams. In this mapping:

   • Prisms correspond to spiders (X or Z spiders depending on lateral Pauli boundaries).
   • Pipes correspond to wires.
   • Ports correspond to inputs/outputs or specific spiders (e.g., $Z(\pi/4)$ for $|T\rangle$ injection).

   This correspondence allows the geometric description of the layout to be transformed into a semantic representation. The authors leverage ZX-calculus rewrite rules (e.g., spider fusion, Hopf rule) to optimize the logical computation while preserving its semantics, ensuring that any valid layout realizing the transformed diagram implements the same computation.

3. Code-Derived Compilation Strategy:
   To convert abstract ZX representations into valid color-code spacetime layouts, the authors propose an automated strategy involving:

   • Edge-Decorated ZX Diagrams: The raw ZX diagram is rewritten into a form tailored to the color code. Clifford phases are moved onto edges as sequences of H and S gates (realized by stacked transparent domain walls in time pipes), and $T$-gates are represented as degree-one $Z(\pi/4)$ spiders (magic-state ports). This ensures the diagram's vertices fit the degree constraints of the color code junctions.
   • Fusion-Region-Aware Routing: Instead of routing edges between fixed prisms, the router identifies "fusion regions" (maximal sets of unfused degree-two spiders). Routes are allowed to start and end at any prism within these regions, enabling the reuse of geometry and the shortening of paths. This approach exploits the semantic equivalence of the ZX diagram to reduce spacetime volume.
   • Automated Pipeline: The process is automated using a Monte Carlo tree search (MCTS) for layer embedding, with recovery mechanisms (e.g., bisection of blocks) to handle embedding failures.

Key Contributions

• Unified Framework: The paper provides the first systematic framework for the automated logical compilation of the 2D color code, bridging the gap between individual primitives and full-stack algorithm synthesis.
• Spacetime Block Language: It introduces a novel block-diagram language (prisms, pipes, ports) that captures the unique anyon-condensation and domain-wall behaviors of the color code, supporting universal logical operations (Clifford gates, Pauli measurements, and $T$-gate teleportation).
• Semantic-Geometric Bridge: By establishing a rigorous correspondence with ZX diagrams, the work enables the use of semantic transformations to optimize geometric layouts, ensuring correctness through ZX equivalence.
• Optimization Strategy: The introduction of "edge-decorated ZX diagrams" and "fusion-region-aware routing" specifically addresses the structural constraints of the color code, allowing for more efficient spatial and temporal packing than previous surface-code-based methods.

Results
The authors implemented the compilation pipeline and benchmarked it against nine algorithms (including VQE, QFT, QPE, Grover, and GHZ/W state preparation) and compared the results with the TopoLS surface-code compilation framework.

• Volume Reduction: The pipeline consistently produced layouts with smaller spacetime volumes (both occupied-prism and bounding-box metrics) compared to TopoLS across all tested circuits.
• Impact of Routing: The "fusion-region-aware" routing strategy significantly reduced volume metrics compared to a baseline "inplace" routing without fusion awareness, demonstrating the efficacy of exploiting semantic equivalence during geometric embedding.
• Scalability: The automated process successfully compiled a broad range of algorithms, validating the framework's ability to handle diverse computational tasks.

Significance
The paper claims that this work advances the color-code architecture from the construction of individual logical primitives to the automated synthesis of logical computations. By enabling the coordination of the code's native logical capabilities across entire algorithms, the framework addresses a critical disconnect between algorithm design and quantum error correction (QEC) layers. The resulting specifications are not tied to a specific circuit realization, offering compatibility with different physical implementations. The authors position this as a significant step toward full-stack color-code FTQC, providing a tractable basis for system-wide optimization and opening avenues for extending code-derived compilation strategies to other topological codes, such as QLDPC codes.