Source-linked AI summary
Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
Prakash Murali, Jonathan M. Baker, Ali Javadi Abhari, Frederic T. Chong, Margaret Martonosi
TL;DR
Current quantum hardware is too small, noisy, and variable to run many proposed algorithms reliably, making efficient NISQ mapping essential. The paper develops LLVM-based optimal and heuristic, calibration-aware compilation methods and evaluates them on real IBM hardware. The best approach improves success rate by 2.9x on average and up to 18x over IBM Qiskit, while addressing compilation scalability.
Problem
NISQ hardware has severe resource constraints, low reliability, limited connectivity, and spatially and temporally varying characteristics, creating a need for efficient mappings.
Method
The paper develops an LLVM compiler that maps quantum programs to OpenQASM and IBMQ16 executables using optimal and heuristic methods informed by calibration data and routing choices.
Results
2.9x average success-rate improvement, up to 18x, was achieved over IBM Qiskit, while SMT methods scaled to 32 qubits and heuristics scaled beyond 32 qubits.
Takeaways & Limitations
Calibration-aware placement and mapping can substantially improve the reliability and runtime of quantum executions on NISQ hardware.
Takeaways & Limitations
The mapping model assumes hardware qubits arranged on a 2-D grid with two-qubit operations permitted only between adjacent qubits, and SMT methods may not scale well to systems of 500 qubits or more.
Abstract
from arXiv · showhide
A massive gap exists between current quantum computing (QC) prototypes, and the size and scale required for many proposed QC algorithms. Current QC implementations are prone to noise and variability which affect their reliability, and yet with less than 80 quantum bits (qubits) total, they are too resource-constrained to implement error correction. The term Noisy Intermediate-Scale Quantum (NISQ) refers to these current and near-term systems of 1000 qubits or less. Given NISQ's severe resource constraints, low reliability, and high variability in physical characteristics such as coherence time or error rates, it is of pressing importance to map computations onto them in ways that use resources efficiently and maximize the likelihood of successful runs. This paper proposes and evaluates backend compiler approaches to map and optimize high-level QC programs to execute with high reliability on NISQ systems with diverse hardware characteristics. Our techniques all start from an LLVM intermediate representation of the quantum program (such as would be generated from high-level QC languages like Scaffold) and generate QC executables runnable on the IBM Q public QC machine. We then use this framework to implement and evaluate several optimal and heuristic mapping methods. These methods vary in how they account for the availability of dynamic machine calibration data, the relative importance of various noise parameters, the different possible routing strategies, and the relative importance of compile-time scalability versus runtime success. Using real-system measurements, we show that fine grained spatial and temporal variations in hardware parameters can be exploited to obtain an average $2.9$x (and up to $18$x) improvement in program success rate over the industry standard IBM Qiskit compiler.
1 Introduction
NISQ systems bridge the gap between quantum algorithms’ resource demands and current hardware, but their noise, limited connectivity, and changing characteristics make reliable compilation difficult. The paper develops calibration-aware optimal and heuristic mappings and evaluates them on IBMQ16, achieving substantial gains in success rate, runtime, and scalability.
- Motivation: Current quantum prototypes provide far fewer resources than most proposed QC algorithms require, limiting practical execution.Public systems have roughly 20 qubits or fewer, while even a 72-qubit system would remain 5–6 orders of magnitude smaller than Shor’s resource requirements.
- NISQ constraints: NISQ computers have roughly 1000 qubits or fewer, are typically too small for error correction, and require efficient mappings to produce useful results.The paper evaluates mapped executables on a public 16-qubit IBM system.
- Compiler requirements: Reliable mapping requires intelligent initial placement, efficient orchestration of computation and SWAP operations, and reduced exposure to operational and decoherence errors.Topology-aware placement is important because unnecessary movement adds communication operations and associated failure risk.
- Approach: The LLVM compiler maps Scaffold programs to OpenQASM and IBMQ16 executables while comparing optimal and heuristic methods, movement policies, and calibration adaptation across 12 programs.The framework supports real-system evaluation of alternative mapping strategies.
- Results: 2.9x average success-rate improvement, up to 18x, and 2.7x average execution-time improvement, up to 6x, were achieved over IBM Qiskit.Against an optimal calibration-unaware baseline, gains reached 1.68x in execution time and 9x in success rate.
- Scalability: SMT-based methods scale to 32 qubits, while calibration-aware heuristics provide similar reliability and execution time with more scalable compile-times beyond 32 qubits.This addresses the need for compilation that remains tractable across NISQ-range machines.
- Mapping effects: Zero-qubit-movement mappings achieved up to 2.8x higher success likelihood than programs requiring even one qubit-movement operation.The comparison spans the paper’s 12 benchmarks.
- Significance: NISQ systems are presented as stepping-stones toward mature quantum computing, with calibration-aware mapping helping advance practical execution.The contribution targets the gap between current hardware and larger-scale quantum computing.
2 Background on Quantum Computing
Quantum programs manipulate qubit amplitudes with gates and obtain classical outputs through measurement. NISQ hardware makes this process difficult because qubits decohere, operations are noisy, connectivity is limited, and calibration characteristics vary over time.
- Quantum computing principles: A qubit stores quantum information as a superposition of |0⟩ and |1⟩, represented by complex amplitudes whose squared magnitudes sum to 1.Quantum gates modify these amplitudes, while measurement collapses the state to a classical basis-vector output.
- Quantum computing principles: A CNOT is a two-qubit gate that flips its target when the control is |1⟩ and can create entanglement between the qubits.The paper denotes a CNOT with control C and target T as CNOT C,T.
- Quantum computing principles: An n-qubit fully entangled system has a state space of size 2^n, with initialization, amplitude manipulation, and measurement forming the application workflow.The desired classical outputs are obtained after measurement.
- NISQ systems: NISQ systems have short coherence times, high gate-error rates, limited connectivity, and insufficient resources for error-correcting codes.These constraints make efficient mapping necessary for useful near-term applications.
- Hardware constraints: On IBMQ16, hardware CNOTs are supported only between adjacent grid qubits, so non-adjacent interactions require SWAP operations.Each SWAP requires three CNOT gates, adding execution operations and exposure to CNOT errors.
- Calibration variability: IBM machines expose daily measurements of relaxation time, coherence time, gate errors, and readout errors, whose qubit characteristics vary substantially across space and time.The paper reports coherence time varying up to 9.2x across qubits and daily calibrations.
- Reliability motivation: Programs with more than 16 CNOT operations have less than a 50% chance of executing correctly, motivating compiler strategies that avoid unreliable hardware regions.The optimization target is higher individual-run success probability.
3 Compilation Framework: Overview
The framework compiles machine-independent quantum programs into executables by jointly mapping qubits, scheduling operations, and adapting decisions to hardware topology and noise. It supports optimization-based and heuristic strategies, with IBM Qiskit as the comparative baseline.
- Framework overview: Noise-aware mappings use calibration data to avoid unreliable qubits and high-error gates while reducing movement required for non-adjacent CNOTs.The BV4 example contrasts a naive mapping requiring swaps and unreliable operations with a mapping that avoids both.
- Framework overview: Compiler inputs include the program, hardware configuration, and options such as routing policy and solver approach; outputs are mapped, scheduled executables.The optimization pipeline generates constraints before assigning program qubits to hardware qubits and scheduling operations.
- Optimization-based mappings: Optimization-based variants formulate program information, topology, timing, and routing as constrained SMT problems with mapping, start-time, and path variables.Constraints enforce distinct qubit assignments, dependency-respecting schedules, and non-overlapping routing paths.
- Optimization-based mappings: The reliability objective models overall execution reliability from gate reliabilities, while heuristic alternatives analyze program-graph CNOT structure and gate frequency.The paper compares optimization-based approaches with greedy methods designed to improve scalability.
- Heuristic mappings: GreedyV⋆ places qubits in descending degree order, whereas GreedyE⋆ places frequently interacting CNOT pairs first to reduce movement and improve reliability.GreedyV⋆ prioritizes highly connected program qubits; GreedyE⋆ prioritizes edges by the number of invoked CNOTs.
4 Optimal Compilation
Optimal compilation expresses mapping, scheduling, routing, timing, and reliability requirements as constraints over a hardware model. Variants optimize execution time or reliability while incorporating routing policies and, for calibration-aware methods, hardware-specific durations and coherence limits.
- Notations and assumptions: The compiler represents qubit locations, gate start times, durations, reliabilities, and dependencies while assuming a 2-D grid with adjacent-qubit two-qubit operations.CNOT and readout operations dominate the reliability score used in the formulation.
- Mapping and scheduling: Mapping constraints assign distinct hardware qubits, while scheduling constraints enforce dependency order and account for gate durations and routing time.CNOT duration includes the operation itself and state movement needed to bring qubits adjacent.
- Timing and coherence: Calibration-aware variants use hardware-specific CNOT durations and require gates to finish before the coherence times of the qubits they use.These variants incorporate daily changes in coherence time and CNOT duration into optimization constraints.
- Routing policies: Rectangle reservation blocks the bounding region of each CNOT, preventing spatially overlapping CNOTs from executing simultaneously.The routing constraint combines spatial overlap checks with temporal non-overlap requirements.
- Routing policies: One-bend routing restricts each CNOT to one of two paths along the control-target bounding rectangle and selects a junction for the route.The two path segments are checked for overlap using the same rectangle-based reasoning.
- Reliability optimization: Reliability optimization tracks CNOT and readout reliabilities, converts their product into an additive logarithmic objective, and can weight readout errors separately.Single-qubit errors are omitted for IBMQ16 because they are much smaller than CNOT and readout errors.
- Reliability optimization: R-SMT⋆ places qubits at reliable hardware locations and indirectly reduces movement, producing optimal reliability under the model and near-optimal execution duration experimentally.Its reliability objective accounts for both CNOT and readout operations and routing effects.
5 Heuristic Compilation
The heuristic compiler methods use a program graph and precomputed reliable hardware paths to place qubits without solving the full optimization problem. They prioritize either highly connected qubits or frequently used CNOT edges.
- Scalability: Heuristics are evaluated as scalable alternatives because they may approach SMT reliability while remaining tractable for larger NISQ systems.The paper motivates heuristic methods as comparators to optimization-based approaches for future machines with hundreds of qubits.
- Heuristic framework: Heuristic methods construct a program graph with qubit nodes and CNOT edges, then compute the most reliable hardware path between every hardware-qubit pair.Dijkstra’s algorithm uses negative-log CNOT reliability as the edge weight.
- Greatest vertex degree first: GreedyV⋆ orders program qubits by descending degree and places the highest-degree qubit at a highly reliable hardware location.Subsequent placements maximize the total reliability of paths to already placed neighbors.
- Greatest weighted edge first: GreedyE⋆ orders program edges by descending weight, where edge weight is the number of CNOT invocations between the corresponding qubits.High-weight edges are placed first to keep frequently interacting qubits close together and reduce movement.
6 Experimental Setup
The experiments evaluate 12 Scaffold-derived quantum programs, synthetic circuits spanning 4–128 qubits and 128–2048 gates, and compilation configurations that vary solver, routing, calibration, and optimization choices.
- Benchmarks: 12 benchmark programs include Bernstein–Vazirani, Hidden Shift, Quantum Fourier Transform, a one-bit adder, Toffoli, and other quantum kernels.The benchmarks were selected from prior compilation and system-benchmarking work and implemented in Scaffold.
- Benchmarks: Synthetic benchmarks contain randomly generated circuits with 4–128 qubits and 128–2048 gates.Gates are uniformly sampled from H, X, Y, Z, S, T, and CNOT.
- Compiler configurations: Compilation configurations vary solver settings, routing policy, calibration-data use, and other parameters.The study compares R-SMT⋆ with T-SMT⋆ for noise adaptation and T-SMT⋆ with T-SMT for calibration-derived gate-time and coherence-time effects.
- Experimental setup: Experiments run on an Intel Skylake processor with Python 3.5, gcc 5.4, and the Z3 SMT solver, using IBM Quantum Experience APIs for IBMQ16.Daily machine calibration data is obtained through the APIs.
- Metrics: Each benchmark is recompiled before execution using the latest calibration data and evaluated on IBMQ16 with 8192 trials per run.Success rate is the fraction of trials producing the correct answer.
7 Optimizing Execution Reliability
The experiments show that calibration-aware reliability optimization improves success rates, while carefully chosen objectives and heuristics can retain near-optimal execution time and improve compilation scalability.
- Baseline comparison: 2.9x geomean success-rate improvement over Qiskit, reaching up to 18x, is obtained by R-SMT⋆ in the real-system comparison.Qiskit uses lexicographic placement without considering CNOT and readout errors; for BV8, it adds 15 movement CNOTs, whereas R-SMT⋆ requires none.
- Movement and reliability: Up to 2.8x higher success likelihood occurs for applications with zero-qubit-movement mappings than for programs requiring even one movement operation.Extra CNOTs increase both error rate and execution duration.
- Optimization objective: Up to 9.2x success-rate improvement over T-SMT⋆ occurs for R-SMT⋆ when machine-state variability is high, even with equal movement counts.The comparison indicates that gate-error optimization remains important beyond minimizing qubit communication.
- Choice of optimization objective: R-SMT⋆ with ω = 0.5 achieves the highest success rate among the methods, with up to 9.25x gain over T-SMT⋆.This setting simultaneously optimizes CNOT gate error, readout error, and qubit movement; ω roughly near 0.5 is generally appropriate on IBMQ16.
- Gate durations: Up to 1.68x execution-time improvement results from considering real gate durations, while compilation time increases by up to 3x.Even with real durations, each benchmark requires only a few seconds of compilation.
- Coherence time: Each benchmark finishes in fewer than 150 timeslots, while the machine’s worst-qubit coherence time exceeds 300 timeslots.For these benchmarks, fine-grained coherence-time variation is therefore unnecessary.
- Execution duration: R-SMT⋆ achieves execution durations close to T-SMT⋆, and all three routing policies produce similar durations because the benchmarks are small with few parallel CNOTs.R-SMT⋆ remains reliability-oriented while staying close to the duration optimized by T-SMT⋆.
- Heuristic methods: GreedyE⋆ matches R-SMT⋆ success in all tested cases and outperforms the vertex-based GreedyV⋆ heuristic.The edge-based heuristic prioritizes reliability for the most frequent CNOTs.
8 Related Work
Related work includes quantum programming languages and frameworks, low-level hardware interfaces, and prior compilation and scheduling methods for different hardware technologies and circuit classes.
- Quantum programming systems: Quantum programming systems include Quipper, LIQUi|⟩, Scaffold, ProjectQ, and PyQuil, with earlier backends often targeting simulators or resource estimation.These systems extend classical languages or provide frameworks for describing and compiling quantum circuits.
- Hardware interfaces: OpenQASM and Quil provide low-level assembly interfaces to quantum hardware, and this compiler generates optimized OpenQASM code for IBM machines.The compiler can also be extended to other low-level interface languages.
- Compilation and scheduling: Prior compilation research addresses scheduling on linear topologies and uses AI planners for specific quantum-circuit classes.The cited work spans different hardware technologies and topologies.
9 Conclusions
The paper finds that calibration-aware compilation improves NISQ program reliability while revealing trade-offs between optimization quality and compile-time scalability. These results support noise-adaptive resource management for current and future quantum systems.
- SMT-based compilation is highly effective for current and near-term systems but may not scale to far-NISQ machines with 500 qubits or more.The paper therefore develops heuristic alternatives for larger systems.
- GreedyV⋆ and GreedyE⋆ offer nearly as good results as SMT approaches with much more tractable compile times.
- Calibration-aware compilation should prioritize CNOT and readout error rates, while coherence-time optimization is useful but less critical in this setting.Gate errors severely limit useful computation time, making CNOT and readout noise especially important.
- 2.9X average and up to 18X improvement in success rate were achieved over the current IBM Qiskit baseline.The best-performing approach also produced up to 6X and 2.7X average runtime improvement.
- Noise-adaptive compilation remains relevant to future error-correcting circuits because logical qubits will still be composed of many noisy physical qubits.
- Ultra-efficient use of available NISQ resources is identified as central for the next five years or more, with the tool targeting runtime usage and reliability.