Quantum computing hardware and error correction theory have seen rapid progress in recent years. We are on the verge of achieving early fault-tolerant quantum computing (FTQC), with a stream of new architectural proposals targeting cryptanalysis and chemistry simulations. The design of quantum architectures, and compilation of useful applications to such architectures, is becoming a popular area of research with many new problems and opportunities.
This workshop aims to formulate clean TCS problems arising from this emerging topic, with particular emphasis on architectural design choices and tradeoffs, bottlenecks in space-time overhead, compilation methods and challenges, and mathematical formulation of hardware constraints. Example questions include lower bounds and tradeoffs on space-time overhead for FTQC, bounds on non-Clifford resources in algorithms, hypergraph expansion and sparsification for code surgery, adapting classical code-design principles to quantum codes, and more. As the race toward application-scale quantum computers accelerates, these architectural choices create timely opportunities for theoretical computer scientists to shape both algorithms and hardware.
Overview of modern FTQC architectures
Co-Designing Quantum Error Correction and Quantum Algorithms
High-rate quantum LDPC codes reduce the qubit overhead of fault tolerance, but they also change how logical operations must be designed, since many logical qubits share a single code block. For a given quantum error-correcting code, it is likely that certain operations are easier to do than others, motivating a complex instruction set. An important question is therefore how the error correction instruction set can be co-designed with the needs of quantum algorithms.
In this talk, we will describe recent work on co-designing logical instruction sets with algorithms, including the role of structure and parallelism in lowering the space-time cost of implementing logical algorithms. We discuss batching logical operations as a motif for applying the same fault-tolerant gadget across many code blocks at once and achieving constant space-time overhead, and then discuss how further adaptations into in-block batching can achieve further reductions in overhead.
Control complexity and fault tolerance of neutral-atom quantum computers
Reconfigurable neutral-atom arrays have emerged as a promising platform for high-rate quantum error correction and fault-tolerant computation, thanks to their long-range interactions and highly parallel control. In this tutorial, we will attempt to understand this connection from a theoretical perspective. What makes a fault-tolerant protocol easy or hard to implement on such a machine, and how should we quantify that distinction?
We will explore coarse-grained mathematical models that capture the essential capabilities and constraints of physical control and use simplified complexity analyses to understand how implementation costs scale with system size. Through examples of error correction and logical computation, we will examine why some protocols are better suited to the hardware and how their structure shapes tradeoffs between qubit overhead, parallelism, and control complexity. The goal is to identify general design principles and open theoretical questions for fault-tolerant architectures that remain efficient to control as they scale.
Surgery with ultra-low space overhead
We extend the design-space of LDPC surgery and use it to build very low overhead gadgets for BB codes.