45. Quantum Compilation
45.1What a Quantum Compiler Does
One sentence: transform a logical circuit into a hardware schedule, preserving semantics (the unitary, up to global phase), minimizing a cost function under hardware constraints. Same contract as classical compilers, three twists: semantics is a matrix, not a program behavior (correctness = unitary equivalence, checkable by simulation at small n — a gift); the cost function is physical (error probability ≈ Σ per-gate errors, plus decoherence ∝ depth); and the hardware description itself is mutable data (calibration drift means the backend "target" is a snapshot, and compiling twice a day apart can differ). Qiskit's PassManager is the reference architecture; QIR (LLVM-based) and OpenQASM 3 are the interop layers.
45.2Parsing
Front end: read circuits in OpenQASM 2/3 (the field's lingua franca — human-readable, hardware-honest with its gate definitions), Qiskit's Python API (the de facto authoring format), QIR (LLVM bitcode for the LLVM-generation tools), or vendor formats. A parser must handle: gate definitions (user-defined macros expanding to primitives), parameter expressions (θ/2 arithmetic — symbolic, resolved at compile time), barriers (scheduling fences), and classical registers + control flow (OpenQASM 3's if/while — dynamic circuits). Your toy compiler (end of part) parses the 17.10 format, extended with parameters; parsing well-designed input formats is 20% of compiler effort and 80% of interop pain.
45.3Intermediate Representations
The IR is where passes live. Options, honestly compared: DAG circuits (Qiskit's DAGCircuit — nodes are operations, edges are data dependencies; the workhorse, since gate commutation and cancellation become graph operations), ZX-diagrams (category-theory-flavored graphs; rewrites are sound local moves; the most powerful optimizing IR), tensor networks (compilation-as-contraction, niche but growing), and QIR's SSA-flavored form (for embedding in classical toolchains). Design lesson from classical compilers, fully applicable: passes should be small, composable, individually testable, and the IR should make invalid circuits unrepresentable. You will implement a DAG IR in the project; the exercise generalizes.
45.4Gate Decomposition
The algebraic core (44.6 made practical): basis translation via KAK/Cartan decomposition (any two-qubit gate → ≤3 CX + singles; Qiskit TwoQubitBasisDecomposer), Euler-angle decomp for single-qubit gates (ZXZ is native-friendly for IBM, XYX elsewhere), rotation merging (RZ(a)·RZ(b) → RZ(a+b) — free depth), and multi-controlled gate synthesis choosing among tradeoffs (no ancilla = more gates; ancillas = fewer but wider). The pass must be conservative: decompositions differ in noise profile, and the "shortest" decomposition is not always the best-echoed. Test every decomposition with Operator(equivalence) checks — matrix equality up to global phase is a one-liner, and it is your proof of correctness.
45.5Optimization
The peephole heart. Rules worth implementing: adjacent-gate cancellation (X·X = I; H·H = I; CX·CX = I — pattern-match on the DAG), rotation merging across barriers' absence, commutation-gated cancellation (slide X past a control it commutes with, then cancel — the classic Optimize1qGatesDecomposition win), identity deletion of zero-angle rotations, and template matching (precomputed small-circuit equivalences, rewrote-in-place). Yield on real circuits: 20–40% depth reduction before routing; more after, since routing creates adjacent-gate garbage. All rules are mathematically justified equivalences — implement each with its own unit test (matrix equality), because one unsound peephole rule silently corrupts every downstream computation.
45.6Routing
Making the circuit fit the coupling graph. The standard: SWAP insertion — to run a two-qubit gate between non-adjacent qubits, insert SWAPs along the shortest path, then track the accumulating permutation of logical→physical mapping. The search space is huge (which qubits to swap, in what order), so heuristics rule: SABRE (swap-map bidirectional heuristic — Qiskit's default) scores candidate swaps by look-ahead decayed distance. Smarter variants: bridge gates (4 CX emulate a remote CX without full swap), remote CNOT via teleportation (needs entanglement budget — real in fault-tolerant machines), and Pauli-network routing (commute CX-rich chemistry circuits into routable order first — enormous wins, see 46.5). Measure routing by SWAP count and resulting depth; they disagree.
45.7Qubit Mapping
Where each logical qubit initially lands — chosen before routing, tuned with it. The optimizer's information: per-qubit T1/T2, per-gate fidelities (calibration data varies 2–3× across a chip!), coupling quality. Layout scoring heuristics: noise-adaptive layout (Qiskit's VF2Layout/NoiseAdaptiveLayout) picks the best-error-rate subgraph matching your circuit's interaction shape; mapping a line-shaped circuit onto a line-shaped subgraph of heavy-hex avoids most routing. The underappreciated lever: identical circuits on different layouts differ 2–5× in success probability — free performance, no algorithm change, just a better initial_layout. Always benchmark layout choice on your actual workload; defaults are averages, and your circuit is not average.
45.8Scheduling
From gate list to timeline (44.7's engineering view, here the compiler's): compute ASAP/ALAP times over the DAG with real gate durations; insert delays on idle qubits; optionally schedule deliberately — align independent layers to enable dynamical decoupling insertion (46.6's cousin), batch two-qubit gates within crosstalk constraints, respect measurement windows. Output formats: the scheduled DAG, or pulse schedules at the bottom layer. The metric is not just depth but idling time distribution — a circuit can be depth-optimal and still die because one qubit idles 2 µs. Scheduling against decoherence is where quantum compilation most plainly becomes systems engineering; Gantt-chart your circuits (Qiskit's timeline drawer) at least once to feel it.
45.9Noise-Aware Compilation
The modern frontier: compile for the noise, not just against it. Ingredients: a noise model (from calibration: per-gate error, T1/T2, readout error per qubit — or learned, see Ch. 61), cost functions that estimate total circuit error (not gate count), and passes that use it: noise-adaptive layout (45.7), fidelity-aware routing (prefer swaps through clean couplers), dynamical decoupling tailored to the noise spectrum, and echo/pulse-stretching choices per gate instance. The 2020s research wave — including ML-based compilation policies — lives here. Honest caveat: calibration data is a snapshot of a drifting machine; noise-aware gains are real but must be re-earned each run. Your benchmark harness should re-pull calibration data every experiment.
45.10Compilation Cost Functions
You cannot optimize what you cannot score. The menu, from cheap to honest: gate count (fast, dumb), depth (better, still physical-fiction), two-qubit gate count (the standard proxy — dominates error), Σ per-gate error over the schedule (needs calibration data; the practical standard), full noisy simulation of the compiled circuit (small n only), and expected logical error under a code model (fault-tolerant era). Benchmarking discipline (46.8): fix the metric, fix the input set (a standard circuit zoo: QFT, adders, Grover instances, chemistry ansätze), report distributions over seeds (routing heuristics are randomized!), and always compile with your cost function in mind — compilers game any metric they're given, including yours.