PaperlayerView exact revision on arXiv

Source-linked AI summary

Reversible Circuit Synthesis Using a Cycle-Based Approach

Mehdi Saeedi, Morteza Saheb Zamani, Mehdi Sedighi, Zahra Sasanian

arXiv:1004.4320v2quant-phcs.ET

TL;DR

Reversible synthesis must produce efficient circuits for arbitrary reversible specifications, a task conventional synthesis algorithms cannot directly handle. This paper combines direct k-cycle synthesis, decomposition, and an RM-based method; its hybrid framework is reported to converge and improve benchmark costs and average runtime.

  • Problem

    Reversible synthesis seeks efficient circuits for arbitrary-size specifications, but mature irreversible synthesis algorithms cannot directly apply because reversible circuits prohibit loops and fanout.

    Source: §1 · p. 2

  • Method

    The paper synthesizes cycles using building blocks and decomposition, then combines k-cycle synthesis with a recent RM-spectrum NCT-based method in a hybrid framework.

    Source: §1 · p. 2

  • Results

    The hybrid framework always converges, improves average runtime, and produces lower-cost circuits for benchmark functions.

    Source: §5 · p. 24

  • Takeaways & Limitations

    The proposed framework combines cycle-based synthesis with another synthesis method to improve benchmark circuit costs and average runtime.

    Source: §5 · pp. 23–24

    The decomposition approach assumes n≥7 and handles zero and 2^i terms separately; experiments using the method of imposed a 12-hour time limit.

    Source: §3.1 · p. 5, §4 · p. 21

Abstract

from arXiv · show

Reversible logic has applications in various research areas including signal processing, cryptography and quantum computation. In this paper, direct NCT-based synthesis of a given $k$-cycle in a cycle-based synthesis scenario is examined. To this end, a set of seven building blocks is proposed that reveals the potential of direct synthesis of a given permutation to reduce both quantum cost and average runtime. To synthesize a given large cycle, we propose a decomposition algorithm to extract the suggested building blocks from the input specification. Then, a synthesis method is introduced which uses the building blocks and the decomposition algorithm. Finally, a hybrid synthesis framework is suggested which uses the proposed cycle-based synthesis method in conjunction with one of the recent NCT-based synthesis approaches which is based on Reed-Muller (RM) spectra. The time complexity and the effectiveness of the proposed synthesis approach are analyzed in detail. Our analyses show that the proposed hybrid framework leads to a better quantum cost in the worst-case scenario compared to the previously presented methods. The proposed framework always converges and typically synthesizes a given specification very fast compared to the available synthesis algorithms. Besides, the quantum costs of benchmark functions are improved about 20% on average (55% in the best case).

1 Introduction

Reversible-circuit synthesis seeks efficient circuits for arbitrary reversible specifications, which conventional synthesis methods cannot directly handle. This paper proposes k-cycle synthesis and a hybrid framework, reporting lower quantum costs and improved runtime.

1 Introduction

  • Reversible logic is motivated in part by potential energy-efficiency gains and its relevance to quantum computing.Landauer’s limit and Bennett’s argument are cited as foundations for the energy-efficiency motivation,.Source: §1 · p. 2
  • Reversible synthesis must generate efficient circuits for arbitrary-size specifications, and mature irreversible synthesis algorithms cannot be applied directly because reversible circuits prohibit loops and fanout.Source: §1 · p. 2
  • The proposed framework combines k-cycle-based synthesis with a recent NCT-based method.Its cycle-based method uses building blocks and a decomposition algorithm to synthesize large cycles directly.Source: §1 · p. 2
  • The k-cycle-based synthesis method is reported to have guaranteed convergence.The paper analyzes cycle-based synthesis for reversible functions with different characterizations.Source: §1 · p. 2
  • The hybrid framework improves worst-case quantum cost over previously presented methods.The paper also reports better average quantum costs for available NCT-library benchmarks.Source: §1 · p. 3
  • The proposed approach improves average runtime compared with present synthesis algorithms while maintaining favorable synthesis costs.Source: §1 · p. 3

2 Preliminaries

The preliminaries define cycles and reversible gates, then review NCT-based synthesis and its costs. Earlier methods decompose permutations into transpositions, while the paper motivates direct k-cycle synthesis as a way to reduce cost.

2 Preliminaries

  • A permutation can be represented as disjoint cycles, and a k-cycle maps each element to the next, with the last returning to the first.A cycle of length two is a transposition.Source: §2 · p. 3
  • The NCT library comprises NOT, CNOT, and Toffoli gates, and quantum cost counts elementary gates used to simulate a gate.A generalized Toffoli flips its target only when all control lines are 1.Source: §2 · pp. 3–4
  • When k Toffoli gates share controls, their implementation can use 2k+3 elementary gates; Toffoli costs five, while NOT and CNOT cost one each.Source: §2 · p. 4, Figure 1 · p. 4
  • Reversible implementations face a restricted supply of bits, so circuits with equal linear costs are preferred when they avoid garbage lines.The cited gate-simulation costs can rise exponentially for a Cn−1NOT gate when no garbage line is available.Source: §2 · p. 4
  • The earlier method synthesizes permutations by implementing disjoint transpositions and decomposes a k-cycle recursively into transpositions and a smaller cycle.The extension reduces quantum cost by using unit-cost NOT and CNOT gates in place of Toffoli gates in many situations.Source: §2 · pp. 4–5

3 k-Cycle-Based Synthesis Method

Section 3 presents a k-cycle-based NCT synthesis method that directly synthesizes selected single-cycle and cycle-pair building blocks and decomposes larger permutations into elementary cycles. It establishes convergence and worst-case gate bounds for unrestricted and LNN synthesis.

3.1 Building Blocks

  • An arbitrary pair of 2-cycles can be implemented by at most 34n −64 elementary gates.The circuit maps the four terms to canonical values, applies κ0(2,2), and reverses the mapping; the stated setup assumes n ≥7 and excludes 0 and powers of two from the cycle terms.Source: §3.1 · pp. 5–6
  • An arbitrary pair of 3-cycles requires at most 38n −46 elementary gates; the canonical κ0(3,3) circuit costs 24n −112.A single 3-cycle requires at most 32n −82 elementary gates and can itself serve as a building block because it is even.Source: §3.1 · pp. 8–9
  • An arbitrary pair comprising a 4-cycle and a 2-cycle requires at most 50n −122 elementary gates; its κ0(4,2) circuit costs 36n −180.The method maps the cycle terms to canonical inputs, applies κ0(4,2), and reverses the mapping.Source: §3.1 · pp. 10–11
  • Theorem 3.5 states that an arbitrary pair (a,b,c,d) (e,f,g,h) can be implemented by at most 56n −126 elementary gates; the κ0(4,4) circuit for (2n −8, 2n −2, 2n −6, 2n −4) (2n −7, 2n −1, 2n −5, 2n −3) costs 36n −228.Source: §3.1 · p. 11
  • An arbitrary 5-cycle requires at most 60n −130 elementary gates, while the κ0(5) circuit has cost 48n −166.The method applies the canonical κ0(5) circuit between a forward mapping of the cycle terms and its inverse.Source: §3.1 · pp. 12–13
  • Theorem 3.7 states that an arbitrary pair of 5-cycles, (a,b,c,d,e) and (f,g,h,i,j), can be implemented using at most 64n −54 elementary gates.Source: §3.1 · p. 13
  • Direct k-cycle implementations show potential to reduce cost relative to the 2-cycle-based method, while decomposition makes general k-cycles tractable to synthesize.The building blocks are used with the decomposition algorithm to synthesize large cycles.Source: §3.1 · p. 14

3.2 Decomposition Method

  • The decomposition recursively extracts 5-cycles from longer cycles, leaving elementary cycles of lengths 2, 3, 4, or 5; its total synthesis complexity is O(2^2n × n), the same as.For n < 7, the algorithm instead decomposes the permutation into 2-cycles; for n ≥ 7, it synthesizes the extracted elementary cycles using the proposed building blocks.Source: §3.2 · pp. 15–17
  • The proposed k-cycle-based synthesis method always converges for arbitrary cycle elements, with preprocessing for 0 and 2^i terms and separate synthesis scenarios for n < 7 and n ≥ 7.For n ≥ 7, the building blocks can be synthesized when cycle elements are neither 0 nor 2^i, and the decomposition algorithm can always reduce large cycles to elementary cycles.Source: §3.2 · p. 18

3.3 Worst Case Analysis

  • The proposed method’s maximum cost is 8.5n2^n + o(2^n) elementary gates, below the 11n2^n + o(n2^n) upper bound reported for.The worst case occurs when the maximum number of permutation rows is changed.Source: §3.3 · p. 18
  • For LNN architecture, the maximum cost is 51n^2 2^n elementary gates.The bound applies a SWAP-based cost for bringing nonadjacent controls and targets together and restoring qubit positions.Source: §3.3 · p. 19

4 Experimental Results

The experiments compare the proposed k-cycle method and a hybrid framework with prior NCT-based synthesis methods on reversible benchmarks. The hybrid selects methods based on function characteristics and improves average quantum cost and runtime, though runtime and memory rise with circuit size.

4 Experimental Results

  • The evaluation used completely specified reversible benchmarks and compared against documented NCT synthesis costs, applying methods and when benchmark results were unavailable.Method was given a 12-hour limit; when it failed, method was used.Source: §4 · pp. 19–20
  • The k-cycle method’s quantum-cost performance varies across benchmarks, motivating a hybrid with the method of.The paper cites hwb11 and cycle10 2 as examples of differing results.Source: §4 · p. 20
  • Benchmarks were grouped by input size and Distance(f): category 1 has fewer than seven inputs, while categories 2 and 3 have n ≥7 and Distance above or below 0.5, respectively.Distance models the distribution of output code words relative to the identity function; ham7 has Distance 0.38, cycle10 2 has 0.001, and hwb10 has 0.62.Source: §4 · p. 20
  • The hybrid also uses output-pattern count: functions with NoP below threshold Th may be treated as somewhat similar to identity and synthesized with the RM-based method.The threshold was set to 0.005 × 2^n; ham7 is shown with NoP = 12.Source: §4 · pp. 22–23, Figure 21 · p. 23
  • The hybrid framework outperforms the best results in average quantum cost and runtime, while hwb functions with n ≥20 use more than 2GB peak memory.The authors note that runtime and memory grow as the number of variables and synthesized gates grow.Source: §4 · p. 23
  • The hybrid framework always converges, with worst-case cost equal to the cycle-based method’s bound, 8.5n2^n + o(2^n).The bound applies to large functions with Distance(f) ≥0.5 and no regular output patterns.Source: §4 · p. 23

5 Conclusion and future directions

The paper concludes that its cycle-based method and hybrid framework improve reversible synthesis outcomes, with guaranteed convergence and better average runtime. It identifies longer-cycle and incompletely specified-function synthesis as future directions.

5 Conclusion and future directions

  • The method synthesizes elementary cycles and decomposes large cycles into them, then applies these techniques to synthesize permutations.The paper reports that worst-case analysis gives the hybrid framework a lower upper bound than existing synthesis algorithms.Source: §5 · p. 23
  • The hybrid framework always converges, improves average runtime, and yields lower costs for benchmark functions; future work includes cycles longer than 5 and incompletely specified functions.The authors state that longer-cycle work could further improve the hybrid framework’s results.Source: §5 · p. 24

Related papers

Loading 1004.4320v2…