Foreword: Special Issue on Reversible Computation
Rolf Drechsler, Irek Ulidowski and Robert Wille
INTRODUCTION
In the recent years, reversible computation established itself as a very promising research area and an emerging technology. This is motivated by a widely supported prediction that the conventional computer hardware technologies are going to reach their limits in the not too distant future. In particular, the impact of power consumption on the intended behavior of electronic devices is becoming a serious problem. While the unwanted behavior of transistors can be reduced by higher levels of integration and new fabrication processes, a more fundamental problem exists: As proven by Landauer in 1961, each time a bit of information is deleted exactly k·T·log2 joule of energy are dissipated, where k is the Boltzmann constant and T is the temperature. While this amount of energy does not seem presently significant, it forms potentially a barrier for future technologies. Transistors that perform millions of operations per second are fairly common these days – and more and more operations are performed on smaller and smaller transistors. Since these trends are most likely to continue, dissipation of k·T·log2 joule of energy per lost bit of information will become crucial and may bring the progress of conventional computer technologies to a halt.
In contrast, reversible computations may reduce or even eliminate this power dissipation. This holds since n-input n-output functions, for some appropriate n, can be used to map each possible input vector to a unique output vector. Data is bijectively transformed in this way without losing any of the original information, thus avoiding energy dissipation. In fact, computations with zero power dissipation are only possible if they are performed in a reversible manner. Thus, in order to overcome the limitations caused by Landauer’s barrier computation has to be reversible.
Besides that, quantum computation has become a major application area for reversible logic. It uses qubits instead of the conventional bits. Qubits allow to represent not only 0 and 1 but also a superposition of both. As a result, qubits can represent multiple states at the same time enabling theoretically enormous speed-ups in computation. It has been shown that, for example, using a quantum circuit it is possible to solve the factorization problem in polynomial time while for conventional circuits only exponential methods exist. Admittedly, although the research in the domain of quantum circuits is still in its infancy, the first simple quantum circuits are being physically implemented. Reversible computation is therefore essential because every quantum operation is inherently reversible. Thus, progress in the domain of reversible logic can be directly applied to quantum logic.
Further applications of reversible computation paradigms can be found in decoding, program debugging, testing, database recovery, discrete event simulation, reversible algorithms, reversible specification formalisms, reversible programming languages, process algebras and semantics of concurrency, or the modeling of biochemical systems.
CONTRIBUTIONS
The Workshop on Reversible Computation provides a platform to present and to discuss newtrends and recent developments in this promising area. The first Workshop on Reversible Computation took place in March 2009 as a satellite event of ETAPS 2009, the twelfth European Joint Conference on Theory and Practice of Software. The proceedings appeared as ENTCSVolume 253, issue 6. The second edition of the workshop (RC 2010) took place on July 2nd and 3rd 2010 in Bremen, Germany. The program included presentations that concerned reversible software, reversible hardware, as well as quantum circuits and concluded with the consideration of physical realizations as well as the testing methods for reversible computation. This special issue of the Journal of Multiple-Valued Logic and Soft Computing presents revised and extended versions of the best papers of RC 2010.
The first paper considers the software aspects of reversible computation. The authors T. Yokoyama, H. B. Axelsen, and R. Glück present a novel garbage-less simulation method for injective functions. The reversible programming language Janus is thereby applied. It is shown by means of text encoding that the computation can be performed twice as fast as with the method previously introduced by Bennett.
Reversible hardware elements are in the subject of the second and third paper. In the former, A. De Vos, S. Burignat, and M. K. Thomsen introduce first steps towards reversible implementations of two linear transformations, namely the Haar wavelet and the H.264 transform. These functions are used, for example, for the H.264 video coding standard and thus represent an interesting practical case study for reversible computation. K. Morita, T. Ogiro, A. Alhazov, and T. Tanizawa present in the third paper significant theoretical results concerning non-degenerate 2-state reversible logic elements with three or more symbols. They prove that all these elements are universal, namely that it is possible to simulate a reversible Turing machine with these kind of hardware elements.
The fourth paper presents a software toolkit called RevKit that assists users in the design of reversible circuits. RevKit is developed by M. Soeken, S. Frehse, R. Wille, and R. Drechsler. It provides various functionalities ranging from synthesis and optimization to verification of reversible circuits. Furthermore, RevKit is open source so that other researchers can use and extend its functionalities.
Finally, the application of reversible computation to the domain of quantum computation is covered in the last three papers. A. DeVos, M. Boes, and S. De Baerdemacker go all the way down from reversible architectures to quantum architectures. The discussion about possible groups and decompositions between these two abstractions leads to a better understanding in applying the group theory to both reversible and quantum computation. This issue is addressed more specifically by Z. Sasanian and D. M. Miller. They investigate the decomposition rules leading to new – more compact – mappings from reversible Toffoli gates to elementary quantum gates. Direct synthesis of quantum gates is eventually addressed in the final paper. Here, S.Yamashita, S. Minato, and D. M. Miller introduce an appropriate synthesis methodology based on decision diagrams.
ACKNOWLEDGEMENTS
We would like to thank all the authors for their valuable contributions to this special issue devoted to RC 2010. Furthermore, many thanks are due to the members of the Program Committee and all external reviewers for their excellent work in evaluating the submissions as well as for providing detailed feedback and further suggestions to the authors. Finally, we wish to thank Dan Simovici and Ivan Stojmenovic, the Editors-in-Chief of the Journal of Multiple-Valued Logic and Soft Computing, for agreeing to publish this special issue. Support from the University of Bremen and the University of Leicester is also gratefully acknowledged.