Source-linked AI summary
A Software Methodology for Compiling Quantum Programs
Thomas Häner, Damian S. Steiger, Krysta Svore, Matthias Troyer
TL;DR
Scalable quantum computing needs a complete software methodology beyond manually optimized logic-level programs. The paper presents a layered, embedded-language compilation architecture that translates quantum programs through intermediate representations, libraries, error correction, and hardware-specific mapping. The methodology is designed to support diverse backends and accelerate collaboration and innovation across quantum software and hardware development.
Problem
Quantum computing lacks a complete end-to-end methodology for compiling and optimizing programs beyond logic-level descriptions and manual optimization.
Method
The paper proposes a layered architecture centered on an embedded domain-specific language, quantum intermediate representations, reusable libraries, optimization, error correction, and hardware-specific backends.
Results
The methodology supports scalable compilation for diverse backends, including simulators, emulators, resource analyzers, and quantum hardware.
Takeaways & Limitations
The software stack provides a common platform for developing and testing quantum algorithms, hardware components, and interfaces among researchers and experimentalists.
Abstract
from arXiv · showhide
Quantum computers promise to transform our notions of computation by offering a completely new paradigm. To achieve scalable quantum computation, optimizing compilers and a corresponding software design flow will be essential. We present a software architecture for compiling quantum programs from a high-level language program to hardware-specific instructions. We describe the necessary layers of abstraction and their differences and similarities to classical layers of a computer-aided design flow. For each layer of the stack, we discuss the underlying methods for compilation and optimization. Our software methodology facilitates more rapid innovation among quantum algorithm designers, quantum hardware engineers, and experimentalists. It enables scalable compilation of complex quantum algorithms and can be targeted to any specific quantum hardware implementation.
I. INTRODUCTION
Quantum computing lacks a complete end-to-end methodology for compiling programs beyond manually optimized logic operations. The proposed scalable flow uses embedded high-level languages, layered compilation, reusable libraries, and hardware-specific backends to connect algorithm development with quantum hardware.
- Quantum-classical system context: Quantum computers operate as coprocessors controlled by classical hardware, requiring fast feedback and, in many implementations, distributed temperature environments.Qubits may require cryogenic temperatures while classical processors and memory units are placed at several temperatures to balance heat dissipation and communication speed.
- Motivation: Quantum computing remains mostly described at the logic-operation level, while a complete end-to-end compilation and optimization methodology is lacking.The paper frames scalability as supporting quantum algorithms of any size.
- High-level programming: The methodology begins with an embedded domain-specific language that represents hybrid classical and quantum programs while leveraging existing host-language infrastructure.Its high-level compilers remain hardware-agnostic and use quantum meta functions such as conditional instructions and user annotations for optimization.
- Backends and impact: The architecture targets simulators, emulators, resource analyzers, and diverse quantum hardware, enabling communication among algorithm designers, engineers, and experimentalists.It is intended to support hardware implementations including ion traps, superconducting systems, quantum dots, and topological quantum computers.
- Libraries and optimization: Quantum and classical libraries support code reuse, while library compilation and auto-tuning can select efficient circuit representations for target backends.The methodology extends existing compilation frameworks with tuned arithmetic, subroutine, and gate libraries.
- Compilation stack: The compilation stack generates quantum intermediate representations, links pre-compiled libraries, creates a logical layout, applies error correction, and maps the resulting low-level representation to hardware.The layered flow separates high-level compilation from hardware-specific mapping and supports optimization before final hardware realization.
III. QUANTUM PROGRAMS
Quantum programs combine classical and quantum instructions through an embedded DSL, libraries, quantum types, and compiler-aware control patterns. These abstractions support hardware-conscious optimization while respecting reversibility, limited qubits, and the cost of controlled operations.
- An embedded DSL supports hybrid quantum/classical programs by combining host-language, user, and quantum libraries.
- Quantum types: Quantum types include qubits, quantum registers, integers, fixed-point values, and floating-point values, with variable register sizes for early hardware.Variable-size representations address the extremely limited qubit counts of early quantum computers.
- Quantum control flow: Compute/uncompute annotations let the compiler reverse temporary computations automatically and optimize controlled sequences.Ancilla qubits must be clean before disposal or reuse.
- Quantum control flow: Controlled operations can multiply gate costs, so decompositions trade rotation locality, parallelization, and extra qubits to reduce controlled gates.A single control can double rotations and add CNOTs or require Fredkin gates plus an additional qubit.
- Quantum control flow: The quifelse meta function reduces a conditional inverse rotation from ten gates to three.It replaces two controlled rotations with operations selected by whether the control qubit is 0 or 1.
- Quantum libraries: Quantum arithmetic and mathematical libraries provide optimized reversible implementations selected for target architectures through auto-tuning.Reversible quantum math is difficult because methods must work across superpositions, and straightforward Newton iteration can scale exponentially with qubit count.
IV. COMPILATION PROCESS
Compilation translates high-level quantum programs into hardware instructions through layered compilers and intermediate representations. The process is illustrated with Shor’s algorithm, whose high-level pseudocode is compiled toward a specific backend.
- Quantum compilation is a layered sequence of compilation and optimization steps producing QIR and, after error correction, LLQIR.Layering keeps higher-level compilers hardware-agnostic and increases code reuse.
- The toolchain translates eDSL quantum programs through QIR and LLQIR before producing hardware instructions.
- Shor’s algorithm provides the running example for compiling high-level pseudocode to a specific quantum hardware target.The example includes quantum phase estimation and a final measurement.
A. Host language compilation
The host-language compiler handles classical control and early optimizations, dispatches quantum operations to backend-dependent libraries, and transforms high-level mathematical and quantum constructs into backend calls.
- The host compiler resolves classical control statements, performs initial optimizations, and dispatches quantum statements to backend-dependent library functions.Using the classical compiler for these tasks reduces the effort required to implement the quantum compilation framework.
- The detailed toolchain represents successive compiler outputs as QIR and LLQIR before translating the result into hardware instructions.
- Host compilation can replace resource allocation with backend initialization and translate mathematical, QPE, and measurement operations into backend or library calls.
B. High-level quantum compiler
The high-level quantum compiler expands library calls and meta functions while exploiting program structure for optimization. It repeatedly lowers available source-level abstractions until no further source-backed library calls remain.
- The high-level quantum compiler uses structural information to replace meta instructions and optimize the quantum program.
- Controlled compilation can avoid controlling compute/uncompute sections and choose controlled library implementations or generate them from source.
- Combining rotations before gate synthesis performs a quantum analogue of constant folding at a higher abstraction level.
- For Shor’s algorithm, the compiler inlines QPE, selects iterative phase estimation when register size limits precision, and resolves controls on Ua.
- Compilation iterates library replacement and optimization until no source-available library calls remain, producing a quantum intermediate representation.
C. Low-level quantum compiler
The low-level compiler translates quantum gates into sequences from a discrete, technology-dependent gate set, then applies hardware-specific synthesis and local optimization. In the Shor example, controlled rotations are decomposed into elementary gates, with approximation choices trading runtime against accuracy.
- The low-level compiler translates quantum gates into sequences from a discrete gate set determined by the hardware and error-correction strategy.
- Rewriting and synthesis of gates: Gate synthesis decomposes multi-qubit and single-qubit operations into hardware-specific primitives such as CNOT, T, H, and S gates.
- Optimizations: Local optimization reduces expensive operations, including the number of T gates on architectures where they are costly.
- Shor example: In Shor’s algorithm, inverse-QFT controlled rotations are decomposed into CNOT, S, H, and T gates during low-level compilation.
- Shor example: Rotation synthesis exposes a runtime–accuracy trade-off: tolerance 10^-10 uses a longer sequence than tolerance 10^-4.
D. Logical layout generator and optimizer
The logical layout stage assigns quantum variables and library operations to logical qubits while accounting for hardware-relevant locality, operations, timing, and parallelism. Early machines may skip a separate error-correction stage by treating physical qubits as logical qubits.
- Low-level compiler output still contains library calls that must be replaced with hardware-optimized code before logical layout is completed.
- Logical qubits are ideal algorithm-level abstractions, whereas physical qubits are noisy and may be combined through error correction to represent one logical qubit.
- Logical layout maps quantum variables to logical qubits and considers locality, available operations, timing, and parallelism.
- Nonlocal interactions may require expensive teleportation or swapping when gates can only connect neighboring qubits.
- Early quantum computers without enough qubits for error correction treat physical qubits as logical qubits and skip the next correction step.
E. Quantum error correction (QEC)
Quantum error correction protects logical qubits by encoding them across physical qubits and decoding measured error information classically. The required code and resources depend on device properties, gate fidelity, and algorithmic workload.
- Quantum error correction protects logical qubits by encoding information across multiple physical qubits and extracting error information through measurement.
- The number of physical qubits per logical qubit depends on device error rates and the selected code’s protection capacity, or distance.
- The surface code can protect against error rates of up to 1%.
- Quantum decoding is classical and occurs on a classical processor, often requiring more computation than a classical repetition-code majority vote.
- QEC protocol selection depends on hardware-qubit properties, gate fidelity, and the number of logical gates in the algorithm.
F. Physical layout generator and optimizer
The physical layout stage maps physical qubits to hardware qubits and adjusts gate operations for the target device. The mapping can be straightforward when the hardware layout is designed around a specific error-correction scheme.
- Physical qubits are mapped to actual hardware qubits during the physical layout stage.
- The mapping may be straightforward when the hardware layout is designed around a specific error-correction scheme.
- Some gate operations may require adjustments for the target hardware.
G. Mapping to hardware
The methodology supports diverse software and hardware backends by translating physical gates into device-specific control while providing simulators, emulators, and resource counters for development and analysis.
- Hardware backends: Hardware backends map physical gate operations to device-specific control signals, such as microwave pulses for superconducting-qubit X gates.Each quantum technology and device can expose distinct native gates and control interfaces.
- Backend variety: The architecture supports software backends including simulators, emulators, and resource counters in addition to hardware backends.This backend variety allows programs to be analyzed or executed across multiple target environments.
- Simulators: Simulators represent quantum states with wave functions whose size grows as 2^N for N qubits and can model hardware noise.Current supercomputers can simulate approximately 40–50 qubits, while sparse matrix-vector multiplication implements gate operations.
- Emulators: Emulators accelerate selected computations by replacing detailed gate sequences with higher-level operations such as classical mathematical functions or fast Fourier transforms.They can also diagonalize matrices for small quantum phase-estimation instances and record full measurement distributions.
- Emulators: Repeated gate sequences can use dense-matrix repeated squaring, trading O(n) sparse matrix-vector operations against O(log n) dense matrix-matrix operations.The faster choice depends on the operation trade-off for the specific repetition count and representation.
- Resource counters: Resource counters track the qubits and gates an algorithm would use on a specified quantum computer to guide algorithm design and optimization.Absolute crossover time matters in addition to asymptotic scaling.
VI. OPTIMIZATION AND AUTO-TUNING OF LIBRARIES
The paper describes library-level auto-tuning and multiple compilation strategies, while emphasizing that quantum libraries expose a large architecture-dependent optimization space.
- Auto-tuning: Auto-tuning compiles multiple library-function variants and selects the version with the best runtime.Because optimization is expensive, tuning is performed on pre-compiled library functions to keep quantum-program compilation times reasonable.
- Optimization space: Trivially applying auto-tuning is infeasible because quantum libraries expose many parameters and alternative implementations.Adder selection depends on operation count, gate types, space constraints, uncomputation cost, and the target architecture.
- Compilation strategies: Quantum compilation may occur at runtime, at host-language compile time, or by post-processing an intermediate representation.Examples include transforming LLVM output from C++ or MSIL output from C# or F# compilers.
- Language integration: The software architecture uses embedded domain-specific languages to represent quantum types and operations through types and functions in a classical host language.This approach leverages existing host-language infrastructure and avoids porting classical functionality to a new quantum language.
- Implications: The methodology is intended to support testing and development across hardware and software components and to accelerate innovation among quantum theorists, engineers, and experimentalists.The paper anticipates demonstrations of quantum programs across different devices and values optimized emulation backends for algorithm development.
Appendix A: Appendix
The appendix introduces vector and matrix representations of quantum states and operations, then illustrates how gate application produces circuit behavior.
- State representation: A single qubit is represented by a two-dimensional complex vector whose amplitudes satisfy |α|^2 + |β|^2 = 1.The normalization condition ensures that measurement probabilities sum to 1.
- State representation: Two-qubit basis states enumerate the four classical-bit configurations, and an n-qubit state is represented by a complex vector of length 2^n.The two-qubit state may include amplitudes for |00⟩, |01⟩, |10⟩, and |11⟩.
- Composite states: The state of two independent qubits is formed by the tensor product of their individual states, equivalent to the Kronecker product in vector notation.The appendix contrasts product states with entangled states, which cannot all be written in this form.
- Gate application: Applying a CNOT or NOT gate is modeled as multiplying the state vector by the corresponding gate matrix.The resulting circuit diagram is shown in Figure 11.