No Tile Left Behind: Multiprogramming for Surface-Code Architectures

This paper introduces a formal framework for multiprogramming fault-tolerant quantum computing architectures that addresses the unique structural constraints of surface-code floorplans through hierarchy-aware scheduling and dynamic resource management, achieving a 3.1x system speedup over existing baselines.

The Gist

Imagine a future where quantum computers are so advanced that they can solve problems impossible for today's supercomputers. To make this happen, these machines need to be incredibly reliable, using a system called Fault-Tolerant Quantum Computing (FTQC).

However, building a quantum computer is like building a massive, highly organized city. You can't just throw random people (data) into the streets; they need specific neighborhoods, specific roads, and specific supply lines to function without making mistakes.

This paper, titled "No Tile Left Behind," tackles a specific problem: How do we run multiple different jobs at the same time on this quantum city without causing a traffic jam or running out of space?

Here is the breakdown using simple analogies:

1. The Quantum City: Surface Codes

Think of the quantum computer's layout as a giant grid of tiles (like a floor plan).

• Data Tiles: These are the "houses" where the actual information (the logical qubits) lives.
• Ancilla Tiles: These are the "construction crews" or "workbenches." They are temporary spaces used to check for errors or move data around.
• Magic State Ports: These are "specialized factories" that produce a rare, high-quality ingredient (magic states) needed to perform complex calculations. Without them, the computer can't do certain math.

In the past (the "NISQ" era), running multiple jobs was like trying to park cars in an empty parking lot. You just fit them wherever you could. But in this new "Fault-Tolerant" era, the city is structured. You can't just park anywhere; you need a whole neighborhood, a nearby workbench, and a factory nearby. If you park one car poorly, you might block the road for the next three cars.

2. The Problem: The "Packing" Nightmare

The authors explain that running multiple jobs (multiprogramming) on this structured grid is much harder than before.

• Fragmentation: If you place Job A in a way that leaves a tiny, useless gap between two big blocks, Job B might need a big block and can't fit in that gap. The space is "fragmented."
• Resource Starvation: If Job A grabs all the "workbenches" (ancilla) near it, Job B might have to wait forever to get its work done, even if there is empty space elsewhere.
• The Magic State Bottleneck: If there are only a few "factories" (magic state ports), and three jobs need them at once, two of them have to wait.

3. The Solution: A Smart City Planner

The team created a new "scheduler" (a smart city planner) that manages this grid. Instead of just throwing jobs in, it uses a set of rules to ensure everything fits together perfectly.

How their planner works:

• The "Compact Cluster" Rule: When a new job arrives, the planner doesn't just look for any empty space. It looks for a tight, compact group of "houses" right next to the job's assigned "factory." It builds the job's neighborhood as a tight, efficient cluster so it doesn't waste space.
• The "Workbench" Hierarchy: The planner knows that some workbenches are more important than others.
  • Core Workbenches: These are permanently assigned to a job.
  • Primary Scratchpads: These are nearby workbenches the job uses frequently.
  • Secondary Scratchpads: These are shared workbenches the job can borrow if needed.
    The planner dynamically shares these resources. If a job isn't using its secondary workbench, another job can borrow it, preventing idle time.
• The "Cultivation" Upgrade: In a more advanced version of their system, they get rid of the fixed "factories." Instead, any empty "workbench" tile can temporarily turn into a factory to produce the needed ingredients (magic states) and then turn back into a workbench when done. This is like having a mobile kitchen that sets up wherever there is space, rather than building a permanent restaurant in one spot.

4. The Results: Faster and Smoother

The authors tested their system using computer simulations with thousands of fake quantum jobs.

• Speed: Their system ran jobs 3.1 times faster than running them one by one.
• Improvement: It was about 29% faster than the previous best method for handling multiple jobs.
• Fairness: Even with many jobs running at once, the "slowdown" for any single job was very small (only about 10% slower than if it were running alone).
• Space Efficiency: Their method kept the "city" much less fragmented, leaving large, usable chunks of space available for new jobs, rather than a bunch of tiny, unusable gaps.

Summary

In short, this paper presents a new way to manage a quantum computer that is built like a structured city. By using smart rules to pack jobs tightly, share resources dynamically, and even turn empty spaces into temporary factories, they can run many complex jobs at once much more efficiently than before. They call this approach "No Tile Left Behind" because they make sure every single piece of the quantum floor plan is used effectively.

Technical Summary

1. Problem Statement

As quantum computing transitions from the Noisy Intermediate-Scale Quantum (NISQ) era to Fault-Tolerant Quantum Computing (FTQC), the challenge of multiprogramming (concurrently executing multiple workloads) evolves significantly.

• The Shift in Abstraction: In NISQ, multiprogramming deals with physical qubit topology and noise. In FTQC, specifically Surface Code architectures, the abstraction shifts to logical qubits protected by Quantum Error Correction (QEC).
• The Core Challenge: FTQC hardware is not a flat pool of qubits but a structured "floorplan" consisting of:
  1. Data Tiles: Logical patches storing qubits.
  2. Ancilla Tiles: Temporary workspace for lattice surgery (measurement, routing).
  3. Magic-State Resources: Dedicated factories or ports for non-Clifford (T) gates.
• The Difficulty: Concurrent execution must manage spatio-temporal constraints. Poor placement leads to floorplan fragmentation, starvation of magic-state resources, and contention for ancilla tiles, degrading throughput and Quality of Service (QoS). Existing NISQ schedulers are insufficient because they do not account for these structured, resource-constrained logical layouts.

2. Methodology

The authors propose a formal framework and a heuristic scheduler to manage these constraints.

A. Hardware Abstraction

The surface-code floorplan is modeled as an unweighted undirected graph $G=(V, E)$ where vertices represent tiles (Data, Ancilla, Magic State Ports).

• Workload Representation: A workload is a connected subgraph containing a set of data tiles, a set of ancilla tiles (core), and a magic-state port.
• Resource Classes:
  • Core Ancilla: Permanently pinned to the workload.
  • Primary Scratchpad: Ancilla adjacent to the core, used for immediate operations.
  • Secondary Scratchpad: Shared, elastic ancilla pool.

B. Static Allocation (Baseline)

For a batch of workloads with sufficient resources, the authors define a Static Allocation Problem to minimize ancilla commitment while maintaining connectivity.

• Algorithm 1 (Greedy Compact Partitioning): Assigns data tiles to workloads by seeding at the data vertex closest to a magic-state port and greedily expanding the cluster to the nearest unoccupied data vertex. This ensures spatial compactness and minimizes fragmentation.
• Algorithm 2 (Incremental Rooted Core Construction): Connects the assigned data cluster to the magic-state port using the minimum number of ancilla tiles (Steiner tree heuristic), forming a connected resident subgraph.

C. Resource-Limited Scenarios & Online Scheduling

The framework extends to scenarios where resources (Data, Magic State Ports, or Ancilla) are scarce and workloads arrive online.

• Limited Data Tiles: Uses a "best-fit" admission policy. Workloads are prioritized by size and how well they fit into remaining free regions to avoid fragmentation.
• Limited Magic State Ports: Ports are treated as shared services. The scheduler dynamically assigns ports based on delivery latency ($T_{init} + T_{prep} + \text{distance}$), using a lexicographic priority to resolve contention.
• Limited Ancilla Tiles: Introduces a hierarchical sharing policy.
  • Core Ancilla is strictly pinned.
  • Primary/Secondary Scratchpads are elastic.
  • A State Machine (QUEUE $\to$ PARKED $\to$ READY $\to$ ACTIVE) manages workloads. If resources are unavailable, workloads are "parked" (releasing core ancilla but keeping data pinned) or delayed in wait states.

D. Cultivation-Enabled Architectures

The framework is generalized to support Magic State Cultivation, where magic states are generated on-demand on idle ancilla tiles rather than via fixed distillation factories.

• Dynamic Abstraction: Removes fixed magic-state ports. Ancilla tiles cycle between Cultivating, Routing, and Ready states.
• Arbitration: The scheduler dynamically reclaims cultivating tiles for routing if needed, prioritizing data movement over magic state generation, then resumes cultivation.

3. Key Contributions

1. Formal Framework: Defined FTQC multiprogramming as a multi-constrained spatio-temporal placement problem, capturing data, ancilla, and magic-state constraints jointly.
2. Heuristic Algorithms: Developed Algorithm 1 (compact data partitioning) and Algorithm 2 (minimal ancilla core construction) to minimize resource wastage and fragmentation.
3. Hierarchical Policies: Designed policies for limited-resource scenarios (data, ports, ancilla) and online job arrivals, utilizing a state-machine approach for resource arbitration.
4. Cultivation Integration: Extended the framework to support dynamic magic-state generation, eliminating the need for fixed distillation factories.

4. Experimental Results

The authors evaluated the framework using synthetic Clifford+T workloads on a 20x12 floorplan (50% data density).

• Throughput Improvement:
  • Achieved a normalized system speedup of 3.1× compared to sequential standalone execution.
  • Outperformed the prior state-of-the-art (ILP-C and Corner Greedy baselines) by ~29%.
  • Outperformed random and naive baselines by ~64% and ~43%, respectively.
• Fragmentation Reduction: The proposed framework maintained ~10% more contiguous free space in the floorplan during peak execution compared to baselines, proving its effectiveness in preventing fragmentation.
• Quality of Service (QoS):
  • The average slowdown (ratio of shared execution time to standalone time) was kept low at ~1.10×.
  • The primary bottleneck identified was contention for secondary scratchpad ancilla under heavy loads.
• Cultivation Benefits:
  • Switching to cultivation-enabled architectures increased throughput by ~10% and reduced slowdown by ~1%.
  • Resource Savings: Eliminated the need for fixed distillation factories, saving approximately 173,000 physical qubits (for a distance-23 code) by removing the dedicated factory footprint.

5. Significance

This paper addresses a critical gap in the roadmap toward large-scale quantum computing. As hardware scales to hundreds of logical qubits, the ability to share resources efficiently is paramount.

• Architectural Impact: It moves beyond simple qubit counting to a holistic view of logical floorplan management, acknowledging that fragmentation is a primary killer of performance in FTQC.
• Scalability: The proposed heuristics are computationally efficient and scalable, making them viable for real-time cloud-based quantum scheduling.
• Future-Proofing: By integrating magic state cultivation, the framework aligns with emerging hardware trends that favor dynamic resource usage over static, hardware-heavy factories, significantly reducing the physical qubit overhead required for fault tolerance.

In summary, "No Tile Left Behind" provides the first comprehensive, formalized approach to multiprogramming in surface-code FTQC, demonstrating that intelligent spatial and temporal resource management can yield substantial performance gains and resource savings for future quantum cloud providers.