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

RADIOELECTRONIC AND COMPUTER SYSTEMS

Using artificial intelligence methods for the optimal synthesis of reversible networks

Taras Kyryliuk, Mykhailo Palahuta, V. G. Deĭbuk

Published Nov 21, 2024• 0 citations
Publisher

Abstract

Considering the relentless progress in the miniaturization of electronic devices and the need to reduce energy consumption, technical challenges in the synthesis of circuit design solutions have become evident. According to Moore's Law, the reduction of transistor sizes to the atomic scale faces physical limits, which complicate further development. Additionally, reducing transistor sizes causes current leakage, leading to increased thermal noise, which can disrupt the proper functioning of digital devices. A promising solution to these problems is the application of reversible logic in circuit design. Reversible logic allows for a reduction in energy and information losses because logical reversible operations are performed without loss. The research synthesized optimal reversible circuits based on reversible gates using evolutionary algorithms and compare them with existing analogues. The focus of this study is on logical circuits built using reversible gates, which can significantly reduce energy losses, which is critical for modern and future electronic devices. The synthesis of reversible circuits is closely related to quantum computing, where quantum gates also possess a reversible nature. This enables the use of synthesis methods to create quantum reversible logical computing devices, which in turn promotes the development of quantum technologies. The study focuses on the application of evolutionary artificial intelligence algorithms, specifically genetic algorithms and ant colony optimization algorithms, for the optimal synthesis of reversible circuits. As a result, a detailed description of the key concepts of the improved algorithms, simulation results, and comparison of the two methods is provided. The efficiency of the reversible device synthesis was evaluated using the proposed implementation of the genetic algorithm and the ant colony optimization algorithm. The obtained results were compared to existing analogs and verified using the Qiskit framework in the IBM quantum computing laboratory. The conclusions describe the developed algorithms, which demonstrate high efficiency in solving circuit topology optimization problems. A genetic algorithm was developed, featuring multi-component mutation and a matrix approach to chromosome encoding combined with Tabu search to avoid local optima. The ant colony optimization algorithms were improved, including several changes to the proposed data representation model, structure, and operational principles of the synthesis algorithm, enabling effective synthesis of devices on the NCT basis along with Fredkin gates. An improved structure for storing and using pheromones was developed to enable multi-criteria navigation in the solution space.

DOI
10.32620/reks.2024.4.10

Related papers

Quantum-Inspired Tabu Search Algorithm for reversible logic circuit synthesis

Wen-Hsin Wang, Chia-Hui Chiu, Shu–Yu Kuo +2 more

Reversible logic plays an important role in quantum computation, which is a promising research field. The reversible logic synthesis problem focuses on generating a reversible circuit automatically and finding the lowest cost when an output function is given. The synthesis of reversible logic circuits can be formulated as a combinatorial optimization problem. This paper proposes a new evolutionary algorithm for synthesizing reversible circuits based on Quantum-Inspired Tabu Search Algorithm (QTS). The proposed algorithm uses the QTS-based approach to find fewer gates and reduce the cost of reversible circuits. This method is simpler, has better performance in computational cost, and reduce the gate counts of reversible circuits. This paper also compares experimental results with other heuristic and evolutionary algorithms. The final outcome shows that the QTS-based approach performs much better than other algorithms.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2012•24 citations

Reversible Logic Circuit Synthesis and Optimization Using Adaptive Genetic Algorithm

Trailokya Nath Sasamal, Ashutosh Kumar Singh, Anand Mohan

In the recent years reversible logic circuits have gained a remarkable interest in the light of advancements made in quantum computation. The promise of theoretically zero power consumption is a major driving force for researchers to develop circuits using this logic. Synthesis of reversible logic and generating reversible logic circuit automatically with lower cost always has been a challenging task as reducing the search space is one of the major issues in the synthesis process using permutation. In this work, we proposed an Adaptive Genetic Algorithm (AGA) for synthesizing reversible logic circuits. NCT (NOT, CNOT, Toffoli) gate based library has been considered for synthesis of reversible logic circuits (RLC). The proposed algorithm produces a cascade of Toffoli gates for a given reversible specification of a circuit. Comparison of experimental results for several benchmark circuits shows that proposed evolutionary algorithm enables optimal or near-optimal solutions with lesser Gate Counts.

Procedia Computer Science•Jan 1, 2015•33 citations

Improved ant colony optimization for quantum cost reduction

Shaveta Thakral, Dipali Bansal

Heuristic algorithms play a significant role in synthesize and optimization of digital circuits based on reversible logic yet suffer with multiple disadvantages for multiqubit functions like scalability, run time and memory space. Synthesis of reversible logic circuit ends up with trade off between number of gates, quantum cost, ancillary inputs and garbage outputs. Research on optimization of quantum cost seems intractable. Therefore post synthesis optimization needs to be done for reduction of quantum cost. Many researchers have proposed exact synthesis approaches in reversible logic but focussed on reduction of number of gates yet quantum cost remains undefined. The main goal of this paper is to propose improved Ant Colony Optimization (ACO) algorithm for quantum cost reduction. The research efforts reported in this paper represent a significant contribution towards synthesis and optimization of high complexity reversible function via swarm intelligence based approach. The improved ACO algorithm provides low quantum cost based toffoli synthesis of reversible logic function without long computation overhead.

Bulletin of Electrical Engineering and Informatics•Aug 1, 2020•4 citations

Reversible Logic Synthesis Using Binary Decision Diagrams With Exploiting Efficient Reordering Operators

Baker K. Abdalhaq, Ahmed Awad, Amjad Hawash

With the continuous shrinkage of transistor sizes in very large scale integrated circuits, power consumption forms a serious concern to be tackled. With their ability to allow for zero energy dissipation, reversible circuits have been considered as promising solution to meetup with low power design requirements. Moreover, advances in their synthesis methodologies can be easily applied to quantum circuits due to the inherited reversibility of the latter. Although numerous algorithms have been proposed in the literature to synthesize reversible circuits and map them into their corresponding quantum circuits, the scalability and computational effort of such algorithms form a serious concern when synthesizing large size input functions. Binary Decision Diagram-based synthesis for reversible circuits has shown great evidence in realizing reversible circuits with low quantum cost through exploiting proper reduction rules for smaller graph size. However, the order of the variables in the decision diagram impacts its overall size, and thus, the cost of its corresponding reversible circuit. While several reordering algorithms have been proposed in this manner, their direct impact on the quantum cost has not been considered. In this article, a Binary Decision Diagram-based algorithm for reversible circuit synthesis is proposed to synthesize reversible circuits for a given Boolean function with low quantum cost through exploiting a linearized relationship between the decision diagram size and the corresponding quantum cost. Thereafter, different decision diagram reordering algorithms have been integrated with the proposed algorithm and compared in terms of their impact on the quantum cost. Experimental results show that Genetic Algorithm-based reordering for decision diagram, supported with, cycle crossover, inverse mutation, and tournament selection, results in the least quantum cost of the output circuit if compared with other algorithms due to its property in preserving the nodes of the decision diagram in their near-optimal locations during the optimiation recipe.

IEEE Access•Jan 1, 2020•7 citations

Genetic Synthesis of Compact Quaternary Reversible Comparators for Quantum Computing

Asma Taheri Monfared, Andrea Bombarda, Angelo Gargantini +1 more

Reversible logic is fundamental to quantum circuit design, as quantum operations are inherently information-preserving and reversible. While most quantum synthesis methods rely on binary logic, quaternary reversible computing can increase data density, reduce circuit width, and potentially lead to more efficient realizations. We introduce a genetic-algorithm-based approach for designing compact quaternary reversible comparator circuits, which are important components in quantum architectures. This technique utilizes a gate library based on extended Shift and Muthukrishnan–Stroud gates tailored to quaternary systems. Chromosomes encode sequences of quaternary gates, and evolutionary operators search for configurations with minimal quantum cost. Although demonstrated on comparator circuits, the approach applies to any quaternary reversible circuit defined by its truth table. The synthesis process occurs in two phases: candidate circuits first evolve toward correct behavior; then correct circuits are optimized to obtain compact implementations. We evaluate the approach on comparators performing lower-than, greater-than, and equality operations, as well as on a 1-qudit full comparator. The method achieves average quantum cost improvements of about 30% for restoring and 58% for non-restoring configurations compared to existing designs. These reductions support more efficient and more error-resilient quantum circuits, showing that this approach is a strong candidate for quaternary quantum systems.

ACM Transactions on Quantum Computing•May 13, 2026•0 citations

Evolutionary Design Technology of Quantum Reversible Logic Circuit Based on Matrix Coding

Zhang Zhai

The synthesis method of quantum reversible logic circuits based on the genetic algorithm was studied.The multi-objective optimal design of reversible logic circuit's function,the number of quantum gates,the number of garbage bits and quantum cost was achieved by new synthesis method.The mathematical model for quantum reversible logic circuit synthesis was established,the matrix encoding method of quantum reversible logic circuits was proposed,the evolution operations and the multi-objective evolutionary algorithm for quantum reversible logic circuit design were developed.The 8 bits reversible multiplier was designed as an example,the experimental results show that the proposed multi-objective evolutionary design method for quantum reversible logic circuit synthesis is correct and effective.

Dianzi xuebao•Jan 1, 2011•0 citations
Considering the relentless progress in the miniaturization of electronic devices and the need to reduce energy consumption, technical challenges in the synthesis of circuit design solutions have become evident. According to Moore's Law, the reduction of transistor sizes to the atomic scale faces physical limits, which complicate further development. Additionally, reducing transistor sizes causes current leakage, leading to increased thermal noise, which can disrupt the proper functioning of digital devices. A promising solution to these problems is the application of reversible logic in circuit design. Reversible logic allows for a reduction in energy and information losses because logical reversible operations are performed without loss. The research synthesized optimal reversible circuits based on reversible gates using evolutionary algorithms and compare them with existing analogues. The focus of this study is on logical circuits built using reversible gates, which can significantly reduce energy losses, which is critical for modern and future electronic devices. The synthesis of reversible circuits is closely related to quantum computing, where quantum gates also possess a reversible nature. This enables the use of synthesis methods to create quantum reversible logical computing devices, which in turn promotes the development of quantum technologies. The study focuses on the application of evolutionary artificial intelligence algorithms, specifically genetic algorithms and ant colony optimization algorithms, for the optimal synthesis of reversible circuits. As a result, a detailed description of the key concepts of the improved algorithms, simulation results, and comparison of the two methods is provided. The efficiency of the reversible device synthesis was evaluated using the proposed implementation of the genetic algorithm and the ant colony optimization algorithm. The obtained results were compared to existing analogs and verified using the Qiskit framework in the IBM quantum computing laboratory. The conclusions describe the developed algorithms, which demonstrate high efficiency in solving circuit topology optimization problems. A genetic algorithm was developed, featuring multi-component mutation and a matrix approach to chromosome encoding combined with Tabu search to avoid local optima. The ant colony optimization algorithms were improved, including several changes to the proposed data representation model, structure, and operational principles of the synthesis algorithm, enabling effective synthesis of devices on the NCT basis along with Fredkin gates. An improved structure for storing and using pheromones was developed to enable multi-criteria navigation in the solution space.
Reversible logic plays an important role in quantum computation, which is a promising research field. The reversible logic synthesis problem focuses on generating a reversible circuit automatically and finding the lowest cost when an output function is given. The synthesis of reversible logic circuits can be formulated as a combinatorial optimization problem. This paper proposes a new evolutionary algorithm for synthesizing reversible circuits based on Quantum-Inspired Tabu Search Algorithm (QTS). The proposed algorithm uses the QTS-based approach to find fewer gates and reduce the cost of reversible circuits. This method is simpler, has better performance in computational cost, and reduce the gate counts of reversible circuits. This paper also compares experimental results with other heuristic and evolutionary algorithms. The final outcome shows that the QTS-based approach performs much better than other algorithms.
In the recent years reversible logic circuits have gained a remarkable interest in the light of advancements made in quantum computation. The promise of theoretically zero power consumption is a major driving force for researchers to develop circuits using this logic. Synthesis of reversible logic and generating reversible logic circuit automatically with lower cost always has been a challenging task as reducing the search space is one of the major issues in the synthesis process using permutation. In this work, we proposed an Adaptive Genetic Algorithm (AGA) for synthesizing reversible logic circuits. NCT (NOT, CNOT, Toffoli) gate based library has been considered for synthesis of reversible logic circuits (RLC). The proposed algorithm produces a cascade of Toffoli gates for a given reversible specification of a circuit. Comparison of experimental results for several benchmark circuits shows that proposed evolutionary algorithm enables optimal or near-optimal solutions with lesser Gate Counts.
Heuristic algorithms play a significant role in synthesize and optimization of digital circuits based on reversible logic yet suffer with multiple disadvantages for multiqubit functions like scalability, run time and memory space. Synthesis of reversible logic circuit ends up with trade off between number of gates, quantum cost, ancillary inputs and garbage outputs. Research on optimization of quantum cost seems intractable. Therefore post synthesis optimization needs to be done for reduction of quantum cost. Many researchers have proposed exact synthesis approaches in reversible logic but focussed on reduction of number of gates yet quantum cost remains undefined. The main goal of this paper is to propose improved Ant Colony Optimization (ACO) algorithm for quantum cost reduction. The research efforts reported in this paper represent a significant contribution towards synthesis and optimization of high complexity reversible function via swarm intelligence based approach. The improved ACO algorithm provides low quantum cost based toffoli synthesis of reversible logic function without long computation overhead.
With the continuous shrinkage of transistor sizes in very large scale integrated circuits, power consumption forms a serious concern to be tackled. With their ability to allow for zero energy dissipation, reversible circuits have been considered as promising solution to meetup with low power design requirements. Moreover, advances in their synthesis methodologies can be easily applied to quantum circuits due to the inherited reversibility of the latter. Although numerous algorithms have been proposed in the literature to synthesize reversible circuits and map them into their corresponding quantum circuits, the scalability and computational effort of such algorithms form a serious concern when synthesizing large size input functions. Binary Decision Diagram-based synthesis for reversible circuits has shown great evidence in realizing reversible circuits with low quantum cost through exploiting proper reduction rules for smaller graph size. However, the order of the variables in the decision diagram impacts its overall size, and thus, the cost of its corresponding reversible circuit. While several reordering algorithms have been proposed in this manner, their direct impact on the quantum cost has not been considered. In this article, a Binary Decision Diagram-based algorithm for reversible circuit synthesis is proposed to synthesize reversible circuits for a given Boolean function with low quantum cost through exploiting a linearized relationship between the decision diagram size and the corresponding quantum cost. Thereafter, different decision diagram reordering algorithms have been integrated with the proposed algorithm and compared in terms of their impact on the quantum cost. Experimental results show that Genetic Algorithm-based reordering for decision diagram, supported with, cycle crossover, inverse mutation, and tournament selection, results in the least quantum cost of the output circuit if compared with other algorithms due to its property in preserving the nodes of the decision diagram in their near-optimal locations during the optimiation recipe.
Reversible logic is fundamental to quantum circuit design, as quantum operations are inherently information-preserving and reversible. While most quantum synthesis methods rely on binary logic, quaternary reversible computing can increase data density, reduce circuit width, and potentially lead to more efficient realizations. We introduce a genetic-algorithm-based approach for designing compact quaternary reversible comparator circuits, which are important components in quantum architectures. This technique utilizes a gate library based on extended Shift and Muthukrishnan–Stroud gates tailored to quaternary systems. Chromosomes encode sequences of quaternary gates, and evolutionary operators search for configurations with minimal quantum cost. Although demonstrated on comparator circuits, the approach applies to any quaternary reversible circuit defined by its truth table. The synthesis process occurs in two phases: candidate circuits first evolve toward correct behavior; then correct circuits are optimized to obtain compact implementations. We evaluate the approach on comparators performing lower-than, greater-than, and equality operations, as well as on a 1-qudit full comparator. The method achieves average quantum cost improvements of about 30% for restoring and 58% for non-restoring configurations compared to existing designs. These reductions support more efficient and more error-resilient quantum circuits, showing that this approach is a strong candidate for quaternary quantum systems.
The synthesis method of quantum reversible logic circuits based on the genetic algorithm was studied.The multi-objective optimal design of reversible logic circuit's function,the number of quantum gates,the number of garbage bits and quantum cost was achieved by new synthesis method.The mathematical model for quantum reversible logic circuit synthesis was established,the matrix encoding method of quantum reversible logic circuits was proposed,the evolution operations and the multi-objective evolutionary algorithm for quantum reversible logic circuit design were developed.The 8 bits reversible multiplier was designed as an example,the experimental results show that the proposed multi-objective evolutionary design method for quantum reversible logic circuit synthesis is correct and effective.