Dagstuhl Seminar 11502
Design of Reversible and Quantum Circuits
( Dec 11 – Dec 14, 2011 )
- Kenichi Morita (Hiroshima University, JP)
- Robert Wille (Universität Bremen, DE)
- Annette Beyer (for administrative matters)
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.
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.
- Holger Bock Axelsen (University of Copenhagen, DK)
- Stéphane Burignat (Ghent University, BE)
- Alexis De Vos (Ghent University, BE)
- Rolf Drechsler (Universität Bremen, DE) [dblp]
- Gerhard W. Dueck (University of New Brunswick at Fredericton, CA)
- Rusins Martins Freivalds (University of Latvia - Riga, LV)
- Simon Gay (University of Glasgow, GB) [dblp]
- Robert Glück (University of Copenhagen, DK) [dblp]
- Mika Hirvensalo (University of Turku, FI)
- Pawel Kerntopf (Warsaw University of Technology, PL)
- Michael Kirkedal Thomsen (University of Copenhagen, DK)
- D. Michael Miller (University of Victoria, CA)
- Shin-ichi Minato (Hokkaido University, JP) [dblp]
- Kenichi Morita (Hiroshima University, JP)
- Zahra Sasanian (University of Victoria, CA)
- Julia Seiter (Universität Bremen, DE)
- Mathias Soeken (Universität Bremen, DE) [dblp]
- Marek Szyprowski (Warsaw Univ. of Technology, PL)
- Mehdi B. Tahoori (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Robert Wille (Universität Bremen, DE) [dblp]
- Shigeru Yamashita (Ritsumeikan University - Shiga, JP) [dblp]
- Tetsuo Yokoyama (Nanzan University, JP) [dblp]
- data structures / algorithms / complexity / hardware / programming languages
- reversible logic
- quantum computation
- computer aided design
- hardware and software design