Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2012 | Book

Time Complexity of Tape Reduction for Reversible Turing Machines Read chapter Read first chapter

Reversible Computation

Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers

Editors: Alexis De Vos, Robert Wille

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the thoroughly refereed post-conference proceedings of the 7th International Reversible Computation, RC 2011, held in Gent, Belgium, in July 2011. The 10 revised full papers presented were carefully reviewed and selected from 25 initial submissions for inclusion in the book. The papers are devoted to all aspects of reversible computation, ranging from theoretical and experimental aspects to various applications. Topics addressed are: functional language for reversible computations, logic design, reversible circuits designed by a software toolkit called RevKit, application of reversible computation to the domain of quantum circuits, and physical realizations of reversible circuits in CMOS technologies.

Table of Contents

Frontmatter
Time Complexity of Tape Reduction for Reversible Turing Machines
Abstract
Studies of reversible Turing machines (RTMs) often differ in their use of static resources such as the number of tapes, symbols and internal states. However, the interplay between such resources and computational complexity is not well-established for RTMs. In particular, many foundational results in reversible computing theory are about multitape machines with two or more tapes, but it is non-obvious what these results imply for reversible complexity theory.
Here, we study how the time complexity of multitape RTMs behaves under reductions to one and two tapes. For deterministic Turing machines, it is known that the reduction from k tapes to 1 tape in general leads to a quadratic increase in time. For k to 2 tapes, a celebrated result shows that the time overhead can be reduced to a logarithmic factor. We show that identical results hold for multitape RTMs.
This establishes that the structure of reversible time complexity classes mirrors that of irreversible complexity theory, with a similar hierarchy.
Holger Bock Axelsen
Towards a Reversible Functional Language
Abstract
We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete.
Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glück
A Reversible Processor Architecture and Its Reversible Logic Design
Abstract
We describe the design of a purely reversible computing architecture, Bob, and its instruction set, BobISA. The special features of the design include a simple, yet expressive, locally-invertible instruction set, and fully reversible control logic and address calculation. We have designed an architecture with an ISA that is expressive enough to serve as the target for a compiler from a high-level structured reversible programming language.
All-in-all, this paper demonstrates that the design of a complete reversible computing architecture is possible and can serve as the core of a programmable reversible computing system.
Michael Kirkedal Thomsen, Holger Bock Axelsen, Robert Glück
Optimization of Reversible Circuits Using Reconfigured Templates
Abstract
This paper presents a new method to optimize the quantum costs of reversible circuits. A single quantum implementation of the Toffoli-3 gate has been used to decompose reversible circuits into quantum circuits. Reconfigured quantum templates using splitting rules are introduced. The Controlled-NOT, Controlled-V, and Controlled-V  +  gates can be split into two gates – splitting rules are derived from this fact. Quantum costs of reversible circuits are measured by the number of two-qubit operations. Therefore, the costs of reconfigured templates will be unchanged when the splitting rules are applied. Although the number of quantum gates of reconfigured templates increases, their quantum cost remains invariant. Experimental results show that significant cost reductions can be achieved with the proposed method.
Md. Mazder Rahman, Gerhard W. Dueck, Anindita Banerjee
Hybrid GF(2) – Boolean Expressions ..for Quantum Computing Circuits
Abstract
An extension of Toffoli gates is proposed, that allows them to efficiently realize operations in GF(2) and lattice operations of a Boolean algebra. An equivalent extension is introduced into Reed Muller expressions, including mixed polarities and lattice operations, to support the design of quantum computing circuits with low quantum cost.
Claudio Moraga
RevKit: An Open Source Toolkit for the Design of Reversible Circuits
Abstract
In recent years, research in the domain of reversible circuit design has attracted significant attention leading to many different approaches e.g. for synthesis, optimization, simulation, verification, and test. The open source toolkit RevKit is an attempt to make these developments publicly available to other researchers. For this purpose, a modular and extendable framework has been provided which easily enables the addition of new methods and tools.
In this paper, we introduce the functionality as well as the internals of RevKit. We provide examples and use cases showing how to apply RevKit and its components in order to create and execute customized design flows. Furthermore, we demonstrate how the architecture and the design concepts of RevKit can be exploited to easily develop new or improved methods for reversible circuit design.
Mathias Soeken, Stefan Frehse, Robert Wille, Rolf Drechsler
Transforming MCT Circuits to NCVW Circuits
Abstract
Mapping a circuit of reversible gates to a circuit of elementary quantum gates is a key step in synthesizing quantum realizations of Boolean functions. The library containing NOT, controlled-NOT and controlled square-root-of-NOT gates has been considered extensively. In this paper, we extend the library to include fourth-root-of-NOT gates. Experimental results using REVLIB benchmark circuits show that using this extended library results in smaller quantum circuits.
Zahra Sasanian, D. Michael Miller
Changing the Gate Order for Optimal LNN Conversion
Abstract
While several physical realization schemes have been proposed for future quantum information processing, most known facts suggest that quantum information processing should have intrinsic limitations; physically realizable operations would be only interaction between neighbor qubits. To use only such physically realizable operations, we need to convert a general quantum circuit into one for an so-called Linear Nearest Neighbor (LNN) architecture where any gates should be operated between only adjacent qubits. Thus, there has been much attention to develop efficient methods to design quantum circuits for an LNN architecture. Most of the existing researches do not consider changing the gate order of the original circuit, and thus the result may not be optimal. In this paper, we propose a method to convert a quantum circuit into one for an LNN architecture with the smallest number of SWAP gates. Our method improves the previous result for Approximate Quantum Fourier Transform (AQFT) by the state-of-the-art design method.
Atsushi Matsuo, Shigeru Yamashita
Towards the Limits of Cascaded Reversible (Quantum-Inspired) Circuits
Abstract
Several prototypes and proofs of concept of reversible (quantum-inspired) digital circuits have been successfully realized these last years, proving that digital reversible dual-line pass-transistor technology may be used for reversible linear computations. In order for this new technology to be used in commercial applications, several questions have to be answerd first. In particular, the number of gates possibly cascaded, the maximum reachable frequency, the maximum acceptable delays and amplitude drops are the key issues discussed in this paper.
Stéphane Burignat, Mariusz Olczak, Michał Klimczak, Alexis De Vos
Interfacing Reversible Pass-Transistor CMOS Chips with Conventional Restoring CMOS Circuits
Abstract
Recent progress on the prototyping of reversible digital circuits, have shown that adiabatic reversible dual-line pass-transistor logic can be used for special purpose applications in reversible computation. This, however, raises new issues regarding the compatibility between this adiabatic logic implementation and conventional CMOS logic. The greatest difficulty is brought by the difference in signal shape used by these two logic families. Whereas standard switching CMOS circuits are operated by rectangular pulses, dual-line pass-transistor reversible circuits are controlled by triangular or trapezoidal signals to ensure adiabatic switching of the transistors. This work proposes a simple technical solution that allows interfacing reversible pass-transistor logic with conventional CMOS logic, represented here by an FPGA embedded in a commercial Xilinx Spartan-3E board. All proposed solutions have successfully been tested, which enables the FPGA to perform calculations directly on a reversible chip.
Stéphane Burignat, Michael Kirkedal Thomsen, Michał Klimczak, Mariusz Olczak, Alexis De Vos
Backmatter
Metadata
Title
Reversible Computation
Editors
Alexis De Vos
Robert Wille
Copyright Year
2012
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-29517-1
Print ISBN
978-3-642-29516-4
DOI
https://doi.org/10.1007/978-3-642-29517-1

Premium Partner

    Image Credits