Source-linked AI summary
A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
Siyuan Niu, Adrien Suau, Gabriel Staffelbach, Aida Todri-Sanial
TL;DR
NISQ circuits must be adapted to hardware connectivity constraints, including restrictions on which neighboring qubits can perform two-qubit gates. HA uses calibration data to choose mapping-transition gates and can select either a SWAP or Bridge for qubit movement. On IBM devices, HA outperforms state-of-the-art algorithms in additional gates, fidelity, and execution time; on ibmq_valencia, execution time falls by 19% on average, fidelity improves by 8%, and additional gates fall by 38%.
Problem
NISQ circuits must be adapted to hardware connectivity constraints, including restrictions on which neighboring qubits can perform two-qubit gates.
Source: §1 · p. 1Method
HA uses calibration data to choose mapping-transition gates and can select either a SWAP or Bridge for qubit movement.
Source: §1 · p. 2, §3.1.2 · p. 5Results
On IBM devices, HA outperforms state-of-the-art algorithms in additional gates, fidelity, and execution time; on ibmq_valencia, execution time falls by 19% on average, fidelity improves by 8%, and additional gates fall by 38%.
Source: §6 · p. 11, §4.2 · p. 11Takeaways & Limitations
The design guidance is to inspect device topology and calibration data and map the most-used qubit to the physical qubit with the strongest coupling.
Source: §5.1 · p. 11For qft_10, output fidelity is less than 0.01 for all methods tested, making meaningful comparison impossible because base fidelity is too low.
Source: §4.2 · p. 10
Abstract
from arXiv · showhide
Due to several physical limitations in the realisation of quantum hardware, today's quantum computers are qualified as Noisy Intermediate-Scale Quantum (NISQ) hardware. NISQ hardware is characterized by a small number of qubits (50 to a few hundred) and noisy operations. Moreover, current realisations of superconducting quantum chips do not have the ideal all-to-all connectivity between qubits but rather at most a nearest-neighbour connectivity. All these hardware restrictions add supplementary low-level requirements. They need to be addressed before submitting the quantum circuit to an actual chip. Satisfying these requirements is a tedious task for the programmer. Instead, the task of adapting the quantum circuit to a given hardware is left to the compiler. In this paper, we propose a Hardware-Aware mapping transition algorithm (HA) that takes the calibration data into account with the aim to improve the overall fidelity of the circuit. Evaluation results on IBM quantum hardware show that our HA approach can outperform the state of the art both in terms of the number of additional gates and circuit fidelity.
1 INTRODUCTION
NISQ quantum programs must be adapted to hardware connectivity constraints before execution, making qubit mapping a compiler task. The paper proposes a calibration-aware mapping heuristic and evaluates it on real quantum hardware.
1 INTRODUCTION
- The qubit mapping problem adapts quantum programs to device connectivity because current superconducting chips restrict two-qubit gates to neighboring qubits.Programs are written as if they ran on ideal hardware without noise or physical constraints.Source: §1 · p. 1
- Mapping comprises an initial assignment of logical to physical qubits and a transition algorithm that inserts gates to satisfy hardware topology.Finding an optimal solution is likely NP-complete.Source: §1 · p. 1
- ILP, SMT, and CP formulations can have long runtimes and scale poorly, while heuristic methods transform circuits sequentially to satisfy hardware constraints.The formal approaches are described as mathematically equivalent formulations of the mapping problem.Source: §1 · p. 1
- Prior calibration-aware methods use strongly linked qubits but may omit holistic initial mapping or efficient candidate selection; many mapping methods minimize gates without considering noise.Most previous approaches use SWAPs for qubit movement, with a cited exception that also considers Bridge gates [23].Source: §1 · p. 2
- HA selects mapping-transition SWAPs using calibration data, can choose a SWAP or Bridge, and targets improved fidelity and execution time with fewer added gates.The authors compare the algorithm with mapping methods from the literature on real quantum hardware.Source: §1 · p. 2
2 STATE OF THE ART
The section surveys quantum hardware constraints, explains the compilation and mapping problem, and illustrates why calibration data can guide qubit movement.
2.1 Current state-of-the-art on quantum hardware
- NISQ devices have 50 to a few hundred noisy qubits; although IBM architectures are the focus, the authors describe the method as applicable to gate-model chips generally.The section introduces the ibmq_almaden topology and its calibration characteristics.Source: §2.1 · p. 2, Figure 1 · p. 2, Table 2 · p. 3
- Two-qubit gates are roughly an order of magnitude slower and more error-prone than one-qubit gates; CNOT links vary substantially, and hardware characteristics change at recalibration.For ibmq_almaden, the best CNOT error rate is 4.18 times lower than the worst, while the maximum execution time is 3.46 times the minimum.Source: §2.1 · p. 3
2.2 Qubit mapping problem
- Compilation decomposes abstract gates into device gates, then mapping inserts topology-compliant operations for restricted two-qubit interactions, often also optimizing a chosen circuit metric.The mapping problem is defined as the second compilation step, though mapping algorithms often also target optimization goals from the third step.Source: §2.2 · p. 3
2.3 Motivational example
- When a CNOT targets non-connected qubits, multiple SWAPs may enable it; the example chooses the less noisy option, between physical qubits Q1 and Q2.That choice updates the logical-to-physical mapping before the CNOT can be executed.Source: §2.3 · p. 3
3 PROPOSED SOLUTION
The proposed HA approach combines calibration-aware mapping transition with hardware-aware initial mapping, using SWAP and Bridge choices to improve fidelity and reduce added gates. Its heuristic evaluates candidate mappings using hardware distances, while HSA searches for an initial mapping and the evaluation metrics capture fidelity, added CNOTs, and execution time.
3 PROPOSED SOLUTION
- HA combines a calibration-aware distance matrix, SWAP-versus-Bridge selection, and hardware-aware initial mapping to improve fidelity and reduce additional gates relative to SABRE.The method also aims to reduce execution time.Source: §3 · p. 4
3.1 Hardware-aware SWAP and Bridge based heuristic search
- A dependency DAG organizes gates into executable first-layer gates F and future extended-layer gates E for look-ahead mapping.The DAG's edges represent gate dependencies; a gate is executable when its dependencies have been executed.Source: §3.1 · p. 4
3.1.1 Heuristic cost function.
- The cost function ranks candidate SWAPs using a distance matrix that combines swap distance, error rate, and execution time, with the first layer prioritized over the extended layer.The extended-layer contribution is scaled by W, and both layer costs are normalized by their gate counts.Source: §3.1.1 · pp. 4–5
3.1.2 SWAP gate and Bridge gate.
- A Bridge can replace a SWAP when a negative extended-layer effect makes preserving the current mapping preferable, but only for a CNOT whose qubits are two links apart.Both Bridge and SWAP add three supplementary CNOTs; the example maps the circuit with three additional CNOTs using a Bridge instead of six using two SWAPs.Source: §3.1.2 · p. 5
3.1.3 HA Algorithm.
- HA marks executable gates as mapped, then selects a minimum-cost candidate SWAP and chooses Bridge instead when the SWAP harms the extended layer and topology permits.When no first-layer gate is executable, the algorithm iterates by inserting a SWAP or Bridge until the circuit is fully mapped.Source: §3.1.3 · p. 6
3.1.4 Runtime analysis.
- Initialization takes O(n^3) time for three Floyd–Warshall calls; mapping takes O(g^2dn^2) in the worst case, improving to O(gn^2.5) under stated nearest-neighbor and layer-size assumptions.Calibration retrieval is theoretically O(n^2), but current chips' O(n) links make this step O(n); initialization must be repeated when calibration data change, and internet retrieval may take several seconds.Source: §3.1.4 · pp. 6–7
3.2 Initial mapping
- HSA uses hardware-aware simulated annealing with randomly selected neighborhood moves to search for an initial mapping.Its moves include shuffling assignments among the mapped physical qubits, expanding to another physical qubit, and resetting to seek a new mapping.Source: §3.2 · pp. 7–8
3.3 Metrics
- The evaluation measures success rate as estimated output-state fidelity, additional CNOT count, and circuit execution time.Success rate is estimated over 8192 executions against the expected answer from a simulator; execution time is represented by the longest qubit execution time.Source: §3.3 · p. 8
4 EVALUATION AND COMPARISON OF THE PROPOSED HA ALGORITHM
The evaluation compares HA with existing mapping algorithms on IBM devices, measuring additional gates, fidelity, and execution time. HA+SABRE achieves the best average output-state fidelity and fewest additional gates among the tested combinations, while HA’s gate-count advantage varies by circuit size and chip.
4.1 Methodology
- The real-hardware comparison includes HA with SABRE or HSA initialization, SABRE, N-A Compiler, and Qiskit; comparisons use the same calibration data and disable optimization.For additional-gate comparisons without real hardware, the algorithms are SABRE, DL, and HA.Source: §4.1 · p. 10
- The evaluation uses small benchmarks on real hardware; larger benchmarks are excluded because their gate operations introduce too much noise for meaningful results.Initial-mapping generation is applied to small and medium benchmarks, while large benchmarks use ten random initial mappings because of long runtime.Source: §4.1 · p. 10
4.2 Experimental results
- The Qiskit default mapping is nearly always worst for additional gates and, in most cases, for output-state fidelity.The evaluation compares average additional gates and output-state fidelity over ten initial mappings.Source: §4.2 · p. 10
- HA+SABRE achieves the best average output-state fidelity and minimum additional-gate count; HA+HSA is less consistent but often outperforms SABRE.The paper attributes HA+HSA’s less consistent results to its random nature.Source: §4.2 · p. 10
- For qft_10, every tested method has output fidelity below 0.01, so the paper compares additional gates rather than fidelity.The low base fidelity is given as the reason a fidelity comparison would not be meaningful.Source: §4.2 · pp. 10–11
- On ibmq_valencia, HA reduces execution time by 19% on average, improves fidelity by 8%, and reduces additional gates by 38% versus SABRE.The CNOT-error weight α2 is set to 0 in this comparison.Source: §4.2 · p. 11
- On ibmq_almaden, HA gives similar results to SABRE on medium circuits, improving on only one of eight, but reduces additional gates by 28% on average for large circuits.On ibmq_tokyo, HA reduces additional gates by 14% on average versus DL, which outperforms SABRE.Source: §4.2 · p. 11
5 DISCUSSION
The discussion advises mapping circuits with device topology and calibration in mind, and identifies constraints the current HA algorithm does not address. It also proposes adapting mapping to multiprogramming and specific quantum-application use cases.
5.1 Design guideline
- Check device topology and calibration, and map the circuit’s most-used qubit to the physical qubit with the strongest coupling.Source: §5.1 · p. 11
- Use directly connected qubits with reliable, low-error interconnects for CNOT gates to avoid additional gates and improve overall circuit fidelity.Source: §5.1 · p. 11
- When adjacent qubits are unavailable, consider a SWAP or Bridge gate for a CNOT between qubits at distance two on the coupling graph to reduce additional gates.Source: §5.1 · p. 11
5.2 Future work
- HA currently uses gate-error and execution-time calibration data, while crosstalk error is identified as another physical constraint for future study.The paper also proposes investigating multiprogramming and mapping for VQE quantum-chemistry circuits or VQLS linear-system circuits.Source: §5.2 · p. 11
6 CONCLUSION
The conclusion presents HA as a hardware-aware heuristic for adapting circuits to quantum hardware. Its mapping transition uses calibration data and chooses between SWAP and Bridge gates; IBM-device experiments report improvements over state-of-the-art algorithms in additional gates, fidelity, and execution time.
6 CONCLUSION
- HA uses calibration data and selects either a SWAP or Bridge gate for qubit movement, with IBM-device experiments reporting improvements in additional gates, fidelity, and execution time over state-of-the-art algorithms.The authors state that the algorithm should be general enough for quantum devices from other vendors.Source: §6 · p. 11