Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation

From reversible logic to quantum circuits: Logic design for an emerging technology

Robert Wille, Anupam Chattopadhyay, Rolf Drechsler

Published Jul 1, 2016• 18 citations
Publisher

Abstract

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.

DOI
10.1109/samos.2016.7818357

Related papers

A Quick Guide to Implement Reversible Logic

Shaveta Thakral, Dipali Bansal

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.

International Conference on Computing, Communication and Automation•Dec 1, 2018•2 citations

Decision diagrams for the design of reversible and quantum circuits

Robert Wille, Philipp Niemann, Alwin Zulehner +1 more

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.

International Symposium on Devices, Circuits and Systems (ISDCS)•Mar 1, 2018•2 citations

An introduction to reversible circuit design

Robert Wille

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.

Saudi International Electronics, Communications and Photonics Conference•Apr 1, 2011•11 citations

Computer-aided-design methods for emerging quantum computing technologies

Mitchell Aaron Thornton, David Y. Feinstein

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.

•Jan 1, 2008•3 citations

Logic Synthesis for Quantum State Generation

Philipp Niemann, Rhitam Datta, Robert Wille

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2016•34 citations

Synthesis and optimization of reversible circuits—a survey

Mehdi Saeedi, Igor L. Markov

Reversible logic circuits have been historically motivated by theoretical research in low-power electronics as well as practical improvement of bit manipulation transforms in cryptography and computer graphics. Recently, reversible circuits have attracted interest as components of quantum algorithms, as well as in photonic and nano-computing technologies where some switching devices offer no signal gain. Research in generating reversible logic distinguishes between circuit synthesis, postsynthesis optimization, and technology mapping. In this survey, we review algorithmic paradigms—search based, cycle based, transformation based, and BDD based—as well as specific algorithms for reversible synthesis, both exact and heuristic. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.

arXiv:1110.2574•ACM Computing Surveys•Feb 1, 2013•311 citations
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 electronics as well as practical improvement of bit manipulation transforms in cryptography and computer graphics. Recently, reversible circuits have attracted interest as components of quantum algorithms, as well as in photonic and nano-computing technologies where some switching devices offer no signal gain. Research in generating reversible logic distinguishes between circuit synthesis, postsynthesis optimization, and technology mapping. In this survey, we review algorithmic paradigms—search based, cycle based, transformation based, and BDD based—as well as specific algorithms for reversible synthesis, both exact and heuristic. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.