https://www.dagstuhl.de/11502

11. – 14. Dezember 2011, Dagstuhl Seminar 11502

Design of Reversible and Quantum Circuits

Organisatoren

Kenichi Morita (Hiroshima University, JP)
Robert Wille (Universität Bremen, DE)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 1, Issue 12 Dagstuhl Report
Teilnehmerliste
Gemeinsame Dokumente

Summary

The development of computing machines found great success in the last decades. But the ongoing miniaturization of integrated circuits will reach its limits in the near future. Shrinking transistor sizes and power dissipation are the major barriers in the development of smaller and more powerful circuits. To further satisfy the needs for more computational power and further miniturization, alternatives are needed that go beyond the scope of conventional technologies like CMOS. Reversible logic and quantum logic provide a promising alternative that may enhance or even replace conventional circuits in the future. More precisely:

  • Low Power Computation
    While conventional circuits dissipate energy for each lost bit of information, reversible circuits are information lossless, i.e. theoretically they are not affected by this. Considering the increasing miniaturization, this makes reversible logic interesting for domains like low-power design. Besides this general paradigm, reversible circuits are particularly suited for complementary low-power solutions like adiabatic circuits or on-chip interconnect encoders.
  • Quantum Computation
    Quantum Computation offers the promise of more efficient computing for problems that are of exponential difficulty for conventional computing paradigms. Considering that many of the established quantum algorithms include a significant Boolean component (e.g.the oracle transformation in the Deutsch-Jozsa algorithm, the database in Grover's search algorithm, and the modulo exponentiation in Shor's algorithm), it is crucial to have efficient methods to synthesize quantum gate realisations of Boolean functions. Since any quantum operation inherently is reversible, reversible circuits can be exploited for this purpose.

However, no real design flow for these new kinds of circuits exists so far. Proposed approaches for synthesis, verification, and test are only applicable for very small circuits and systems. This is crucial since the design for reversible and quantum systems significantly differs from their conventional counterparts. Nearly all concepts and methods developed for conventional hardware design in the last decades have to be redeveloped in order to support the new technologies. Additionally, considering that today researchers are still faced with serious challenges for conventional technologies, it is worth working towards design solutions for reversible and quantum technologies already today.

The goal of the seminar was to bring together experts in order to present and to develop new ideas and concepts for the design of complex reversible and quantum circuits. In total, 17 presentations together with 1 tool demonstration (of the open source toolkit RevKit) and one panel sessions (on the different opinions on how reversible circuits can help to reduce power consumption during computation) have been conducted within the seminar. This has been accompanied by several working group and proposal preparation meetings. The most important topics which have been discussed were:

  • Design Methods
    How to (automatically) synthesize reversible and quantum circuits as well as check them for correctness?
    Most of today's synthesis approaches for reversible and quantum circuits still rely on Boolean function descriptions like e.g. permutations, truth tables, or binary decision diagrams. In order to design complex circuits, higher levels of abstractions have to be considered. While for this purpose hardware description languages like VHDL, SystemC, or SystemVerilog have been established in conventional hardware design, high level synthesis of reversible and quantum circuits is just at the beginning. In order to advance this area, ideas about concepts, languages, and synthesis approaches for high level design have been presented and collected at the seminar.
  • Theoretical Consideration
    How can theoretical studies show us the way for realizing reversible/quantum computers?
    In order to implement efficient reversible/quantum circuits and computers, we still need very basic and theoretical studies on them. This is because the paradigm of reversible/quantum computing has very different natures from that of conventional computing. Therefore, we shall still be able to find many novel and useful ideas for them through theoretical studies. In this seminar, theoretical consideration on various models in several levels have been presented and discussed. These models range from the element level to the software level, which include reversible logic elements and circuits, quantum automata, reversible Turing machines, and reversible programming languages.
  • Physical Realizations and Accuracy of Models
    How to physically implement the respective circuits? How to close the gap between the theoretical models and the physical implementation?
    In order to design reversible and quantum circuits, abstractions of the precise physical realizations are applied. These include the used gate library and the respective cost metrics, but also fault models for testing or abstractions for technology mapping. Due to the progress in the development of physical realizations, these models constantly are subject to modifications which needed to be considered in the design phase. During the seminar, recent achievements in the development of physical realizations have been presented. This built the basis for discussions about updating and refining the applied models and abstractions.
  • Applications
    How can reversible and quantum circuits be exploited in practically relevant application
    How to measure and proof the benefits of these emerging technologies (e.g. how to substantiate improvements in the power consumption)
    So far, design methods have mostly been applied to "academic" examples only. However, the design of reversible circuits for precise applications is the next logical step. Possible directions (e.g. in the low-power domain) have been discussed at the seminar. This also included discussions of the requirements for such applications and how the benefits can be measured.

Results of the seminar are currently used in the preparation of upcomming scientific papers. As one example, a special issue on the results triggered by the ideas of this seminar is planned for 2013. Furthermore, the discussions encouraged the preparation of proposals for national and international research projects.

Classification

  • Data Structures / Algorithms / Complexity / Hardware / Programming Languages

Keywords

  • Reversible logic
  • Quantum computation
  • Computer aided design
  • Hardware and software design
  • Applications

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.