From Quantum Gates to Quantum Learning: recent
research and open problems in quantum circuits
Marek A. Perkowski,
Portland Quantum Logic Group,
Department of Electrical Engineering and Computer Science,
Korea Advanced Institute of Science and Technology, and
Department of Electrical and Computer Engineering, Portland State University,
USA.
Abstract
The paper is an overview of basic quantum circuits for researchers specializing in logic design.
After brief intuitive review of quantum circuits, we discuss the issues in synthesis and test problems,
pointing to the similarities with classical digital circuits. Finally, Quantum Computational Intelligence
is mentioned as a new area that uses quantum ideas in the framework of Computational Intelligence,
especially machine learning. The goal of the paper is to demonstrate that with very limited introduction
to quantum fundamentals, the logic design specialists can use their knowledge and skills to become
productive researchers in the new quantumrelated area of computer engineering that we propose to call
Quantum Design Automation (QDA).
";
if (eregi("Netscape",$browser))
$s=1;
?>
A Simple Model for Estimating Quantum Communication Channels
Tomoyuki ARAKI
Department of Electronics and Phtonic Systems Engineering,
Hiroshima Institute of Technology
Email: araki@ieee.org
Abstract
It is well known that quantum mechanics is explained in quantum logic and orthomodular lattices.
However, these logic and algebraic structure have not always been succeeded in explaining behavior
of quantum information systems.
A qubit
ñ = α0ñ + β1ñ ";
?>
in quantum information systems is extension of classical concept
”bit”, where
ñ and 1ñ ";
?>
are basis of a two dimensional quantum system with two orthogonal states,
α and β are probabilistic amplitudes in C. Then, one qubit can have infinite number of values in
contrast with classical one bit.
In this paper, to analyze various infinite number of quantum states, we establish a discrete
algebraic structure as a model of qubit space, which is isomorphic to Kleene algebra
3 = < {0,1/2,1},~,/\,\/ >. Furthermore, we propose weak Kleenean nonadditive measures and weak
KleeneChoquet integrals. Then, we show that we can analyze quantum communication channels
effectively by the proposed framework using a quantum cryptosystem as an example.
All nonlinear reversible logic gates are runiversal
A. De Vos
Imec v.z.w., Vakgroep elektronika and informatiesystemen,
Universiteit Gent
alex@elis.UGent.be
L. Storme
Vakgroep zuivere wiskunde and computeralgebra,
Universiteit Gent
ls@cage.UGent.be
Abstract
Reversible logic plays a fundamental role both in lowpower electronics and in quan
tum computing. Thus it is important to know which reversible logic gates can be used
as building block for the implementation of an arbitrary boolean function and which
cannot.
An Approach to Synthesis of MultipleValued
Reversible Logic Circuits
Pawel Kerntopf
Institute of Computer Science, Department of Electronics and Information
Technology, Warsaw University of Technology, Warsaw, Poland
email: P.Kerntopf@ii.pw.edu.pl
Abstract
Reversible logic has applications in many fields, including quantum computing. Recently,
physical realizations of quantum MVL gates in ion trap technology have been reported [26] and
various ternary quantum gates have been experimentally built [2]. This paper proposes an
approach to synthesis of reversible MVL circuits using a complexity measure based on shared
multiplevalued decision diagrams with cyclic edge negations. It is a generalization of a method
we have recently developed for the binary reversible logic synthesis that showed promising results
in comparison with the known approaches. The approach can be used with arbitrary libraries of
reversible MVL gates and arbitrary cost functions.
Toffoli Templates with 8 Gates
Joshua R. Dick, Gerhard W. Dueck
Faculty of Computer Science
University of New Brunswick
Fredericton, New Brunswick
Canada
y0h7s@unb.ca, gdueck@unb.ca
Dmitri Maslov
Dept. of Computer Science
University of Victoria
Victoria, British Columbia
Canada
dmitri.maslov@unb.ca
Abstract
Reversible logic maps each input pattern to a unique output pattern. In order to realize these
funcToffoli Templates with 8 Gatestions reversible gates, such as Toffoli, are brought together in a cascade to form a reversible
circuit. One effective method for simplifying reversible circuits is accomplished via template
matching. The basis for a template is a series of gates that realizes the identity function. Template
matching deals with matching a set of gates in the circuit with those of a template and replacing the
matching gates with the remaining gates of the template in reverse order if more than half the
template has been matched. There currently exist templates of up to size 7. In order for template
matching to be more effective, larger templates needed. However, discovering such templates is not
a simple task; the search requires an enormous amount of processing power. This paper deals with
the design and implementation of a template finding program on a parallel computer which makes
the template finding process be a feasible task. It also discusses the templates found after running
the program.
Hardware Synthesis of UMLModels
Thomas Beierlein
Hochschule Mittweida
Labor Embedded Control
tb@htwm.de
Dominik Fröhlich
TU Bergakademie Freiberg
Inst. of Computer Science
dfroehli@htwm.de
Bernd Steinbach
TU Bergakademie Freiberg
Inst. of Computer Science
steinb@informatik.tufreiberg.de
Abstract
The automated synthesis of application specific coprocessors has been a complex and demanding
problem. To handle the inherent informational and architectural complexity of this problem novel
development approaches supported by powerful tools are taken. In this paper we present an approach
that is based on UML and hardware/software codesign. We will show how Boolean problem solvers
can be modeled with this language and discuss the synthesis of hardware from such models. Also we
show important problems we recognized with the current approaches that should be investigated in the
future.
FSM's NETWORK ENCODING GUIDED BY INFORMATION RELATIONSHIP MEASURE
Elena Fomina, Alexander Sudnitson, and Roman Vasilyev
Department of Computer Engineering
Tallinn University of Technology
Raja Street, 12618 Tallinn, Estonia
Tel.: +372 620 2251, Fax: +372 620 2246, alsu@cc.ttu.ee
Abstract
The results presented in this paper are intermediate of work on the problem of encoding (or state
assignment) of network of Finite State Machines (FSMs). Partitioning or decomposition requires
to realization of synthesis of FSM in two stages. Initial stage is solving of problem of choosing of
partition’s system. This stage corresponds to primary rough phase of FSM decomposition. Next
stage is coding of given network of FSMs. Following transformations of given network of FSMs is
more delicate optimization.
In current report we devote our investigation to development of an algorithm of FSMs network
coding with minimal code length. We present new encoding strategy based on the measure of
information relationship. An illustrative example allows monitoring all steps of the algorithm.
Experiments on the circuits of MCNC benchmarks present efficiency of the proposed approach in
comparison with standard methods of FSM encoding.
On Deterministic Timed Alternating Finite Automata
Abdelaziz Fellah ^{*}
Dept. of Computer Science
University of Sharjah
Sharjah, UAE
email: abd@sharjah.ac.ae
Abstract
Timed alternating finite automata (TAFA), a natural generalization of timed finite
automata (TFA), are synchronous and powerful models for realtime constraint computations
and embedded systems We introduce deterministic timed alternating finite automata
(DTAFA), a class of timed alternating finite automata, extended with a finite set of re
stricted and mutually exclusive realvalued clocks on events which trigger the state transi
tions of the automaton. We show how to transform deterministic nstate TFA into log n
state DTAFA and state some language properties between TFA, DTAFA, and deterministic
TFA. We then show that, unlike TFA and TAFA, DTAFA are closed under all Boolean
operations, including the complementation. In addition, we present an equational language
representation for DTAFA which parallels that of timed languages for TAFA.
keywords: Timed automata, timed alternating finite automata, timed language equations.
^{*}on leave, Dept. of Math. & Computer Science, University of Lethbridge, Lethbridge, Alberta, Canada.
email: fellah@cs.uleth.ca
Experimental Studies on Test Pattern Generation for BDD Circuits
Junhao Shi, Görschwin Fey, Rolf Drechsler
Institute of Computer Science
University of Bremen
28359 Bremen, Germany
{junhao,fey,drechsle}@informatik.unibremen.de
Abstract
Synthesis for Testability has become a major issue as the size and complexity of circuits
and systems is rapidly increasing. Due to their good testability design styles based on
multiplexors have become very popular. In particular a Binary Decision Diagram (BDD)
can directly be mapped to a BDD circuit using multiplexors. BDD circuits can be modified
to retrieve 100% testable circuits under the stuckat fault model at a low cost.
In this paper Automatic Test Pattern Generation (ATPG) for BDD circuits is studied. BDD
circuits are compared to conventionally optimized circuits. The number of test patterns are
compared for the different methods. For the benchmark circuits the number of test patterns
needed is comparable to the relative sizes of the circuits. Even a gain up to a factor of four
occurred.
Efficient Reprogrammable Architecture for Boolean Functions and Cellular Automata
Harald Richter and Christian Siemers
Clausthal University of Technology, Institute for Computer Science
JuliusAlbertStr. 4, D38678 ClausthalZellerfeld
(richtersiemers)@informatik.tuclausthal.de
Abstract
An architecture was developed that under certain preconditions allows to efficiently implement
any Boolean function f: B^{m} > B^{n}, B={0,1} by means of a reprogrammable CAM/RAM array. It
proved to be a balanced combination of two known approaches for implementing Boolean
functions, i.e. looktable in RAM, and fixed array of AND and OR gates according to the
disjunctive normal form of f.
Remarks on Symmetric Binary and MultipleValued Logic Functions
Radomir S. Stankovic, Jaakko Astola^{1}, Karen Egiazarian^{1}
Dept. of Computer Science, Faculty of Electronics, 18000 Ni·s, Serbia
^{1}Tampere International Center for Signal Processing
Tampere University of Technology, Tampere, Finland
Abstract
This papers extends definitions of elementary symmetric functions for binary valued
switching functions to multiplevalued (MV) functions. It is shown that under a suitable
selection of the underlined algebraic structure, the basic results in reduced polynomial rep
resentations for symmetric binaryvalued functions can be extended to MV functions. The
method of defining elementary symmetric functions can be used to create many symmetric
MV benchmark functions as combinations of elementary symmetric MV functions. Since the
same method can be applied in different algebraic structures, various benchmark functions
can be defined.
Minimization of MultiValued Functions in
Decomposition of a System of Completely Specified
Boolean Functions
Yuri Pottosin^{*}, Eugeny Shestakov, Dmitry Sadnikov
United Institute of Informatics Problems of the NAS of Belarus
Surganov str., 220012 Minsk, Belarus; email: pott@newman.basnet.by
Abstract
A method for decomposition of a system of completely specified Boolean functions using
minimization of multivalued functions is considered. To minimize a multivalued function the
EspressoMV program is used. Experimental results on benchmarks are given.
^{*} The author is supported by ISTC project B986.
Relation between Boolean functions and spreading
sequences for MCCDMA transmission
Ekaterina Pogossova, Karen Egiazarian, Jaakko Astola
Tampere University of Technology,
Dept. of Information Technology, P.O. BOX 553, Tampere, Finland
email:pogosova@cs.tut.fi
Abstract
In this paper, we address the problem of spreading sequence design for multicarrier
CDMA transmission. With the help of Boolean and multiplevalued logic theory, we derive a
number of orthogonal matrices, with the rows well suitable for multicarrier CDMA spreading
n terms of peaktoaverage power ratio of the resulting transmitted signal.
Foundations of Hierarchical SATSolving
Yakov Novikov
KonradZuseZentrum für
Informationstechnik Berlin (ZIB)
yakov_nov@tut.by
Raik Brinkmann
Infineon Technologies AG
München
Raik.Brinkmann@infineon.com
Abstract
The theory of hierarchical Boolean satisfiability (SAT) solving proposed in this paper is based on a
strict axiomatic system and introduces a new important notion of implicativity. The theory makes
evident that increasing implicativity is the core of SATsolving. We provide a theoretical basis for
increasing the implicativity of a given SAT instance and for organizing SATsolving in a
hierarchical way. The theory opens a new domain of research: SATmodel construction. Now
quite different mathematical models can be used within practical SATsolvers. The theory covers
many advanced techniques such as circuitoriented SATsolving, mixed BDD/CNF SATsolving,
merging gates, using pseudoBoolean constraints, using state machines for representation of
Boolean functions, arithmetic reasoning, and managing don’t cares. We believe that hierarchical
SATsolving is a cardinal direction of research in practical SATsolving.
Jordan Normal Form of Boolean Matrices
WolfMichael Wendler
Fachhochschule Braunschweig/Wolfenbüttel
University of Applied Sciences
Fachbereich Fahrzeug, Produktions und Verfahrenstechnik
RobertKochPlatz 1014
38440 Wolfsburg
email: WM.Wendler@FHWolfenbuettel.DE
Abstract
The Jordan normal form of an arbitrary Boolean square matrix is derived and applied
to the analysis of the behavior of the solution of the linear state space equations. The
theory is generalized to all finite fields of prime characteristic.
Binary Maxwellian Equations
WolfMichael Wendler
Fachhochschule Braunschweig/Wolfenbüttel
University of Applied Sciences
Fachbereich Fahrzeug, Produktions und Verfahrenstechnik
RobertKochPlatz 1014
38440 Wolfsburg
email: WM.Wendler@FHWolfenbuettel.DE
Abstract
A finite field formulation of the Maxwellian equations is presented. The derivation of
wave equations as well as solutions are discussed. By means of a Lorentzlike binary
transformation a covariant formulation of these equations is given. The transformational
behavior of the electromagnetic field tensor and the energymomentum tensor are
discussed.
Solving Inconsistent Systems of Linear Logical Equations
Arkadij Zakrevskij
United Institute of Informatics Problems of the National Academy of Sciences,
220012 Minsk, Belarus
email: zakr@newman.basnet.by
Abstract
Inconsistent systems of linear logical equations are considered, the number of equations in
which exceeds the number of variables. The task of finding of a solution satisfying the maximum
number of the equations is put. A combinatorial randomized algorithm to solve this task is offered,
the results of its computer implementation are adduced.
Decomposition of Boolean Function Sets for Boolean Neural Networks
Roman Kohut, Bernd Steinbach
Freiberg University of Mining and Technology
Institute of Computer Science
D09596 Freiberg, Germany
email:{kohut, steinb}@informatik.tufreiberg.de
Abstract
This paper presents a new type of neuron, called Boolean neuron. We suggest algorithms for
decomposition of Boolean functions sets based on Boolean neural networks that include only
Boolean neurons. The advantages of these neural networks consist in the reduction of memory
space and computation time in comparison to the representation of Boolean functions by usual
neural networks. The Boolean neural network can be mapped to a FPGA so that our new approach
substitutes classical design methods of these circuits. We show as example the ANDdecomposition
of a Boolean function set into unique basic functions and their mapping to the general
Boolean neural network.
Building Minimum ESOPs Through Redundancy Elimination
Grant R. Pogosyan
Mathematics and Information Science
International Christian University
Osawa 3102, Mitaka, Tokyo, 1818585 Japan
grant@icu.ac.jp
Ivo G. Rosenberg
Mathematics and Statistics
University of Montreal
C.P. 6128, Succ. Centreville, Montreal, Que, Canada H3C 3J7
rosenb@dms.umontreal.ca
Seiya Takada
School of Frontier Sciences
University of Tokyo
Kashiwanoha 515, Kashiwa, Chiba 2778561, JAPAN
stakada@gavo.t.utokyo.ac.jp
Abstract
Exclusive Sum of Products or ESOP expressions for Boolean functions have been studied
for more than a decade. The interest towards such formulae is triggered by the fact that the
choice of AND, EXOR, NOT as generators for formal expressions is proven to be more effcient
in terms of formula complexity compared to the classical ANDORNOT expressions.
We present an algorithm which nds an exact minimum ESOP for a given Boolean
function, with number of literals as the measure of optimality. This algorithm is based on a
technique of redundant term elimination in the process of selecting a candidate combination
of minterms to match with the given function.
Since the problem of exact minimization has an overpolynomial complexity, such algo
rithms are bound to fail halting within a feasible time for suffciently large functions. Our
gaol was to achieve a faster performance than that of known algorithms, and to be able to
construct minimum ESOPs for more functions in practically workable computation time.
Maitra Cascade Minimization^{*}
Dimitrios Voudouris and George Papakonstantinou
National Technical University of Athens
email: dvoudour@cslab.ece.ntua.gr, papakon@cslab.ece.ntua.gr
Abstract
In this paper an effcient algorithm for the synthesis and minimization of CA (cellular
array architectures) is proposed. Our algorithm starts from a completelyspecified switching
function and produces reversible wave cascades with an effort to minimize the number of the
produced chains (cascades). This kind of topology can easily be mapped to reversible cir
cuits (generalized Toffoli gates) as it is presented in the related bibliography. The proposed
algorithm uses function decomposition and ETDDs (EXOR ternary decision diagrams).
The experimental results that are obtained (they are presented at the end of this work)
prove the effciency of the proposed method.
^{*}This paper has been partially funded by the project Protagoras/NTUA
TwoLevel Boolean Minimizer BOOMII
Petr Fišer, Hana Kubátová
Department of Computer Science and Engineering
Czech Technical University
Karlovo nam. 13, 121 35 Prague 2
email: fiserp@fel.cvut.cz, kubatova@fel.cvut.cz
Abstract
We propose a novel twolevel Boolean minimizer coming in succession to our previously
developed minimizer BOOM, so we have named it BOOMII. It is a combination of two minimizers,
namely BOOM and FCMin. Each of these two methods has its own area where it is most efficiently
applicable. We have combined these two methods together to be able to solve all kinds of problems
efficiently, independently on their size or nature. The tool is very scalable in terms of the required
runtime and/or the quality of the solution. It is applicable to functions with an extremely large
number of both input and output variables.
A Novel Method for Minimization of Boolean Functions
using Gray Code and development of a Parallel
Algorithm
S.Verma and K. Permar
Government Engineering College, Raipur 492 010 CG, India
email: vshrish9@yahoo.com and kdpermar@yahoo.com
Abstract
The present paper proposes a new method for two level minimization of Boolean functions,
which is not only a versatile and elegant paperandpencil method but also the one for which a
parallel minimization algorithm can be readily developed. A novel minterm numbering scheme
based on Gray code is proposed exploiting the Gray code’s unit distance and reflection properties
for obtaining adjacency among the given minterms in paperandpencil method as well as to
develop a parallel algorithm for generating prime implicants and subsequent minimization of the
given Boolean function. The proposed paperandpencil method and the parallel algorithm are
implemented on a few examples having don’t care terms.
Easy testable combinational circuit design
A. Matrosova, S. Ostanin, V. Andreeva
Tomsk State University, Russia
{mau, ostanin, avv}@fpmk.tsu.ru
Abstract
It is found out that a set of test patterns for all multiple stickat faults at the gates
poles of a combinational circuit designed coincides with a set of test patterns for
all single stuckat faults of irredundant sums of prime implicants describing the
combinational circuit behavior. The combinational circuits is designed with a multi
level synthesis method based on division of sums of products and a factorized
two level synthesis method applied to kernels and cokernels. The method of
finding such setoff test patterns is discussed.
Simple folding of arraybased VLSI structures
Liudmila Cheremisinova
The United Institute of Informatics Problems of
National Academy of Sciences of Belarus
email: cld@newman.basnet.by
Abstract
The problem under consideration is to reduce the area of the layout of regular VLSI structures
by means of their folding. Some results of cutting down exhaustive computational efforts on the
search for the optimal regular structure folding have been described. An efficient method for onedimensional
unconstrained simple folding is presented. It is formulated on a Boolean matrix
depicting the compatibility relation among all pairs of columns of the arraybased structure.
Generation of test case templates using the Boolean
representation of software model
Christina Dorotska
Freiberg University of Mining and Technology, Institute of Computer Science,
D09596 Freiberg, Germany,
email: dorotska@informatik.tufreiberg.de
Abstract
This paper is devoted to the problem of testing of object oriented software based on the using
of test cases. The software is described with a Unified Modeling Language (UML) and will be
transferred by the XML to the test tool. For the internal representation of the software the Boolean
model is used, which maps all correct values by a one and all wrong values by a zero. Value that
influences the test result and can be both correct and wrong, is mapped by a dash (don’tcare). The
test cases will be generated by replacing of don’tcares by ones and zeros.
Strengthening Semantictree Method in evaluating QBFs
Mohammad GhasemZadeh, Volker Klotz and Christoph Meinel
FBIV Informatik, University of Trier, Germany
{GhasemZadeh, klotz, meinel}@TI.UniTrier.DE
Abstract
The semantictree approach is the most robust method for deciding QBFs. This method is very
similar to the DPLL algorithm for evaluating SAT instances. In this paper we show how memorization
can be embedded to this method to get better results. In other words we present an algorithm for
evaluating QBFs, which is based on an adopted version of semantictree method and ZDDs (which are
variants of BDDs). The capability of ZDDs in storing sets of subsets efficiently, enabled us to store the
formula very compact and led us to implement the search algorithm in such a way that we could store
and reuse the results of all already solved subformulas. We call this idea: ’strengthening semantictree
method by memorization’. This idea along some other techniques, enabled our algorithm to solve a
bunch of the standard QBF benchmark problems faster than the best existing QBF solvers.
Keywords: DPLL, ZeroSuppressed Binary Decision Diagram (ZDD), Quantified Boolean Formulae
(QBF), Satisfiability, QSAT, Memorization, Dynamic Programming.
Variable Ordering in SBDD Considering Function in
Spectral Domain
Milena Stankovic
Faculty of Electronic,
University of Nis,
Beogradska 14, 18000 Nis, Serbia
mstankovic@elfak.ni.ac.yu
Jaakko Astola, Karen Egiazarian
TICSP, Tampere
University of Technology,
P.O. Box 553, Tampere, Finland
jaakko.astola@tut.fi, karen@cs.tut.fi
Abstract
Determination of a suitable order of variables is an important task in representation of switching
functions by Binary Decision Diagrams (BDDs). This paper presents a deterministic procedure for
determination of order of variables which produces Shared Binary Decision Diagrams (SBDDs) of
the reduced complexity expressed in the number of nonterminal nodes count. Experimental results
show that SBDDs produced by this procedure have equal or comparable number of nodes as
SBDDs for the optimal order of variables.
Structurally synthesized binary decision diagrams
A. Jutman, A. Peder, J. Raik, M. Tombak, R. Ubar
Tallinn University of Technology, University of Tartu
raiub@pld.ttu.ee
Abstract
Current paper presents a special case of BDDs called Structurally Synthesized BDDs.
Different from BDDs, which are generated by Shannon’s expansion, SSBDDs are generated
by a superposition procedure. The paper investigates the mathematical properties of such
kind of BDDs, in order to separate the properties of the underlying ”skeleton” graphs from
the properties of SSBDDs. SSBDD representations for both, Boolean formulae and digital
logic circuits are explained. Finally, usefulness of the model is shown in the application of
fault modeling in digital test.
