Engineering Commons^™

Novel Quantum Algorithms To Minimize Switching Functions Based On Graph Partitions, Peng Gao, Marek A. Perkowski, Yiwei Li, Xiaoyu Song

Electrical and Computer Engineering Faculty Publications and Presentations

After Google reported its realization of quantum supremacy, Solving the classical problems with quantum computing is becoming a valuable research topic. Switching function minimization is an important problem in Electronic Design Automation (EDA) and logic synthesis, most of the solutions are based on heuristic algorithms with a classical computer, it is a good practice to solve this problem with a quantum processer. In this paper, we introduce a new hybrid classic quantum algorithm using Grover’s algorithm and symmetric functions to minimize small Disjoint Sum of Product (DSOP) and Sum of Product (SOP) for Boolean switching functions. Our method is based …

Effectiveness Assessment Of The Search-Based Statistical Structural Testing, Yang Shi, Xiaoyu Song, Marek A. Perkowski, Fu Li

Electrical and Computer Engineering Faculty Publications and Presentations

Search-based statistical structural testing (SBSST) is a promising technique that uses automated search to construct input distributions for statistical structural testing. It has been proved that a simple search algorithm, for example, the hill-climber is able to optimize an input distribution. However, due to the noisy fitness estimation of the minimum triggering probability among all cover elements (Tri-Low-Bound), the existing approach does not show a satisfactory efficiency. Constructing input distributions to satisfy the Tri-Low-Bound criterion requires an extensive computation time. Tri-Low-Bound is considered a strong criterion, and it is demonstrated to sustain a high fault-detecting ability. This article tries to …

A Polarity-Based Approach For Optimization Of Multivalued Quantum Multiplexers With Arbitrary Single-Qubit Target Gates, Kevin Jin, Tahsin Soffat, Justin Morgan, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexers, but the multiplexer circuits created in this way may be highly non-minimal. This paper presents a new approach for optimizing quantum multiplexers with arbitrary single-qubit quantum target functions and ternary controls. For multivalued quantum multiplexers, we define standard forms and two types of new forms: Fixed Polarity Quantum Forms (FPQFs) and Kronecker Quantum Forms (KQFs). Drawing inspiration from the usage of butterfly diagrams, we devise a method to exhaustively construct new forms. In contrast to previous butterfly-based methods, which are used with classical Boolean functions, these …

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 …

A Quantum Algorithm For Automata Encoding, Edison Tsai, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the process of assigning to every state, input value, and output value of a state machine a binary string, which is used to represent that state, input value, or output value in digital logic. Usually, one wishes to choose an encoding that, when the state machine is implemented as a digital logic circuit, will optimize some aspect of that circuit. For instance, one might wish to encode in such a way as to minimize power dissipation or silicon area. For …

Cost Minimization Approach To Synthesis Of Linear Reversible Circuits, Ben Schaeffer, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

This paper presents a heuristic cost minimization approach to synthesizing linear reversible circuits. Two bidirectional linear reversible circuit synthesis methods are introduced, the Alternating Elimination with Cost Minimization method (AECM) and the Multiple CNOT Gate method (MCG). Algorithms, example syntheses, and extensions to these methods are presented. An MCG variant which incorporates line reordering is introduced. Tests comparing the new cost minimization methods with the best known method for large circuits are presented. Results show that of the three methods MCG had the lowest average CNOT gate counts for linear reversible circuits up to 24 lines, and that AECM had …

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 …

Synthesis Of Reversible Synchronous Counters, Marek Perkowski, Mozammel H.A. Khan

Electrical and Computer Engineering Faculty Publications and Presentations

In this paper, we concentrate on design of synchronous counters directly from reversible gates.

Improved Complexity Of Quantum Oracles For Ternary Grover Algorithm For Graph Coloring, Marek Perkowski, Yushi Wang

Electrical and Computer Engineering Faculty Publications and Presentations

The Graph Coloring Grover Algorithm has several applications in logic synthesis, scheduling, allocation, planning, robot motion, robot communication, resource allocation, conflict resolution, floor-planning, and many others.

It can serve as a “generic CSP solver” similar to a general SAT solver.

Quantum Phase Estimation Using Multivalued Logic, Marek Perkowski, Vamsi Parasa

Electrical and Computer Engineering Faculty Publications and Presentations

We generalize the Quantum Phase Estimation algorithm to MVL logic. We show the quantum circuits for QPE using qudits. We derive the performance requirements of the QPE to achieve high probability of success. We show how this leads to logarithmic decrease in the number of qudits and exponential decrease in error probability of the QPE algorithm as the value of the radix d increases.

Synthesis Of Quantum Circuits In Linear Nearest Neighbor Model Using Positive Davio Lattices, Marek Perkowski, Martin Lukac, Dipal Shah, Michitaka Kameyama

Electrical and Computer Engineering Faculty Publications and Presentations

We present a logic synthesis method based on lattices that realize quantum arrays in One-Dimensional Ion Trap technology. This means that all gates are built from 2x2 quantum primitives that are located only on neighbor qubits in a onedimensional space (called also vector of qubits or Linear Nearest Neighbor (LNN) architecture). The Logic circuits designed by the proposed method are realized only with 3*3 Toffoli, Feynman and NOT quantum gates and the usage of the commonly used multi-input Toffoli gates is avoided. This realization method of quantum circuits is different from most of reversible circuits synthesis methods from the literature …

Synthesis Of Reversible Circuits For Large Reversible Functions, Marek Perkowski, Nouraddin Alhagi, Maher Hawash

Electrical and Computer Engineering Faculty Publications and Presentations

This paper presents a new algorithmMP (multiple pass) to synthesize large reversible binary circuits without ancilla bits. The well-known MMD algorithm for synthesis of reversible circuits requires to store a truth table (or a Reed-Muller - RM transform) as a 2n vector to represent a reversible function of n variables. This representation prohibits synthesis of large functions. However, in MP we do not store such an exponentially growing data structure. The values of minterms are calculated in MP dynamically, one-by-one, from a set of logic equations that specify the reversible circuit to be designed. This allows for synthesis of large …

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 …

Fault Testing Quantum Switching Circuits, Marek Perkowski, Jacob Biamonte

Electrical and Computer Engineering Faculty Publications and Presentations

Test pattern generation is an electronic design automation tool that attempts to find an input (or test) sequence that, when applied to a digital circuit, enables one to distinguish between the correct circuit behavior and the faulty behavior caused by particular faults. The effectiveness of this classical method is measured by the fault coverage achieved for the fault model and the number of generated vectors, which should be directly proportional to test application time. This work address the quantum process validation problem by considering the quantum mechanical adaptation of test pattern generation methods used to test classical circuits. We found …

Inductive Learning Of Quantum Behaviors, Marek Perkowski, Martin Lukac

Electrical and Computer Engineering Faculty Publications and Presentations

In this paper studied are new concepts of robotic behaviors - deterministic and quantum probabilistic. In contrast to classical circuits, the quantum circuit can realize both of these behaviors. When applied to a robot, a quantum circuit controller realizes what we call quantum robot behaviors. We use automated methods to synthesize quantum behaviors (circuits) from the examples (examples are cares of the quantum truth table). The don’t knows (minterms not given as examples) are then converted not only to deterministic cares as in the classical learning, but also to output values generated with various probabilities. The Occam Razor principle, fundamental …

Search For Universal Ternary Quantum Gate Sets With Exact Minimum Costs, Marek Perkowski, Normen Giesecke, Dong Hwa Kim, Sazzad Hossain

Electrical and Computer Engineering Faculty Publications and Presentations

The choice of the best set of universal ternary gates for quantum circuits is an open problem. We create exact minimum cost ternary reversible gates with quantum multiplexers using the method of iterative deepening depth-first search (IDDFS) [25]. Such search is better for small problems than evolutionary algorithms or other search methods. Several new gates that are provably exact minimum cost have been discovered. These gates are next used as library building blocks in the minimization of larger ternary quantum circuits like highly testable GFSOP cascades [15,16] (that generalize ESOP) as well as the wave cascades [24] generalized to ternary …

Testing A Quantum Computer, Marek Perkowski, Jacob D. Biamonte

Electrical and Computer Engineering Faculty Publications and Presentations

We address the problem of quantum test set generation using measurement from a single basis and the single fault model. Experimental physicists currently test quantum circuits exhaustively, meaning that each n-bit permutative circuit requires ζ x 2n tests to assure functionality, and for an m stage permutative circuit proven not to function properly the current method requires ζ x 2n x m tests as the upper bound for fault localization, where zeta varies with physical implementation. Indeed, the exhaustive methods complexity grows exponentially with the number of qubits, proportionally to the number of stages in a quantum circuit and directly …

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 …

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 …

A Hierarchical Approach To Computer-Aided Design Of Quantum Circuits, Marek Perkowski, Martin Lukac, Pawel Kerntopf, Mikhail Pivtoraiko, Michele Folgheraiter, Yong Woo Choi, Jung-Wook Kim, Dongsoo Lee, Woong Hwangbo, Hyungock Kim

Electrical and Computer Engineering Faculty Publications and Presentations

A new approach to synthesis of permutation class of quantum logic circuits has been proposed in this paper. This approach produces better results than the previous approaches based on classical reversible logic and can be easier tuned to any particular quantum technology such as nuclear magnetic resonance (NMR). First we synthesize a library of permutation (pseudobinary) gates using a Computer-Aided-Design approach that links evolutionary and combinatorics approaches with human experience and creativity. Next the circuit is designed using these gates and standard 1*1 and 2*2 quantum gates and finally the optimizing tautological transforms are applied to the circuit, producing a …

Evolving Quantum Circuits And An Fpga-Based Quantum Computing Emulator, Goran Negovetic, Marek Perkowski, Martin Lukac, Andrzej Buller

Electrical and Computer Engineering Faculty Publications and Presentations

The goal of the PQLG group is to develop complete methodologies, software tools and circuits for quantum logic. Our interests are mainly in logic synthesis for quantum circuits and quantum system design [10]. Emulation of quantum circuits using standard reconfigurable FPGA technology and FPGA-based Evolvable Quantum Hardware, proposed here, are research areas not yet dealt with by other research groups. A parallel software simulator was presented in [13].

Generalized Inclusive Forms — New Canonical Reed-Muller Forms Including Minimum Esops, Marek Perkowski, Alan Mishchenko, Malgorzata Chzanowka-Jeske

Electrical and Computer Engineering Faculty Publications and Presentations

Reed-Muller (AND/EXOR) expansions play an important role in logic synthesis and circuit design by producing economical and highly-testable implementations of Boolean functions [3–6]. The range of Reed-Muller expansions include canonical forms, i.e. expansions that create unique representations of a Boolean function. Several large families of canonical forms: fixed polarity Reed-Muller forms (FPRMs), generalized Reed-Muller forms (GRMs), Kronecker forms (KROs), and pseudo- Kronecker forms (PKROs), referred to as the Green/Sasao hierarchy, have been described [7–9]. (See Fig. 1 for a settheoretic relationship between these families.)

Term Trees In Application To An Effective And Efficient Atpg For And–Exor And And–Or Circuits, Lech Jozwiak, Aleksander Ślusarczyk, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

A compact data representation, in which the typically required operations are performed rapidly, and effective and efficient algorithms that work on these representations are the essential elements of a successful CAD tool. The objective of this paper is to present a new data representation—term trees (TTs)—and to discuss its application for an effective and efficient structural automatic test-pattern generation (ATPG). Term trees are decision diagrams similar to BDDs that are particularly suitable for structure representation of AND–OR and AND–EXOR circuits. In the paper, a flexible algorithm for minimum term-tree construction is discussed and an effective and efficient algorithm for ATPG …

Multiple-Valued Quantum Logic Synthesis, Marek Perkowski, Anas Al-Rabadi, Pawel Kerttopf

Electrical and Computer Engineering Faculty Publications and Presentations

This paper asks the question: is logic synthesis for quantum computers a practical research subject?

We would like to assume that any two quantum wires can interact, but we are limited by the realization constraints. Structure of atomic bonds in the molecule determines neighborhoods in the circuit. This is similar to restricted routing in FPGA layout - link between logic and layout synthesis known from CMOS design now appears in quantum. Below we are interested only in the so-called “permutation circuits” - their unitary quantum matrices are permutation matrices.

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 …

Logic Synthesis For A Regular Layout, Marek Perkowski, Yang Xu, Malgorzata Chrzanowska-Jeske

Electrical and Computer Engineering Faculty Publications and Presentations

New algorithms for generating a regular two-dimensional layout representation for multi-output, incompletely specified Boolean functions, called, Pseudo-Symmetric Binary Decision Diagrams (PSBDDs), are presented. The regular structure of the function representation allows accurate prediction of post-layout areas and delays before the layout is physically generated. It simplifies power estimation on the gate level and allows for more accurate power optimization. The theoretical background of the new diagrams, which are based on ideas from contact networks, and the form of decision diagrams for symmetric functions is discussed. PSBDDs are especially well suited for deep sub-micron technologies where the delay of interconnections limits …

An Efficient And Effective Approach To Column-Based Input/Output Encoding In Functional Decomposition, Michael Burns, Marek Perkowski, Stanislaw Grygiel, Lech Jozwiak

Electrical and Computer Engineering Faculty Publications and Presentations

Encoding in Curtis-style decompositions is the process of assigning codes to groups of compatible columns (or cubes) so that the binary logic descriptions of the predecessor and successor sub-functions can be created for further decomposition. In doing so, the sub-functions created are functionally equivalent to the set of care values specified in the original function. In this paper an input/output encoding algorithm DC_ENC is presented that is designed to achieve the simplest total complexity of the predecessor and successor sub-functions, and to increase the total number of don't cares for their further utilization in subsequent decomposition steps of these sub-functions.

Exact Graph Coloring For Functional Decomposition: Do We Need It?, Marek Perkowski, Rahul Malvi, Lech Jozwiak

Electrical and Computer Engineering Faculty Publications and Presentations

Finding column multiplicity index is one of important component processes in functional decomposition of discrete functions for circuit design and especially Data Mining applications. How important it is to solve this problem exactly from the point of view of the minimum complexity of decomposition, and related to it error in Machine Learning type of applications? In order to investigate this problem we wrote two graph coloring programs: exact program EXOC and approximate program DOM (DOM cab give provably exact results on some types of graphs). These programs were next incorporated into the multi-valued decomposer of functions and relations NVGUD. Extensive …

Multi-Level Programmable Arrays For Sub-Micron Technology Based On Symmetries, Marek Perkowski, Malgorzata Chrzanowska-Jeske, Yang Xu

Electrical and Computer Engineering Faculty Publications and Presentations

Regular layout is a fundamental concept in VLSI design which can have application in custom design for submicron technologies, designing new architectures for fine-grain Field Programmable Gate Arrays (FPGAs) and Electrically Programmable logic Devices (EPLDs), and minimization of logic functions for existing FPGAs. PLAs are well known examples of regular layouts. Lattice diagrams are another type of regular layouts that have been recently introduced for layout-driven logic synthesis. In this paper we extend and combine theses two ideas, by introducing the multi-level PLA-like structures, composed from multi-output (pseudo) symmetrical lattice planes and other planes (multi-input, multi-output regular blocks). The main …

Programmable Analog Array Circuit, Marek Perkowski, Edmund Pierzchala

Electrical and Computer Engineering Faculty Publications and Presentations

There is disclosed a programmable analog or mixed analog/ digital circuit. More particularly, this invention provides a circuit architecture that is ?exible for a programmable electronic hardWare device or for an analog circuit Whose input and output signals are analog or multi-valued in nature, and primarily continuous in time. There is further disclosed a design for a current-mode integrator and sample-and-hold circuit, based upon Miller effect.