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 International Symposium on Multiple-Valued Logic (ISMVL)

An Improved Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

Takashi Hirayama, Ryo Endo, Katsuhisa Yamanaka

Published May 28, 2024• 1 citation
Publisher

Abstract

This paper presents an improved lower bound, denoted as$v$, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function. The previous lower bound$\sigma-lb$used the characteristic vectors of reversible functions to formulate the theory of lower bounds. We carefully investigate cofactors of reversible functions to refine the characteristic vectors, and obtain a new theoretical basis for improving lower bounds. We show that the proposed lower bound$v$is better than the previous lower bound$\sigma-lb$by making both mathematical and experimental comparisons. Although the gain of refinement is not so significant in the experiments, an improvement of lower bounds is valuable as a theoretical achievement.

DOI
10.1109/ismvl60454.2024.00032

Related papers

A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

Takashi HIRAYAMA, Hayato SUGAWARA, Katsuhisa Yamanaka +1 more

We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.

IEICE Transactions on Information and Systems•Jan 1, 2014•3 citations

Quick Computation of the Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

Takashi Hirayama, Rin Suzuki, Katsuhisa Yamanaka +1 more

We present a time-efficient lower bound $\tilde \sigma $ on the number of gates in Toffoli-based reversible circuits that represent a given reversible logic function. For the characteristic vector s of a reversible logic function, the value of $\tilde \sigma ({\mathbf{s}})$ is almost the same as σ-lb (s), which is known as a relatively-efficient lower bound in terms of the evaluation time and the tightness. By slightly sacrificing the tightness of the lower bound, $\tilde \sigma $ achieves fast computation. We prove that $\tilde \sigma $ is a lower bound on σ-lb. Next, we show $\tilde \sigma $ can be calculated faster than σ-lb. The time complexity of $\tilde \sigma ({\mathbf{s}})$ is О(n2), where n is the dimension of s. Experimental results to compare $\tilde \sigma $ and σ-lb are also given. The results demonstrate that the values of $\tilde \sigma ({\mathbf{s}})$ are equal to those of σ-lb (s) for most reversible functions and that the computation time of $\tilde \sigma ({\mathbf{s}})$ is much shorter than that of σ-lb(s).

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2023•2 citations

New Bounds for Quick Computation of the Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

Takashi HIRAYAMA, Rin Suzuki, Katsuhisa Yamanaka +1 more

We present a time-efficient lower bound κ on the number of gates in Toffoli-based reversible circuits that represent a given reversible logic function. For the characteristic vector s of a reversible logic function, κ(s) closely approximates σ-lb(s), which is known as a relatively efficient lower bound in respect of evaluation time and tightness. The primary contribution of this paper is that κ enables fast computation while maintaining a tightness of the lower bound, approximately equal to σ-lb. We prove that the discrepancy between κ(s) and σ-lb(s) is at most one only, by providing upper and lower bounds on σ-lb in terms of κ. Subsequently, we show that κ can be calculated more efficiently than σ-lb. An algorithm for κ(s) with a complexity of O(n) is presented, where n is the dimension of s. Experimental results comparing κ and σ-lb are also given. The results demonstrate that the two lower bounds are equal for most reversible functions, and that the calculation of κ is significantly faster than σ-lb by several orders of magnitude.

IEICE Transactions on Information and Systems•Jul 31, 2024•1 citation

A framework for reversible circuit complexity

Mathias Soeken, Nabila Abdessaied, Rolf Drechsler

Reversible single-target gates are a generalization of Toffoli gates which are a helpful formal representation for the description of synthesis algorithms but are too general for an actual implementation based on some technology. There is an exponential lower bound on the number of Toffoli gates required to implement any reversible function, however, there is also a linear upper bound on the number of single-target gates which can be proven using a constructive proof based on a former presented synthesis algorithm. Since single-target gates can be mapped to a cascade of Toffoli gates, this synthesis algorithm provides an interesting framework for reversible circuit complexity. The paper motivates this framework and illustrates first possible applications based on it.

arXiv:1407.5878•Jul 22, 2014•8 citations

Reversible Logic Circuit Complexity Analysis via Functional Decomposition

Anupam Chattopadhyay, Anubhab Baksi

Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being Quantum computing. One of the key theoretical problem pertaining to reversible logic synthesis is the upper bound of the gate count. Compared to the known bounds, the results obtained by optimal synthesis methods are significantly less. In this paper, we connect this problem with the multiplicative complexity analysis of classical Boolean functions. We explore the possibility of relaxing the ancilla and if that approach makes the upper bound tighter. Our results are negative. The ancilla-free synthesis methods by using transformations and by starting from an Exclusive Sum-of-Product (ESOP) formulation remain, theoretically, the synthesis methods for achieving least gate count for the cases where the number of variables $n$ is $< 8$ and otherwise, respectively.

arXiv:1602.00101•Jan 30, 2016•3 citations

A novel Toffoli network synthesis algorithm for reversible logic

Yexin Zheng, Chao Huang

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2009•12 citations
This paper presents an improved lower bound, denoted asvvv, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function. The previous lower boundσ−lb\sigma-lbσ−lbused the characteristic vectors of reversible functions to formulate the theory of lower bounds. We carefully investigate cofactors of reversible functions to refine the characteristic vectors, and obtain a new theoretical basis for improving lower bounds. We show that the proposed lower boundvvvis better than the previous lower boundσ−lb\sigma-lbσ−lbby making both mathematical and experimental comparisons. Although the gain of refinement is not so significant in the experiments, an improvement of lower bounds is valuable as a theoretical achievement.
We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.
We present a time-efficient lower bound $\tilde \sigma $ on the number of gates in Toffoli-based reversible circuits that represent a given reversible logic function. For the characteristic vector s of a reversible logic function, the value of σ~(s)\tilde \sigma ({\mathbf{s}})σ~(s) is almost the same as σ-lb (s), which is known as a relatively-efficient lower bound in terms of the evaluation time and the tightness. By slightly sacrificing the tightness of the lower bound, $\tilde \sigma $ achieves fast computation. We prove that $\tilde \sigma $ is a lower bound on σ-lb. Next, we show $\tilde \sigma $ can be calculated faster than σ-lb. The time complexity of σ~(s)\tilde \sigma ({\mathbf{s}})σ~(s) is О(n2), where n is the dimension of s. Experimental results to compare $\tilde \sigma $ and σ-lb are also given. The results demonstrate that the values of σ~(s)\tilde \sigma ({\mathbf{s}})σ~(s) are equal to those of σ-lb (s) for most reversible functions and that the computation time of σ~(s)\tilde \sigma ({\mathbf{s}})σ~(s) is much shorter than that of σ-lb(s).
We present a time-efficient lower bound κ on the number of gates in Toffoli-based reversible circuits that represent a given reversible logic function. For the characteristic vector s of a reversible logic function, κ(s) closely approximates σ-lb(s), which is known as a relatively efficient lower bound in respect of evaluation time and tightness. The primary contribution of this paper is that κ enables fast computation while maintaining a tightness of the lower bound, approximately equal to σ-lb. We prove that the discrepancy between κ(s) and σ-lb(s) is at most one only, by providing upper and lower bounds on σ-lb in terms of κ. Subsequently, we show that κ can be calculated more efficiently than σ-lb. An algorithm for κ(s) with a complexity of O(n) is presented, where n is the dimension of s. Experimental results comparing κ and σ-lb are also given. The results demonstrate that the two lower bounds are equal for most reversible functions, and that the calculation of κ is significantly faster than σ-lb by several orders of magnitude.
Reversible single-target gates are a generalization of Toffoli gates which are a helpful formal representation for the description of synthesis algorithms but are too general for an actual implementation based on some technology. There is an exponential lower bound on the number of Toffoli gates required to implement any reversible function, however, there is also a linear upper bound on the number of single-target gates which can be proven using a constructive proof based on a former presented synthesis algorithm. Since single-target gates can be mapped to a cascade of Toffoli gates, this synthesis algorithm provides an interesting framework for reversible circuit complexity. The paper motivates this framework and illustrates first possible applications based on it.
Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being Quantum computing. One of the key theoretical problem pertaining to reversible logic synthesis is the upper bound of the gate count. Compared to the known bounds, the results obtained by optimal synthesis methods are significantly less. In this paper, we connect this problem with the multiplicative complexity analysis of classical Boolean functions. We explore the possibility of relaxing the ancilla and if that approach makes the upper bound tighter. Our results are negative. The ancilla-free synthesis methods by using transformations and by starting from an Exclusive Sum-of-Product (ESOP) formulation remain, theoretically, the synthesis methods for achieving least gate count for the cases where the number of variables nnn is <8< 8<8 and otherwise, respectively.
Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.