Space-Time Optimisations for Early Fault-Tolerant Quantum Computation

arXiv:2511.08848 · quant-ph · Submitted 2025-11-12 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Space-Time Optimisations for Early Fault-Tolerant Quantum Computation".

Mira: Here's the gist of the paper. The gist: Our work develops compilation techniques tailored to early FTQC systems, including distillation-adaptive qubit layouts and routing techniques, which show that simple greedy heuristics are extremely effective for this problem, offering up to 60 % reduction in the number of qubits compared to prior works.

Kai: Problem Motivation Fault-tolerance is the future of quantum computing, ensuring error-corrected quantum computation that can be used for practical applications Resource requirements for faulttolerant quantum computing (FTQC) are daunting, and hence, compilation techniques must be designed to ensure resource efficiency There is a growing need for compilation strategies tailored to the needs of early FTQC systems, including distillation-adaptive qubit layouts and routing techniques.

Mira: Early fault-tolerant quantum computers (FTQC) are being developed by physically implementing QEC on real hardware.

Kai: These systems currently have only a handful of logical qubits, with very limited support for running logical operations.

Title and authors: Kai: Moving on to what this paper is actually proposing, the title "Space-Time Optimisations for Early Fault-Tolerant Quantum Computation" points directly at how they are trying to optimize the space versus time trade-off in these limited systems.

Mira: It’s about finding a better balance between having enough time for operations and not needing too much physical space on the hardware when you're dealing with magic state distillation factories.

Lev: The core problem they tackle is that magic state distillation is resource intensive, and they are looking at how to manage those resources efficiently during the compilation process.

Kai: They show that their compiler can offer an average fifty-three percent reduction in logical qubit count compared to previous layouts, which sounds pretty significant for scaling up <ref:2511.08848#pg1>.

Mira: That fifty-three percent reduction is substantial when you think about the constraints of early FTQC machines and how limited they are right now.

Lev: But we have to remember that this comes with an average execution time increase of one point two times, so we're trading some time for space savings in this specific case <ref:2511.08848#pg1>.

Kai: And they compare it against layouts from a previous work, specifically layout twenty-eight, which gives us a baseline to see the improvement <ref:2511.08848#pg1>.

The paper's summary: Mira: So, summarizing what the authors are doing, they introduce a compilation pipeline with three stages: mapping, routing, and scheduling for programs written in the Clifford plus T gate set.

Kai: In that mapping stage, they assign circuit qubits to a two-dimensional grid of logical qubits parameterized by the number of routing paths you choose.

Lev: The actual heavy lifting is done in the routing phase where they use an adapted version of Dijkstra’s algorithm with a binary heap priority queue data structure for efficient path finding.

Mira: Their main focus for reducing qubit requirements is on two specific things: first, using only a limited number of ancilla qubits during logical operations on surface codes because those are usually local and need very few ancillas.

Kai: Second, they insert a limited number of routing paths and use greedy heuristics to route magic states from the distillation factories to where they are needed in the logical qubits.

Lev: These two techniques rely on finding a minimum set of logical qubit movements either to rearrange ancillas or move those magic states, which is how they determine the minimum set required.

The paper's improvements: Kai: The results show that across various benchmarks, this compiler offers an average fifty-three percent reduction in logical qubit count compared to layouts from twenty-eight, and an average execution time increase of one point two times <ref:2511.08848#pg1>.

Mira: It’s also interesting when you look at the comparison with layout thirty-one, where their approach achieves a two times reduction in spacetime volume with just one distillation factory, which is impressive <ref:2511.08848#pg1>.

Lev: They are also distillation-adaptive in their design, meaning they allocate just enough routing paths to prevent bottlenecks from magic state routing, which is a smart move for early FTQC.

Kai: They also show that it’s important to jointly optimize the allocation of routing paths in the compiler and the allocation of magic state factories in the architecture.

Mira: This suggests that you can't just optimize one part; you need to look at both how many paths you use and how many factories you have available for a better overall result.

Conclusion: Kai: So, to wrap up, this paper with its focus on Space-Time Optimisations for Early Fault-Tolerant Quantum Computation gives us a way to get an average fifty-three percent reduction in logical qubit count while managing the execution time tradeoff <ref:2511.08848#pg1,Space-Time Optimisations for Early Fault-Tolerant Quantum Computation>.

Mira: It moves away from just handpicking spacetime configurations by offering a richer set of tradeoffs and execution times that are very close to the lower bound, which is good for finding near-optimal resource usage.

Lev: From an engineering standpoint, their compiler offers execution times that are very close to the lower bound, even though we still see an average increase of one point two times compared to what’s theoretically possible with only distillation processing time as the bottleneck <ref:2511.08848#pg1>.

Kai: So, this compiler has the potential to be a really important part of the compilation toolchain as these systems scale up and inform how we design our software for these early FTQC architectures.

Mira: It’s a solid piece of work because it gives us better guidance on how to structure those resource allocations between routing and distillation factories.

Lev: I just want to say that seeing the results against the lower bound, even with that one point two times execution time increase, shows they've done something concrete for real hardware constraints <ref:2511.08848#pg1>.

University of Cambridge

quant-ph

Submitted: 2025-11-12

Updated: 2026-10-22

DOI: 10.1109/CGO68049.2026.11395205

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 62/100

The gist: The gist: Our work develops compilation techniques tailored to early FTQC systems, including distillation-adaptive qubit layouts and routing techniques, which show that simple greedy heuristics are

Key concepts

Distillation-Adaptive Qubit Layouts: This technique involves dynamically adjusting how logical qubits are arranged on a 2D grid based on the needs of magic state distillation factories. The compiler allocates just enough routing paths to prevent bottlenecks from these factories, ensuring efficient qubit usage during complex operations.
Greedy Heuristics for Routing: The compiler uses simple, effective rules (greedy heuristics) during the routing phase to move magic states from distillation factories to where they are needed. This involves determining a minimum set of logical qubit movements required to rearrange ancillas or move these necessary states efficiently.
Spacetime Volume Optimization: This metric measures the resource efficiency of a quantum circuit by balancing the number of qubits (space) and the time taken for computation (time). The compiler's goal is to find configurations where this volume is minimized, often by finding an optimal balance between factory count and routing paths.
Dijkstra’s Algorithm Adaptation: This algorithm is used during the routing phase to efficiently find the best path for qubits or magic states across the 2D grid. It is implemented using a binary heap priority queue, allowing the compiler to quickly select which qubit or state to process next in an optimized sequence.

Terminology

Distillation — 51× in this paper · explained in 2 episodes
Benchmark — 11× in this paper · explained in 2 episodes
Ancilla Qubits — 9× in this paper · explained in 2 episodes
Fidelity — 3× in this paper · explained in 2 episodes
Hubbard Model — 3× in this paper · explained in 5 episodes
Quantum Circuits — 3× in this paper · explained in 2 episodes
Resource Constraints — 3× in this paper · explained in 5 episodes
Abundance — 2× in this paper · explained in 1 episode
Directed Acyclic Graph (DAG) — 2× in this paper · explained in 2 episodes
Abstraction — 1× in this paper · explained in 1 episode
Computational overhead — 1× in this paper · explained in 2 episodes
Decoherence — 1× in this paper · explained in 2 episodes
Physical Constraints — 1× in this paper · explained in 7 episodes
Scan-Access Memory — 1× in this paper
Superconducting Qubits — 1× in this paper · explained in 2 episodes

Summary

The gist: Our work develops compilation techniques tailored to early FTQC systems, including distillation-adaptive qubit layouts and routing techniques, which show that simple greedy heuristics are extremely effective for this problem, offering up to 60 % reduction in the number of qubits compared to prior works.

Problem Motivation

Fault-tolerance is the future of quantum computing, ensuring error-corrected quantum computation that can be used for practical applications Resource requirements for faulttolerant quantum computing (FTQC) are daunting, and hence, compilation techniques must be designed to ensure resource efficiency There is a growing need for compilation strategies tailored to the needs of early FTQC systems, including distillation-adaptive qubit layouts and routing techniques. Early fault-tolerant quantum computers (FTQC) are being developed by physically implementing QEC on real hardware. These systems currently have only a handful of logical qubits, with very limited support for running logical operations. To support application executions well, we require compilation strategies that are tailored to the capabilities of early FTQC systems.

Compilation Techniques

Our compiler takes as input a quantum program expressed in the Clifford+T gate set. The pipeline comprises three stages: mapping, routing, and scheduling. In the mapping stage, the circuit qubits are assigned to a 2D grid of logical qubits. These routing paths are created by assigning rows/columns of bus qubits. The primary optimisation is performed during the routing phase, where we employ an adapted version of Dijkstra’s algorithm for efficient path-finding. We use Dijkstra’s algorithm implemented with binary heap priority queue data structures to efficiently select the next qubit to process.

Key Optimizations

The work focuses on two opportunities to reduce qubit requirements. First, logical operations on the surface code are typically local and require very few ancilla qubits. Second, FTQC requires resource-intensive magic state distillation factories and associated routing qubits. We develop a compiler for early FTQC systems based on greedy heuristics that reduce qubit requirements through two techniques. To reduce qubit requirements during logical operations, we provision a limited number of ancilla qubits. Second, we insert a limited number of routing paths and use greedy heuristics to route magic states from the distillation factories to the logical qubits where they are used. Both techniques rely on determining a minimum set of logical qubit movements either to rearrange ancillas or move magic states.

Performance Results

Across benchmarks, our compiler offers an average 53% reduction in logical qubit count, with an average execution time increase of 1.2×, compared to layouts given in [28]. In comparison with [31], our approach achieves, on average, a 2× reduction in spacetime volume with a single distillation factory. Our compiler is distillation-adaptive and reduces spacetime volume by allocating just enough routing paths to prevent bottlenecks from magic state routing. We show that it is important to jointly optimise the allocation of routing paths in the compiler and the allocation of magic state factories in the architecture.

Conclusion

Our work enables a richer set of space vs. time tradeoffs compared to prior work which handpicks certain spacetime configurations. Our compiler offers execution times that are very close to the lower bound. Overall, our compiler offers execution times that are very close to the lower bound. As systems scale up, our work has the potential to be an important part of the compilation toolchain and inform software design.

How it works

The mapping stage assigns circuit qubits to a 2D grid of logical qubits parameterized by the number of routing paths. The routing phase employs an adapted version of Dijkstra’s algorithm for efficient path-finding combined with gatedependent moves for neighbouring qubits. Gate-dependent moves constitute a form of look-ahead compilation where the compiler examines subsequent operations before deciding the qubit’s movement. Space search is employed to determine an appropriate placement of ancilla for a specific gate operation by searching the 2D grid for the nearest unoccupied cell.

Evaluation Metrics

We compare our results with three state of the art FTQC compilation techniques in Figure 11. We evaluate qubit cost, execution time, and the spacetime volume against the LSQCA approach presented in [22]. We get, on an average, a 20% decrease in spacetime volume across all benchmarks. Our approach offers execution times that are very close to the lower bound. The execution time is calculated by assigning a unit cost (1d timestep) to all operations in lattice surgery.

Architectural Insights

We show that more routing paths are needed to see the effects of a greater factory count. The optimum lies in between, where execution time and qubit count balance out. More magic states require more routing paths to relieve routing congestion and achieve low space-time volume. Our approach is able to generate better, near-optimal results in conditions with a constrained set of resources.

Comparison with DASCOT

When there is an abundance of T states, the spacetime product of the DASCOT approach is the lowest. At one factory in the 2D Fermi-Hubbard circuit (top), the DASCOT spacetime product averages at 1.96× the spacetime product from our approach. As we introduce distillation constraints, DASCOT’s spacetime volume increases relative to our results.

Lower Bound Calculation

The lower bound (l) is calculated by the formula l = nT ∗ tMSF / nMSF (2). The lower bound describes an ideal scenario where the only bottleneck determining the execution time is the preset distillation processing time. On average, we record an increase of roughly 1.2× in the execution time compared to the lower bound.

References

[1] (2025). Pauli product measurement. https://pennylane.ai/compilation/pauli-product-measurement

[2] AbuGhanem, M. (2025). Ibm quantum computers: evolution, performance, and future directions. The Journal of Supercomputing, 81(5):687

[3] Acharya, R., Abanin, D. A., Aghababaie-Beni, L., Aleiner, I., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Astrakhantsev, N., Atalaya, J., Babbush, R., Bacon, D., Ballard, B. C., Bengtsson A., Bilmes A., Blackwell S., Boixo S., Bortoli G., Bourassa A., Bovaird J., Brill L., Broughton M., Browne D. A., Buchea B., Buckley B...

[4] Andersen, C. K., Remm, A., Lazar, S., Krinner, S., Lacroix, N., Norris, G. J., Gabureac M., Eichler C., and Wallraff A. (2020). Repeated quantum error detection in a surface code

[5] Beverland, M., Kliuchnikov, V., and Schoute, E. (2022a). Surface code compilation via edge-disjoint paths

[6] Beverland, M. E., Murali, P., Troyer, M., Svore, K. M., Hoefler T., Kliuchnikov V., Low G. H., Soeken M., Sundaram A., and Vaschillo A. (2022b). Assessing requirements to scale to practical quantum advantage

[7] Blunt, N. S., Geher, G. P., and Moylett, A. E. (2024). Compilation of a simple chemistry application to quantum error correction primitives

[8] Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz T., Ebadi S., Cain M., Kalinowski M., Hangleiter D., Bonilla Ataides J. P., Maskara N., Cong I., Gao X., Sales Rodriguez P., Karolyshyn T., Semeghini G., Gullans M. J., Greiner M., Vuletic V., and Lukin M. D. (2024).

Improvements for AI systems

Optimization of Qubit Allocation for Early FTQC Systems

The improved system can perform circuit compilation that offers an average 53% reduction in logical qubit count compared to prior works by effectively managing ancilla qubits and routing paths, moving from a typical data-to-ancilla ratio of 1:2 or 1:3 down to approximately 2:1.

Distillation-Adaptive Resource Management

The AI system can dynamically determine the optimal combination of factory count and routing paths for each application by balancing qubit overhead and execution time, leading to a reduction in spacetime volume, as seen where the optimum lies in between, where execution time and qubit count balance out.

Application-Specific Layout Determination

The compiler can select the best physical layout for specific problems like condensed matter Hamiltonians by finding that the optimal range to implement these circuits is between 4 and 6 routing paths, tailoring resource allocation to the required instruction mix.