QROB: Quantifying Realization Overhead in Quantum Compilation via Reverse Construction

AI summary

Overview

Research area: Quantum computer architecture and compilation — specifically benchmarking of qubit routing (NISQ SWAP routing), fault-tolerant lattice-surgery scheduling, and capacity-constrained quantum memory-access scheduling.

Technical level: Advanced. The paper assumes familiarity with coupling graphs, the qubit routing problem, surface-code patches, lattice surgery, and routing ancillae, though the central idea is explained through an accessible analogy.

Scope: The paper introduces QROB, a reverse-construction framework that generates quantum compilation benchmark instances together with retained, compiler-independent reference realizations, and uses it to measure how far existing compilers sit from a feasible reference cost.

What This Paper Is About

Quantum programs are written assuming logical qubits can interact freely, but real hardware only allows interactions between nearby qubits, so compilers must insert extra operations (SWAPs in near-term devices, routing channels in fault-tolerant architectures) to bridge the gap. Judging whether a compiler is doing this well requires knowing the best achievable cost, but finding that optimum is NP-hard and unknown at practical scale. QROB's goal is to manufacture benchmark instances backwards from directly realizable circuits, so that a feasible reference solution and its exact cost are known by construction, giving a calibrated yardstick for measuring compiler overhead.

Key Contributions

1. A unified, scalable reverse-construction methodology. QROB retains feasible reference realizations while generating benchmark instances spanning 9 to 900 qubits in sub-second time, covering both NISQ SWAP routing and fault-tolerant lattice-surgery scheduling under one framework.

2. A practical tool for characterizing compiler-reference gaps. QROB supplies calibrated references against which a compiler's realization overhead can be rigorously measured, enabling evaluation of performance-scalability tradeoffs across system sizes.

3. A high-quality data source for learning-based compilation. QROB references serve as supervision for data-driven compilers, providing scalable training targets where validated labels would otherwise be unavailable.

4. An extension beyond geometric routing. QROB-Mem instantiates the same reference-preserving principle for capacity-constrained quantum memory-access scheduling, where a compute region of capacity K must be managed against a larger memory region, with compute–memory exchanges as the cost unit.

Main Findings

• Large NISQ routing gaps: Qiskit SABRE incurs 7.2× the QROB reference SWAP count on average, with the ratio growing from 3× on 16-qubit systems to 24× on 156-qubit processors. The abstract reports NISQ compilers incurring up to 24.1× the reference SWAP cost.

• Large fault-tolerant scheduling gaps: In the fault-tolerant regime, the evaluated lattice-surgery compilers incur 6.3–7.0× the QROB reference execution time (up to 7.0× the reference makespan).

• Training data beats benchmark-fitting: A router trained on QROB references outperforms Qiskit SABRE on 84.8% of real-world application circuits. An identical model trained on adversarial benchmark labels reaches 94.7% validation accuracy yet fails on 75% of real workloads.

• Gap translates to physical fidelity: On real hardware with full Qiskit O3 enabled on three 156-qubit IBM Heron-r2 processors, QROB reference realizations achieve a median mirror-circuit survival rate 1.65× that of O3's own compilations, with the advantage widening as system size increases.

• References track exact optima on small cases: On a 3×3 grid, IR-mode references closely track the OLSQ2 exact solver across increasing circuit complexity, while Qiskit's heuristic degrades substantially.

• Certification at scale: A Controlled Distance Disruption (CDD) mode yields references that are certifiable by construction at scales where exact solvers fail, using monotone distance growth, qubit-disjoint chains, and collateral-free scrambling, combined with a graph-theoretic lower bound based on each nonadjacent interaction requiring at least dist(q_i, q_j) − 1 exchanges.

• Reference cost and structural regime are separable: The weighting function controls how broadly a perturbation couples across the instance, so QROB can produce instances with comparable reference cost but substantially different structural organization.

Methodology in Plain English

The core idea rests on an asymmetry between solving a problem forwards and constructing one backwards, illustrated with a Rubik's Cube: finding a shortest solution to a scramble is expensive search, but a designer who starts from the solved state and applies a known sequence of moves can read off a valid return path simply by reversing that sequence.

QROB does the same for compilation in two stages. First, it builds an ideal circuit whose every two-qubit gate acts on physically adjacent qubits, so its routing cost is zero by construction. Four strategies supply structural variety — Snake and Partition Snake greedily extend paths to mimic deep sequential chains and structured concurrency, while Random Walk and Ensembled Random Walk concentrate interactions into localized bottlenecks and spatially separated clusters. An Extended Variational Strategy additionally emulates block-wise entanglement layers of variational algorithms (such as QAOA/VQE) by isolating a bounded-degree subgraph with 2–3 neighbors and periodically repeating and locally densifying those matching layers.

Second, influence-guided scrambling walks backwards through the circuit's layers, applying exchange (swap) operations on the hardware graph that break the direct realizability of gates. At each step it scores every admissible exchange by how much damage it does to future layers, weighted by one of three planning horizons — Cut-Off (short-sighted, finite lookahead), Decay (gradually diminishing penalty on future layers), and Global (whole sequence deeply coupled). For NISQ the score is the loss of directly executable gates weighted by edge fidelity; for lattice surgery it is conflict pressure over shortest routing paths competing for already-reserved routing ancillae. Because the exchange sequence is recorded, reversing it yields a legal realization and its exact cost without ever solving the forward optimization.

Reference quality is established two ways: solver-based calibration against OLSQ2 on tractable small instances, and construction-based certification via CDD mode at large scale. The authors state explicitly that QROB does not claim to solve optimal compilation — IR-mode references are high-quality heuristic baselines, not proven global optima. The overall construction runs in O(D·|E|·d) time, polynomial in circuit and graph size.

The memory-access extension works differently: instead of spatial routes, it plants a trajectory of resident sets, each holding exactly K logical qubits drawn from an active pool of A > K recurring qubits, then emits gate batches acting only on the members of each set. Replaying the trajectory gives a legal realization whose exchange cost is counted and machine-checked; the scheduler sees only the gate-dependency DAG, K, and the initial resident set.

Why This Matters

Compiler quality in quantum computing has typically been reported as relative improvement over other compilers, with no principled notion of distance to an achievable bound. Classical kernel optimization has ceilings such as the roofline model, and quantum analogues such as the quantum hardware roofline exist — but those are compiler-dependent, since their ceilings are fixed per workload from existing compiler outputs, which makes them circular for judging a compiler. QROB supplies the missing compiler-independent complement: a calibrated reference for minimum realization overhead.

Potential application areas:

• Near-term hardware execution: Reducing SWAP overhead on sparse superconducting coupling maps, where inserted SWAPs and the resulting depth directly worsen decoherence.
• Fault-tolerant surface-code systems: Reducing space–time overhead in static-patch lattice-surgery scheduling, where nonlocal logical interactions consume temporary routing ancillae.
• Compute/memory-separated architectures: Evaluating scheduling policies for logical-qubit residency under a hard compute-region capacity, a problem the paper aligns with classical register allocation.
• Training data pipelines for learned compilers: Supplying validated labels at scales where exact solvers cannot reach, avoiding the failure mode where a model fits adversarial benchmark labels (94.7% validation accuracy) but fails on 75% of real workloads.

Industry relevance: The hardware result — 1.65× median mirror-circuit survival versus full Qiskit O3 on three 156-qubit IBM Heron-r2 processors — indicates that closing algorithmic compilation gaps converts directly into physical fidelity on commercially available machines, which matters to anyone operating or benchmarking quantum systems. The paper is accepted to the 59th IEEE/ACM International Symposium on Microarchitecture (MICRO 2026), placing it in the computer-architecture community rather than only the quantum-information one.

Future Directions

• Determining how close IR-mode references are to true optima at scale. The paper calibrates IR mode against OLSQ2 only on tractable small instances (a 3×3 grid) and certifies optimality only under CDD's restricted structural constraints; whether IR references remain near-optimal on large, structurally diverse instances is not established.
• Broadening certified construction beyond CDD's restrictions. CDD deliberately sacrifices structural diversity for provable optimality, leaving open how to certify references that retain realistic application structure.
• Extending reference preservation to further constraint types. QROB-Mem is described as a test of extensibility beyond geometric routing rather than a full spatial-route construction, so applying the principle to other architecture-specific constraints remains an open direction.
• Using QROB references as training targets for stronger learned compilers. The paper shows a QROB-trained router beating SABRE on 84.8% of real circuits and notes that augmenting basic-strategy GNN training with Extended Variational instances improves performance on real-world variational benchmarks; scaling such supervision further is a natural next step.

Target Audience

Quantum compilation and computer-architecture researchers who need calibrated baselines for evaluating routers and lattice-surgery schedulers; benchmark and tooling developers building evaluation infrastructure for quantum software stacks; machine-learning researchers training data-driven compilers who need validated supervision labels; and hardware teams at superconducting and fault-tolerant quantum vendors who want to quantify how much of their fidelity loss is attributable to compilation rather than to the device itself. Readers without background in coupling graphs, surface-code patches, and lattice surgery will find the methodology section demanding despite the accessible Rubik's Cube framing.

Authors’ abstract

Quantum compilation reconciles a program's idealized interaction topology with hardware locality constraints, yet evaluations at scale lack calibrated references for realization overhead. We present QROB, a scalable reverse-construction methodology that generates compilation instances backward from directly realizable configurations, retaining the inverse paths as feasible, compiler-independent references. QROB provides a common evaluation substrate for NISQ SWAP routing and fault-tolerant lattice-surgery scheduling, while extending its reference-preserving principle to capacity-constrained quantum memory-access scheduling. Across systems ranging from 9 to 156 qubits, evaluations highlight QROB's utility as both a diagnostic benchmark and a data source. First, for compiler characterization, QROB reveals substantial realization gaps in existing tools, with NISQ compilers incurring up to 24.1x the reference SWAP cost and fault-tolerant compilers requiring up to 7.0x the reference makespan. Second, as a supervision source for data-driven compilation, a router trained on QROB references outperforms Qiskit SABRE on 84.8% of real-world application circuits. Finally, on real hardware, QROB reference realizations achieve a median mirror-circuit survival rate 1.65x that of full Qiskit O3 compilations across three 156-qubit IBM Heron-r2 processors, demonstrating that closing algorithmic compilation gaps translates directly into physical fidelity gains.