Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 15 of 15
Full-Text Articles in Engineering
Quantum Algorithm For Variant Maximum Satisfiability, Abdirahman Alasow, Peter Jin, Marek Perkowski
Quantum Algorithm For Variant Maximum Satisfiability, Abdirahman Alasow, Peter Jin, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
In this paper, we proposed a novel quantum algorithm for the maximum satisfiability problem. Satisfiability (SAT) is to find the set of assignment values of input variables for the given Boolean function that evaluates this function as TRUE or prove that such satisfying values do not exist. For a POS SAT problem, we proposed a novel quantum algorithm for the maximum satisfiability (MAX-SAT), which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with information on how far the given Boolean function is from the SAT satisfaction. We used Grover’s algorithm with a …
Novel Quantum Algorithms To Minimize Switching Functions Based On Graph Partitions, Peng Gao, Marek A. Perkowski, Yiwei Li, Xiaoyu Song
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
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 …
Machine-Learning Based Three-Qubit Gate For Realization Of A Toffoli Gate With Cqed-Based Transmon Systems, Sahar Daraeizadeh, Shavindra Premaratne, Xiaoyu Song, Marek A. Perkowski, Anne Y. Matsuura
Machine-Learning Based Three-Qubit Gate For Realization Of A Toffoli Gate With Cqed-Based Transmon Systems, Sahar Daraeizadeh, Shavindra Premaratne, Xiaoyu Song, Marek A. Perkowski, Anne Y. Matsuura
Electrical and Computer Engineering Faculty Publications and Presentations
We use machine learning techniques to design a 50 ns three-qubit flux-tunable controlled-controlled-phase gate with fidelity of >99.99% for nearest-neighbor coupled transmons in circuit quantum electrodynamics architectures. We explain our gate design procedure where we enforce realistic constraints, and analyze the new gate’s robustness under decoherence, distortion, and random noise. Our controlled-controlled phase gate in combination with two single-qubit gates realizes a Toffoli gate which is widely used in quantum circuits, logic synthesis, quantum error correction, and quantum games.
Decomposition Of Reversible Logic Function Based On Cube-Reordering, Martin Lukac, Michitaka Kameyama, Marek Perkowski, Pawel Kerntopf
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
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 …
An Emotional Mimicking Humanoid Biped Robot And Its Quantum Control Based On The Constraint Satisfaction Model, Quay Williams, Scott Bogner, Michael Kelley, Carolina Castillo, Martin Lukac, Dong Hwa Kim, Jeff S. Allen, Mathias I. Sunardi, Sazzad Hossain, Marek Perkowski
An Emotional Mimicking Humanoid Biped Robot And Its Quantum Control Based On The Constraint Satisfaction Model, Quay Williams, Scott Bogner, Michael Kelley, Carolina Castillo, Martin Lukac, Dong Hwa Kim, Jeff S. Allen, Mathias I. Sunardi, Sazzad Hossain, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
The paper presents a humanoid robot that responds to human gestures seen by a camera. The behavior of the robot can be completely deterministic as specified by a Finite State Machine that maps the sensor signals to the effector signals. This model is further extended to the constraints-satisfaction based model that links robots vision, motion, emotional behavior and planning. One way of implementing this model is to use adiabatic quantum computer which quadratically speeds-up every constraint problem and will be thus necessary to solve large problems of this type. We propose to use the remotely-connected Orion system by DWAVE Corporation.
Realization Of Incompletely Specified Functions In Minimized Reversible Cascades, Marek Perkowski, Manjith Kumar, Bala Iyer, Natalie Metzger, Ying Wang
Realization Of Incompletely Specified Functions In Minimized Reversible Cascades, Marek Perkowski, Manjith Kumar, Bala Iyer, Natalie Metzger, Ying Wang
Electrical and Computer Engineering Faculty Publications and Presentations
There is a need to convert non-reversible functions to their corresponding reversible functions to be realized as reversible cascades. The original MMD (D.M.Miller, D. Maslov, and G.W.Dueck) algorithm for synthesis of reversible functions using cascades of reversible gates [1] can be modified to allow for the inclusion of “don't cares” within the given function's truth table (reversible or irreversible). This was achieved in the approach presented, by first initializing the “don't cares” to binary values, synthesizing the network using the base MMD algorithm, comparing the cost, and iterating to find an implementation with the smallest possible cost. The “don't care” …
A Quantum Test Algorithm, Marek Perkowski, Jacob Biamonte
A Quantum Test Algorithm, Marek Perkowski, Jacob Biamonte
Electrical and Computer Engineering Faculty Publications and Presentations
Current processes validation methods rely on diverse input states and exponential applications of state tomography. Through generalization of classical test theory exceptions to this rule are found. Instead of expanding a complete operator basis to validate a process, the objective is to utilize quantum effects making each gate realized in the process act on a complete set of characteristic states and next extract functional information. Random noise, systematic errors, initialization inaccuracies and measurement faults must also be detected. This concept is applied to the switching class comprising the search oracle. In a first approach, the test set cardinality is held …
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
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 …
Synthesis Of Reversible Circuits From A Subset Of Muthukrishnan-Stroud Quantum Realizable Multi-Valued Gates, Marek Perkowski, Nicholas Denler, Bruce Yen, Pawel Kerntopf
Synthesis Of Reversible Circuits From A Subset Of Muthukrishnan-Stroud Quantum Realizable Multi-Valued Gates, Marek Perkowski, Nicholas Denler, Bruce Yen, Pawel Kerntopf
Electrical and Computer Engineering Faculty Publications and Presentations
We present a new type of quantum realizable reversible cascade. Next we present a new algorithm to synthesize arbitrary single-output ternary functions using these reversible cascades. The cascades use “Generalized Multi-Valued Gates” introduced here, which extend the concept of Generalized Ternary Gates introduced previously. While there were 216 GTGs, a total of 12 ternary gates of the new type are sufficient to realize arbitrary ternary functions. (The count can be further reduced to 5 gates, three 2-qubit and two 1-qubit). Such gates are realizable in quantum ion trap devices. For some functions, the algorithm requires fewer gates than results previously …
Cellular Automata Realization Of Regular Logic, Andrzej Buller, Marek Perkowski
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 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
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 …
Fast Heuristic Minimization Of Exclusive-Sums-Of-Products, Alan Mishchenko, Marek Perkowski
Fast Heuristic Minimization Of Exclusive-Sums-Of-Products, Alan Mishchenko, Marek Perkowski
Electrical and Computer Engineering Faculty Publications and Presentations
Exclusive-Sums-Of-Products (ESOPs) play an important role in logic synthesis and design-for-test. This paper presents an improved version of the heuristic ESOP minimization procedure proposed in [1,2]. The improvements concern three aspects of the procedure: (1) computation of the starting ESOP cover; (2) increase of the search space for solutions by applying a larger set of cube transformations; (3) development of specialized datastructures for robust manipulation of ESOP covers. Comparison of the new heuristic ESOP minimizer EXORCISM-4 with other minimizers (EXMIN2 [3], MINT [4], EXORCISM-2 [1] and EXORCISM3 [2]) show that, in most cases, EXORCISM-4 produces results of comparable or better …
Bi-Decomposition Of Multi-Valued Relations, Alan Mishchenko, Marek Perkowski, Bernd Steinbach
Bi-Decomposition Of Multi-Valued Relations, Alan Mishchenko, Marek Perkowski, Bernd Steinbach
Electrical and Computer Engineering Faculty Publications and Presentations
This presentation discusses an approach to decomposition of multivalued functions and relations into networks of two-input gates implementing multi-valued MIN and MAX operations. The algorithm exploits both the incompleteness of the initial specification and the flexibilities generated in the process of decomposition. Experimental results over a set of multi-valued benchmarks show that this approach outperforms other approaches in the quality of final results and CPU time.