Many-valued quantum circuit synthesis of many-valued reversible expansions and fast transforms is introduced in this paper. Since the reduction of power consumption is a major requirement for the circuit design in future technologies, such as in quantum computing, the main features of several future technologies will include reversibility. Consequently, the new quantum circuits can play an important task in the design of future circuits that consume minimal power. In addition, the new quantum circuit methodology is general and can be used to realize any multiple-valued function in the quantum space. It is also shown that the structural generality advantage that results from the new design methodology is opposed with the increased quantum structural complexity disadvantage which may be considered in any further cost-benefit design analysis.
Many-valued quantum circuit synthesis of many-valued reversible expansions and fast transforms is introduced in this paper. Since the reduction of power consumption is a major requirement for the circuit design in future technologies, such as in quantum computing, the main features of several future technologies will include reversibility. Consequently, the new quantum circuits can play an important task in the design of future circuits that consume minimal power. In addition, the new quantum circuit methodology is general and can be used to realize any multiple-valued function in the quantum space. It is also shown that the structural generality advantage that results from the new design methodology is opposed with the increased quantum structural complexity disadvantage which may be considered in any further cost-benefit design analysis.
Novel quantum circuit synthesis, using reversible Davio expansions, is introduced. The new method uses two planes to synthesize the quantum circuits: (1) a reversible butterfly circuit plane; and (2) a plane of quantum gates to perform additions and multiplications. Since the reduction of power consumption is a major requirement for circuit design of future technologies, such as in quantum circuits, the main features of several future technologies must include reversibility, and thus the new synthesis method, using reversible butterfly circuits, can play an important role in the synthesis of circuits that consume minimal power.
The biggest problems in system design today, and in the future, are the high rate of power consumption, and the emergence of quantum effects for highly dense ICs. The real challenge is to design reliable systems that consume as little power as possible and in which the signals are processed and transmitted at very high speeds with very high signal integrity. Current tools are used to design ICs using only classical design methodologies that apply conventional synthesis constraints such as area, delay, and power.
As it was proven, physical processes have to be logically reversible in order to reduce (theoretically eliminate) power consumption. Logical reversibility requires that one can obtain the vector of inputs from the vector of outputs (i.e., backward process) as well as the vector of outputs from the vector of inputs (i.e., forward process). Since only ad-hoc methods were used previously for the reversible synthesis of logic functions, and since systematic and efficient reversible logic synthesis methodologies were significantly missing from previous literature, this dissertation provides several original contributions to reversible logic synthesis by providing a set of tools that can be systematically used to synthesize and evaluate logic functions using reversible logic. This includes, among other new results, Reversible Lattice Structures, Reversible Modified Reconstructability Analysis, Reversible Nets, Reversible Decision Diagrams, and Reversible Cascades.
To solve the problem of high signal integrity when processing (computing and transmitting) information using extremely high dense circuits one needs to incorporate the physical quantum mechanical effects that are unavoidable in the nano scales. Since quantum circuits are reversible, and since many of the underlying theorems and formalisms for multiple-valued quantum computing were significantly missing from previous literature, new fundamental foundations for such computations had to be established. These new results include, but not limited to, Quantum Chrestenson Operator, new types of Quantum Decision Trees and Quantum Decision Diagrams as efficient representations for quantum computing, new Composite Basis States, new multiple-valued Einstein-Podolsky-Rosen (EPR) Basis States, and new classes of quantum primitives.
Initial evaluations and conclusions for the comparative advantages and disadvantages of the new reversible and quantum computing methodologies are also provided.
Research on reversible circuits has gained significance due to its application in quantum computations and many further areas such as the design of encoders. At the same time, the use of multiple-valued logic gained importance since this reduces the number of required entities in physical systems (e.g. in a future quantum computer). While most research is still conducted in the Boolean domain, there exist only few approaches which realize reversible circuits for multiple-valued logic. Moreover, most of the previously proposed solutions for synthesis of multiple-valued reversible circuits are not scalable and consider ternary (i.e. 3-valued circuits) only. Instead of overcoming these issues by developing new synthesis approaches for multiple-valued reversible circuits from scratch, we propose to utilize the recent accomplishments in the design of Boolean reversible circuits and to generalize them for multiple-valued logic. To this end, we discuss how to generalize Quantum Multiple-valued Decision Diagram based (QMDD-based) synthesis - a synthesis approach for Boolean reversible circuits which has been proven to be scalable and which has been used in several recently developed design flows. The discussions eventually show how to bridge the development gap between Boolean and multiple-valued logic for reversible circuits.
Emerging quantum computing technologies are poised to replace standard CMOS logic when the exponential size reduction reaches sub-atomic dimensions. Quantum circuits are reversible and therefore promise the potential of computation without energy loss. This research considers computer aided design (CAD) methods for all major aspects of quantum computing circuit design including logic synthesis, simulation, verification, and testing.
The technologies we investigate include quantum cell automata (QCA) and general quantum circuits (QC), with significantly more emphasis on the later. The recently introduced quantum multi-valued decision diagram (QMDD) provides an efficient method to represent and simulate quantum (and other classical reversible) circuits. A major contribution of this dissertation is the development of a sift-like minimization as well as structure metrics based minimization techniques for QMDD. We have used the enhanced QMDD to efficiently simulate quantum circuits as well as quantum vectors.
Our early investigation of reversible logic is concerned with a virtual implementation that uses a direct translation of relatively complex binary functions into circuits composed of Fredkin reversible gates. This allowed us to project size and speed complexity of complex reversible circuits, although this direct translation approach fails to minimize garbage inputs and outputs. To achieve proper garbage minimization, one must synthesize reversible logic using gate cascades with appropriate optimization methods embedded that attempt to minimize the total number of lines in the circuit. To that end, we developed a novel QMDD-based tool for cascade logic synthesis that utilizes the QMDD minimized variable order for lexicographical synthesis with garbage minimization included as an optimization criterion.
We developed a synthesis tool that investigates the QCA native 3-input majority gates ability to implement complex logic circuits. In particular, we explore the benefit of transforming the logic description into exclusive sum of products (ESOP) forms prior to implementation in the majority gates.
We survey recent efforts in establishing the foundation for QC testing and fault tolerant QC. We project the potential use of random tests as well as built in self test (BIST) techniques for future QC. A major contribution of this dissertation is the investigation of partially redundant reversible logic. Detection of partially redundant logic within any design, reversible or irreversible, has ramifications for logic synthesis, for design verification, and for design for test (DFT) issues.
Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis method.