arXiv:1107.3383

Evolutionary Quantum Logic Synthesis of Boolean Reversible Logic Circuits Embedded in Ternary Quantum Space using Heuristics

Maartin Lukac, Marek A. Perkowski, Michitaka Kameyama

Published Jul 18, 2011• 7 citations

Abstract

It has been experimentally proven that realizing universal quantum gates using higher-radices logic is practically and technologically possible. We developed a Parallel Genetic Algorithm that synthesizes Boolean reversible circuits realized with a variety of quantum gates on qudits with various radices. In order to allow synthesizing circuits of medium sizes in the higher radix quantum space we performed the experiments using a GPU accelerated Genetic Algorithm. Using the accelerated GA we compare heuristic improvements to the mutation process based on cost minimization, on the adaptive cost of the primitives and improvements due to Baldwinian vs. Lamarckian GA. We also describe various fitness function formulations that allowed for various realizations of well known universal Boolean reversible or quantum-probabilistic circuits.

DOI: 10.48550/arxiv.1107.3383

Related papers

Evolutionary quantum logic synthesis of Boolean reversible logic circuits embedded in ternary quantum space using structural restrictions

Martin Lukáč, Marek A. Perkowski, Michitaka Kameyama

IEEE Congress on Evolutionary Computation (CEC)Jul 1, 201019 citations

Study of GPU Acceleration in Genetic Algorithms for Quantum Circuit Synthesis

Martin Lukáč, Georgiy Krylov

In this work we present a comparative study of several GPU accelerated elements of a Genetic Algorithm (GA) for the synthesis of quantum circuits on the level of Electro-Magnetic (EM) pulses. The novelty in our approach is in the implementation: a) a completely GPU accelerated quantum simulator, b) GPU accelerated genetic operators and fitness evaluation and finally c) a set of GPU implemented optimizations for GPU accelerated evolutionary search optimization for the synthesis of quantum circuits. The reason for using EM pulses model for synthesis is the observation that this model requires the largest amount of elementary rotations to implement quantumlogic gates and thus provides a good measure to evaluate the efficiency of the acceleration by the GPU processor. The reason to use a GA is the advantage of pseudo evolutionary search in very large problem space such as the one defined by the Ising model where the EM realized quantum circuits are evolved. As a result of the several GPU optimizations several new circuits implementations are presented and their cost is compared to thecurrently known Ising model implementations.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 20174 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 ScienceJan 1, 201531 citations

Genetic Algorithm based synthesis of ternary Reversible/Quantum circuit

Rashida Khanoma, Tahseen Kamalb, Mozammel H. A. Khan

Reversible/quantum circuits are believed to be one of the future computer technologies. In this paper, a genetic algorithm (GA) based synthesis of ternary reversible/quantum circuits using Muthukrishnan-Stroud gates is presented. The circuit generated by GA may contain redundant gates. We have used post GA reduction to eliminate these redundant gates. We have experimented with ternary half-adder circuit. The proposed GA converges for many combinations of crossover and mutation.

International Conference on Computer and Information Technology (ICCIT)Dec 1, 200812 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 ComputingMay 13, 20260 citations

EFFICIENT GENETIC BASED METHODS FOR OPTIMIZING THE REVERSIBLE AND QUANTUM LOGIC CIRCUITS

Mohammadi Majid

Various synthesis methods have been proposed in the literature for reversible and quantum logic circuits. However, there are few algorithms to optimize an existing circuit with multiple constraints simultaneously. In this paper, some heuristics in genetic algorithms (GA) to optimize a given circuit in terms of quantum cost, number of gates, location of garbage outputs, and delay, are proposed. The proposed methods can optimize an existing circuit with a given truth table, including don’t care values, for different aspects of optimality. The results show good enhancements in the optimization of benchmark circuits compared to the previously published methods.

Jan 1, 20124 citations