PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization of Quantum Circuit Mapping using Gate Transformation and Commutation

Toshinari Itoko, Rudy Raymond, Takashi Imamichi, Atsushi Matsuo

arXiv:1907.02686v2quant-phcs.DScs.ET

TL;DR

NISQ devices restrict which qubit pairs can perform two-qubit operations, so equivalent circuits need added gates to meet hardware coupling constraints. This paper combines gate commutation with SWAP and Bridge transformations, and reports 14.2% fewer additional CNOT gates on average than approaches without the new rules.

  • Problem

    NISQ coupling constraints require equivalent circuit mappings that make two-qubit operations executable, while supplementary gates can increase noise and computation time.

    Source: §1 · pp. 1–2

  • Method

    The paper develops exact and heuristic mapping algorithms that combine gate commutation rules with SWAP and Bridge transformations for non-adjacent CNOTs.

    Source: §1 · p. 2, §3 · p. 5, §6 · p. 9

  • Results

    14.2% fewer additional CNOT gates on average than approaches without the new transformation rules were found on a benchmark dataset.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For the benchmark circuits, the proposed algorithms found mappings with fewer additional gates than state-of-the-art algorithms.

    Source: §6 · p. 9

    The heuristic uses a trivial initial layout, and a better initial layout may further reduce the number of additional gates.

    Source: §5.2 · p. 9

Abstract

from arXiv · show

This paper addresses quantum circuit mapping for Noisy Intermediate-Scale Quantum (NISQ) computers. Since NISQ computers constraint two-qubit operations on limited couplings, an input circuit must be transformed into an equivalent output circuit obeying the constraints. The transformation often requires additional gates that can affect the accuracy of running the circuit. Based upon a previous work of quantum circuit mapping that leverages gate commutation rules, this paper shows algorithms that utilize both transformation and commutation rules. Experiments on a standard benchmark dataset confirm the algorithms with more rules can find even better circuit mappings compared with the previously-known best algorithms.

1 Introduction

NISQ coupling constraints require input circuits to be mapped to hardware qubits with additional gates, which can increase noise and computation time. This paper combines gate commutation with SWAP and Bridge transformations; experiments report fewer added CNOT gates than approaches without the new rules.

1 Introduction

  • Because NISQ devices cannot apply CNOT gates between every qubit pair, quantum circuit mapping seeks an equivalent circuit that obeys hardware coupling constraints.Added gates can increase noise and computation time because CNOT gates are noisy and take significantly longer than single-qubit gates.Source: §1 · pp. 1–2
  • Earlier work showed that commuting gates can reduce added SWAP gates compared with resolving two-qubit operations layer by layer.The paper describes four simple commutation rules involving CNOT and single-qubit gates.Source: §1 · p. 2
  • SWAP gates move neighboring qubits until they are adjacent, while Bridge gates implement a CNOT between non-adjacent qubits without permuting logical-qubit order.The choice can affect whether later gates allow further reductions in additional CNOTs.Source: §1 · p. 2
  • This paper extends that approach by combining commutation rules with the choice of using SWAP or Bridge transformations for non-adjacent CNOTs.The transformations can affect later opportunities to reduce additional CNOT gates.Source: §1 · p. 2
  • 14.2% fewer additional CNOT gates on average than approaches without the new transformation rules were found on a benchmark dataset.Source: §1 · p. 2

2 Motivation and Related Work

The paper extends quantum circuit mapping with gate commutation and both SWAP and Bridge transformations, addressing limitations of fixed-layer and standard-DAG formulations. Earlier work, to the authors’ knowledge, had not fully considered commutation rules or transformations beyond SWAP gates.

2 Motivation and Related Work

  • Earlier studies either did not fully consider gate commutation or did not consider transformation rules beyond SWAP gates.The paper addresses this gap with algorithms using both commutation and Bridge/SWAP transformation rules.Source: §2 · pp. 2–3
  • Fixed-layer mapping requires all gates in a layer to be mapped before gates in the next, while commutation can permit a later-layer gate to move earlier.In the example, moving CX 4 before Rz and then before CX 2 allows CX 1 and CX 4 to run before swapping b2 and b3 to run CX 2, CX 3, and CX 5.Source: §2 · p. 3
  • Fixed-layer mapping can require two additional SWAP gates where reordering gates by standard commutation rules requires one.The example illustrates how changing gate order can avoid a mapping cost imposed by fixed layers.Source: §2 · p. 3, Figure 4 · p. 4
  • The standard-DAG formulation allows more flexibility than fixed layers but can still produce suboptimal mappings, including two additional SWAP gates in the illustrated circuit.It models trivial commutation between consecutive gates that do not share qubits.Source: §2 · p. 3
  • Prior dependency-graph work models the true partial order imposed by commutation rules, while other studies considered fewer commutation rules or circuit-specific rules without systematic exploitation.The paper also situates its approach alongside prior Bridge/SWAP mapping work, including a heuristic reported to perform poorly on nonsynthetic circuits.Source: §2 · pp. 3–4

3 Problem Formulation

The section formulates mapping as finding an equivalent physical circuit that obeys hardware coupling constraints while minimizing added CNOT gates. It defines the circuit, hardware, layout, and cost terms used in this optimization.

3 Problem Formulation

  • The formulation assumes the logical and physical qubit sets have equal size by adding ancillary qubits when the logical circuit uses fewer qubits.Logical qubits are from the original circuit; physical qubits are those of the hardware.Source: §3 · p. 4
  • A layout is a permutation from logical qubits to physical qubits, and a physical circuit complies with the coupling graph when every CNOT’s control and target are adjacent.The coupling graph has physical qubits as nodes and hardware couplings as edges.Source: §3 · p. 4
  • The mapping objective minimizes additional CNOT gates because they are usually noisier and slower to run than single-qubit gates.A valid physical circuit is equivalent in computation to the logical circuit and complies with the hardware coupling graph.Source: §3 · p. 4
  • Minimum CNOT Gate Mapping (MCGM) takes a logical circuit, coupling graph, and commutation-rule set, and seeks an initial layout and equivalent compliant physical circuit with the fewest CNOT gates.The formulation considers mappings that incorporate commutation rules.Source: §3 · p. 4

4 Algorithms

The algorithms map circuits using dependency graphs that incorporate gate commutation, tracking blocking gates as they resolve gates with SWAP or Bridge operations. An exact dynamic program seeks an optimum, while a look-ahead heuristic targets larger circuits.

4 Algorithms

  • Both algorithms solve Minimum CNOT Gate Mapping by minimizing additional SWAP and Bridge gates, each requiring three additional CNOT gates; Bridge applies only at distance two.They use dependency graphs and blocking gates to track the gates that remain unresolved under the current layout.Source: §4 · pp. 5–6

4.1 Exact algorithm

  • The exact dynamic program explores layout-and-blocking-gate states in increasing gate cost and returns an optimal mapping when no blocking gates remain.It activates each state at most once, but its long runtime limits use to small circuits.Source: §4.1 · pp. 6–7

4.2 Heuristic algorithm

  • The look-ahead heuristic scores coupling-edge swaps by weighted shortest-path changes across unresolved gates, prioritizing blocking gates and nearby future gates.It can replace a distance-two CNOT with a Bridge when the highest swap score is below 1; its loop is guaranteed to terminate.Source: §4.2 · pp. 7–8

5 Experimental Results

The experiments compare the formulation and heuristic with alternatives on random and benchmark circuits. The proposed heuristic reduced additional gates on all tested instances against QRAND and ZPW, while exact-algorithm runtime grew exponentially with circuit size.

5.1 Comparison to formulations with fewer commutation rules and one without Bridge gates

  • Proposed used fewer additional SWAP and Bridge gates than Std-DAG and slightly fewer than Fixed-layer across coupling architectures; Bridge gates improved optimality over No-Bridge.The exact comparison used two sets of 10 random circuits with five or six qubits and 100 gates per circuit.Source: §5.1 · p. 8, Table 1 · p. 9

5. Experimental Results

  • In the second experiment, the heuristic was compared with QRAND and ZPW using 44 circuits with at least 10 qubits and at most 50,000 gates, mapped to the ibmqx3 coupling architecture.Source: §5.2 · p. 9

5.2 Comparison with other heuristic algorithms for larger circuits

  • 14.2% average decrease in additional gates, with Proposed outperforming QRAND and ZPW on all instances.Additional SWAP and Bridge gates decreased by 10.0–72.3% (average 53.2%) versus QRAND and 10.9–48.8% (average 34.7%) versus ZPW.Source: §5.2 · p. 9
  • The heuristic evaluations used a trivial initial layout, which may leave further reductions in additional gates possible with a better starting layout.The authors also applied post-processing to remove leading useless SWAP gates.Source: §5.2 · p. 9

6 Conclusion

The paper addresses mapping quantum circuits to NISQ devices with as few additional gates as possible. Its algorithms combine gate commutation with SWAP and Bridge transformations, and find mappings with fewer additional gates on a commonly used benchmark dataset.

6 Conclusion

  • The mapping task is to compile circuits for NISQ devices whose coupling architecture constrains operations, while minimizing added gates.Source: §6 · p. 9
  • The proposed algorithms find benchmark mappings with fewer additional gates than state-of-the-art circuit-mapping algorithms.Table 2 compares added SWAP and Bridge gate counts for Proposed, No-Bridge, QRAND, and ZPW on RevLib circuits with 10 to 16 qubits.Source: §6 · p. 9, Table 2 · p. 10
  • The proposed exact and heuristic algorithms combine gate commutation rules with SWAP and Bridge transformations.Source: §6 · p. 9

A Construction of dependency graph

Algorithm 3 constructs a dependency graph from a circuit’s gate list, using criteria tailored to the paper’s commutation rules. The resulting graph may contain redundant edges.

A Construction of dependency graph

Loading 1907.02686v2…