Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 6th International Conference on Reversible Computation, RC 2014, held in Kyoto, Japan, in July 2014. The 14 contributions presented together with three invited talks were carefully reviewed and selected from 27 submissions. The papers are organized in topical sections on automata for reversible computation; notation and languages for reversible computation; synthesis and optimization for reversible circuits; validation and representation of quantum logic.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Concurrency and Reversibility

Reversible computation has attracted increasing interest in recent years, with applications in hardware, software and biochemistry. In this paper we show how to model reversibility in concurrent computation as realised abstractly in terms of event structures. Two different forms of event structures are presented and it is shown how to extend them with reversibility.
Irek Ulidowski, Iain Phillips, Shoji Yuen

Reversible Computing Using Adiabatic Superconductor Logic

The adiabatic quantum-flux-parametron (AQFP), which is adiabatic superconductor logic, is well suitable to realize reversible computing, because of the extremely high energy efficiency. In AQFP logic, dynamic energy dissipation can be significantly reduced by varying potential energy adiabatically during a switching event, which prevents non-adiabatic energy dissipation. In this paper, we report recent research results toward reversible computing using AQFP logic. First, we show experimental demonstrations of adiabatic switching operations of an AQFP gate. Then we discuss the minimum energy dissipation for an adiabatic switching operation using numerical analyses. Finally, we report reversible computing using AQFP gates and discuss the minimum energy dissipation required for logic operations using logically and physically reversible gates.
Naoki Takeuchi, Yuki Yamanashi, Nobuyuki Yoshikawa

Classical Control of Large-Scale Quantum Computers

The accelerated development of quantum technology has reached a pivotal point. Early in 2014, several results were published demonstrating that several experimental technologies are now accurate enough to satisfy the requirements of fault-tolerant, error corrected quantum computation. While there are many technological and experimental issues that still need to be solved, the ability of experimental systems to now have error rates low enough to satisfy the fault-tolerant threshold for several error correction models is a tremendous milestone. Consequently, it is now a good time for the computer science and classical engineering community to examine the classical problems associated with compiling quantum algorithms and implementing them on future quantum hardware. In this paper, we will review the basic operational rules of a topological quantum computing architecture and outline one of the most important classical problems that need to be solved; the decoding of error correction data for a large-scale quantum computer. We will endeavour to present these problems independently from the underlying physics as much of this work can be effectively solved by non-experts in quantum information or quantum mechanics.
Simon J. Devitt

Automata for Reversible Computation

Degrees of Reversibility for DFA and DPDA

The notion of k-reversibility is generalized to pushdown automata. A pushdown automaton is said to be (k,l)-reversible if its predecessor configurations can uniquely be computed by a pushdown automaton with input lookahead of size k and stack lookahead of size l. It turns out that there are problems which can be solved by (k + 1,1)-reversible pushdown automata, but not by (k,l)-reversible pushdown automata. So, infinite hierarchies dependent on the degree of reversibility are shown. On the other hand, any reversible pushdown automaton of degree (k,l + 1) can be simulated by a reversible pushdown automaton of degree (k,1). So, there are no hierarchies induced by the size of the stack lookahead. These results complement the situation for finite automata which is also discussed and presented in our setting.
Martin Kutrib, Thomas Worsch

Trace Complexity of Chaotic Reversible Cellular Automata

Delvenne, Kůrka and Blondel have defined new notions of computational complexity for arbitrary symbolic systems, and shown examples of effective systems that are computationally universal in this sense. The notion is defined in terms of the trace function of the system, and aims to capture its dynamics. We present a Devaney-chaotic reversible cellular automaton that is universal in their sense, answering a question that they explicitly left open. We also discuss some implications and limitations of the construction.
Jarkko Kari, Ville Salo, Ilkka Törmä

Notation and Languages for Reversible Computation

Arbitration and Reversibility of Parallel Delay-Insensitive Modules

We analyse the external behaviour of parallel delay-insensitive modules in order to formalise the notions of arbitration and reversibility, and investigate universality of classes of such modules. A new notation for parallel modules is developed, where inputs can be sets of signals, which is used to define arbitration and module inversion. We show that arbitrating modules are more expressive than non-arbitrating modules, and propose universal sets for two classes of non-arbitrating modules. We demonstrate previously unrealised constructions of M ×N Join and M ×N Fork in terms of purely reversible and non-arbitrating modules.
Daniel Morrison, Irek Ulidowski

Reference Counting for Reversible Languages

Modern programming languages and operating systems use heap memory that allows allocation and deallocation of memory to be decoupled, so they don’t follow a stack discipline. Axelsen and Glück have presented a reversible heap manager where allocation and deallocation are each other’s logical inverses: Freeing a block of memory is done by running the allocation procedure backwards.
Axelsen and Glück use this heap manager to sketch implementation of a simple reversible functional language where pattern matching a constructor is the inverse of construction, so pattern-matching implies deallocation. This requires the language to be linear: A pointer can not be copied and it can only be eliminated by deallocating the node to which it points.
We overcome this limitation by adding reference counts to nodes: Copying a pointer to a node increases the reference count of the node and eliminating a pointer decreases the reference count. We show reversible implementations of operations on nodes with reference counts. We then show these operations can be used when implementing a reversible functional language RCFUN to the reversible imperative language Janus.
Torben Ægidius Mogensen

Synthesis and Optimization of Reversible Circuits

Constructive Reversible Logic Synthesis for Boolean Functions with Special Properties

Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being quantum computing. The problem of implementing a given Boolean function using a set of elementary reversible logic gates is known as reversible logic synthesis. Though several generic reversible logic synthesis methods have been proposed so far, yet the scalability and implementation efficiency of these methods pose a difficult challenge. Compared to these generic synthesis methods, few reversible logic synthesis approaches for restricted classes of Boolean functions demonstrated better implementation efficiency and scalability. In this paper, we propose a novel constructive reversible logic synthesis technique for Boolean functions with special properties. The proposed techniques are scalable, fast and outperforms state-of-the-art generic reversible synthesis methods in terms of quantum cost, gate count and the number of lines.
Anupam Chattopadhyay, Soumajit Majumder, Chander Chandak, Nahian Chowdhury

RevVis: Visualization of Structures and Properties in Reversible Circuits

The recent interest in reversible computation led to plenty of (automatic) approaches for the design of the corresponding circuits. While this automation is desired in order to provide a proper support for the design of complex functionality, often a manual consideration and human intuition enable improvements or provide new ideas for design solutions. However, this manual interaction requires a good understanding of the structure or the properties of a reversible cascade which, with increasing circuit size, becomes harder to grasp. Visualization techniques that abstract irrelevant details and focus on intuitively displaying important structures or properties provide a solution to this problem and have already successfully been applied in other domains such as design of conventional software, hardware debugging, or Boolean satisfiability. In this work, we introduce RevVis, a graphical interface which visualizes structures and properties of reversible circuits. RevVis collects relevant data of a given reversible cascade and presents it in a simple but intuitive fashion. By this, RevVis unveils information on characteristic structures and properties of reversible circuits that could be utilized for further optimization. A case study demonstrates this by considering circuits obtained from several synthesis approaches.
Robert Wille, Jannis Stoppe, Eleonora Schönborn, Kamalika Datta, Rolf Drechsler

Templates for Positive and Negative Control Toffoli Networks

This paper proposes templates for positive and negative control Toffoli gates for post synthesis optimization of reversible circuits. Templates 1 − 5 can be applied to two adjacent Toffoli gates T 1(C 1,t 1) and T 2(C 2,t 2) where C i is the set of controls, |C 1| = |C 2|, and |t 1| = |t 2|. Templates 6 − 7 can be applied to two different size Toffoli gates T 1(C 1,t 1) and T 2(C 2,t 2) where C i is the set of controls, |C 1| = |C 2| and t i is the target, |t 1| = |t 2|. When applying our templates to circuits generated by the improved shared cube synthesis approach [14] a reduction in quantum cost was achieved for 98 of the 122 circuits. On average a 16.82% reduction in quantum cost was achieved, and in some cases up to 49.60% reduction was obtained.
Md Zamilur Rahman, Jacqueline E. Rice

Minimal Designs of Reversible Sequential Elements

In this paper we propose minimal designs of reversible sequential elements. The proposed designs have been synthesized using exact multiple control Toffoli network synthesis algorithm with SAT/SMT techniques. The designs have minimal gate count, minimal garbage bits, optimal quantum cost and optimal delay. The optimized sequential circuits are compared with results from earlier proposals. For a fair comparison, previous circuits designed using non-standard gates are converted into equivalent minimal NCT circuits.
Anindita Banerjee, Anirban Pathak, Gerhard W. Dueck

Synthesis and Optimization of Quantum Circuits

Quantum Circuit Optimization by Hadamard Gate Reduction

Due to its fault-tolerant gates, the Clifford+T library consisting of Hadamard (denoted by H), T, and CNOT gates has attracted interest in the synthesis of quantum circuits. Since the implementation of T gates is expensive, recent research is aiming at minimizing the use of such gates. It has been shown that T-depth optimizations can be implemented efficiently for circuits consisting only of T and CNOT gates and that H gates impede the optimization significantly.
In this paper, we investigate the role of H gates in reducing the T-count and T-depth for quantum circuits. To reduce the number of H gates, we propose several algorithms targeting different steps in the synthesis of reversible functions as quantum circuits.
Experiments show the effect of H gate reductions on the costs for T-count and T-depth. Our approach yields a significant improvement of up to 88% in the final T-depth compared to the best known T-depth optimization technique.
Nabila Abdessaied, Mathias Soeken, Rolf Drechsler

Mapping NCV Circuits to Optimized Clifford+T Circuits

The need to consider fault tolerance in quantum circuits has led to recent work on the optimization of circuits composed of Clifford+T gates. The primary optimization objectives are to minimize the T-count (number of T gates) and the T-depth (the number of groupings of parallel T gates). These objectives arise due to the high cost of the fault tolerant implementation of the T gate compared to Clifford gates. In this paper, we consider the mapping of a circuit composed of NOT, Controlled-NOT and square-root of NOT (NCV) gates to an equivalent circuit composed of Clifford+T gates. Our approach is heuristic and proceeds through three phases: (i) mapping a circuit of NCV gates to a Clifford+T circuit; (ii) optimization of the placement of the T gates in the Clifford+T circuit; and (iii) optimization of the subcircuits between T gate groupings. The approach takes advantage of earlier work on the optimization of NCV circuits. Examples are presented to show the approach presented here compares well with other approaches. Our approach does not add ancilla lines.
D. Michael Miller, Mathias Soeken, Rolf Drechsler

2D Qubit Layout Optimization for Topological Quantum Computation

Nowadays,Topological quantum computation is considered to be one of the most promising methods in realizing the future of quantum computation. The circuit model for topological quantum computation differs from the conventional quantum circuit model even in the logic level; which is multiple CNOT gates can only be performed at the same time if the order of qubits satisfies a certain property. Thus, there has been a wide research to find a good qubit order in one-dimension to satisfy such a property for topological quantum computation. This paper proposes a new method by using two-dimensional qubit layouts for topological quantum computation in order to reduce the computational time steps instead of one-dimensional qubit layouts used by the conventional computer. The general idea is to find a good two-dimensional qubit layout, so our propose is to find the best set of one-dimensional qubit layouts exactly by solving a minimum clique partition problem, and by then we will find the best two-dimensional layout that can embed as many of one-dimensional layouts as possible. The further task may need a very time-consuming(exponential number of) enumerations because we try to find the best possible solution by using an efficient graph structure called πDDs. Indeed, despite this, we still could not find a solution for larger cases more than 16 qubits (4x4 layout) case in our preliminary experiment. Thus, we also implement an SA-based method in order to find a good two-dimensional qubit layout for a reasonable time. Our preliminary experiment shows that the SA-based method works very well for larger cases.
Nurul Ain Binti Adnan, Shigeru Yamashita, Simon J. Devitt, Kae Nemoto

Validation and Representation of Quantum Logic

Cross-Level Validation of Topological Quantum Circuits

Quantum computing promises a new approach to solving difficult computational problems, and the quest of building a quantum computer has started. While the first attempts on construction were succesful, scalability has never been achieved, due to the inherent fragile nature of the quantum bits (qubits). From the multitude of approaches to achieve scalability topological quantum computing (TQC) is the most promising one, by being based on an flexible approach to error-correction and making use of the straightforward measurement-based computing technique. TQC circuits are defined within a large, uniform, 3-dimensional lattice of physical qubits produced by the hardware and the physical volume of this lattice directly relates to the resources required for computation. Circuit optimization may result in non-intuitive mismatches between circuit specification and implementation. In this paper we introduce the first method for cross-level validation of TQC circuits. The specification of the circuit is expressed based on the stabilizer formalism, and the stabilizer table is checked by mapping the topology on the physical qubit level, followed by quantum circuit simulation. Simulation results show that cross-level validation of error-corrected circuits is feasible.
Alexandru Paler, Simon Devitt, Kae Nemoto, Ilia Polian

Equivalence Checking in Multi-level Quantum Systems

Motivated by its superiority compared to conventional solutions in many applications, quantum computation has intensely been investigated from a theoretical, physical, and design perspective. While these investigations mainly focused on two-level quantum systems, recently also advantages and benefits of higher-level quantum systems became evident. Though this led to several approaches for the representation and realization of quantum functionality in different dimensions, no efficient solution for verifying their equivalence has been proposed yet. In the present paper, we address this problem. We propose a scheme which is capable of verifying the equivalence of two quantum operations regardless of the dimension of their underlying quantum system. The proposed scheme can be incorporated into data-structures such as Quantum Multiple-Valued Decision Diagrams (QMDD) particularly suited for the representation of quantum functionality and, by this, enables an efficient verification. Experiments confirm the efficiency of the proposed approach.
Philipp Niemann, Robert Wille, Rolf Drechsler

BDD Operations for Quantum Graph States

A quantum graph state determined by an underlying graph is very fundamental in quantum computation and information, such as measurement-based quantum computing, stabilizer states and codes. For a graph state, a reversible operation, called the local complementation, transforms it to another graph state, and local Clifford operations map it to a stabilizer state. Besides these operations, taking the inner product of a graph/stabilizer state with an arbitrary complete product state leads to analyzing measurements for an arbitrary basis and solving a #P-complete problem of computing the partition function of a graph in Ising model. We recently observe that a graph state naturally corresponds to a Boolean function associated with a graph, and apply our top-down construction algorithm for the function. In this paper, we further discuss BDD operations for the above-mentioned operations on them. Specific bounds on the sizes and computational times of these BDDs are given in terms of the linear rank-width of a graph, and an efficient exact exponential algorithm for the Ising partition function is derived.
Hidefumi Hiraishi, Hiroshi Imai

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise