Why Are We Unrolling? The Importance of Structured Quantum Programs for Compilation

AI summary

Overview

Research area: Quantum compilation and quantum software engineering, specifically the representation and optimization of structured (non-straight-line) quantum programs.

Technical level: Intermediate. Readers should know what a quantum circuit is and have some familiarity with compiler pipelines, but the paper's argument is largely conceptual and is presented without dense mathematics.

Scope: The paper argues that quantum compilation must preserve program structure — loops, conditionals, runtime-dependent qubit allocation and indexing — rather than unrolling everything into flat circuits, and backs this argument with a formal definition, a taxonomy, a survey of existing frameworks, and a benchmark suite.

What This Paper Is About

Quantum compilers have historically treated compilation as circuit synthesis and optimization over a flat list of gates, but many fault-tolerant algorithms cannot be expressed as a single flat circuit at all, and unrolling those that can quickly becomes intractable. The paper defines what a "structured quantum program" is, classifies its constituent features by whether they merely help compilation or are strictly required for it, and asks the community to compile such programs without unrolling them. It also supplies the tooling to measure progress: a survey of current framework support and a benchmark suite of algorithms with varying structural requirements.

Key Contributions

1. A formal definition and taxonomy of structured quantum programs. Definition 1 states that a program is structured if its program counter does not evolve exclusively by unit increments. Seven structural primitives are identified (StatIter, DynIter, DynVal, CCond, QCond, DynAlloc, DynIdx) and grouped into Tier 0 (straight-line circuits), Tier 1 (structure as an enabler: StatIter, DynVal, CCond, DynAlloc — reducible to straight-line form at compile time), and Tier 2 (structure as a requirement: DynIter, QCond, DynIdx — impossible to unroll in advance).

2. A survey of structured-program support across major frameworks. Table III rates Qiskit, TKETv1, TKETv2, Catalyst, and mqt-cc against all seven primitives, distinguishing mere compatibility (a single checkmark: the framework can consume the construct and preserve semantics) from exploitability (a double checkmark: the compiler actively transforms and optimizes using the structure).

3. A structured-program benchmark suite distributed in the jeff exchange format. Table IV lists 26 algorithm entries spanning basic subroutines and primitives, transforms and arithmetic, heuristics/optimization/search, complex algorithms and simulation, and error correction/fault tolerance, annotated with which structural elements each requires and whether each scales to arbitrary size.

4. An end-to-end case study of the Repeat-Until-Success (RUS) benchmark through the parse, optimize, and lower stages of four compiler stacks, showing exactly where each pipeline breaks.

Main Findings

• Support is fragmented and incomplete. In Table III, Qiskit is compatible with StatIter, DynVal, CCond, QCond, and DynAlloc but incompatible with DynIter and DynIdx. TKETv1 is compatible only with CCond and QCond. TKETv2 is compatible with all seven and exploitable for all except DynAlloc, which is only compatible. Catalyst is exploitable across all seven. mqt-cc is compatible with StatIter, DynIter, and DynIdx and exploitable for DynVal, CCond, QCond, and DynAlloc.

• Exchange formats set a lowest common denominator. Neither QIR nor OpenQASM 3 is designed as an IR for aggressive transformation; both serve primarily as exchange formats. QIR's Base Profile restricts compilers to a flat profile, and OpenQASM 3 marks features such as dynamic qubit indexing as optional. Because hardware targets lack native support, many toolchains based on these formats bypass structured control flow entirely.

• Tier 1 features are easy to support but hard to exploit. Because statically-bounded loops and classical conditionals can be deterministically unrolled at compile time, a naive compiler achieves baseline compatibility as a preprocessing step. The value only appears when the compiler preserves them natively in its IR.

• Unrolling Grover's search scales catastrophically. The iteration count is N = O(sqrt(2^n)) for an n-qubit search space, so unrolling forces the optimizer to reprocess every gate in every iteration. Performing optimizations inside the loop body instead avoids this.

• Tier 2 features make unrolling impossible in principle. Dynamically-bounded loops, dynamic qubit indexing, and measurement-conditioned branches cannot be reduced to straight-line circuits under any circumstances, so compilers must handle them natively to be compatible at all. Shor's algorithm is used as the running example, with its runtime-selected value a affecting classical conditionals, loop termination, and gate parameters.

• The RUS pipeline fails at different stages in different stacks. Qiskit's API does not allow specifying dynamically-bounded while loops, so compilation fails at the parsing level. mqt-cc preserves these loops through optimization, and lowering succeeds when targeting the QIR Adaptive Profile but fails for the QIR Base Profile. TKETv2 compiles structured programs in the Guppy language to HUGR and lowers to streaming execution on the Helios quantum computer, completing the full pipeline. Catalyst supports structure at the language level via PennyLane, through compiler representation and transformations, and at execution level — but supports an array of simulators and no current hardware devices.

• Preserving structure can give constant compilation times. Figure 1 illustrates that structured programs can compile in time independent of problem-instance size, while unrolling produces polynomial or exponential growth in program size; the paper notes such constant scaling was demonstrated empirically in multiple frameworks and that the comparison programs were generated with mqt-cc.

• Classical compilation already settled this question. Polyhedral compilers (Pluto, PPCG) retain loop nests as explicit iteration spaces; accelerator IRs deliberately keep loops and conditionals until a final lowering step; database query engines optimize a relational-algebra plan before generating machine code. Where flattening happens in these systems, it is a local, deliberate choice rather than a wholesale expansion.

Methodology in Plain English

The authors proceed by argument and survey rather than by experiment. They start from the observation that fault-tolerant resource estimates reach millions of physical qubits and billions of gates, then give a formal definition of structure based on how the program counter moves during execution. From there they classify structural features by their effect on a compilation pipeline: features that can be resolved at compile time (Tier 1) and features that depend on runtime information (Tier 2). They then audit existing frameworks against these seven features, assigning each a mark for compatibility versus active exploitation, and diagnose why support is uneven by examining the design goals of QIR and OpenQASM 3. To make the problem measurable, they assemble a benchmark suite from published fault-tolerant algorithms, annotate each entry with the structural elements it needs, distribute it in the jeff exchange format, and walk one benchmark — Repeat-Until-Success — through four real compiler stacks to locate the failure points.

Why This Matters

Impact on research. Compilation time and memory that are independent of problem size change which algorithms are practically compilable. The paper reframes quantum compilation from circuit rewriting to structured-program transformation, and explicitly connects quantum work to decades of classical compiler research on loop nests, polyhedral optimization, and control-flow lowering.

Real-world applications (as named in the benchmark suite):

• Cryptography: Shor's algorithm, whose gates, loops, and register indexing depend on runtime values and therefore cannot be flattened before execution.
• Chemistry and materials simulation: block encodings for Hamiltonian simulation, quantum singular value transformations, and X-ray absorption spectroscopy.
• Search and optimization: Grover's search and Grover's search with weak measurement, plus variational workloads (VQE, QAOA, ML-QAE).
• Fault tolerance: magic state distillation, logical state preparation, syndrome measurement and correction, repeat-until-success, and measurement-based quantum computation.

Industry relevance. The survey covers the major compiler stacks and SDKs in use — Qiskit, TKETv1, TKETv2, Catalyst, and mqt-cc — plus IRs and languages including QIR, OpenQASM 3, MLIR, HUGR, Kirin, and Guppy, and hardware execution including Helios. Vendors building these tools get a direct scorecard of where their pipelines break, and the jeff-format benchmarks with existing or in-progress conversions to PennyLane/Catalyst, HUGR, Kirin, and mqt-cc lower the barrier to acting on it. The paper also stresses that dynamic control flow requires coordination with hardware control systems — a compiler can only optimize dynamic operations to the extent the device's classical control logic can execute them.

Future Directions

• Automated higher-level optimization that uses structure. The paper calls general, automated optimization strategies that leverage program structure "an exciting and open area of research"; existing systematic approaches are limited, with assertion-based optimization via the Z3 theorem prover and relational analysis for phase folding both facing constraints.
• Fixing the representation gap across the full toolchain. Since support is dictated by the weakest layer, IRs and exchange formats such as QIR (beyond the Base Profile) and OpenQASM 3 need to carry structured primitives natively rather than marking them optional.
• Co-design with hardware control systems. Dynamic loops, measurement-conditioned branches, and runtime indexing only pay off if devices and their classical control logic can execute them efficiently at runtime.
• Scalability evaluation by the community. Because many benchmarks (for example GHZ preparation over any number of qubits) scale to arbitrary size, framework developers are asked to stress-test compilation time and memory footprint at increasing instance sizes and to report support versus utilization separately.

Target Audience

Compiler engineers and SDK maintainers working on quantum software stacks, since the benchmark suite and the compatibility table translate directly into engineering roadmaps. Quantum algorithm researchers will find the taxonomy useful for expressing dynamic algorithms that current toolchains silently flatten. Graduate students and newcomers to quantum software seeking an entry point into structured-program compilation will benefit from the formal definition, the worked Shor example, and the classical-compiler parallels. Readers focused on near-term, straight-line circuit workloads are least likely to be affected, since the argument targets fault-tolerant scale and algorithms with runtime-dependent control flow.

Authors’ abstract

As quantum software stacks scale up to support future fault-tolerant quantum hardware and algorithms, quantum compilation is becoming an increasingly important component of the stack. How do we ensure that our software stacks support dynamic algorithms, including patterns such as mid-circuit measurement feedforward and repeat-until-success, with hundreds of logical qubits and billions of quantum operations? To do so, we must re-think how we represent quantum programs beyond straight-line circuits, to representations that include classical structure and dynamism, and make this the default representation to consider when performing quantum compilation. In this work, we present important patterns and algorithms from fault-tolerant quantum applications which admit a structured representation that we argue is crucial to preserve, and set a challenge to the community to compile such representations without unrolling them into straight-line quantum circuits. We also explore the status quo of structured program support in quantum software, and ask ourselves the rhetorical question: how much more efficient can we make quantum compilation tooling when we take into account the additional information from classical structure?