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:2302.06074 · Information and Computation

Asymptotically optimal synthesis of reversible circuits

Xian Wu, Lvzhou Li

Published Nov 8, 2024• 2 citations
arXivHTMLPDF
DOI
10.1016/j.ic.2024.105235

Related papers

Depth-optimized reversible circuit synthesis

Mona Arabzadeh, Morteza Saheb Zamani, Mehdi Sedighi +1 more

arXiv:1208.5425•Quantum Information Processing•Sep 8, 2012•19 citations

Synthesis, optimization and testing of reversible and quantum circuits

Anindita Banerjee

•Jun 12, 2010•1 citation

Synthesis of reversible circuits with minimal costs

Guowu Yang, Xiaoyu Song B, William N. N. Hung +2 more

CALCOLO•Sep 1, 2008•16 citations

Asymptotically Optimal Regular Synthesis of Reversible Logic Networks

Dmitri Maslov, Gerhard W. Dueck

We propose a network of generalized Tooli gates with mul-tiple EXORs for the realization of reversible functions. If implemented as a quantum circuit, the cost of such gates is shown to be only marginally higher than the cost of a Tooli gate with a single EXOR and the same number of controls. The main result is a regular synthesis procedure which al-lows for the creation of asymptotically optimal reversible networks. However, asymptotic optimality does not neces-sarily mean absolute optimality. Thus, when the algorithm terminates, and a network is created, simplication proce-dures that may reduce the number of gates in the network can be applied.

•Jan 1, 2003•8 citations

Efficient designs of reversible sequential circuits

Davar Kheirandish Taleshmekaeil, Majid Haghparast, Midia Reshadi +1 more

The Journal of Supercomputing•May 3, 2021•6 citations

Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)

Dmitry Vladimirovich Zakablukov

In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.

arXiv:1806.00687•Jun 2, 2018•1 citation
We propose a network of generalized Tooli gates with mul-tiple EXORs for the realization of reversible functions. If implemented as a quantum circuit, the cost of such gates is shown to be only marginally higher than the cost of a Tooli gate with a single EXOR and the same number of controls. The main result is a regular synthesis procedure which al-lows for the creation of asymptotically optimal reversible networks. However, asymptotic optimality does not neces-sarily mean absolute optimality. Thus, when the algorithm terminates, and a network is created, simplication proce-dures that may reduce the number of gates in the network can be applied.
In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.