Quantum computing has been attracting increasing attention in recent years because of the rapid advancements that have been made in quantum algorithms and quantum system design. Quantum algorithms are implemented with the help of quantum circuits. These circuits are inherently reversible in nature and often contain a sizeable Boolean part that needs to be synthesized. The logic design of such quantum circuits constitutes a non-trivial task and, hence, have heavily been investigated by researchers in the recent past. This paper provides a brief overview of these research. We review the major steps to be conducted in the logic design of quantum circuits and provide a sketch for each single step. These descriptions are enriched with discussions as well as references to the respective related work.
Quantum computing has been attracting increasing attention in recent years because of the rapid advancements that have been made in quantum algorithms and quantum system design. Quantum algorithms are implemented with the help of quantum circuits. These circuits are inherently reversible in nature and often contain a sizeable Boolean part that needs to be synthesized. The logic design of such quantum circuits constitutes a non-trivial task and, hence, have heavily been investigated by researchers in the recent past. This paper provides a brief overview of these research. We review the major steps to be conducted in the logic design of quantum circuits and provide a sketch for each single step. These descriptions are enriched with discussions as well as references to the respective related work.
Increasing miniaturization and demand of low power electronics is highly motivating research on reversible logic. Reversible logic has attracted signification attention in fields of Low power VLSI design, computer graphics, quantum computing and communication. A lot of work has been done on synthesis and optimization of reversible circuits followed by quantitative analysis on various optimization metrics like ancillary inputs, garbage outputs and quantum cost. It is therefore obvious to present a quick guide on reversible logic implementation to bridge gap between theory and implementation. Taxonomy diagrams of work done in reversible logic domain are also presented to give a quick review of all about reversible logic. Quantum realization of popular reversible Fredkin gates using RCViewer tool is also presented which will be stepping stone for a new researcher to synthesize and optimize any complex reversible logic based circuit.
Reversible circuits found great interest in the past as an alternative computation paradigm which can be beneficial e.g. for encoder circuits, low power design, adiabatic circuits, verification, and much more. Besides that, reversible circuits provide the basis for many components of quantum circuits, which by themselves emerged as a very promising computing technology that, particularly these days, gains more and more relevance. All that led to a steadily increasing demand for methods that efficiently and correctly design such circuits. Decision diagrams play an important role in the design of conventional circuitry. In the meantime, also their benefits for the design of the newly emerging reversible and quantum circuits become evident. In this overview paper, we review and illustrate past work on decision diagrams for such circuits and sketch corresponding design methods relying on them. By this, we demonstrate how broadly decision diagrams can be employed in this area and what benefits they yield for these emerging technologies.
After decades of continuous improvements and shrinking feature sizes, the development of conventional computing technologies faces enormous challenges. In particular, power dissipation in today's computer chips becomes crucial. Reversible computation is a promising alternative to these technologies, where power dissipation can be reduced or even eliminated. Furthermore, reversible logic builds the basis for quantum computation - a completely new way of processing which enables to solve certain problems exponentially faster compared to conventional methods. However, the design of reversible and quantum circuits is significantly different. Thus, new methods e.g. for synthesis, optimization, or verification are needed. This paper provides a brief introduction into reversible circuits and their respective design methods that have been proposed within the last years.
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.
Quantum computation established itself as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided-design (CAD). However, quantum mechanical phenomena such as superposition, phase shifts, or entanglement lead to a logic model which poses serious challenges to the development of a proper design flow for quantum circuits. Consequently, researchers addressed synthesis of quantum circuits not as a single design step, but considered sub-tasks such as synthesis of Boolean components or synthesis of restricted subsets of quantum functionality. Generating a particularly desired quantum state is another of these sub-tasks. However, logic synthesis of quantum circuits accomplishing that has hardly been considered yet. In this work, we propose a generic method which automatically synthesizes a quantum circuit generating any desired quantum state from an initially given basis state. The proposed method allows for both, a theoretical determination of upper bounds as well as an experimental evaluation of the number of quantum gates needed for this important design step.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.