⚛️ quantum physics

Efficient and high-performance routing of lattice-surgery paths on three-dimensional lattice

This paper proposes a high-performance scheduling algorithm for lattice-surgery operations in fault-tolerant quantum computing by reducing the problem to embedding 3D paths in a lattice and solving it with a look-ahead Dijkstra projection, which achieves a 3.8-fold reduction in execution time compared to naive greedy methods.

Original authors: Kou Hamada, Yasunari Suzuki, Yuuki Tokunaga

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kou Hamada, Yasunari Suzuki, Yuuki Tokunaga

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Quantum Traffic Jam: A New Way to Get Data Moving

Imagine you are trying to organize a massive, high-speed train system in a futuristic city. But there's a catch: the tracks are made of "quantum glass," which is incredibly fragile. If two trains try to cross the same piece of track at the same time, the whole system shatters (this is what physicists call an error).

This is the reality of Fault-Tolerant Quantum Computing. To make a quantum computer work, scientists use a technique called Lattice Surgery. Think of this as a way to connect different "quantum islands" (logical qubits) using temporary bridges made of extra space (ancillary cells) so they can talk to each other.

The problem? As quantum computers get bigger, the instructions for these connections become a chaotic traffic jam. If you try to schedule them one by one, the trains wait in line for hours, wasting precious time.

This paper, by Hamada, Suzuki, and Tokunaga, proposes a brilliant new way to solve this traffic jam. Here is the breakdown in simple terms:

1. The Old Way: The 2D Map (Flatland)

Previously, schedulers tried to route these connections on a flat, 2D map (like a piece of paper).

The Problem: If Train A needs to go from Point X to Point Y, and Train B needs to go from Point Z to Point W, and their paths cross, one train has to wait.
The Result: The system sits idle, waiting for the tracks to clear. It's like trying to drive across a city where you can only move North, South, East, or West, and you can't go over or under anything.

2. The New Idea: The 3D Skyscraper

The authors realized that time is actually a third dimension. Instead of just looking at a flat map, imagine the city is a giant 3D skyscraper.

The Floor (X and Y): This is the physical layout of the quantum chips.
The Height (Z): This represents time.

In this 3D world, a "path" isn't just a line on a map; it's a staircase or a ramp that moves through space and time.

3. The "Split and Stack" Strategy

The core genius of this paper is a strategy they call Instruction Splitting.

Imagine you have a giant, heavy box (a complex quantum instruction) that needs to move from the lobby to the 10th floor.

The Old Way: You try to move the whole box at once. If the elevator is full or the hallway is blocked, you wait.
The New Way: You break the box into smaller pieces. You send the first piece up the elevator, then the second piece, then the third. While the first piece is moving up, the second piece is already getting ready on the ground floor.

In the quantum world, this means breaking a single, long connection into a chain of smaller, shorter connections. By doing this, you can fill in the "empty space" in the 3D skyscraper that was previously wasted. You are essentially building a staircase of instructions that fits perfectly into the available gaps.

4. The "Look-Ahead Dijkstra" Algorithm

To manage this 3D traffic, the authors invented a new navigation tool called Look-Ahead Dijkstra Projection.

Dijkstra: This is a famous computer algorithm used to find the shortest path (like Google Maps).
Projection: Instead of trying to calculate the path in the massive 3D skyscraper (which is slow and hard), they project the problem down to a 2D map, solve it quickly, and then "stack" the solution back up into 3D time.
Look-Ahead: The algorithm doesn't just look at the next train; it peeks at the next few trains. It asks, "If I send this train now, will it block the next one? Or can I send a different train first to clear the way?"

The Results: Why It Matters

The researchers tested this on realistic quantum problems (specifically, simulating chemical reactions and materials).

The Speedup: Their new method was 3.8 times faster than the old, standard methods.
The Cost: It took a little bit more time for the computer to plan the route (about 7 times longer to compile), but because the actual quantum computer runs 3.8 times faster, the total time saved is massive.
The Analogy: It's like spending an extra 10 minutes planning your road trip on a map, but saving 40 minutes on the actual drive because you avoided all the traffic jams.

Summary

Think of this paper as the invention of a new traffic control system for the quantum world.

Old System: Flat maps, one train at a time, lots of waiting.
New System: 3D skyscrapers, breaking big jobs into small pieces, stacking them like Tetris blocks in time.
The Tool: A smart GPS that looks ahead and finds the most efficient "staircase" for the data to climb.

This breakthrough means that in the future, we might be able to run complex quantum simulations (like designing new medicines or batteries) much faster, bringing us closer to the day when quantum computers solve problems that are currently impossible.

1. Problem Statement

Fault-tolerant quantum computing (FTQC) using surface codes relies heavily on lattice surgery to perform multi-qubit logical operations (e.g., Pauli measurements, CNOT gates). Lattice surgery connects logical qubits via ancillary cells, requiring a path of physical qubits to be occupied for a duration proportional to the code distance ( $d$ ).

The core challenge is scheduling: determining the order and routing of these lattice-surgery instructions to maximize throughput (parallelism) while minimizing total execution time.

Complexity: Finding the optimal scheduling is known to be NP-hard.
Limitations of Existing Methods:
- Greedy/BFS approaches: Simple Breadth-First Search (BFS) often fails to find paths due to resource contention, leading to idle time and low throughput.
- Instruction Splitting: While splitting large instructions into smaller fragments (e.g., Bell state preparations) to execute them in advance is a promising strategy, existing methods either lack versatility (fixed qubit allocation) or are limited to narrow time windows.
- 2D Constraints: Traditional approaches treat routing as a 2D spatial problem, ignoring the potential to utilize the time dimension for parallelism.

2. Methodology

The authors propose a paradigm shift: converting the lattice-surgery scheduling problem into a 3D path-search problem within a space-time lattice.

A. Theoretical Foundation: 3D Routing and Kinks

3D Lattice Representation: The qubit plane is the $XY$-plane, and time flows along the $Z$ -axis. A lattice-surgery instruction is visualized as a path connecting two logical qubits through this 3D grid.
Instruction Splitting via 3D Paths: A single long-range lattice-surgery instruction can be decomposed into a sequence of smaller operations. The paper proves that a 3D path connecting two logical qubits corresponds to a valid sequence of lattice-surgery instructions if it satisfies specific topological conditions regarding "kinks" (90-degree bends in the path).
- Theorem 1: A 3D path connecting boundaries of the same type (e.g., Z-to-Z) with an even number of kinks results in a logical Pauli-XX or ZZ measurement. A path connecting different boundary types with an odd number of kinks results in a logical CNOT.
Optimization Goal: The scheduling problem is reduced to packing multiple 3D paths into the lattice to minimize the total height (execution time) while satisfying the kink parity constraints.

B. Proposed Algorithms

The authors propose four algorithms to solve this 3D path-packing problem, ranging from simple extensions to optimized projections:

3D BFS: Extends standard BFS to search for the shortest path in the 3D lattice (including time). It finds the lowest available path but has high computational cost ($O(nh)$ per path, where $h$ is lattice height).
3D Dijkstra: Uses weighted Dijkstra's algorithm on the 3D lattice, assigning exponential weights to higher time steps ( $2^h$ ) to prioritize paths that stay "low" in the lattice, encouraging dense packing.
Dijkstra Projection (Key Contribution): To avoid the high cost of 3D search, this method searches for a path in the 2D lattice first, weighted by the current "height" of occupied cells. It then "projects" (lifts) this 2D path into the 3D lattice along the time axis.
- Complexity: $O(n \log n)$ per path, significantly faster than 3D search.
- Performance: Achieves throughput comparable to 3D Dijkstra but with much lower compilation time.
Look-ahead Dijkstra Projection: Integrates an instruction dependency graph (DAG) to select the next executable instruction based on the "height" of its operands. This allows the scheduler to pick instructions that can be executed earliest, further flattening the schedule and reducing path conflicts.

C. Kink Parity Correction

Since the projection method might generate paths with incorrect kink parity (violating Theorem 1), the authors propose a post-processing modification:

Lifting/Aligning: If a path has the wrong parity, the algorithm identifies the first 90-degree corner and "lifts" or "aligns" voxels to flip the parity (creating or removing a kink) without affecting other corners. This is done in linear time relative to path length.

3. Key Contributions

3D Formulation: Extended the lattice-surgery scheduling problem from a 2D routing problem to a 3D path-embedding problem, strictly containing the original problem as a special case and enabling superior solutions.
Look-ahead Dijkstra Projection: Developed a polynomial-time approximation algorithm that leverages 3D routing concepts but operates on 2D search spaces for efficiency. It balances high throughput with reasonable compilation time.
Theoretical Reduction: Established a rigorous mapping between 3D lattice paths and sequences of lattice-surgery instructions, proving that complex multi-qubit operations can be reduced to graph search problems.
Scalability: Demonstrated that the method works for general logical-qubit mappings and can be extended to many-body lattice surgery (Appendix A).

4. Results

The algorithms were evaluated using random circuits and SELECT circuits (derived from Quantum Phase Estimation for a 2D Heisenberg model).

Throughput Improvement:
- The Look-ahead Dijkstra Projection achieved a 3.8x speedup in execution time compared to a naive Look-ahead BFS baseline on realistic benchmark programs (SELECT 5).
- On random circuits, it showed a 1.5x throughput improvement over the best baseline (Look-ahead BFS).
- It outperformed the existing Edge-Disjoint Paths Compilation (EDPC) algorithm significantly, particularly in high-congestion scenarios.
Compilation Time:
- While the proposed method increases compilation time by a factor of ~7 in worst-case scenarios compared to BFS, it still completes within tens of seconds for practical-scale applications (e.g., 60k instructions).
- This is negligible compared to the hours-long execution time of the actual quantum algorithm.
Resource Overhead:
- Active Volume: The method may increase the "active volume" (total number of occupied voxels) by ~30% in some cases, but this can be compensated by a modest increase in code distance (e.g., from $d=23$ to $d=25$ ), resulting in only an ~18% increase in physical qubits.
- Error Rates: The increase in error probability due to longer paths is manageable and does not negate the throughput gains.

5. Significance

Compiler Optimization: This work bridges the gap between quantum circuit compilation and classical graph algorithms, showing that complex FTQC scheduling can be efficiently solved using path-search techniques.
Practical FTQC: By significantly reducing the runtime of quantum algorithms (via higher throughput), the method makes fault-tolerant quantum advantage more achievable with current resource estimates.
Versatility: The approach is not limited to specific qubit layouts or instruction sets; it supports general logical-qubit mappings and can be adapted for distributed quantum computing and many-body operations.
Future Direction: It provides a foundation for full-stack compilation frameworks, suggesting that future optimizations should integrate path-search algorithms with qubit placement and circuit synthesis.

In summary, the paper presents a highly efficient scheduling algorithm that treats time as a spatial dimension, allowing for the flexible decomposition and parallel execution of lattice-surgery instructions, thereby drastically improving the performance of fault-tolerant quantum computers.