PureMagic: A Dynamic Scheduler for Lattice Surgery

PureMagic is a dynamic scheduler for lattice surgery that eliminates dedicated bus patches by repurposing all ancilla patches for both routing and stochastic magic state cultivation, achieving significant improvements in efficiency, resource utilization, and preparation time compared to traditional static approaches.

The Gist

Imagine you are trying to run a massive, incredibly complex factory. This factory doesn't make cars or phones; it makes quantum computers that can solve problems impossible for today's machines. But there's a catch: the factory is incredibly fragile. If a single worker sneezes, the whole production line might crash. To fix this, the factory uses a "safety net" system called error correction, where many workers do the same job to ensure accuracy.

However, to do the most advanced work, the factory needs a special, rare ingredient called a "magic state." Making this ingredient is tricky.

The Old Way: The Dedicated "Magic Factory"

In the traditional approach (used by previous systems), the factory built huge, permanent buildings dedicated solely to making these magic states.

• The Problem: These buildings took up a massive amount of space (logical qubits). They were like giant warehouses sitting on the edge of the factory floor.
• The Bottleneck: Because they were fixed in place, they couldn't move. If the main production line needed a worker to move a box from one side of the factory to the other, the workers in the magic factories couldn't help; they were stuck making magic.
• The Gamble: Making the magic state is like rolling a die. Sometimes it takes a few seconds; sometimes, due to bad luck, it takes hours. The old system had to wait for the "slow rolls" to finish before moving on, causing the whole factory to sit idle.

The New Way: PureMagic (The "Swiss Army Knife" Workers)

The paper introduces PureMagic, a new way to run the factory that changes the rules completely.

1. No More Dedicated Factories
Instead of building special buildings for magic states, PureMagic says: "Everyone is a magic maker."
Every single worker in the factory (called an "ancilla patch") is trained to make magic states. They are constantly trying to brew the magic ingredient.

2. The Dynamic Switch
Here is the clever part: These workers are also the delivery drivers.

• Scenario A: A worker is busy brewing magic.
• Scenario B: Suddenly, the main production line needs that worker to carry a box across the factory (routing).
• The Magic Move: The worker instantly stops brewing, drops the half-finished magic, and carries the box. Once the box is delivered, they immediately start brewing magic again from scratch.

Why is this better?

• Cutting the "Long Tail": In the old system, if a magic-making attempt got stuck in a "bad luck" loop (taking forever), the whole factory waited. In PureMagic, if a worker gets stuck brewing, they get interrupted by a delivery job. This naturally cuts off the "long tail" of slow attempts. The factory only keeps the "fast" magic makers, making the average time to get magic much faster (4.5 times faster, according to the paper).
• No Idle Time: In the old system, the delivery workers sat idle while the magic factories worked, and vice versa. In PureMagic, every worker is always doing something—either making magic or moving things. There is no wasted space.

3. The "Weight Limit" Trick
The paper also mentions a software trick called a "weight limit" (denoted as $\omega$). Think of this as a rule for how many boxes a worker can carry at once.

• The old way tried to carry huge loads (complex instructions) to save steps, but it got stuck easily.
• PureMagic uses a rule to break instructions into tiny, single-box loads. This means the factory can run many workers in parallel at the same time. Because PureMagic has so many workers available (since they aren't stuck in magic factories), it can exploit this parallelism much better than the old system.

The Results

The researchers tested this new system on 29 different "factory designs" (benchmark circuits). Here is what they found:

• Efficiency: PureMagic was 40% to 150% more efficient than the old bus-routing system.
• Space: It used 19% to 80% fewer workers (logical qubits) to do the same job.
• Speed: It reduced the time needed to prepare the magic ingredient by 4.5 times.
• Comparison: When compared to the best existing static scheduler (DASCOT), PureMagic was up to 15 times more efficient when you count the cost of making the magic states.

The Bottom Line

PureMagic treats the factory floor like a fluid, dynamic environment rather than a rigid grid with fixed roles. By letting every worker switch between "making magic" and "delivering packages" instantly, it eliminates wasted space, cuts out the slowest attempts, and keeps the quantum computer running at peak speed. The paper claims this approach gets so close to the theoretical limit of perfection that it's nearly impossible to do much better without changing the fundamental physics of the machine.

Technical Summary

Technical Summary: PureMagic

Problem Statement

Fault-tolerant quantum computation using surface codes relies on magic states to achieve universality. Traditional approaches utilize distillation factories, which are large, static arrays of logical qubits (121–176 patches per output port) that produce magic states deterministically. This necessitates a static, peripheral placement of resources, creating a rigid architecture where "bus" patches are dedicated solely to routing and "magic" patches are dedicated solely to production.

An alternative, magic state cultivation, reduces the footprint to a single logical qubit but introduces inherent stochasticity. The time required to produce a high-fidelity magic state follows an exponential distribution with a "long tail," meaning some attempts take significantly longer than the average. Static schedulers, which assume deterministic resource availability, cannot adapt to this variability, leading to stalls and inefficiencies. Furthermore, the long tail of cultivation times forces static schedulers to either over-provision resources or accept significant delays.

Methodology

The authors propose PureMagic, a dynamic scheduling framework that fundamentally rethinks the role of ancilla patches in lattice surgery.

1. Dual-Purpose Ancilla Architecture

PureMagic eliminates the distinction between dedicated bus patches and magic state cultivators. Instead, all ancilla patches are treated as dual-purpose resources:

• Cultivation: Every non-data patch continuously attempts to cultivate a magic state.
• Routing: When a routing path is required for a Pauli product, any patch (including those currently cultivating) can be repurposed immediately.
• Interruption and Restart: If a patch is needed for routing, its ongoing cultivation is canceled. Once the routing task is complete, cultivation restarts from scratch on that patch. This mechanism naturally truncates the long tail of the cultivation time distribution, as slow-growing states are interrupted by routing demands, ensuring that only the fastest successful attempts contribute to the schedule.

2. Dynamic Scheduling Algorithm

The scheduler operates within the Pauli-Based Computation (PBC) framework, where Clifford+T circuits are transpiled into sequences of multi-qubit Pauli product measurements.

• Real-Time Adaptation: The scheduler makes decisions within a single logical cycle (approx. 17µs for code distance $d=17$). It handles two sources of non-determinism: stochastic cultivation completion times and the 50% probability of T-state injection failure (requiring an S-gate correction).
• Heuristic Packing: To solve the NP-hard Lattice Surgery Scheduling Problem (LSSP), PureMagic employs a greedy Steiner forest packing algorithm. It prioritizes Pauli products based on estimated tree size (using Manhattan distance) to schedule the most compact operations first.
• Pathfinding: For single-operator Pauli products, an efficient A* algorithm is used to find paths to available magic states. For multi-qubit products, a shortest-path heuristic approximates the Steiner tree.

3. Transpilation with Weight Limit ($\omega$)

The authors introduce a transpilation extension using the Tableau algorithm with a weight limit $\omega$.

• $\omega = 1$ (Lightweight-PBC): Limits Pauli products to single operators. This increases the total gate count slightly (2–6%) but drastically reduces circuit depth (up to 26×) by maximizing parallelism.
• $\omega = \infty$ (Heavyweight-PBC): The standard approach where all Clifford gates are commuted, resulting in fewer gates but higher-weight Pauli products and lower parallelism.
  PureMagic is specifically designed to exploit the high parallelism of the $\omega = 1$ setting, as the increased number of available cultivating patches can service more concurrent routing requests.

Key Contributions

1. PureMagic Architecture: A layout design that eliminates dedicated bus patches, allowing every ancilla patch to serve interchangeably as a cultivator and a routing resource.
2. Dynamic Scheduler: A real-time scheduler that adapts to stochastic cultivation times and T-state injection failures, utilizing a greedy Steiner forest packing approach.
3. Simulation Framework: A logical-qubit level simulator that models probabilistic cultivation and injection failures to evaluate scheduling performance.
4. Weight-Limited Transpilation: An extension of the Tableau algorithm that trades gate count for circuit parallelism, optimizing the workload for the PureMagic architecture.

Experimental Results

The framework was evaluated on 29 benchmark circuits from the Benchpress suite, simulating execution on an abstract surface code model ($d=17$).

• Efficiency Gains: Compared to a traditional bus routing layout, PureMagic achieves a 40% to 150% improvement in efficiency (inverse of spacetime volume). The gains are most pronounced when using the lightweight transpilation setting ($\omega = 1$).
• Resource Reduction: PureMagic uses 19% to 80% fewer logical qubits than bus routing layouts, as it does not require a fixed perimeter of dedicated magic state factories.
• Cultivation Time: The average magic state preparation time is reduced by 4.5× (from an average of 26 cycles to 5.8 cycles) due to the truncation of the long tail of the cultivation distribution.
• Comparison to Static Schedulers: When compared to DASCOT (a state-of-the-art static scheduler that assumes immediate magic state availability), PureMagic is up to 15× more efficient when the cost of magic state preparation (cultivation time or distillation factory area) is included.
• Theoretical Bounds: PureMagic's scheduled volumes fall between the conservative and optimistic FLASQ theoretical lower bounds, demonstrating that the dynamic dual-purpose strategy closely approaches the ideal of "fluid" ancilla resources.

Significance and Claims

The paper argues that the separation of routing and magic state production is an artifact of the high overhead of distillation factories. By adopting cultivation and dynamic scheduling, the "fluid-ancilla" ideal—where any available resource can serve any function—becomes achievable.

The authors claim that PureMagic demonstrates that dynamic scheduling is essential for efficient fault-tolerant quantum computing, particularly when using resource-efficient methods like cultivation. They suggest that future comparisons of Quantum Error Correction Codes (QECCs) should move beyond static gate-level metrics and include the overhead of dynamic scheduling and resource management. The work implies that as algorithms demand higher-fidelity magic states (requiring longer cultivation times), the benefits of PureMagic's ability to amortize cultivation across a large pool of patches will become even more significant.