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

arXiv:1408.3955 · Journal of Symbolic Computation

Ancilla-free synthesis of large reversible functions using binary decision diagrams

Mathias Soeken, Laura Tague, Gerhard W. Dueck, Rolf Drechsler

Published Mar 4, 2015• 52 citations
arXivHTMLPDF
DOI
10.1016/j.jsc.2015.03.002

Related papers

Reversible Synthesis through Shared Functional Decision Diagrams

Milena Stanković, Suzana Stojković

Lecture notes in computer science•Jan 1, 2009•0 citations

Synthesis of Reversible Circuits with Reduced Nearest-Neighbor Cost Using Kronecker Functional Decision Diagrams

Dengli Bu, Junjie Yan, Pengjie Tang +1 more

Journal of Electronic Testing•Feb 1, 2022•1 citation

Binary-decision-diagram-based decomposition of Boolean functions into reversible logic elements

Jia Lee, Ya-Hui Ye, Xin Huang +1 more

Theoretical Computer Science•Jan 20, 2020•8 citations

Reversible Circuits Synthesis from Functional Decision Diagrams by using Node Dependency Matrices

Suzana Stojković, Radomir S. Stanković, Claudio Moraga +1 more

Decision diagrams are a data structure suitable for reversible circuit synthesis. Functional decision diagrams (FDDs) are particularly convenient in synthesis with Toffoli gates, since the functional expressions for decomposition rules used in them are similar to the functional expressions of Toffoli gates. The main drawback of reversible circuit synthesis based on decision diagrams is the usually large number of ancilla lines. This paper presents two methods for the reduction of the number of ancilla lines in reversible circuits derived from FDDs by selecting the order of implementation of nodes. In the first method, nodes are implemented by levels, starting from the bottom level to the top. The method uses appropriately defined level dependency matrices for choosing the optimal order of implementation of nodes at the same level. In this way, the optimization is performed level by level. The second method uses a diagram dependency matrix expressing mutual dependencies among all the nodes in the diagram. This method is computationally more demanding than the first method, but the reductions of both the number of lines and the Quantum cost of the circuits are larger.

Journal of Circuits Systems and Computers•Jun 10, 2019•7 citations

Realization and synthesis of reversible functions

Guowu Yang, Fei Xie, William N. N. Hung +2 more

Theoretical Computer Science•Nov 30, 2010•9 citations

Positive Davio-based synthesis algorithm for reversible logic

Yu Pang, Shaoquan Wang, Zhilong He +3 more

Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Oct 1, 2011•17 citations
Decision diagrams are a data structure suitable for reversible circuit synthesis. Functional decision diagrams (FDDs) are particularly convenient in synthesis with Toffoli gates, since the functional expressions for decomposition rules used in them are similar to the functional expressions of Toffoli gates. The main drawback of reversible circuit synthesis based on decision diagrams is the usually large number of ancilla lines. This paper presents two methods for the reduction of the number of ancilla lines in reversible circuits derived from FDDs by selecting the order of implementation of nodes. In the first method, nodes are implemented by levels, starting from the bottom level to the top. The method uses appropriately defined level dependency matrices for choosing the optimal order of implementation of nodes at the same level. In this way, the optimization is performed level by level. The second method uses a diagram dependency matrix expressing mutual dependencies among all the nodes in the diagram. This method is computationally more demanding than the first method, but the reductions of both the number of lines and the Quantum cost of the circuits are larger.
Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.