Reversible Computation

Computational complexity theory is the study of the fundamental resource requirements associated with the solutions of different problems. Time, space (memory) and randomness (number of coin tosses) are some of the resource types that have been examined both independently, and in terms of tradeoffs between each other, in this context. Since it is well known that each bit of information “forgotten” by a device is linked to an unavoidable increase in entropy and an associated energy cost, one can also view energy as a computational resource. Constant-memory machines that are only allowed to access their input strings in a single left-to-right pass provide a good framework for the study of energy complexity. There exists a natural hierarchy of regular languages based on energy complexity, with the class of reversible languages forming the lowest level. When the machines are allowed to make errors with small nonzero probability, some problems can be solved with lower energy cost. Tradeoffs between energy and other complexity measures can be studied in the framework of Turing machines or two-way finite automata, which can be rewritten to work reversibly if one increases their space and time usage.

Process calculi such as CCSor the \(\pi \)-calculus provide specification languages for the study and correctness of communication protocols. They also served in detailing subtle differences between formalisms to represent infinite behaviors, notably in expressiveness [7, 16]. To our knowledge, such results were never investigated from a reversible perspective. One question we would like to answer is how recursion, replication and iteration compare in the reversible setting. Of course, comparing them requires to define them first, and this short note highlights some of the difficulties in defining replication for reversible concurrent calculi.

Reversible computation is a paradigm allowing computation to proceed not only in the usual, forward direction, but also backwards. Reversible computation has been studied in a variety of models, including sequential and concurrent programming languages, automata, process calculi, Turing machines, circuits, Petri nets, event structures, term rewriting, quantum computing, and others. Also, it has found applications in areas as different as low-power computing, debugging, simulation, robotics, database design, and biochemical modeling. Thus, while the broad idea of reversible computation is the same in all the areas, it has been interpreted and adapted to fit the various settings. The existing notions of reversible computation however have never been compared and categorized in detail. This work aims at being a first stepping stone towards a taxonomy of the approaches that co-exist under the term reversible computation. We hope that such a work will shed light on the relation among the various approaches.

The computational complexity of problems related to reaction systems (RSs) such as, e.g., reachability, simulation, etc., are well understood. We investigate the complexity of some of these problems for reversible RSs. Since some of the computational complexity (lower bound) proofs in the general case rely on reductions from Turing machine problems here the main challenge is to present constructions that ensure the reversibility of the RS that encodes Turing machine configurations by sets, which allows ambiguous representation. For the problems under consideration we can show that there is no difference in complexity for reversible RSs compared to the general case. One exception is the question of the existence of a reversible subcomputation.

Growing interest in reversible computation has led to an accelerated development of reversible programming languages and software, which reinforces the need for optimizing compilers. In this paper, we report on our recent progress on optimizing reversible intraprocedural control flow. Like previous work on the optimization of reversible programs, the techniques in this paper are based on the reversible intermediate language RSSA. A formalization of RSSA’s control flow as an extended directed multigraph is introduced. This serves as a basis for three analysis and optimization techniques for reversible control flow, which enable the identification and removal of a) unreachable code, b) branches between strictly consecutive code sequences, and c) immediately redirected branches. To our knowledge, this is the first work being done to investigate the optimization of reversible control flow.

Tail recursive functions allow for a wider range of optimisations than general recursive functions. For this reason, much research has gone into the transformation and optimisation of this family of functions, in particular those written in continuation passing style (CPS).

Though the CPS transformation, capable of transforming any recursive function to an equivalent tail recursive one, is deeply problematic in the context of reversible programming (as it relies on troublesome features such as higher-order functions), we argue that relaxing (local) reversibility to (global) invertibility drastically improves the situation. On this basis, we present an algorithm for tail recursion conversion specifically for invertible functions. The key insight is that functions introduced by program transformations that preserve invertibility, need only be invertible in the context in which the functions subject of transformation calls them. We show how a bespoke data type, corresponding to such a context, can be used to transform invertible recursive functions into a pair of tail recursive function acting on this context, in a way where calls are highlighted, and from which a tail recursive inverse can be straightforwardly extracted.

Training a multilayered neural network involves execution of the network on the training data, followed by calculating the error between the predicted and actual output, and then performing backpropagation to update the network’s weights in order to minimise the overall error. This process is repeated many times, with the network updating its weights until it produces the desired output with a satisfactory level of accuracy. It requires storage in memory of activation and gradient data for each layer during each training run of the network. This paper surveys the main approaches to recomputing the needed activation and gradient data instead of storing it in memory. We discuss how these approaches relate to reversible computation techniques.

Reversible programming is an unconventional paradigm that offers new ways to construct software. When programs have inherent inverse counterparts, such as compression/decompression, the invertibility of reversible implementations enables a “write once, verify once” approach. The nature of today’s computers is, however, irreversible.

This work-in-progress contribution explores the dereversibilization of reversible source programs into irreversible target programs. As a first step into this space, we explore the use of state-of-the-art Satisfiability-Modulo-Theories (SMT) solvers to statically remove redundant assertions. We divide the problem space into two parts: High-level dereversibilization of Janus-like source programs and classical compilation to machine code.

In this contribution, we focus on the semantics-preserving removal of assertions from reversible control-flow statements. Our prototype reduces the size of the assembly code and marks the first step towards automatic dereversibilization and new opportunities of using reversible programs.

The string matching problem is one of the fundamental problems in computer science with applications in a variety of fields. Basically, it consists in finding all occurrences of a given pattern within a larger text. Despite its straightforward formulation, it has given rise to a huge number of solutions based on very different approaches and varied computational paradigms. But it is only very recently that the first solution based on quantum computation has been proposed by Niroula and Nam, allowing the problem to be solved in \(\mathcal {O}(\sqrt{n}(\log ^2(n)+\log (m)))\) time, with a quadratic speed-up compared to classical computation. To date, these two research fields have remained almost entirely separate, mainly because the technical aspects typical of the quantum computation field remain almost obscure to those involved in text processing. This paper aims to reconcile the two fields by unfolding the technical aspects of the Niroula-Nam quantum solution and providing a detailed general procedure working in \(\mathcal {O}(\sqrt{n}\log ^2(n))\) time that can be used as a framework for solving other string matching problems, including nonstandard ones. In this direction, the paper also proposes an extension of the algorithm to the approximate string matching problem with swaps, reporting the configuration of the occurrence together with its position, and achieving a quasi-linear \(\mathcal {O}(\sqrt{n}\log ^2(n))\) time complexity when \(m=\mathcal {O}(\log (n))\).

Pebble games are usually used to study space/time trade-offs. Recently, spooky pebble games were introduced to study classical space/quantum space/time trade-offs for simulation of classical circuits on quantum computers. In this paper, the spooky pebble game framework is applied for the first time to general circuits. Using this framework we prove an upper bound for quantum space in the spooky pebble game. Moreover, we present a solver for the spooky pebble game based on a SAT solver. This spooky pebble game solver is empirically evaluated by calculating optimal classical space/quantum space/time trade-offs. Within limited runtime, the solver could find a strategy reducing quantum space when classical space is taken into account, showing that the spooky pebble model is useful to reduce quantum space.

Uncomputation is an essential part of reversible computing and plays a vital role in quantum computing. Using this technique, memory resources can be safely deallocated without performing a non-reversible deletion process. For the case of quantum computing, several algorithms depend on this as they require disentangled states in the course of their execution. Thus, uncomputation is not only about resource management, but is also required from an algorithmic point of view. However, synthesizing uncomputation circuits is tedious and can be automated. In this paper, we describe the interface for automated generation of uncomputation circuits in our Qrisp framework. Our algorithm for synthesizing uncomputation circuits in Qrisp is based on an improved version of “Unqomp”, a solution presented by Paradis et al. Our paper also presents some improvements to the original algorithm, in order to make it suitable for the needs of a high-level programming framework. Qrisp itself is a fully compilable, high-level programming language/framework for gate-based quantum computers, which abstracts from many of the underlying hardware details. Qrisp’s goal is to support a high-level programming paradigm as known from classical software development.

The matrices that can be exactly represented by a circuit over the Toffoli-Hadamard gate set are the orthogonal matrices of the form \(M/\sqrt{2}{}^k\), where M is an integer matrix and k is a nonnegative integer. The exact synthesis problem for this gate set is the problem of constructing a circuit for a given such matrix. Existing methods produce circuits consisting of \(O(2^n\log (n)k)\) gates, where n is the dimension of the matrix. In this paper, we provide two improved synthesis methods. First, we show that a technique introduced by Kliuchnikov in 2013 for Clifford+T circuits can be straightforwardly adapted to Toffoli-Hadamard circuits, reducing the complexity of the synthesized circuit from \(O(2^n\log (n)k)\) to \(O(n^2\log (n)k)\). Then, we present an alternative synthesis method of similarly improved cost, but whose application is restricted to circuits on no more than three qubits. Our results also apply to orthogonal matrices over the dyadic fractions, which correspond to circuits using the 2-qubit gate \(H\otimes H\), rather than the usual single-qubit Hadamard gate H.

Process calculi (\(\pi \)-calculus, CCS, ambient calculus, etc.) are an abstraction of concurrent systems useful to study, specify and verify distributed programs and protocols. This project, IRDC, is concerned with the implementation of such an abstraction for reversible process calculi. It is, to the best of our knowledge, the first such publicly available tool. We briefly present the current state of this tool, some of its features, and discuss its future developments.

Quantum computing offers substantial speedup over conventional computing in solving certain computationally hard problems. The emergence of quantum computers in recent years has motivated researchers to develop design automation tools to map quantum circuits to such platforms. One major challenge is to limit the noise or computational error during gate operations; in particular, errors are higher when gates operate on non-neighbor qubits. A common approach to tackle this problem is to make the circuits Nearest-Neighbor (NN) compliant by inserting either Swap gates or CNOT templates. Reduction of gate overhead also becomes important as it serves to limit the overall noise and error. In some recent works, mapping of quantum circuits to hexagonal qubit architecture have been investigated. Hexagonal layout of qubits offers extended neighborhood that helps to reduce the number of Swap or additional CNOT gates required for NN-compliance. Existing approaches incur high gate overheads that can be reduced by improved gate mapping strategies with better cost metrics. The present work proposes one such approach using a priority-based cost metric. The proposed cost-metric is general and can be applied to any architectures; however, in this work we show its benefit for hexagonal architecture. Experiments on benchmark circuits confirm that the proposed method reduces gate overhead by \(29\%\) over a very recent work based on greedy mapping.

Elementary gate decomposition of larger Toffoli operations is often carried out using additional qubits (ancilla). The number of gates and the circuit depth vary in such transformation depending on the type of ancilla used (clean or dirty). The present Noisy Intermediate Scale Quantum (NISQ) devices have limited number of coherent qubits with faulty native operation support. Superconducting devices also have coupling restrictions or Nearest-Neighbor (NN) constraints, which require additional gates to map the transformed netlist for execution. While the mapping overhead is correlated with the number of 2-qubit gates and involved qubits, the fidelity of execution is inversely proportional to the number of gates and circuit depth. There is a tradeoff in devising the transpilation (i.e. low-level transformation and mapping) approach — dirty ancilla demands less qubits and overhead at the expense of more gates and depth as compared to clean ancilla, which involves less gates and depth at the expense of more qubits and overhead. This paper analyzes the disparity in gates, depth and qubits between: (i) the low-level transformation approaches without considering device coupling information, and (ii) the mapping schemes based on netlist transformation using a specific type of ancilla. We analyze the benefits of using NN-constraints at the transformation stage, and the impact of distributing clean ancilla across architectures. We have carried out experiments on IBM Q20 and Hexagonal Q20 architectures, which show improvements of 17% and 13% respectively in terms of number of gates.