PaperlayerView exact revision on arXiv

Source-linked AI summary

An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures

Alwin Zulehner, Alexandru Paler, Robert Wille

arXiv:1712.04722v3quant-ph

TL;DR

Mapping quantum circuits onto IBM QX hardware requires decomposition and logical-to-physical qubit assignment under restrictive CNOT constraints while limiting added gates. The paper proposes an integrated, generic methodology using partitioning, A∗ search, look-ahead, and adaptive initialization. It maps every circuit within the one-hour limit in the reported evaluation and produces lower-cost circuits than IBM’s solution.

  • Problem

    IBM QX mapping must satisfy hardware-specific CNOT constraints while minimizing the additional gates required for executable circuits.

  • Method

    The methodology decomposes functionality into elementary gates, partitions circuits by depth, and uses A∗ search, look-ahead, and evolving initial mappings before integration into QISKit.

  • Results

    IBM’s solution timed out in 10 of 60 cases, while the proposed algorithm mapped every circuit within the time limit and produced 24.0% fewer gates and 18.3% less depth than IBM’s minimum observed results.

  • Takeaways & Limitations

    The generic integrated methodology efficiently maps circuits to IBM QX architectures and yields smaller circuits with fewer gates and reduced depth.

Abstract

from arXiv · show

In the past years, quantum computers more and more have evolved from an academic idea to an upcoming reality. IBM's project IBM Q can be seen as evidence of this progress. Launched in March 2017 with the goal to provide access to quantum computers for a broad audience, this allowed users to conduct quantum experiments on a 5-qubit and, since June 2017, also on a 16-qubit quantum computer (called IBM QX2 and IBM QX3, respectively). Revised versions of these 5-qubit and 16-qubit quantum computers (named IBM QX4 and IBM QX5, respectively) are available since September 2017. In order to use these, the desired quantum functionality (e.g. provided in terms of a quantum circuit) has to be properly mapped so that the underlying physical constraints are satisfied - a complex task. This demands solutions to automatically and efficiently conduct this mapping process. In this paper, we propose a methodology which addresses this problem, i.e. maps the given quantum functionality to a realization which satisfies all constraints given by the architecture and, at the same time, keeps the overhead in terms of additionally required quantum gates minimal. The proposed methodology is generic, can easily be configured for similar future architectures, and is fully integrated into IBM's SDK. Experimental evaluations show that the proposed approach clearly outperforms IBM's own mapping solution. In fact, for many quantum circuits, the proposed approach determines a mapping to the IBM architecture within minutes, while IBM's solution suffers from long runtimes and runs into a timeout of 1 hour in several cases. As an additional benefit, the proposed approach yields mapped circuits with smaller costs (i.e. fewer additional gates are required). All implementations of the proposed methodology is publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping.

I. INTRODUCTION

Quantum computing has moved toward practical cloud-accessible hardware, but executing circuits on IBM QX devices requires complex constraint-aware mapping. The proposed generic methodology addresses this mapping problem efficiently and outperforms IBM’s solution in runtime and circuit cost.

  • Mapping quantum functionality requires decomposition into supported operations and assignment of logical qubits to physical qubits under architecture constraints.
  • The methodology combines depth-based partitioning, A∗ search, look-ahead, and evolving initial mappings, and is generic across current and similar future architectures.
  • The approach is integrated into IBM’s QISKit SDK, including IBM’s post-mapping optimizations in performance evaluation.
  • The proposed method maps many circuits within minutes, whereas IBM’s solution often runs for long periods or reaches a 1-hour timeout, while producing fewer additional gates.

A. Quantum Circuits

Quantum circuits manipulate qubits with single- and multi-qubit gates, commonly represented through circuit diagrams. IBM QX hardware supports parameterized single-qubit U gates and CNOTs, but imposes strict decomposition and connectivity constraints.

  • Quantum circuits operate on qubits that can represent superpositions of basis states, supporting quantum algorithms with potential speedups over classical algorithms.
  • Quantum gates manipulate one or multiple qubits, and multi-qubit gates distinguish control and target qubits.
  • Circuit diagrams represent qubits as horizontal lines passed through gates, with gate placement defining the circuit’s operation sequence.
  • IBM QX architectures support U(θ, φ, λ) and CNOT operations, with U parameters realizing gates such as H and T.
  • Non-elementary operations must be decomposed into U and CNOT gates, while CNOTs are restricted to dedicated qubit pairs and directions.

III. MAPPING OF QUANTUM CIRCUITS TO THE IBM QX ARCHITECTURES

Mapping circuits to IBM QX architectures involves decomposing operations into hardware-supported gates and assigning logical qubits to physical qubits that satisfy CNOT constraints. The paper treats decomposition as established work and focuses on efficient constraint satisfaction.

  • A circuit must be decomposed into elementary CNOT and parameterized U gates supported by the IBM QX hardware.
  • Each logical qubit is assigned to a physical qubit so that all architecture-specific CNOT constraints are satisfied.
  • OpenQASM supports complex gates defined through elementary CNOT and U operations, provided their decompositions are supplied by the circuit designer.
  • Synthesis and decomposition methods can generate realizations for libraries such as Clifford+T or NCV when functionality is not specified in OpenQASM.
  • A SWAP is decomposed into three CNOTs, with Hadamard gates implemented as U(π/2, 0, π) when reversing an otherwise invalid CNOT direction.
  • The paper identifies satisfying the architecture’s additional CNOT constraints as the less-developed problem compared with elementary-gate decomposition.

B. Satisfying CNOT-constraints

IBM QX mapping must limit the extra gates and depth introduced to satisfy directional and connectivity constraints. The paper illustrates how alternative mappings can substantially reduce circuit cost compared with straightforward insertion or IBM’s search-based solution.

  • IBM QX mappings may require direction changes and inserted Hadamard gates when logical CNOTs do not match permitted physical directions.
  • Additional gates increase operation count and can reduce reliability, while circuit depth relates to execution time; therefore, mappings should use as few SWAPs as possible.
  • 51 elementary operations and depth 36 were reduced to 23 operations and depth 10 through an alternative mapping.
  • Prior nearest-neighbor methods target simpler one- or two-dimensional architectures where adjacent-qubit interactions are sufficient, unlike IBM QX constraints.
  • IBM’s SDK uses heuristic random search for mappings, but the method is reported as inefficient for many circuits and sometimes cannot determine a result.
  • The mapping problem centers on efficiently assigning logical to physical qubits while satisfying all CNOT constraints.

IV. EFFICIENTLY SATISFYING CNOT-CONSTRAINTS

The paper presents an efficient method for satisfying IBM QX CNOT constraints after circuit decomposition, while minimizing added elementary gates. Its multi-step methodology uses depth-based partitioning, A∗ search, look-ahead, and dynamic initial mappings.

  • The proposed method maps decomposed quantum circuits to IBM QX architectures while targeting minimal additional elementary gates.
  • The approach partitions circuits into layers and determines compliant mappings for each layer before applying further cost-reduction optimizations.

A. Partitioning the Circuit Into Layers

The circuit is partitioned into layers of concurrently executable gates, and permutation layers are inserted between them to maintain CNOT compliance as mappings change.

  • Gates acting on distinct qubit sets are combined into layers because they can be applied concurrently.
  • The example partitions the circuit into three layers: l0 = {g0, g1}, l1 = {g2, g3}, and l2 = {g4}.
  • Permutation layers πi use SWAP operations to transform the mapping from layer li−1 into the compliant mapping required for layer li.

B. Determining Compliant Mappings for the Layers

For each circuit layer, the method uses A∗ search to find a minimum-cost compliant mapping, guided by an admissible heuristic based on CNOT distances and SWAP costs.

  • A mapping assigns each logical qubit to a physical qubit, and the search starts from an initial mapping that satisfies the preceding layer’s CNOT constraints.
  • A∗ search addresses the exponential worst-case mapping space by expanding state nodes toward a minimum-cost goal mapping.
  • The search evaluates nodes using current cost plus heuristic cost, selecting the lowest-cost leaf for expansion.
  • Concurrent SWAP gates are considered to minimize circuit depth when solutions require the same number of additional operations.
  • Each CNOT’s cost is based on the shortest coupling-map path, with directional correction adding 4 operations when Hadamards are required.
  • The heuristic uses the maximum individual CNOT cost rather than a sum, avoiding overestimation when one SWAP reduces multiple CNOT distances.
  • The worked mapping inserts two SWAP operations and produces a circuit with 37 elementary operations and depth 15.

C. Optimizations

The methodology is optimized with look-ahead information and evolving partial mappings to reduce total circuit cost while satisfying layer constraints.

  • A∗ determines an optimal mapping for each layer by minimizing additionally required operations.
  • Look-ahead scheme: The look-ahead heuristic sums estimated CNOT costs from the current and following layers rather than using only the current layer.This can overestimate remaining costs and removes local-optimality guarantees.
  • Look-ahead scheme: 31 elementary operations and depth 12 result when look-ahead accepts a locally costlier layer mapping that avoids further SWAPs in the next layer.The locally optimal first-layer mapping costs 14, whereas the look-ahead mapping costs 22 but produces a cheaper overall circuit.
  • Initial mapping: Partial mappings allow the initial logical-to-physical assignment to evolve during mapping instead of being fixed randomly at the beginning.Unmapped qubits are assigned to free physical qubits chosen to minimize the cost of finding the next mapping.
  • Initial mapping: The optimized partial-mapping example produces 23 elementary operations with circuit depth 10.

V. EXPERIMENTAL EVALUATION

The evaluation benchmarks the proposed methodology on circuits mapped to IBM’s 16-qubit QX5 architecture and compares its implementation within QISKit against IBM’s design flow.

  • The methodology was implemented in C++ and integrated into QISKit, with a standalone version also made publicly available.
  • Benchmarks: The evaluation uses RevLib functions, Quipper and Scaffold algorithms, quantum ripple-carry adders, and small Shor algorithm instances.
  • Experimental setup: All benchmarks requiring at most 16 qubits were mapped to the QX5 architecture.The graphical circuit in Fig. 7 leaves SWAP operations undecomposed for readability.

A. Effect of the Optimizations

The optimization study compares baseline A∗ mapping with look-ahead and evolving initial mappings, showing lower gate counts and depths but a scalability trade-off for look-ahead alone.

  • The baseline uses A∗ to determine locally optimal mappings for each circuit layer, while enhanced settings add look-ahead and evolving initial mappings.
  • Look-ahead: 16.1% fewer gates and 13.4% fewer layers are obtained on average with look-ahead compared with the baseline.
  • Look-ahead: Look-ahead alone times out in nine cases, compared with five baseline timeouts, indicating reduced scalability.The timeout threshold is one hour.
  • Fully optimized methodology: 19.7% fewer gates and 14.1% fewer circuit-depth layers are achieved on average when evolving the initial mapping is added to the optimizations.These improvements are measured against the baseline.
  • Fully optimized methodology: The combined optimizations increase scalability while also reducing the size of the resulting circuits.

B. Comparison to the State of the Art

Against IBM’s QISKit mapping solution, the proposed methodology completes all evaluated mappings within the time limit and produces smaller circuits, often much faster.

  • The comparison applies the same decomposition schemes and post-mapping optimizations to both solutions through QISKit integration.
  • Runtime: IBM’s solution times out after one hour in 10 of 60 cases, whereas the proposed algorithm maps every circuit within the limit.
  • Circuit cost: 24.0% fewer gates and 18.3% lower circuit depth are achieved on average than IBM’s minimum observed results across repeated runs.
  • Circuit cost: 27.5% fewer gates and 22.0% lower circuit depth are achieved on average than IBM’s average results.

VI. CONCLUSIONS

The paper presents an integrated methodology for efficiently mapping quantum circuits to IBM QX architectures and satisfying their physical constraints. Experimental evaluation reports faster mappings than IBM’s solution, with fewer gates and smaller circuit depth.

  • The methodology decomposes quantum functionality into supported elementary gates and then satisfies architecture-imposed CNOT constraints.Its solution combines depth-based partitioning, A∗ search, look-ahead, and dedicated mapping initialization.
  • The approach was integrated into IBM’s SDK QISKit and determined mappings within seconds in most cases.IBM’s solution required more than one hour in several cases.
  • Mapped circuits had significantly fewer gates and smaller circuit depth, which positively influences circuit reliability and runtime.
  • The methodology is generic across existing QX architectures and similar future architectures.
Loading 1712.04722v3…