Reversible Computation

We present tools for resource-aware compilation of higher-level, irreversible programs into lower-level, reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks. We discuss a number of examples to illustrate our compilation strategy for problems at scale, including a reversible implementation of hash functions such as SHA-256, automatic generation of reversible integer arithmetic from irreversible descriptions, as well as a test-bench of Boolean circuits that is used by the classical Circuits and Systems community. Our main findings are that, when compared with Bennett’s original “compute-copy-uncompute”, it is possible to reduce the space complexity by 75% or more, at the price of having an only moderate increase in circuit size as well as in compilation time. Finally, we discuss some emerging new paradigms in quantum circuit synthesis, namely the use of dirty ancillas to save overall memory footprint, probabilistic protocols such as the RUS framework which can help to reduce the gate complexity of rotations, and synthesis methods for higher-dimensional quantum systems.

Information loss from a computation implies energy dissipation due to Landauer’s Principle. Thus, increasing the amount of useful computational work that can be accomplished within a given energy budget will eventually require increasing the degree to which our computing technologies avoid information loss, i.e., are logically reversible. But the traditional definition of logical reversibility is actually more restrictive than is necessary to avoid information loss and energy dissipation due to Landauer’s Principle. As a result, the operations that have traditionally been viewed as the atomic elements of reversible logic, such as Toffoli gates, are not really the simplest primitives that one can use for the design of reversible hardware. Arguably, a complete theoretical framework for reversible computing should provide a more general, parsimonious foundation for practical engineering. To this end, we use a rigorous quantitative formulation of Landauer’s Principle to develop the theory of Generalized Reversible Computing (GRC), which precisely characterizes the minimum requirements for a computation to avoid information loss and the consequent energy dissipation, showing that a much broader range of computations are, in fact, reversible than is acknowledged by traditional reversible computing theory. This paper summarizes the foundations of GRC theory and briefly presents a few of its applications.

By former and recent results the model of reversible deterministic finite automata is well understood. On the other hand, reversible nondeterministic finite automata and their accepted languages have not systematically been considered in the literature. Here it turns out that reversible nondeterministic finite automata (\(\text {REV-NFA}\)s) are more powerful compared to their reversible deterministic counterparts, but still cannot accept all regular languages. Moreover, we compare the family of languages accepted by \(\text {REV-NFA}\)s to the language families accepted by deterministic and nondeterministic finite state automata with irreversibility degree k. Besides these results on the computational power of \(\text {REV-NFA}\)s we consider closure properties of the language family induced by these devices.

This paper introduces a new paradigm to implement logic gates based on variable capacitance components instead of transistor elements. Using variable capacitors and Bennett clocking, this new logic family is able to discriminate logic states and cascade combinational logic operations. In order to demonstrate this, we use the capacitive voltage divider circuit with the variable capacitor modulated by an input bias state to the set output state. We propose the design of a four-terminal capacitive element which is the building block of this new logic family. Finally, we build a Verilog-A model of an electrically-actuated MEMS capacitive element and analyze the energy transfer and losses within this device during adiabatic actuation. The proposed model will be used for capacitive-based adiabatic logic circuit design and analysis, including construction of reversible gates.

We extend the reversible language Janus with support for class-based object-oriented programming, class inheritance and subtype-polymorphism. We describe how to implement these features on reversible hardware - with emphasis on the implementation of reversible dynamic dispatch using virtual method tables. Our translation is effective (i.e. garbage-free) and we demonstrate its practicality by implementation of a fully-featured compiler targeting the reversible assembly language PISA.

With the emergence of reversible circuits as an energy-efficient alternative of classical circuits, ensuring fault tolerance in such circuits becomes a very important problem. Parity-preserving reversible logic design is one viable approach towards fault detection. Interestingly, most of the existing designs are ad hoc, based on some pre-defined parity preserving reversible gates as building blocks. In the current work, we propose a systematic approach towards parity preserving reversible circuit design. We prove a few theoretical results and present two algorithms, one from reversible specification to parity preserving reversible specification and another from irreversible specification to parity preserving reversible specification. We derive an upper-bound for the number of garbage bits for our algorithm and perform its complexity analysis. We also evaluate the effectiveness of our approach by extensive experimental results and compare with the state-of-the-art practices. To our knowledge, this is the first work towards systematic design of parity preserving reversible circuit and more research is needed in this area to make this approach more scalable.

Computing classical functions is at the core of many quantum algorithms. Conceptually any classical, irreversible function can be carried out by a Toffoli network in a reversible way. However, the Bennett method to obtain such a network in a “clean” form, i.e., a form that can be used in quantum algorithms, is highly space-inefficient. We present REVS, a tool that allows to trade time against space, leading to circuits that have a significantly smaller memory footprint when compared to the Bennett method. Our method is based on an analysis of the data dependency graph underlying a given classical program. We report the findings from running the tool against several benchmarks circuits to highlight the potential space-time tradeoffs that REVS can realize.

In this paper, a transformation method is presented which converts complementary control lines of a reversible gate pair to equal/similar control lines. A set of optimization rules is discussed that take advantage of the increased equal control lines to reduce the cost. A greedy optimization algorithm, which uses the proposed transformation method and the optimization rules, is presented. Results for a large set of benchmarks confirm that the proposed algorithm performs better when compared with other Exclusive-OR Sum-Of-Product (ESOP) based methods available in the literature.

Reversible logic finds applications in emerging technologies such as quantum computing, optical computing, etc. This has motivated research into development of synthesis and optimization algorithms for reversible circuits. In this paper, a set of rules is presented for the decomposition of a pair of multi-control Toffoli gates (MCT) to reduce the quantum cost of reversible circuits. These rules find pairs of MCT gates, which when decomposed to a network of smaller gates, result in reduced quantum cost. This technique is used in conjunction with an Exclusive-OR Sum-Of-Product (ESOP) based reversible circuit synthesis algorithm to check its efficiency. Results indicate that there is a reduction in quantum cost of several benchmark circuits when compared to the known ESOP based synthesis algorithms.

This paper presents a quantum-level realization and synthesis approach using SWAP and Fredkin (SF) gates. Our quantum realization of negative-controlled Fredkin gate requires five 2-qubit elementary quantum gates, the same as that required for realizing a positive-controlled Fredkin gate. We also propose and evaluate the performance of a synthesis approach using SF gates for realizing conservative reversible functions. Our result shows that circuit realization for conservative function using SF gates is more efficient than Toffoli gates. We achieve up to \(87\%\) improvement in gate count and quantum cost for \((4 \times 4)\) conservative reversible functions.

In a quantum logic circuit, the minimum number of qubits required in a quantum error-correcting code (QECC) to correct a single error was shown by Laflamme to be five. Due to the presence of multi-control gates in the circuit block for a 5-qubit QECC, this block cannot be readily implemented with present day technology. Further, the fault-tolerant decomposition of the QECC circuit block requires a large number of quantum logic gates (resources). In this paper, we (i) propose a smaller 5-qubit error detection circuit which can also correct a single error in 2 of the 5 qubits, and (ii) establish how to use a 3-qubit error correction circuit to correct the single errors when detected in the other 3 qubits. This approach to quantum error-correction circuit design, functionally equivalent to a 5-qubit QECC, yields a significant reduction in the number of quantum logic gates. For a given quantum logic circuit, we also provide a scheme to decide the locations where these error detection and error correction blocks are to be placed in attaining reduction in gate requirement compared to the case where the original 5-qubit QECC block is used. A comparative study of the resource requirement for the benchmark circuits shows that the proposed method outperforms even Shor and Steane codes in terms of resources. Thus, our proposed method provides quantum error correction with minimum qubit requirement and reduced resource requirement on the average.

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for more than one decade. With physical technologies for realizing the quantum bits (qubits) being announced, the problem of testing such circuits is also becoming important. There have been several works for identifying fault models for reversible circuits, and test generation algorithms for the same. In this work, we aim to show that the problem of testing reversible circuits with respect to recent fault models (like missing gate, missing control, reduced control, etc.) is easy, and it is not really worth to spend time and effort for generating better test patterns. To establish this point, test generators using two extreme scenarios have been implemented: a naive test generator that is very fast but does not guarantee optimality and a SAT-based test generator that is slow but guarantees smallest test sets. Experiments have been carried out on reversible benchmark circuits, which establish the fact that the size of the test patterns does not drastically differ across the spectrum.

In conventional binary reversible circuit synthesis, reversible gates are decomposed into quantum gates using some standard quantum gate library. In recent years there has been increased attention in synthesis using ternary reversible gates since it leads to a reduction in the number of lines. However, very few works exist that address the problem of decomposing ternary reversible gates based on some ternary quantum gate library. Most of these works use Muthukrishnan-Stroud (M-S) gates for decomposition of ternary Toffoli gate, and they use a naive approach that requires an exponential (in number of control lines) number of M-S gates. Also the number of ancilla lines required is (\(c-1\)), where c is the number of control lines. The present paper proposes a method for decomposing ternary Toffoli gates to M-S gates that requires less number of ancilla lines, and also requires a number of M-S gates that is linear in c. A template-based post-decomposition optimization step has also been used to further reduce the number of M-S gates required. Decomposition results for up to 16 control lines have been presented.

In reversible as well as quantum computation, unitary matrices (so-called transformation matrices) are employed to comprehensively describe the respectively considered functionality. Due to the exponential growth of these matrices, dedicated and efficient means for their representation and manipulation are essential in order to deal with this complexity and handle reversible/quantum systems of considerable size. To this end, Quantum Multiple-Valued Decision Diagrams (QMDDs) have shown to provide a compact representation of those matrices and have proven their effectiveness in many areas of reversible and quantum logic design such as embedding, synthesis, or equivalence checking. However, the desired functionality is usually not provided in terms of QMDDs, but relies on alternative representations such as Boolean Algebra, circuit netlists, or quantum algorithms. In order to apply QMDD-based design approaches, the corresponding QMDD has to be constructed first—a gap in many of these approaches. In this paper, we show how QMDD representations can efficiently be obtained for Boolean functions, both reversible and irreversible ones, as well as general quantum functionality.

In recent years, reversible circuits have become an established emerging technology through their variety of applications. Since these circuits employ a completely different structure from conventional circuitry, dedicated functional synthesis algorithms have been proposed. Although scalability has been achieved by using approaches based on decision diagrams, the resulting circuits employ a significant complexity measured in terms of quantum cost. In this paper, we aim for a reduction of this complexity. To this end, we review QMDD-based synthesis. Based on that, we propose optimizations that allow for a substantial reduction of the quantum costs by jointly considering paths and nodes in the decision diagram that employ a certain redundancy. In fact, in our experimental evaluation, we observe substantial improvements of up to three orders of magnitudes in terms of runtime and up to six orders of magnitudes (a factor of one million) in terms of quantum cost.

With the development in quantum computing, nearest neighbor constraint has become important for circuit realization. Various works have tried to make a circuit nearest neighbor compliant (NNC) by using minimum number of SWAP gates. To this end, an efficient qubit placement strategy is proposed that considers interaction among qubits and their positions of occurrence. Experimental results show that the proposed method reduces the number of SWAP gates by \(3.3\%\) to \(36.1\%\) on the average as compared to recently published works.