International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)

Realization and synthesis of reversible functions throng double-coset

Fu Chen, Guowu Yang, Xiaoyu Li

Published Dec 1, 2010• 0 citations

Abstract

Reversible circuits play an important role in quantum computation. The realization of reversible quantum circuits is required for any quantum computer to be universal. This paper1studies the realization and synthesis problem of reversible circuits. Using group theory, we present two sets of new 3-bit reversible logic gates, which included g1g2g3and nine complex gates, respectively. It is shown that any 3-bit reversible logic circuit is realizable by cascading NOT and Feynman gates, and at most one instance of our proposed gates. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2n, and the other (2n- N) input patterns will be the same as their outputs. According to a synthesis example, it demonstrates that the main results are constructive and practical than others.

DOI: 10.1109/ispacs.2010.5704651

Related papers

A Constructive Algorithm for Reversible Logic Synthesis

Guowu Yang, Fei Xie, Xiaoyu Song B +2 more

This paper presents a constructive synthesis algorithm for any n-qubit reversible function. Given any n-qubit reversible function, there are N distinct input patterns different from their corresponding outputs, where N les 2n, and the other (2n- N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2nldrN '(n - 1)'-CNOT gates and 4n2ldr N NOT gates. The time complexity of our algorithm has asymptotic upper bound O(n ldr 4n). The space complexity of our synthesis algorithm is also O(n ldr 2n). The computational complexity of our synthesis algorithm is exponentially lower than the complexity of breadth-first search based synthesis algorithm.

IEEE Congress on Evolutionary Computation (CEC)Sep 22, 200624 citations

On synthesis of 3 × 3 reversible logic functions

Ming Gu, Guowu Yang, Xiaoyu Song B +1 more

Reversible logic plays an important role in quantum computing. This article presents some novel results on synthesis of 3 × 3 reversible Boolean gates. We derive the relationship between reversible 3 × 3 gates and corresponding symmetric groups. By introducing a set of universal libraries, we show how to use group theory to synthesize any 3 × 3 reversible gate.

International Journal of Computer MathematicsFeb 22, 20050 citations

Synthesis of ternary non-reversible logic circuits

Xiaoyu Li, Guowu Yang, Desheng Zheng

Reversible quantum circuits are a necessary subclass of quantum computation and its realization is required for any quantum computer to be universal. This paper investigates how to synthesis of arbitrary ternary non-reversible logic circuits by adding inputs with constant value and garbage outputs. Group theory has been also used to solve the synthesis of reversible logic circuits. Our algorithm uses the SNT (ternary Swap gate, ternary NOT gate, ternary Toffoli gate) library, by reducing the ternary non-reversible logic circuit synthesis problem to group theory representation. The main result shows the relationship of ternary non-reversible logic circuits and the reversible circuits. The realization approach is constructive and can be further used to develop software for synthesis of arbitrary d-level circuits. This result is significantly different from the binary non-reversible logic circuits.

IEEE Congress on Evolutionary Computation (CEC)Jul 1, 20101 citation

Group theory based synthesis of binary reversible circuits

Guowu Yang, William N. N. Hung, Marek A. Perkowski

Abstract. This paper presents an important result addressing a fundamental question in synthesizing binary reversible logic circuits for quantum computation. We show that any even-reversible-circuit of n (n>3) qubits can be realized using NOT gate and Toffoli gate (‘2’-Controlled-Not gate), where the numbers of Toffoli and NOT gates required in the realization are bounded by (n+ ⌊ n 3 ⌋)(3×22n−3 −2 n+2)and4n(n+ ⌊ n 3 ⌋)2n, respectively. A provable constructive synthesis algorithm is derived. The time complexity of the algorithm is 10 3 n2 · 2 n. Our algorithm is exponentially lower than breadth-first search based synthesis algorithms with respect to space and time complexities. 1

Apr 7, 20095 citations

Logic Synthesis of Ternary Quantum Circuits with Minimal Qutrits

Xiaoyu Li, Guowu Yang, Desheng Zheng

Abstract — This paper investigates a universal approach of synthesizing arbitrary ternary logic circuits in quantum computation based on the truth table technology. It takes into account of the relationship of classical logic and quantum logic circuits. By adding inputs with constant value and garbage outputs, the classical non-reversible logic can be transformed into reversible logic. Combined with group theory, it provides an algorithm using the ternary Swap gate, ternary NOT gate and ternary Toffoli gate library. Simultaneously, the main result shows that the numbers of qutrits we use are minimal compared to other methods. We also illustrate with two examples to test our approach. Index Terms — ternary quantum computation, reversible logic, circuit synthesis, group theory I.

Journal of ComputersJul 17, 201317 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOct 30, 2006379 citations