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.

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.Source: §I · p. 1
  • Two-qubit gates require logical-to-physical mappings and intermediate transitions that place interacting qubits on coupled hardware qubits.Source: §I · p. 1
  • Previous solver-based methods have very long runtimes, while many heuristic methods target regular lattices rather than irregular NISQ couplings.Source: §I · p. 1
  • SABRE reduces search complexity through an optimized SWAP-based heuristic scheme focused on qubits involved in executable two-qubit gates.Source: §I · pp. 1–2
  • 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.Source: §I · p. 2
  • Reverse traversal improves the initial mapping, while decay-aware costs trade circuit depth against gate count for different optimization objectives.Source: §I · p. 2

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.Source: A. QC Software Basics · p. 2
  • Quantum gates are unitary operations that modify qubit states; CNOT is a two-qubit operation controlled by one qubit and targeting another.Source: A. QC Software Basics · p. 2
  • Quantum circuits represent quantum programs with lines for qubits and blocks for operations, including decompositions into single- and two-qubit gates.Source: A. QC Software Basics · p. 2
  • NISQ computers are expected to contain dozens to hundreds of qubits, without quantum error correction mapping logical qubits directly onto physical qubits.Source: B. QC Hardware in the NISQ Era · p. 3
  • Short coherence times limit sequential computation, imperfect operations accumulate errors, and physical coupling restricts two-qubit gates to nearby qubits.Source: B. QC Hardware in the NISQ Era · p. 3

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.Source: A. Problem in Qubit Mapping · p. 3
  • SWAP operations exchange qubit states through three CNOT gates, allowing separated logical qubits to become adjacent for later two-qubit gates.Source: A. Problem in Qubit Mapping · p. 3
  • The paper focuses on symmetric coupling, where connected physical qubit pairs support CNOT gates in either direction, and therefore considers SWAP-based mapping changes.Source: A. Problem in Qubit Mapping · p. 4
  • The updated circuit becomes executable after inserting one SWAP, but its gate count rises from 6 to 9 and depth from 5 to 8.Source: A. Problem in Qubit Mapping · p. 4
  • Qubit mapping seeks an initial mapping and SWAP-based intermediate transitions that satisfy coupling constraints while minimizing added gates and circuit depth.Source: A. Problem in Qubit Mapping · p. 4

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

Preprocessing

  • SABRE preprocesses the device coupling graph and circuit DAG, initializes a front layer, and starts search from a temporary random mapping.Source: A. Preprocessing · pp. 4–5

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.Source: B. SWAP-Based Heuristic Search · p. 5
  • 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.Source: B. SWAP-Based Heuristic Search · pp. 5–6
  • 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.Source: B. SWAP-Based Heuristic Search · p. 5
  • 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.Source: B. SWAP-Based Heuristic Search · p. 5
  • 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.Source: B. SWAP-Based Heuristic Search · p. 6
  • 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.Source: B. SWAP-Based Heuristic Search · p. 6

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.Source: C. Key Design Decisions · p. 6

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.Source: 1) SWAP-Based Search Scheme · p. 6
  • SABRE reduces the search space by considering SWAPs associated with qubits in the current front layer.The approach avoids enumerating all possible mappings.Source: 1) SWAP-Based Search Scheme · p. 6, Figure 5 · p. 7
  • 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.Source: 1) SWAP-Based Search Scheme · p. 6
  • 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.Source: 1) SWAP-Based Search Scheme · pp. 6–7

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

Trade-off between the Circuit Depth and the Number of Gates

Key Design Decisions

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.Source: 1) Nearest Neighbor Cost Function · p. 8

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.Source: 2) Look-Ahead Ability and Parallelism · p. 8

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.Source: 2) Look-Ahead Ability and Parallelism · p. 8, §V · p. 9

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.Source: §V · pp. 8–9

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.Source: §V · p. 9

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.Source: §V · p. 9

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

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.Source: 1) Small Size Cases and Ising Model · p. 9

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.Source: 2) Large Size Cases · p. 9
  • 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.Source: 2) Large Size Cases · pp. 9–10

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.Source: B. Runtime Speedup and Scalability · p. 10
  • For qft 16, BKA required over 40GB and 474.81 seconds, while SABRE used about 200MB and 0.08 seconds.Source: 2) Limit of BKA and Scalability · p. 10

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.Source: C. Trade-off between Number of Gates… · p. 10
  • Increasing δ too far may increase both circuit depth and gate count because the search considers unmoved qubits and introduces redundant SWAPs.Source: C. Trade-off between Number of Gates… · p. 10

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.Source: §VI · p. 10

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.Source: §VII · p. 11
  • Dynamic programming can find optimal mappings but requires exponential time and space and supports circuits with eight or fewer qubits.Source: §VII · p. 11
  • BKA searches all combinations of concurrent SWAPs, retaining exponential runtime, and its initial mapping considers only gates at the circuit beginning.Source: §VII · p. 11

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.Source: §VIII · p. 11

Related papers

Loading 1809.02573v2…