nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Reversible Computation

5th International Conference, RC 2013, Victoria, BC, Canada, July 4-5, 2013. Proceedings

herausgegeben von: Gerhard W. Dueck, D. Michael Miller

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 5th International Conference on Reversible Computation, RC 2013, held in Victoria, BC, Canada, in July 2013. The 19 contributions presented together with one invited paper were carefully reviewed and selected from 37 submissions. The papers are organized in topical sections on physical implementation; arithmetic; programming and data structures; modelling; synthesis and optimization; and alternative technologies.

Inhaltsverzeichnis

Frontmatter

Invited Address

Efficient Algorithms for Universal Quantum Simulation

Abstract

A universal quantum simulator would enable efficient simulation of quantum dynamics by implementing quantum-simulation algorithms on a quantum computer. Specifically the quantum simulator would efficiently generate qubit-string states that closely approximate physical states obtained from a broad class of dynamical evolutions. I provide an overview of theoretical research into universal quantum simulators and the strategies for minimizing computational space and time costs. Applications to simulating many-body quantum simulation and solving linear equations are discussed

Barry C. Sanders

Physical Implementation

Reversible Delay-Insensitive Distributed Memory Modules

Abstract

We introduce two eight-line one-bit memory modules which are useful in the modelling of distributed memory in asynchronous delay-insensitive circuits. Our modules are reversible and together with the Merge element are serial-universal. We show how they can be used to realise Morita’s Rotary Element and other reversible modules thus showing their computation universality. We also propose three sets of modules that are universal for all modules.

Daniel Morrison, Irek Ulidowski

Energy Recovery and Logical Reversibility in Adiabatic CMOS Multiplier

Abstract

Overcoming the IC power challenge requires signal energy recovery, which can be achieved utilizing adiabatic charging principles and logically reversible computing in the circuit design. This paper demonstrates the energy-efficiency of a Bennett-clocked adiabatic CMOS multiplier via a simulation model. The design is analyzed on the logic gate level to determine an estimate for the number of irreversible bit erasures occurring in a combinatorial implementation, showing considerable potential for minimizing the logical information loss.

Ismo Hänninen, Hao Lu, Craig S. Lent, Gregory L. Snider

Comparing CMOS-Based and NEMS-Based Adiabatic Logic Circuits

Abstract

In this paper, a detailed comparison between the expected performance of CMOS-based and nanoelectromechanical systems (NEMS) based adiabatic logic circuits is presented. The modeling of the NEMS devices is done using a 1-dimensional reduced order model (1d ROM) of the electromechanical switches. This model will give an honest analytical depiction of the NEMS-based adiabatic circuits. The performance of NEMS-based circuits compares favorably with that of CMOS-based circuits. To the best knowledge of the authors, this is the first reported detailed comparison between NEMS and CMOS devices for adiabatic circuits.

Samer Houri, Alexandre Valentian, Hervé Fanet

Arithmetic

Strength of the Reversible, Garbage-Free 2 k ±1 Multiplier

Abstract

Recently, a reversible garbage-free 2^k ±1 constant-multiplier circuit was presented by Axelsen and Thomsen. This was the first construction of a garbage-free, reversible circuit for multiplication with non-trivial constants. At the time, the strength, that is, the range of constants obtainable by cascading these circuits, was unknown.

In this paper, we show that there exist infinitely many constants we cannot multiply by using cascades of 2^k±1-multipliers; in fact, there exist infinitely many primes we cannot multiply by. Using these results, we further provide an algorithm for determining whether one can multiply by a given constant using a cascade of 2^k ±1-multipliers, and for generating the minimal cascade of 2^k ±1-multipliers for an obtainable constant, giving a complete characterization of the problem. A table of minimal cascades for multiplying by small constants is provided for convenience.

Eva Rotenberg, James Cranch, Michael Kirkedal Thomsen, Holger Bock Axelsen

Constant-Factor Optimization of Quantum Adders on 2D Quantum Architectures

Abstract

Quantum arithmetic circuits have practical applications in various quantum algorithms. In this paper, we address quantum addition on 2-dimensional nearest-neighbor architectures based on the work presented by Choi and Van Meter (JETC 2012). To this end, we propose new circuit structures for some basic blocks in the adder, and reduce communication overhead by adding concurrency to consecutive blocks and also by parallel execution of expensive Toffoli gates. The proposed optimizations reduce total depth from \(140\sqrt n+k_1\) to \(92\sqrt n+k_2\) for constants k ₁,k ₂ and affect the computation fidelity considerably.

Mehdi Saeedi, Alireza Shafaei, Massoud Pedram

Garbage-Free Reversible Constant Multipliers for Arbitrary Integers

Abstract

We present a method for constructing reversible circuitry for multiplying integers by arbitrary integer constants. The method is based on Mealy machines and gives circuits whose size are (in the worst case) linear in the size of the constant. This makes the method unsuitable for large constants, but gives quite compact circuits for small constants. The circuits use no garbage or ancillary lines.

Torben Ægidius Mogensen

Identities in Modular Arithmetic from Reversible Coherence Operations

Abstract

This paper investigates some issues arising in categorical models of reversible logic and computation. Our claim is that the structural (coherence) isomorphisms of these categorical models, although generally overlooked, have decidedly non-trivial computational content. The theory of categorical coherence is based around reversible structural operations (canonical isomorphisms) that allow for transformations between related, but distinct, mathematical structures. A number of coherence theorems are commonly used to treat these transformations as though they are identity maps, from which point onwards they play no part in computational models. We simply wish to point out that doing so overlooks some significant computational content.

We give a single example (taken from an uncountably infinite set of similar examples, and based on structures used in models of reversible logic and computation) of a category whose structural isomorphisms manipulate modulo classes of natural numbers. We demonstrate that the coherence properties that usually allow us to ignore these structural isomorphisms in fact correspond to countably infinite families of non-trivial identities in modular arithmetic. Further, proving the correctness of these equalities without recourse to the theory of categorical coherence appears to be a hard task.

Peter M. Hines

Programming and Data Structures

Reversible Representation and Manipulation of Constructor Terms in the Heap

Abstract

We currently have limited understanding of how complex data (e.g. algebraic data types) can be represented and manipulated in reversible machine code, in particular without generating garbage. In this paper we present methods for representing and manipulating binary trees (constructor terms) in the heap of a reversible machine. We also give methods for enforcing the so-called first-match policy for a simplified version of the recent reversible functional language RFUN by Yokoyama et al., and simple methods to support let-calls via stack environments.

Holger Bock Axelsen, Robert Glück

An Introduction to Quantum Programming in Quipper

Abstract

Quipper is a recently developed programming language for expressing quantum computations. This paper gives a brief tutorial introduction to the language, through a demonstration of how to make use of some of its key features. We illustrate many of Quipper’s language features by developing a few well known examples of Quantum computation, including quantum teleportation, the quantum Fourier transform, and a quantum circuit for addition.

Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, Benoît Valiron

On the “Q” in QMDDs: Efficient Representation of Quantum Functionality in the QMDD Data-Structure

Abstract

The Quantum Multiple-valued Decision Diagram (QMDD) data-structure has been introduced as a means for an efficient representation and manipulation of transformation matrices realized by quantum or reversible logic circuits. A particular challenge is the handling of arbitrary complex numbers as they frequently occur in quantum functionality. These numbers are represented through edge weights which, however, represent a severe obstacle with respect to canonicity, modifiability, and applicability of QMDDs. Previously introduced approaches did not provide a satisfactory solution to these obstacles. In this paper, we propose an improved factorization scheme for complex numbers that ensures a canonical representation while, at the same time, allows for local changes. We demonstrate how the proposed solution can be exploited to improve the data-structure itself (e.g. through variable re-ordering enabled by the advanced modifiability) and how applications such as equivalence checking benefit from that.

Philipp Niemann, Robert Wille, Rolf Drechsler

Modelling

Modelling of Bonding with Processes and Events

Abstract

We introduce two forms of modelling of systems that consist of objects that are combined together by the means of bonds. In reaction systems for bonding we define how bonds are created and dissolved via reduction-style semantics. The usefulness of reaction systems is illustrated with examples taken from software engineering and biochemistry. We also introduce reversible event structures and define the notion of configuration. We then discuss how to give semantics of reaction systems for bonding in terms of reversible event structures.

Iain Phillips, Irek Ulidowski, Shoji Yuen

Universal Gates in Other Universes

Abstract

I describe a new formalization for computation which is similar to traditional circuit models but which depends upon the choice of a family of [semi]groups – essentially, a choice of the structure group of the universe of the computation. Choosing the symmetric groups results in the reversible version of classical computation; the unitary groups give quantum computation. Other groups can result in models which are stronger or weaker than the traditional models, or are hybrids of classical and quantum computation.

One particular example, built out of the semigroup of doubly stochastic matrices, yields classical but probabilistic computation, helping explain why probabilistic computation can be so fast. Another example is a smaller and entirely ℝeal version of the quantum one which uses a (real) rotation matrix in place of the (complex, unitary) Hadamard gate to create algorithms which are exponentially faster than classical ones.

I also articulate a conjecture which would help explain the different powers of these different types of computation, and point to many new avenues of investigation permitted by this model.

Jonathan A. Poritz

Time-Symmetric Machines

Abstract

Reversible computational models with discrete internal states are said to be time-symmetric, if they can go back and forth in time by applying the same transition function. The direction in time is adjusted by a weak transformation of the phase-space, that is, an involution. So, these machines themselves cannot distinguish whether they run forward or backward in time. From this viewpoint, finite state machines and pushdown machines are studied in detail. In essence, it turns out that there are reversible machines which are not time-symmetric, but equivalent time-symmetric machines can effectively be constructed. The notion of time-symmetry is discussed, several examples are given, and further results concerning unary inputs and descriptional complexity issues are shown.

Martin Kutrib, Thomas Worsch

Synthesis and Optimization

Reversible Circuit Synthesis of Symmetric Functions Using a Simple Regular Structure

Abstract

In this paper, we introduce a new method to realize symmetric functions with reversible circuits. In contrast to earlier methods, our solution deploys a simple and regular cascade structure composed of low-cost gates which enables significant reductions with respect to quantum costs. However, the number of garbage outputs increases slightly. To overcome this, we next propose an optimized design by reusing the garbage outputs. The resulting design thus offers a powerful approach towards reversible synthesis of symmetric Boolean functions.

Arighna Deb, Debesh K. Das, Hafizur Rahaman, Bhargab B. Bhattacharya, Robert Wille, Rolf Drechsler

White Dots do Matter: Rewriting Reversible Logic Circuits

Abstract

The increased effort in recent years towards methods for computer aided design of reversible logic circuits has also lead to research in algorithms for optimising the resulting circuits; both with higher-level data structures and directly on the reversible circuits. To obtain structural patterns that can be replaced by a cheaper realisation, many direct algorithms apply so-called moving rules; a simple form of rewrite rules that can only swap gate order.

In this paper we first describe the few basic rules that are needed to perform rewriting directly on reversible logic circuits made from general Toffoli circuits. We also show how to use these rules to derive more complex formulas. The major difference compared to existing approaches is the use of negative controls (white dots), which significantly increases the algebraic strength. We show how existing optimisation approaches can be adapted as problems based on our rewrite rules.

Finally, we outline a path to generalising the rewrite rules by showing their forms for reversible control-gates. This can be used to expand our method to other gates such as the controlled-swap gate or quantum gates.

Mathias Soeken, Michael Kirkedal Thomsen

Exploiting Negative Control Lines in the Optimization of Reversible Circuits

Abstract

The development of approaches for synthesis and optimization of reversible circuits received significant attention in the past. This is partly due to the increasing emphasis on low power design methodologies, and partly motivated by recent works in quantum computation. While most of them relied on a gate library composed of multiple-control Toffoli (MCT) gates with positive control lines, some initial works also exist which additionally incorporate negative control lines. This usually leads to smaller circuits with respect to the number of gates as well as the corresponding quantum costs. However, despite these benefits, negative control lines have hardly been considered in post-synthesis optimization of reversible circuits so far. In this paper, we address this issue. We are presenting an optimization scheme inspired by template matching which explicitly makes use of negative control lines. Experimental evaluations demonstrate that exploiting negative control lines in fact lead to a reduction in the number of gates and the quantum costs by up to 60% and 25%, respectively.

Kamalika Datta, Gaurav Rathi, Robert Wille, Indranil Sengupta, Hafizur Rahaman, Rolf Drechsler

Reducing the Depth of Quantum Circuits Using Additional Circuit Lines

Abstract

The synthesis of Boolean functions, as they are found in many quantum algorithms, is usually conducted in two steps. First, the function is realized in terms of a reversible circuit followed by a mapping into a corresponding quantum realization. During this process, the number of lines and the quantum costs of the resulting circuits have mainly been considered as optimization objectives thus far. However, beyond that also the depth of a quantum circuit is vital. Although first synthesis approaches that consider depth have recently been introduced, the majority of design methods did not consider this metric.

In this paper, we introduce an optimization approach aiming for the reduction of depth in the process of mapping a reversible circuit into a quantum circuit. For this purpose, we present an improved (local) mapping of single gates as well as a (global) optimization scheme considering the whole circuit. In both cases, we incorporate the idea of exploiting additional circuit lines which are used in order to split a chain of serial gates. Our optimization techniques enable a concurrent application of gates which significantly reduces the depth of the circuit. Experiments show that reductions of approx. 40% on average can be achieved when following this scheme.

Nabila Abdessaied, Robert Wille, Mathias Soeken, Rolf Drechsler

Alternative Technologies

Quantum Process Calculus for Linear Optical Quantum Computing

Abstract

We extend quantum process calculus in order to describe linear optical elements. In all previous work on quantum process calculus a qubit was considered as the information encoded within a 2 dimensional Hilbert space describing the internal states of a localised particle, most often realised as polarisation information of a single photon. We extend quantum process calculus by allowing multiple particles as information carriers, described by Fock states. We also consider the transfer of information from one particular qubit realisation (polarisation) to another (path encoding), and describe post-selection. This allows us for the first time to describe linear optical quantum computing (LOQC) in terms of quantum process calculus. We illustrate this approach by presenting a model of an LOQC CNOT gate.

Sonja Franke-Arnold, Simon J. Gay, Ittoop V. Puthoor

Logically and Physically Reversible Natural Computing: A Tutorial

Abstract

This year marks the 40^th anniversary of Charles Bennett’s seminal paper on reversible computing. Bennett’s contribution is remembered as one of the first to demonstrate how any deterministic computation can be simulated by a logically reversible Turing machine. Perhaps less remembered is that the same paper suggests the use of nucleic acids to realise physical reversibility. In context, Bennett’s foresight predates Leonard Adleman’s famous experiments to solve instances of the Hamiltonian path problem using strands of DNA — a landmark date for the field of natural computing — by more than twenty years. The ensuing time has seen active research in both reversible computing and natural computing that has been, for the most part, unrelated. Encouraged by new, experimentally viable DNA computing models, there is a resurgent interest in logically reversible computing by the natural computing community. We survey these recent results, and their underlying ideas, which demonstrate the potential for logically and physically reversible computation using nucleic acids.

Chris Thachuk

Backmatter

Titel: Reversible Computation
herausgegeben von: Gerhard W. Dueck
D. Michael Miller
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-38986-3
Print ISBN: 978-3-642-38985-6
DOI: https://doi.org/10.1007/978-3-642-38986-3

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Invited Address

Efficient Algorithms for Universal Quantum Simulation

Physical Implementation

Reversible Delay-Insensitive Distributed Memory Modules

Energy Recovery and Logical Reversibility in Adiabatic CMOS Multiplier

Comparing CMOS-Based and NEMS-Based Adiabatic Logic Circuits

Arithmetic

Strength of the Reversible, Garbage-Free 2 k ±1 Multiplier

Constant-Factor Optimization of Quantum Adders on 2D Quantum Architectures

Garbage-Free Reversible Constant Multipliers for Arbitrary Integers

Identities in Modular Arithmetic from Reversible Coherence Operations

Programming and Data Structures

Reversible Representation and Manipulation of Constructor Terms in the Heap

An Introduction to Quantum Programming in Quipper

On the “Q” in QMDDs: Efficient Representation of Quantum Functionality in the QMDD Data-Structure

Modelling

Modelling of Bonding with Processes and Events

Universal Gates in Other Universes

Time-Symmetric Machines

Synthesis and Optimization

Reversible Circuit Synthesis of Symmetric Functions Using a Simple Regular Structure

White Dots do Matter: Rewriting Reversible Logic Circuits

Exploiting Negative Control Lines in the Optimization of Reversible Circuits

Reducing the Depth of Quantum Circuits Using Additional Circuit Lines

Alternative Technologies

Quantum Process Calculus for Linear Optical Quantum Computing

Logically and Physically Reversible Natural Computing: A Tutorial

Backmatter

Premium Partner