Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Congress on Evolutionary Computation (CEC)

A Constructive Algorithm for Reversible Logic Synthesis

Guowu Yang, Fei Xie, Xiaoyu Song B, William N. N. Hung, Marek A. Perkowski

Published Sep 22, 2006• 24 citations
Publisher

Abstract

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.

DOI
10.1109/cec.2006.1688608

Related papers

Realization and synthesis of reversible functions throng double-coset

Fu Chen, Guowu Yang, Xiaoyu Li

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.

International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)•Dec 1, 2010•0 citations

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, 2009•5 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 Systems•Oct 30, 2006•379 citations

Reversible logic circuit synthesis

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design•Jan 1, 2002•157 citations

Synthesis of reversible logic circuits

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 29, 2003•570 citations

Reversible logic circuit synthesis

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

International Conference on Computer Aided Design•Jun 25, 2003•68 citations
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.
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.
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
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
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.