PaperlayerView exact revision on arXiv

Source-linked AI summary

Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

Gushu Li, Yufei Ding, Yuan Xie

arXiv:1809.02573v2cs.ETquant-ph

TL;DR

Limited NISQ coupling prevents many quantum circuits from executing directly and makes mapping overhead important. SABRE uses SWAP-based bidirectional heuristic search with improved initialization and decay-aware control, outperforming prior methods on benchmark scalability and added-gate metrics while remaining subject to hardware-model limitations.

  • Problem

    Limited physical coupling prevents arbitrary logical two-qubit gates from executing directly, so compilation must find mappings and transitions that satisfy hardware constraints.

  • Method

    SABRE combines optimized SWAP-based heuristic search, reverse traversal for initial mapping, and decay-aware costs for gate-count/depth trade-offs.

  • Results

    Across benchmarks, SABRE achieved exponential speedup, reduced additional gates by 91% or more for small cases and about 10% on average for larger cases, and remained more scalable than BKA.

  • Takeaways & Limitations

    SABRE provides a flexible and scalable mapping solution for NISQ devices with arbitrary connections and controllable circuit-depth versus gate-count outcomes.

  • Takeaways & Limitations

    The model omits gate-specific and qubit-pair-specific error variation and imperfections such as crosstalk.

Abstract

from arXiv · show

Due to little consideration in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in the compiler is needed to enable the two-qubit gates in the algorithm, which introduces additional operations and inevitably reduces the fidelity of the algorithm. Previous solutions in finding such remapping suffer from high complexity, poor initial mapping quality, and limited flexibility and controllability. To address these drawbacks mentioned above, this paper proposes a SWAP-based BidiREctional heuristic search algorithm SABRE, which is applicable to NISQ devices with arbitrary connections between qubits. By optimizing every search attempt,globally optimizing the initial mapping using a novel reverse traversal technique, introducing the decay effect to enable the trade-off between the depth and the number of gates of the entire algorithm, SABRE outperforms the best known algorithm with exponential speedup and comparable or better results on various benchmarks.

I. INTRODUCTION

NISQ hardware restricts which two-qubit gates can execute directly, making qubit mapping necessary and costly. SABRE addresses prior complexity, initialization, flexibility, and controllability limitations with optimized SWAP search, reverse traversal, and decay-aware heuristics.

  • NISQ devices permit only a subset of theoretically possible operations, creating a software–hardware gap.
  • Two-qubit gates require logical-to-physical mappings and intermediate transitions that place interacting qubits on coupled hardware qubits.
  • Previous solver-based methods have very long runtimes, while many heuristic methods target regular lattices rather than irregular NISQ couplings.
  • SABRE reduces search complexity through an optimized SWAP-based heuristic scheme focused on qubits involved in executable two-qubit gates.
  • 91% fewer additional gates were achieved for small benchmarks, while larger benchmarks showed exponential speedup and about 10% average gate reduction versus the prior solution.
  • Reverse traversal improves the initial mapping, while decay-aware costs trade circuit depth against gate count for different optimization objectives.

II. BACKGROUND

Quantum circuits represent programs as qubits and quantum operations, but NISQ devices impose short coherence, imperfect operations, and restricted physical coupling. These constraints motivate hardware-aware circuit execution.

  • A qubit can occupy a linear combination of basis states and can participate in entangled multi-qubit states.
  • Quantum gates are unitary operations that modify qubit states; CNOT is a two-qubit operation controlled by one qubit and targeting another.
  • Quantum circuits represent quantum programs with lines for qubits and blocks for operations, including decompositions into single- and two-qubit gates.
  • NISQ computers are expected to contain dozens to hundreds of qubits, without quantum error correction mapping logical qubits directly onto physical qubits.
  • Short coherence times limit sequential computation, imperfect operations accumulate errors, and physical coupling restricts two-qubit gates to nearby qubits.

III. PROBLEM ANALYSIS

Qubit mapping transforms a circuit so every two-qubit gate respects the device coupling graph. SWAP insertion makes execution possible but increases gate count and depth, creating the optimization problem.

  • In the four-qubit example, four of six CNOT gates execute directly, while two fail under the assumed initial mapping because their physical pairs are uncoupled.
  • SWAP operations exchange qubit states through three CNOT gates, allowing separated logical qubits to become adjacent for later two-qubit gates.
  • The paper focuses on symmetric coupling, where connected physical qubit pairs support CNOT gates in either direction, and therefore considers SWAP-based mapping changes.
  • The updated circuit becomes executable after inserting one SWAP, but its gate count rises from 6 to 9 and depth from 5 to 8.
  • Qubit mapping seeks an initial mapping and SWAP-based intermediate transitions that satisfy coupling constraints while minimizing added gates and circuit depth.

B. Objectives and Metrics

The mapping heuristic is evaluated against flexibility, fidelity, and parallelism objectives. SABRE prepares coupling and circuit representations, then searches mappings using distance-based and dependency-aware information.

  • Objectives and Metrics: Because qubit mapping is NP-Complete, the paper designs a heuristic rather than directly seeking an optimal solution.
  • Objectives and Metrics: Flexibility requires support for arbitrary symmetric coupling graphs, including irregular designs that may evolve over time.
  • Objectives and Metrics: Fidelity favors fewer gates, especially two-qubit gates, while parallelism favors SWAPs that reduce added circuit depth.
  • Preprocessing: SABRE preprocesses the device coupling graph and circuit DAG, initializes a front layer, and starts search from a temporary random mapping.

B. SWAP-Based Heuristic Search

SABRE repeatedly executes hardware-compatible front-layer gates and inserts heuristic-selected SWAPs when gates are not directly executable. Its search traverses the circuit DAG until all two-qubit gates are executed.

  • SABRE represents two-qubit-gate dependencies with a circuit DAG and initializes the front layer with gates having no unexecuted predecessors.The preprocessing stage produces the circuit DAG and initial front layer before SWAP-based search begins.
  • The procedure repeats while the front layer is nonempty, terminating after all circuit gates have been executed and the final mapping is produced.Algorithm 1 outputs inserted SWAPs and the final mapping π_f.
  • At each iteration, SABRE executes front-layer gates whose mapped physical qubits are adjacent in the chip coupling graph.Executed gates are removed from the front layer, and dependency-resolved successors are added.
  • When no front-layer gate is hardware-executable, SABRE inserts SWAPs to bring the involved logical qubits closer together.This condition triggers mapping transitions rather than direct gate execution.
  • SABRE restricts candidate SWAPs to swaps associated with logical qubits involved in the front layer, rather than searching all mappings.Candidate swaps are generated from neighboring physical qubits and reverse-mapped to logical-qubit pairs.
  • A heuristic cost function scores candidate SWAPs, and SABRE selects the SWAP with the minimal score to update the mapping.The updated mapping is then used in subsequent executable-gate checks.

C. Key Design Decisions

SABRE combines three design decisions aimed at scalability, initial-mapping quality, and controllable circuit optimization objectives.

  • SABRE’s three design decisions target exponential speedup, a high-quality initial mapping, and controllability across optimization objectives.

1) SWAP-Based Search Scheme:

SABRE replaces mapping-based exhaustive search with a restricted SWAP search guided by heuristic costs. This reduces worst-case complexity while preserving look-ahead information for selecting useful swaps.

  • Mapping-based exhaustive search can require O(exp(N)) time and space, limiting prior algorithms on larger NISQ devices.
  • SABRE reduces the search space by considering SWAPs associated with qubits in the current front layer.The approach avoids enumerating all possible mappings.
  • The heuristic cost function evaluates candidate SWAPs using front-layer qubit distances and gates immediately after the front layer.This look-ahead helps select a SWAP that both enables current gates and improves later dependencies.
  • SABRE reduces the search space from O(exp(N)) to O(N), while the overall search requires at most O(N^2.5) work per two-qubit gate.The bound combines linear candidate evaluation with the maximum number of SWAP steps needed on the coupling graph.

2) Reverse Traversal for Initial Mapping:

SABRE uses reverse traversal to improve the initial logical-to-physical mapping by incorporating information from the full reversible circuit. A decay effect then controls the trade-off between added gates and circuit depth.

  • Reverse Traversal for Initial Mapping: Earlier initial-mapping methods lacked global consideration of circuit information and temporal behavior.
  • Reverse Traversal for Initial Mapping: Because quantum circuits are reversible, SABRE traverses a reversed circuit whose two-qubit gates preserve the original gates in reverse order.
  • Reverse Traversal for Initial Mapping: The updated mapping considers all gates, weighting gates nearer the circuit beginning more strongly while retaining information from later gates.
  • Reverse Traversal for Initial Mapping: SABRE first traverses the original circuit, then uses its final mapping as the starting mapping for a reverse traversal that updates the original initial mapping.
  • Trade-off between the Circuit Depth and the Number of Gates: The paper illustrates a depth-versus-gate-count trade-off: four additional SWAPs can increase depth by 1, whereas three additional SWAPs increase depth by 2.
  • Trade-off between the Circuit Depth and the Number of Gates: SABRE introduces decay into its heuristic cost so overlapping SWAPs become less attractive, enabling control over circuit depth and gate count.
  • Key Design Decisions: Together, the design decisions provide exponential speedup, a high-quality initial mapping, and controllability across optimization objectives.

D. Design the Heuristic Cost Function

SABRE’s heuristic cost function combines nearest-neighbor movement, look-ahead over successor gates, and decay-based control of parallel SWAPs. The evaluation uses diverse benchmarks on IBM’s 20-qubit coupling model with fixed algorithmic settings.

  • Heuristic Cost Function: Nearest Neighbor Cost estimates the minimal SWAPs needed to make two physical qubits adjacent on an irregular coupling graph.For NISQ devices, this is computed as the shortest path length between physical qubits in the coupling graph.
  • Look-Ahead Ability: The Extended Set adds successor gates beyond the front layer, enabling look-ahead while keeping its size flexible to limit inaccurate estimation and computation.The updated function combines normalized contributions from the front layer and Extended Set, with front-layer gates receiving priority through weight W.
  • Parallelism: Decay penalizes recently reused qubits, encouraging non-overlapping SWAPs and allowing δ to control the trade-off between circuit parallelism and other circuit objectives.The decay function is reset every five search steps or after a CNOT gate in the reported configuration.
  • Evaluation Setup: SABRE is evaluated on benchmarks from QISKit, RevLib, Quipper, and ScaffCC using IBM’s Q 20 Tokyo coupling graph.The hardware model uses symmetric couplings with bidirectional CNOT gates, and experiments run on a server with 48 logical cores and 378GB memory.
  • Algorithm Configuration: Each benchmark uses five initial mappings, three forward-backward-forward traversals per attempt, and reports the best result across attempts.The evaluation fixes |E| = 20, W = 0.5, and begins δ at 0.001.
  • Comparison: SABRE is compared with Zulehner et al.’s algorithm, selected as the Best Known Algorithm on the same IBM 20-qubit hardware model.The comparison uses the existing source code with its embedded hardware model modified to match the evaluation device.

A. Number of Gates Reduction

SABRE reduces additional gates across benchmark sizes, with especially strong gains on small circuits and an average 10% reduction for larger circuits through reverse-traversal initial mapping.

  • Number of Gates Reduction: SABRE outperforms BKA across benchmarks of different sizes.The reported comparison concerns additional-gate counts in Table II.
  • Small Size Cases and Ising Model: 91% or more of additional gates are reduced on small benchmarks, with some cases fully eliminating them.SABRE can find high-quality initial mappings requiring few or no additional SWAPs, including optimal solutions for the evaluated Ising benchmarks.
  • Large Size Cases: 10% average reduction in additional gates is achieved for larger ‘large’ and ‘qft’ circuits after reverse traversal updates the initial mapping.The first traversal can be worse than BKA because BKA searches a larger space, but SABRE’s reverse traversal improves the subsequent result.
  • Large Size Cases: Large benchmarks show smaller gate-count reductions because a physical coupling subgraph matching the logical-qubit couplings usually does not exist.Small benchmarks often admit a perfect or near-perfect matching, whereas larger circuits generally require additional SWAPs.

B. Runtime Speedup and Scalability

SABRE scales beyond BKA's exponential search by using a linear-size search space, while its decay effect provides controllable circuit-depth variation. Its evaluation also identifies benchmark, architecture, and hardware-model boundaries.

  • Runtime Speedup and Scalability: O(N) search space in SABRE contrasts with BKA's O(exp(N)) space, giving SABRE better scalability despite a worst-case complexity of O(N^2.5g).BKA's exponential search space limits larger cases, whereas SABRE selects one SWAP per step.
  • Runtime Speedup and Scalability: For qft 16, BKA required over 40GB and 474.81 seconds, while SABRE used about 200MB and 0.08 seconds.
  • Trade-off between Number of Gates and Depth: SABRE provides about 8% variation in generated circuit depth by varying the number of gates through the decay parameter δ.The x-axis normalizes gate count to g_ori, and the y-axis normalizes depth to the original circuit depth.
  • Trade-off between Number of Gates and Depth: Increasing δ too far may increase both circuit depth and gate count because the search considers unmoved qubits and introduces redundant SWAPs.
  • Limitations: The evaluation is bounded by benchmark representativeness, vendor-specific chip architectures, and simplified hardware modeling that omits effects such as crosstalk.The benchmarks may not capture emerging practical NISQ applications, and the study targets IBM-style symmetric CNOT coupling.

VII. RELATED WORK

Earlier qubit-mapping approaches used mathematical solvers or heuristic search, but faced runtime, scalability, or hardware-model limitations. SABRE addresses these issues with optimized bidirectional SWAP search and reverse-traversal initial mapping for realistic NISQ coupling.

  • Prior Approaches: Mathematical-solver approaches have long runtimes and are generally limited to small cases, while heuristic methods often target ideal 1D/2D lattices.
  • Prior Approaches: Dynamic programming can find optimal mappings but requires exponential time and space and supports circuits with eight or fewer qubits.
  • Prior Approaches: BKA searches all combinations of concurrent SWAPs, retaining exponential runtime, and its initial mapping considers only gates at the circuit beginning.
  • Scope: SABRE targets arbitrary symmetric CNOT coupling on IBM chips, while more general vendor-specific transformations and single-qubit-gate considerations remain outside the paper's scope.
Loading 1809.02573v2…