Introduction

A quantum compiler is the engineering bridge between a quantum idea and a quantum device.

At the beginning, a programmer may have an algorithm: estimate the energy of a molecule, search a structured space, simulate a quantum system, or prepare a parameterized state for a variational experiment. At the end, a machine must receive instructions that fit its actual hardware: which qubits are used, which gates are allowed, when operations occur, how measurements are returned, and sometimes which microwave or laser pulses are applied. Between these two ends lies the work of compilation.

In classical computing, a compiler translates a program written in a language such as C, Rust, or Python into a lower-level form that a processor can execute. It also analyzes and improves the program: removing redundant instructions, choosing registers, arranging memory access, and scheduling operations. A quantum compiler plays a similar role, but the objects it manipulates are different. A quantum program is not only a sequence of ordinary instructions. It describes operations on quantum states, and those operations must respect the mathematical rules of quantum mechanics: linearity, unitarity for closed-system evolution, probabilistic measurement, and the impossibility of freely copying unknown quantum data. These rules are central to standard quantum computation texts such as Nielsen and Chuang’s Quantum Computation and Quantum Information (Nielsen and Chuang, 2010).

This book is about the engineering discipline that grows around that translation problem. We will study how quantum circuits are represented, analyzed, optimized, mapped to hardware, scheduled, checked for correctness, and executed on real quantum systems.

Why quantum compilation matters

A quantum algorithm is often described in a clean mathematical form. For example, a textbook might say: “Apply the quantum Fourier transform to these qubits,” or “repeat a phase-estimation circuit until the desired precision is reached.” Such descriptions are useful because they reveal the algorithmic idea. They are not, by themselves, usually executable on a specific device.

A real quantum device has constraints. It may allow only a small set of native gates. A native gate is an operation that the hardware can implement directly or nearly directly, such as a particular one-qubit rotation or a particular two-qubit interaction. It may connect only certain pairs of qubits. It may have qubits with different error rates. It may require measurements to take a non-negligible amount of time. It may be recalibrated frequently, so yesterday’s best placement of a circuit may not be today’s best placement.

This is especially important in the current era of noisy intermediate-scale quantum devices, often abbreviated NISQ. The term was introduced to describe devices with tens to hundreds, and later more, physical qubits that are not yet fully error-corrected and therefore remain strongly affected by noise (Preskill, 2018). In this setting, a compiler is not merely a translator. It is also a tool for survival: it tries to reduce the number of error-prone operations, shorten the circuit, choose better qubits, and preserve the intended computation as accurately as possible.

Consider a simple example. Suppose an algorithm asks for a CNOT gate between logical qubits q0 and q5. A CNOT, or controlled-NOT gate, flips the target qubit if the control qubit is in state 1. On paper, we may draw this operation between any two qubits. On hardware, q0 and q5 might not be directly connected. The compiler must then insert extra operations, often SWAP gates, to move quantum information through connected qubits until the CNOT can be performed. A SWAP gate exchanges the states of two qubits. This solves the connectivity problem, but it also increases circuit depth and exposes the computation to more noise. Mapping circuits to devices with limited connectivity is therefore a central compilation problem, studied in works such as Zulehner, Paler, and Wille’s methodology for mapping quantum circuits to IBM QX architectures (Zulehner, Paler, and Wille, 2018).

The compiler’s decisions can change whether an experiment succeeds. Two compiled circuits may implement the same ideal unitary operation, but one may require fewer two-qubit gates, use better-calibrated qubits, or finish before decoherence has damaged the state too much. Noise-adaptive compilation methods explicitly use calibration information to choose mappings that improve expected performance on noisy devices (Murali et al., 2019).

The first mental model: from meaning to machine

The central question of compilation is:

How do we transform a program while preserving the computation it is supposed to perform?

To answer this, we need two ideas: semantics and implementation.

The semantics of a program is its meaning. In quantum circuit compilation, the semantics might be a unitary matrix, a probability distribution over measurement outcomes, or a hybrid quantum-classical behavior involving measurements and conditional control. For example, the circuit

H q0
H q0

has the same ideal effect as doing nothing to q0, because the Hadamard gate is its own inverse: applying it twice gives the identity operation. A compiler can safely remove this pair if no intervening operation changes the meaning.

The implementation is the concrete form used to run the program. For the same example, an implementation might be a gate-level instruction stream saying that no gate needs to be applied to q0. On a different target, implementation may go even lower and describe calibrated pulses that realize a gate. This book focuses mainly on circuit-level and intermediate-representation-level compilation, while also explaining how those levels connect to real hardware execution.

A useful way to picture the compilation path is:

algorithmic idea
    ↓
quantum program or circuit
    ↓
intermediate representation
    ↓
optimized circuit
    ↓
mapped and routed circuit
    ↓
scheduled hardware-level program
    ↓
execution and measurement results

Each arrow hides engineering choices. When translating an algorithm to a circuit, we choose gate decompositions. When building an intermediate representation, we choose what information the compiler can inspect. When optimizing, we choose which transformations are valid. When mapping, we choose physical qubits. When scheduling, we choose timing. When executing, we confront calibration, noise, and measurement.

The goal is not simply to produce a runnable circuit. The goal is to produce a circuit that is correct enough, efficient enough, and appropriate for the target machine.

What is different from classical compilation?

Classical compiler engineering gives us many useful concepts: parsing, intermediate representations, data-flow analysis, optimization passes, register allocation, scheduling, testing, and target-specific code generation. Quantum compiler engineering inherits this general structure, but it must adapt it to quantum information.

First, quantum data cannot be treated like ordinary bits. A classical bit is either 0 or 1. A qubit is described by a state vector in a complex vector space. For one qubit, a pure state can be written as

\[ \alpha |0\rangle + \beta |1\rangle, \]

where \(\alpha\) and \(\beta\) are complex numbers and \(|\alpha|^2 + |\beta|^2 = 1\). The numbers \(|\alpha|^2\) and \(|\beta|^2\) are the probabilities of observing 0 or 1 if the qubit is measured in the computational basis. This mathematical representation is standard in the circuit model of quantum computation (Nielsen and Chuang, 2010).

Second, most quantum gates used in ideal circuit descriptions are unitary. A unitary operation is a linear transformation that preserves inner products, and therefore preserves total probability. This means a compiler cannot arbitrarily erase unknown quantum data the way a classical optimizer might delete or overwrite temporary values. Deleting an unused classical variable is often harmless. Discarding or resetting a live qubit can change the state of the entire computation, especially if that qubit is entangled with others.

Third, measurement is not just reading a value that was already there in the classical sense. A measurement produces a classical outcome according to quantum probabilities and generally changes the quantum state. For example, if a qubit is in

\[ \frac{|0\rangle + |1\rangle}{\sqrt{2}}, \]

then measuring it in the computational basis returns 0 with probability \(1/2\) and 1 with probability \(1/2\). After the measurement, the qubit is no longer in the same superposition; it has been projected into a state consistent with the outcome. Therefore, compiler transformations around measurements require special care.

Fourth, unknown quantum states cannot be copied perfectly. This is the no-cloning theorem: there is no physical operation that takes an arbitrary unknown quantum state and produces two identical independent copies of it. The theorem was established in early work by Wootters and Zurek and independently by Dieks (Wootters and Zurek, 1982; Dieks, 1982). This affects compiler design because many classical compiler techniques rely on copying values freely. In a quantum compiler, copying a computational-basis classical value stored in a qubit may be possible under certain conditions, but copying an arbitrary quantum state is not.

Fifth, hardware constraints are unusually visible. In classical computing, most programmers do not think about which exact transistor performs an addition. In near-term quantum computing, the distinction between qubit 3 and qubit 7 may matter because their coherence times, gate errors, readout errors, and connectivity differ. A compiler for such machines often uses a target description: a structured summary of the operations, qubits, timing, and error data available on a backend.

These differences make quantum compilation a rich subject. It combines mathematics, computer architecture, algorithms, programming-language design, optimization, and experimental constraints.

Circuits as the first working language

The main representation we will begin with is the quantum circuit. A circuit is a structured description of operations applied to qubits over time. It is not necessarily a literal physical wire diagram. It is a mathematical and engineering notation.

For example, the following circuit prepares a simple entangled state called a Bell state:

H q0
CNOT q0, q1

Read it line by line. First, apply a Hadamard gate H to q0. Starting from \(|00\rangle\), this creates

\[ \frac{|00\rangle + |10\rangle}{\sqrt{2}}. \]

Then apply a CNOT with q0 as control and q1 as target. The result is

\[ \frac{|00\rangle + |11\rangle}{\sqrt{2}}. \]

This state is entangled: it cannot be written as a product of one independent state for q0 and one independent state for q1. If we measure both qubits in the computational basis, we get either 00 or 11, each with probability \(1/2\). The outcomes are correlated.

A compiler must preserve this meaning unless it is explicitly allowed to approximate. It may replace the Hadamard gate with a sequence of native rotations. It may reverse the direction of a CNOT using additional one-qubit gates if the hardware supports only the opposite direction. It may insert SWAP gates to satisfy connectivity. But after all transformations, the intended outcome probabilities should remain the same in the ideal model, or close enough under a stated approximation metric.

This is why circuit semantics appears early in the book. Without a precise meaning for circuits, “optimization” becomes dangerous. A shorter circuit is not better if it computes the wrong thing.

Intermediate representations: the compiler’s workspace

A compiler rarely works directly with only the source text the programmer wrote. It usually converts the program into an intermediate representation, or IR. An IR is an internal form designed to make analysis and transformation easier.

In a quantum compiler, an IR may look like a list of gates, a graph of dependencies, a control-flow structure with quantum and classical variables, or a hybrid representation that combines several of these. The choice matters.

Suppose a circuit contains the gates

Rz(theta) q0
Rz(phi)   q0

where Rz is a rotation around the \(z\)-axis of the Bloch sphere. Since two rotations around the same axis on the same qubit combine, the compiler may replace them with

Rz(theta + phi) q0

This is easy if the IR stores symbolic parameters such as theta and phi in a form the compiler understands. It is harder if the operations are opaque strings.

Now suppose a circuit contains measurement and classical control:

measure q0 -> c0
if c0 == 1:
    X q1

The compiler must represent not only quantum operations but also classical data dependencies. The X q1 gate depends on the measurement result c0. An optimization pass must not move the conditional gate before the measurement, because that would change the program’s meaning.

Much of compiler engineering is the design of representations that make correct transformations natural and incorrect transformations difficult.

Optimization is not one thing

The word optimization often suggests making something “best.” In compiler engineering, it usually means improving a program according to selected cost metrics while preserving semantics. A cost metric is a quantity used to evaluate a compiled program.

Different applications care about different metrics. For a near-term experiment, reducing two-qubit gate count may be crucial because two-qubit gates often have higher error rates than one-qubit gates on many platforms. For a fault-tolerant algorithm, reducing T-count or T-depth may be more important because non-Clifford resources can dominate the cost of error-corrected computation. For a dynamic circuit, measurement latency and classical feedforward time may matter. For a variational algorithm, keeping compilation stable across parameter updates may be as important as reducing gate count.

Here is a small example of local optimization:

X q0
X q0

Because the Pauli-X gate is its own inverse, the two gates cancel. The compiler can replace them with nothing, provided no measurement, reset, or other operation between them observes or changes q0.

But optimization can also be global. Consider a circuit with many CNOT gates. Some may commute past other gates. Some may cancel only after reordering. Some may be expensive because they occur between distant physical qubits. The compiler must choose which transformations to try and in what order. A pass that reduces one metric may worsen another. Reducing gate count can increase depth. Improving mapping can reduce fidelity if it uses worse qubits. There is no single universal optimization strategy for all quantum programs and all machines.

Correctness and approximation

A compiler pass is correct if it preserves the intended semantics according to an agreed criterion. For purely unitary circuits, one common criterion is equality up to global phase. A global phase is a complex factor of magnitude one multiplying the entire state, such as \(e^{i\theta}\). Global phase is not observable in ordinary measurement probabilities, so two unitary circuits that differ only by global phase are physically equivalent for many purposes.

For example, the matrices \(U\) and \(-U\) differ by a global phase of \(-1\). If applied to the same state and then measured, they produce the same outcome probabilities.

However, not all programs are purely unitary. Measurements, resets, classical control, and noise require more general notions of equivalence. Sometimes exact equality is also impossible or too expensive. If a target gate set cannot implement a rotation exactly, the compiler must approximate it. Then correctness becomes a statement such as: “The compiled circuit is within error \(\epsilon\) of the ideal circuit under this distance measure.”

This book will introduce the necessary distance ideas carefully. The important point for now is that optimization and mapping must be guided by a precise meaning of “same enough.”

The path through the book

We begin by asking what a quantum compiler does in the larger quantum software stack. Then we build the mathematical foundations needed for precise reasoning: complex vector spaces, tensor products, unitary matrices, projectors, norms, and probability. These tools are not decorative; they are the language in which compiler correctness is expressed.

After that, we study qubits, gates, measurements, and circuits. We then examine universal gate sets and cost models, because a compiler needs to know what operations are allowed and what makes one circuit cheaper than another. We move from algorithms to compiler inputs, then to programming languages and circuit formats such as OpenQASM, an assembly-like representation for quantum circuits introduced to support experiments on gate-based quantum processors (Cross et al., 2017).

The middle chapters develop the compiler’s core machinery: intermediate representations, semantics, circuit analysis, local optimization, Clifford compilation, gate synthesis, reversible logic, approximate synthesis, mapping, routing, scheduling, and noise-aware compilation.

The later chapters specialize these ideas. Variational algorithms require parameter handling and stable compilation. Fault-tolerant machines require logical resource estimates and careful accounting of expensive operations. Verification, testing, and debugging help us trust compiler implementations. Finally, we build a minimal compiler and compare ideas with real toolchains and research directions.

The theme throughout is engineering with semantics. A quantum compiler is not a bag of tricks for shortening circuits. It is a disciplined system for transforming quantum programs while keeping their meaning under control.

How to study this book

As you read, keep three questions nearby.

First, ask: What is the program’s meaning? If you cannot say what a transformation must preserve, you cannot judge whether it is correct.

Second, ask: What does the target machine allow? A circuit that is elegant on paper may be inefficient or impossible on a particular backend.

Third, ask: Which cost matters here? Gate count, depth, two-qubit count, fidelity, latency, T-count, memory, compilation time, and verification effort are different quantities. Good compiler engineering begins by knowing which tradeoff is being made.

You do not need to know all of quantum computing before reading this book. The necessary mathematics and circuit concepts will be built step by step. But you should be willing to move between two modes of thinking: the mathematical mode, where we ask what a circuit means, and the engineering mode, where we ask how to make that meaning run on imperfect hardware.

That movement between meaning and machine is the heart of quantum compiler engineering.

References

Cross, A. W., Bishop, L. S., Smolin, J. A., and Gambetta, J. M. (2017). “Open Quantum Assembly Language.” arXiv:1707.03429.

Dieks, D. (1982). “Communication by EPR devices.” Physics Letters A, 92(6), 271–272.

Murali, P., Baker, J. M., Javadi-Abhari, A., Chong, F. T., and Martonosi, M. (2019). “Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers.” Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’19), 1015–1029.

Nielsen, M. A., and Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.

Preskill, J. (2018). “Quantum Computing in the NISQ era and beyond.” Quantum, 2, 79.

Wootters, W. K., and Zurek, W. H. (1982). “A single quantum cannot be cloned.” Nature, 299, 802–803.

Zulehner, A., Paler, A., and Wille, R. (2018). “An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 38(7), 1226–1236.