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:2607.19059

On the completeness of transformation rules in reversible logic synthesis

Shiguang Feng, Zongxing Xiong, Lvzhou Li

Published Jul 21, 2026• 0 citations
arXivHTMLPDF

Abstract

Transformation rules play a central role in reversible circuit optimization, template-based rewriting, and equivalence checking, and establishing their completeness is a fundamental problem in reversible logic synthesis. In this work, we investigate the completeness of transformation rules for reversible circuits both with and without ancillary bits and garbage outputs. For reversible circuits without ancillary bits and garbage outputs, we introduce a refined and complete transformation rule set $\mathcal{RC}^{r}$, obtained by replacing one rule in the rule set $\mathcal{RC}$ proposed in the previous work (TCAD, 45, pp. 3711--3724, 2026) with a simpler and widely adopted transformation rule. Since all rules in $\mathcal{RC}^{r}$ are commonly used in reversible logic synthesis, this result reveals that practically adopted transformation rules are already sufficient to establish a complete rewriting framework. Based on this result, we further propose an extended rule set, denoted by $\mathcal{RC}^+$, and prove its completeness for reversible circuits with ancillary bits and garbage outputs. To the best of our knowledge, this work presents the first complete transformation rule set for arbitrary reversible circuits, regardless of whether ancillary bits or garbage outputs are employed. The proposed framework establishes a theoretical foundation for circuit optimization, template generation, and equivalence checking, and may facilitate the development of automated design tools for reversible and quantum circuits.

DOI
10.48550/arxiv.2607.19059

Related papers

A Complete Set of Transformation Rules for Reversible Circuits

Shiguang Feng, Lvzhou Li

Reversible logic synthesis is a crucial component in quantum electronic design automation. While rule-based methodologies have gained prominence in reversible circuit optimization, the completeness of the transformation rule systems is a longstanding problem in this domain. In this work, we propose the first complete set of transformation rules for reversible circuits, comprising five fundamental rules: any two equivalent reversible circuits can be transformed into each other using the rules. To prove the completeness, a canonical circuit representation for reversible functions is introduced, and we show that every reversible function is computed by a unique reversible circuit in the canonical form, and any reversible circuit can be transformed into its canonical form by applying the rules.

arXiv:2508.17273•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Dec 8, 2025•1 citation

Reduction of the reversible circuits gate complexity without using the equivalent replacement tables for the gate compositions

Dmitri Zakablukov

The subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources. Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions. This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted). Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers. The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered. The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.

Science and Education of the Bauman MSTU•Mar 3, 2014•5 citations

Heuristic Synthesis of Reversible Logic – A Comparative Study

Chua Shin Cheng, Ashutosh Kumar Singh

Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.

Advances in Electrical and Electronic Engineering•Sep 30, 2014•12 citations

Heuristic Synthesis of Reversible Logic – A Comparative Study

Chua Shin Cheng, Ashutosh Kumar Singh

Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.

Advances in Electrical and Electronic Engineering•Sep 30, 2014•8 citations

A Quick Guide to Implement Reversible Logic

Shaveta Thakral, Dipali Bansal

Increasing miniaturization and demand of low power electronics is highly motivating research on reversible logic. Reversible logic has attracted signification attention in fields of Low power VLSI design, computer graphics, quantum computing and communication. A lot of work has been done on synthesis and optimization of reversible circuits followed by quantitative analysis on various optimization metrics like ancillary inputs, garbage outputs and quantum cost. It is therefore obvious to present a quick guide on reversible logic implementation to bridge gap between theory and implementation. Taxonomy diagrams of work done in reversible logic domain are also presented to give a quick review of all about reversible logic. Quantum realization of popular reversible Fredkin gates using RCViewer tool is also presented which will be stepping stone for a new researcher to synthesize and optimize any complex reversible logic based circuit.

International Conference on Computing, Communication and Automation•Dec 1, 2018•1 citation

Boolean Matching Reversible Circuits: Algorithm and Complexity

Tian-Fu Chen, Jie-Hong Roland Jiang

Boolean matching is an important problem in logic synthesis and verification. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.

arXiv:2404.12184•ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•4 citations
Transformation rules play a central role in reversible circuit optimization, template-based rewriting, and equivalence checking, and establishing their completeness is a fundamental problem in reversible logic synthesis. In this work, we investigate the completeness of transformation rules for reversible circuits both with and without ancillary bits and garbage outputs. For reversible circuits without ancillary bits and garbage outputs, we introduce a refined and complete transformation rule set RCr\mathcal{RC}^{r}RCr, obtained by replacing one rule in the rule set RC\mathcal{RC}RC proposed in the previous work (TCAD, 45, pp. 3711--3724, 2026) with a simpler and widely adopted transformation rule. Since all rules in RCr\mathcal{RC}^{r}RCr are commonly used in reversible logic synthesis, this result reveals that practically adopted transformation rules are already sufficient to establish a complete rewriting framework. Based on this result, we further propose an extended rule set, denoted by RC+\mathcal{RC}^+RC+, and prove its completeness for reversible circuits with ancillary bits and garbage outputs. To the best of our knowledge, this work presents the first complete transformation rule set for arbitrary reversible circuits, regardless of whether ancillary bits or garbage outputs are employed. The proposed framework establishes a theoretical foundation for circuit optimization, template generation, and equivalence checking, and may facilitate the development of automated design tools for reversible and quantum circuits.
Reversible logic synthesis is a crucial component in quantum electronic design automation. While rule-based methodologies have gained prominence in reversible circuit optimization, the completeness of the transformation rule systems is a longstanding problem in this domain. In this work, we propose the first complete set of transformation rules for reversible circuits, comprising five fundamental rules: any two equivalent reversible circuits can be transformed into each other using the rules. To prove the completeness, a canonical circuit representation for reversible functions is introduced, and we show that every reversible function is computed by a unique reversible circuit in the canonical form, and any reversible circuit can be transformed into its canonical form by applying the rules.
The subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources. Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions. This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted). Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers. The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered. The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.
Increasing miniaturization and demand of low power electronics is highly motivating research on reversible logic. Reversible logic has attracted signification attention in fields of Low power VLSI design, computer graphics, quantum computing and communication. A lot of work has been done on synthesis and optimization of reversible circuits followed by quantitative analysis on various optimization metrics like ancillary inputs, garbage outputs and quantum cost. It is therefore obvious to present a quick guide on reversible logic implementation to bridge gap between theory and implementation. Taxonomy diagrams of work done in reversible logic domain are also presented to give a quick review of all about reversible logic. Quantum realization of popular reversible Fredkin gates using RCViewer tool is also presented which will be stepping stone for a new researcher to synthesize and optimize any complex reversible logic based circuit.
Boolean matching is an important problem in logic synthesis and verification. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.