PaperlayerView exact revision on arXiv

Source-linked AI summary

Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures

Mehdi Saeedi, Robert Wille, Rolf Drechsler

arXiv:1110.6412v2quant-phcs.ET

TL;DR

Quantum circuit synthesis must account for limited interaction distance in LNN architectures rather than treating the restriction naively. The paper combines template matching, exact synthesis, and qubit reordering into an LNN-aware flow, reducing the resulting quantum-cost increase by more than 50% on average.

  • Problem

    Limited interaction distance between gate qubits constrains physical quantum implementations, while conventional synthesis does not explicitly account for LNN restrictions.

  • Method

    The paper extends synthesis with template-matching optimization, exact nearest-neighbor synthesis, and qubit-reordering strategies combined into an integrated flow.

  • Results

    More than 50% average reduction in the quantum-cost increase is achieved, reaching 83% in the best case.

  • Takeaways & Limitations

    NNC-optimal circuits can be synthesized with a moderate increase in quantum cost.

  • Takeaways & Limitations

    The exact synthesis method is limited to functions with small numbers of qubits and gates because of its exponential search space.

Abstract

from arXiv · show

While a couple of impressive quantum technologies have been proposed, they have several intrinsic limitations which must be considered by circuit designers to produce realizable circuits. Limited interaction distance between gate qubits is one of the most common limitations. In this paper, we suggest extensions of the existing synthesis flow aimed to realize circuits for quantum architectures with linear nearest neighbor (LNN) interaction. To this end, a template matching optimization, an exact synthesis approach, and two reordering strategies are introduced. The proposed methods are combined as an integrated synthesis flow. Experiments show that by using the suggested flow, quantum cost can be improved by more than 50% on average.

1 Introduction

Quantum computing offers potential advantages but faces physical implementation constraints, especially limited interaction distance between gate qubits. The paper extends synthesis for LNN architectures using optimization, exact synthesis, and qubit-reordering methods.

  • Limited interaction distance between gate qubits is a common constraint across quantum technologies.
  • LNN circuit realization has been studied for specific algorithms and general quantum or reversible circuits.
  • The paper integrates these approaches into an extended synthesis flow for LNN architectures.
  • The proposed flow combines improved template matching, exact nearest-neighbor synthesis, and qubit-reordering strategies.
  • The paper is organized around background concepts, naive and explicit LNN-aware synthesis, integration, experiments, and conclusions.

2 Background

The paper introduces reversible and quantum logic fundamentals, including reversible functions, quantum gates, decomposition into elementary gates, and the resulting quantum-cost metric. Standard decompositions map reversible gates to physical elementary operations.

  • 2.1 Reversible Logic: A reversible function maps each input assignment to a unique output assignment and has equal numbers of input and output variables.
  • 2.1 Reversible Logic: Multiple-control Toffoli, Fredkin, and Peres gates are introduced as common reversible gates and circuit-building elements.
  • 2.1 Reversible Logic: A decomposed reversible circuit is a cascade of elementary quantum gates representing the original reversible gates.
  • 2.2 Quantum Logic: A qubit occupies states |0⟩ and |1⟩ or their linear combinations, with superposition written as |ψ⟩= α|0⟩+ β|1⟩.
  • 2.2 Quantum Logic: An n-qubit gate performs a 2^n × 2^n unitary operation, with Hadamard, Controlled-V, and Controlled-V+ given as examples.
  • 2.3 Synthesis Cost: Quantum cost counts the elementary gates required to realize a reversible gate, under a technology-dependent definition of elementary gates.
  • 2.3 Synthesis Cost: A t2 gate decomposes into 5 elementary gates, while an f_m gate uses the cost of a t_{m+1} gate plus two.

3 The Naive Synthesis Flow for the LNN Architectures

The naive synthesis flow first synthesizes reversible circuits and decomposes them into elementary gates, then inserts SWAP gates to enforce nearest-neighbor interaction. This guarantees NNC-optimality but can substantially increase quantum cost.

  • Naive synthesis: Reversible circuits are commonly synthesized with multiple-control Toffoli gates before mapping them to elementary quantum gates.
  • Naive synthesis: Standard decomposition can produce non-adjacent gates, requiring SWAP insertion to satisfy LNN interactions.
  • Naive synthesis: 11 elementary gates can replace a standard Toffoli decomposition with NNC 0 after inserting two SWAP gates.
  • Naive synthesis: The naive method inserts SWAP gates consecutively for non-adjacent gates and determines an NNC-0 circuit in linear time.
  • Naive synthesis: A smaller NNC-optimal realization can cost 9 instead of 11, motivating synthesis methods that explicitly consider NNC.

4 Explicit Consideration of NNC

The paper extends synthesis for LNN architectures with template matching, exact synthesis, and reordering methods that explicitly minimize non-neighbor interactions and circuit cost. These approaches can optimize existing circuits, construct small optimal circuits, and exploit those circuits as macros.

  • Explicit NNC-aware synthesis: The proposed flow combines template matching, exact synthesis, and reordering strategies that explicitly account for LNN restrictions.Template matching simplifies existing circuits, exact synthesis targets minimal quantum cost and NNC, and reordering reduces distances between interacting qubits.
  • NNC-based Template Matching: Template matching replaces gate cascades with equivalent cascades and applies moving and deletion rules to remove unnecessary interactions.The proposed templates contain one, two, or three SWAP gates; moving rules interchange compatible neighboring gates, while deletion rules remove certain neighboring SWAP gates.
  • NNC-based Template Matching: 37% lower quantum cost is achieved in an example by applying proposed templates followed by the deletion rule.The circuit begins with quantum cost 16, and successive template applications produce the final optimized circuit.
  • NNC-based Template Matching: 20% improvement over a prior nearest-neighbor template is obtained for a Toffoli-CNOT combination, reducing quantum cost from 30 to 24.The proposed templates are applied together with the deletion rule after naive NNC-based decomposition.
  • NNC-based Template Matching: The proposed templates reduce an 8-qubit AQFT realization from 36 SWAP gates to 20, compared with 24 SWAP gates from another method.The AQFT uses approximation parameter 5; the 36-SWAP circuit is obtained by the method of Takahashi et al., while the 24-SWAP circuit uses Hirata et al.'s method.
  • Exploiting Exact Synthesis: The exact synthesis method searches SAT instances using a restricted library of adjacent gates to construct circuits with minimal quantum cost and NNC.For a function f, the gate count c is increased until a realizing circuit is found; the exponential search space limits applicability to small functions.
  • Exploiting Exact Synthesis: The exact method reduces the Toffoli decomposition cost from 11 to 9 while preserving NNC optimality, and its optimal circuits can serve as macros.Macros replace naive decompositions in larger circuits; one example reduces total cost from 96 to 92, while the generated macros reduce each gate's cost by up to 63%.

5 A Synthesis Flow for LNN Architectures

The extended synthesis flow combines synthesis, optional macro replacement, decomposition, qubit reordering, SWAP insertion, and template matching to produce circuits for LNN architectures.

  • 5 A Synthesis Flow for LNN Architectures: The flow synthesizes a reversible or quantum specification into an initial circuit and outputs a circuit for LNN architectures.Macro replacement, decomposition, reordering, SWAP insertion, and template matching are optional or sequential flow stages.
  • 5 A Synthesis Flow for LNN Architectures: Macro replacement can be applied before decomposing each gate into elementary gates.The flow conditionally applies available macros and then performs elementary-gate decomposition.
  • 5 A Synthesis Flow for LNN Architectures: Global reordering changes initial qubit locations, while local reordering updates line ordering during circuit traversal.The local strategy inserts a SWAP before a non-adjacent gate and propagates the resulting ordering through the remaining circuit.
  • 5 A Synthesis Flow for LNN Architectures: The flow inserts SWAP gates for non-adjacent gates and can apply templates when template matching is enabled.These stages explicitly address nearest-neighbor constraints and circuit optimization.

6 Experimental Results

Experiments compare the proposed LNN-aware synthesis flow with a naive approach on RevLib benchmark circuits under two SWAP-cost definitions. The proposed methods reduce quantum cost substantially, while most configurations run in less than one CPU second.

  • 6 Experimental Results: The evaluation uses RevLib benchmark circuits and compares the proposed flow with the naive synthesis approach.The methods were implemented in C++ and tested on a varied benchmark collection.
  • 6 Experimental Results: Tables 2 and 3 report quantum cost for established and extended definitions of elementary gates, respectively.The configurations combine macro replacement, global reordering, local reordering, and template matching.
  • 6 Experimental Results: The naive method significantly increases quantum cost when decomposing circuits for LNN architectures.The proposed methods improve the results overall, although reordering can worsen results in some cases.
  • 6 Experimental Results: More than 50% average quantum-cost reductions were observed, reaching 83% in the best case under the established decomposition.Similar results were obtained with the extended elementary-gate definition.

7 Conclusions

The paper modifies synthesis to address limited qubit interaction distance in LNN architectures. Its NNC-based decomposition and template-matching flow reduces the cost increase caused by the LNN restriction by more than 50% on average.

  • 7 Conclusions: Limited interaction distance is identified as a common limitation of current quantum technologies.The conclusion frames this constraint as relevant to producing efficient circuits for limited-interaction architectures.
  • 7 Conclusions: The proposed flow combines NNC-based decomposition methods with an NNC-based template-matching algorithm.It is designed to produce efficient circuits for quantum technologies with limited interactions.
  • 7 Conclusions: More than 50% average reduction, and 83% in the best case, reduces the quantum-cost increase caused by naive treatment of the LNN restriction.The conclusion reports that naive treatment can require up to one order of magnitude higher quantum cost.
Loading 1110.6412v2…