Electrical and Computer Engineering Commons^™

An Extended Approach For Generating Unitary Matrices For Quantum Circuits, Zhiqiang Li, Wei Zhang, Gaoman Zhang, Juan Dai, Jiajia Hu, Marek Perkowski, Xiaoyu Song

Electrical and Computer Engineering Faculty Publications and Presentations

In this paper, we do research on generating unitary matrices for quantum circuits automatically. We consider that quantum circuits are divided into six types, and the unitary operator expressions for each type are offered. Based on this, we propose an algorithm for computing the circuit unitary matrices in detail. Then, for quantum logic circuits composed of quantum logic gates, a faster method to compute unitary matrices of quantum circuits with truth table is introduced as a supplement. Finally, we apply the proposed algorithm to different reversible benchmark circuits based on NCT library (including NOT gate, Controlled-NOT gate, Toffoli gate) and …

Using Homing, Synchronizing And Distinguishing Input Sequences For The Analysis Of Reversible Finite State Machines, Martin Lukac, Michitaka Kameyama, Marek A. Perkowski, Pawel Kerntopf

Electrical and Computer Engineering Faculty Publications and Presentations

A digital device is called reversible if it realizes a reversible mapping, i.e., the one for which there exist a unique inverse. The field of reversible computing is devoted to studying all aspects of using and designing reversible devices. During last 15 years this field has been developing very intensively due to its applications in quantum computing, nanotechnology and reducing power consumption of digital devices. We present an analysis of the Reversible Finite State Machines (RFSM) with respect to three well known sequences used in the testability analysis of the classical Finite State Machines (FSM). The homing, distinguishing and synchronizing …

Synthesis Of Linear Reversible Circuits And Exor-And-Based Circuits For Incompletely Specified Multi-Output Functions, Ben Schaeffer

Dissertations and Theses

At this time the synthesis of reversible circuits for quantum computing is an active area of research. In the most restrictive quantum computing models there are no ancilla lines and the quantum cost, or latency, of performing a reversible form of the AND gate, or Toffoli gate, increases exponentially with the number of input variables. In contrast, the quantum cost of performing any combination of reversible EXOR gates, or CNOT gates, on n input variables requires at most O(n^₂/log₂n) gates. It was under these conditions that EXOR-AND-EXOR, or EPOE, synthesis was developed.

In this …

Minimization Of Quantum Circuits Using Quantum Operator Forms, Martin Lukac, Michitaka Kameyama, Marek Perkowski, Pawel Kerntopf

Electrical and Computer Engineering Faculty Publications and Presentations

In this paper we present a method for minimizing reversible quantum circuits using the Quantum Operator Form (QOF); a new representation of quantum circuit and of quantum-realized reversible circuits based on the CNOT, CV and CV† quantum gates. The proposed form is a quantum extension to the well known Reed-Muller but unlike the Reed-Muller form, the QOF allows the usage of different quantum gates. Therefore QOF permits minimization of quantum circuits by using properties of different gates than only the multi-control Toffoli gates. We introduce a set of minimization rules and a pseudo-algorithm that can be used to design circuits …

Reversible Circuits Synthesis Based On Exor-Sum Of Products Of Exor-Sums, Linh Hoang Tran

Dissertations and Theses

Power dissipation in modern technologies is an important matter and overheating is a severe concern for both manufacturer (impossibility of introducing new and smaller scale technologies and limited temperature range for operating the product) and customer (power supply, which is especially important for mobile systems). One of the main profits that reversible circuit carries is theoretically the zero power dissipation in the sense that it is independent of underlying technology; irreversibility means heat generation. In the other words, reversible circuits may offer a feasible solution in the future that will aid certain reduction of the power loss.

Reversible circuits are …

Methods For Efficient Synthesis Of Large Reversible Binary And Ternary Quantum Circuits And Applications Of Linear Nearest Neighbor Model, Maher Mofeid Hawash

Dissertations and Theses

This dissertation describes the development of automated synthesis algorithms that construct reversible quantum circuits for reversible functions with large number of variables. Specifically, the research area is focused on reversible, permutative and fully specified binary and ternary specifications and the applicability of the resulting circuit to the physical limitations of existing quantum technologies.

Automated synthesis of arbitrary reversible specifications is an NP hard, multiobjective optimization problem, where 1) the amount of time and computational resources required to synthesize the specification, 2) the number of primitive quantum gates in the resulting circuit (quantum cost), and 3) the number of ancillary qubits …

Decomposition Of Reversible Logic Function Based On Cube-Reordering, Martin Lukac, Michitaka Kameyama, Marek Perkowski, Pawel Kerntopf

Electrical and Computer Engineering Faculty Publications and Presentations

We present a novel approach to the synthesis of incompletely specified reversible logic functions. The method is based on cube grouping; the first step of the synthesis method analyzes the logic function and generates groupings of same cubes in such a manner that multiple sub-functions are realized by a single Toffoli gate. This process also reorders the function in such a manner that not only groups of similarly defined cubes are joined together but also don’t care cubes. The proposed method is verified on standard benchmarks for both reversible and irreversible logic functions. The obtained results show that for functions …

Evolutionary Quantum Logic Synthesis Of Boolean Reversible Logic Circuits Embedded In Ternary Quantum Space Using Heuristics, Martin Lukac, Marek Perkowski, Michitaka Kameyama

Electrical and Computer Engineering Faculty Publications and Presentations

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 …

Atpg For Reversible Circuits Using Technology-Related Fault Models, Jeff S. Allen, Jacob D. Biamonte, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

We address the problem of test set generation and test set reduction, to first detect, and later localize faults occurring in reversible circuits. Reversible Computation has high promise of low power consumption. Some new fault models are first presented here. An explanation of the new fault models is made based on a physical realization representing the state of the art in the reversible CMOS circuit technology. Evidence is then presented showing that the fault models presented in the current literature are not adequate for existing realizations of reversible logic such as CMOS. We designed a ATPG software package with a …

Deterministic And Probabilistic Test Generation For Binary And Ternary Quantum Circuits, Sowmya Aligala, Sreecharani Ratakonda, Kiran Narayan, Kanagalakshmi Nagarajan, Martin Lukac, Jacob D. Biamonte, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

It is believed that quantum computing will begin to have an impact around year 2010. Much work is done on physical realization and synthesis of quantum circuits, but nothing so far on the problem of generating tests and localization of faults for such circuits. Even fault models for quantum circuits have been not formulated yet. We propose an approach to test generation for a wide category of fault models of single and multiple faults. It uses deterministic and probabilistic tests to detect faults. A Fault Table is created that includes probabilistic information. If possible, deterministic tests are first selected, while …

Exact Synthesis Of 3-Qubit Quantum Circuits From Non-Binary Quantum Gates Using Multiple-Valued Logic And Group Theory, Guowu Yang, William N. N. Hung, Xiaoyu Song, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

We propose an approach to optimally synthesize quantum circuits from non-permutative quantum gates such as Controlled-Square-Root–of-Not (i.e. Controlled-V). Our approach reduces the synthesis problem to multiple-valued optimization and uses group theory. We devise a novel technique that transforms the quantum logic synthesis problem from a multi-valued constrained optimization problem to a permutable representation. The transformation enables us to utilize group theory to exploit the symmetric properties of the synthesis problem. Assuming a cost of one for each two-qubit gate, we found all reversible circuits with quantum costs of 4, 5, 6, etc, and give another algorithm to realize these reversible …

Cellular Automata Realization Of Regular Logic, Andrzej Buller, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

This paper presents a cellular-automatic model of a reversible regular structure called Davio lattice. Regular circuits are investigated because of the requirement of future (nano-) technologies where long wires should be avoided. Reversibility is a valuable feature because it means much lower energy dissipation. A circuit is reversible if the number of its inputs equals the number of its outputs and there is a one-to-one mapping between spaces of input vectors and output vectors. It is believed that one day regular reversible structures will be implemented as nanoscale 3-dimensional chips. This paper introduces the notion of the Toffoli gate and …

Automated Synthesis Of Generalized Reversible Cascades Using Genetic Algorithms, Martin Lukac, Mikhail Pivtoraiko, Alan Mishchenko, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

We propose an automated synthesis of Reversible logic (RL) circuits using Darwinian and Lamarckian Genetic Algorithms (GA). Our designs are in a form of cascades of generalized gates which generalize factorized Exclusive-Or-Sum-of-Products (ESOP) circuits. GA can be used to explore the problem space of combinational functions and here it is used to evolve reversible logic circuits. We emphasize the role of problem encoding - a well-designed encoding leads to improved results. Our method with well-encoded circuits is compared to standard method on classical benchmarks in GA, and shows good results for synthesis of both random functions and benchmark functions with …

A General Decomposition For Reversible Logic, Marek Perkowski, Lech Jozwiak, Pawel Kerntopf, Alan Mishchenko, Anas Al-Rabadi, Alan Coppola, Andrzej Buller, Xiaoyu Song, Svetlana Yanushkevich, Vlad P. Shmerko, Malgorzata Chrzanowska-Jeske, Mozammel Huq Azad Khan

Electrical and Computer Engineering Faculty Publications and Presentations

Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis tasks is to reduce the number of garbage signals. Previous approaches to reversible logic synthesis minimized either only the garbage or (predominantly) the number of gates. Here we present for the first time a method that minimizes concurrently the number of gates, their total delay and the total garbage. Our method adopts for reversible logic many ideas developed previously for standard logic synthesis (such as Ashenhurst/Curtis Decomposition, Dietmeyer’s Composition, non-linear preprocessing …