We present the results of application of Evolutionary Algorithms to the problem of synthesizing quantum circuits which belong to the class of reversible circuits, represented as an input/output mapping vectors. The paper specifically focuses on large quantum circuits where many valid solutions exist in an exponentially inflating search space. Valid solutions represent the set of all input vector permutations (arrangements) which satisfy the circuit specification. The search space for circuits with large number of variables grows exponentially making it impossible to discover the set of optimal solutions. The paper compares three methods for selecting valid solutions of input vector sequences: 1) randomly, 2) genetic algorithm, 3) Tabu search. The objective function calculates the number of elementary quantum gates needed to represent the solution such that lower number of gates represents better solutions. In addition to the choice of selection algorithm, we illustrate the impact of using different partition depths for the Covered Set Partitions algorithm used to construct valid input vector sequences.
We present the results of application of Evolutionary Algorithms to the problem of synthesizing quantum circuits which belong to the class of reversible circuits, represented as an input/output mapping vectors. The paper specifically focuses on large quantum circuits where many valid solutions exist in an exponentially inflating search space. Valid solutions represent the set of all input vector permutations (arrangements) which satisfy the circuit specification. The search space for circuits with large number of variables grows exponentially making it impossible to discover the set of optimal solutions. The paper compares three methods for selecting valid solutions of input vector sequences: 1) randomly, 2) genetic algorithm, 3) Tabu search. The objective function calculates the number of elementary quantum gates needed to represent the solution such that lower number of gates represents better solutions. In addition to the choice of selection algorithm, we illustrate the impact of using different partition depths for the Covered Set Partitions algorithm used to construct valid input vector sequences.
Due to the non- intuitive nature of Quantum algorithms, it becomes difficult for a classically trained person to efficiently construct new ones. So rather than designing new algorithms manually, lately, Genetic algorithms (GA) are being implemented for this purpose. GA is a technique to automatically solve a problem using principles of Darwinian evolution. This has been implemented to explore the possibility of evolving an n-qubit circuit when the circuit matrix has been provided using a set of single, two and three qubit gates. Using a variable length population and universal stochastic selection procedure, a number of possible solution circuits, with different number of gates can be obtained for the same input matrix during different runs of GA. The given algorithm has also been successfully implemented to obtain two and three qubit Boolean circuits using Quantum gates. The results demonstrate the effectiveness of the GA procedure even when the search spaces are large.
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.
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.
Quantum algorithms will likely play a key role in future high-performance-computing (HPC) environments. These algorithms are typically expressed as quantum circuits composed of arbitrary gates or as unitary matrices. Executing these on physical devices, however, requires translation to device-compatible circuits, in a process called quantum compilation or circuit synthesis, since these devices support a limited number of native gates. Moreover, these devices typically have specific qubit topologies, which constrain how and where gates can be applied. Consequently, logical qubits in input circuits and unitaries may need to be mapped to and routed between physical qubits. Furthermore, current Noisy Intermediate-Scale Quantum (NISQ) devices present additional constraints. They are vulnerable to errors during gate application and their short decoherence times lead to qubits rapidly succumbing to accumulated noise and possibly corrupting computations. Therefore, circuits synthesized for NISQ devices need to minimize gates and execution times. The problem of synthesizing device-compatible circuits, while optimizing for low gate count and short execution times, can be shown to be computationally intractable using analytical methods. Therefore, interest has grown towards heuristics-based synthesis techniques, which are able to produce approximations of the desired algorithm, while optimizing depth and gate-count. In this work, we investigate using genetic algorithms (GA)—a proven gradient-free optimization technique based on natural selection—for circuit synthesis. In particular, we formulate the quantum synthesis problem as a multi-objective optimization (MOO) problem, with the objectives of minimizing the approximation error, number of multi-qubit gates, and circuit depth. We also employ fuzzy logic for runtime parameter adaptation of GA to enhance search efficiency and solution quality in our proposed method.
This paper demonstrates an application of an evolutionary approach for solving a class of non-trivial, hardware-design problems. Array processing features of the computer language APL simplify the implementation of an evolutionary solution in which simulation is performed by a genetic algorithm on a population of candidate solutions until one or more are satisfactory quantum algorithms. The objective of the simulation model is the automatic discovery of quantum computer algorithms. The algorithms are expressed in a circuit model that specifies the sequences in which quantum operators are to be applied. The automatically configured circuits operate as quantum computers that for the present have their domains of application limited to evaluation of only a few specific functions. The simulations use a small collection of basic and relatively low-level operators to obtain perfect results for five different target functions. These functions were chosen to demonstrate how, on a personal computer, an evolutionary method is able to discover novel designs of computing hardware. The results establish that it is feasible to use genetic algorithms in an evolutionary method to invent correct hardware designs. The progress of simulated evolution is directed by input/output constraints and a fitness function. Alternative configurations of circuit models can obtain algorithms with promise for future quantum computers. Current simulations yield primitive quantum algorithms with a total of twelve or fewer inputs and outputs. The discovered algorithms produce the correct results for evaluating the five selected logical and arithmetic functions.
This paper demonstrates an application of an evolutionary approach for solving a class of non-trivial, hardware-design problems. Array processing features of the computer language APL simplify the implementation of an evolutionary solution in which simulation is performed by a genetic algorithm on a population of candidate solutions until one or more are satisfactory quantum algorithms. The objective of the simulation model is the automatic discovery of quantum computer algorithms. The algorithms are expressed in a circuit model that specifies the sequences in which quantum operators are to be applied. The automatically configured circuits operate as quantum computers that for the present have their domains of application limited to evaluation of only a few specific functions. The simulations use a small collection of basic and relatively low-level operators to obtain perfect results for five different target functions. These functions were chosen to demonstrate how, on a personal computer, an evolutionary method is able to discover novel designs of computing hardware. The results establish that it is feasible to use genetic algorithms in an evolutionary method to invent correct hardware designs. The progress of simulated evolution is directed by input/output constraints and a fitness function. Alternative configurations of circuit models can obtain algorithms with promise for future quantum computers. Current simulations yield primitive quantum algorithms with a total of twelve or fewer inputs and outputs. The discovered algorithms produce the correct results for evaluating the five selected logical and arithmetic functions.