International Conference on Information and Digital Technologies (IDT)
Comparison of various error-detecting and error-correcting encodings of reversible automata built from irreversible state tables using EPOE circuits with EXOR lattices
This paper presents a new approach to synthesize reversible (quantum permutative) automata from standard state tables. It uses various variants of error-detecting and error-correcting encodings. Next, a combination of recently introduced “EPOE circuits” as well as EXOR Lattices are used for synthesis. The goal is to compare the costs of various encodings and synthesis methods for the same machine, especially strongly unspecified one.
This paper presents a new approach to synthesize reversible (quantum permutative) automata from standard state tables. It uses various variants of error-detecting and error-correcting encodings. Next, a combination of recently introduced “EPOE circuits” as well as EXOR Lattices are used for synthesis. The goal is to compare the costs of various encodings and synthesis methods for the same machine, especially strongly unspecified one.
This paper introduces new algorithms to synthesize reversible functions using EXOR-sum of Products-of-EXOR-sums (EPOE) structures. The motivation for using these structures is to reduce the number of as well as the sizes of multiple controlled Toffoli gates, and thus the quantum cost. To achieve these reductions the paper generalizes from existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. Our approach can be applied to reversible and permutative quantum circuits to synthesize single output functions on to an output line, with no additional ancilla bits. A comparison of the ESOP minimizer EXORCISM-4 and two variants of the EPOE minimizer, called EPOEM-1s and EPOEM-2, is presented. The results show that EPOE circuits do in fact achieve the above-stated cost reductions, in particular when expressed in terms of Maslov's quantum cost, the metric commonly used in quantum circuit synthesis.
At this time the synthesis of reversible circuits for quantum computing is an active area of research. In the most restrictive quantum computing models there are no ancilla lines and the quantum cost, or latency, of performing a reversible form of the AND gate, or Toffoli gate, increases exponentially with the number of input variables. In contrast, the quantum cost of performing any combination of reversible EXOR gates, or CNOT gates, on n input variables requires at most O(n2/log2n) gates. It was under these conditions that EXOR-AND-EXOR, or EPOE, synthesis was developed. In this work, the GF(2) logic theory used in EPOE is expanded and the concept of an EXOR-AND product transform is introduced. Because of the generality of this logic theory, it is adapted to EXOR-AND-OR, or SPOE, synthesis. Three heuristic spectral logic synthesis algorithms are introduced, implemented in a program called XAX, and compared with previous work in classical logic circuits of up to 26 inputs. Three linear reversible circuit methods are also introduced and compared with previous work in linear reversible logic circuits of up to 100 inputs.
We present a new approach to the synthesis of quantum automata. In previous research, reversible quantum automata were designed from tabular specifications or state graphs, and minimum length codes, which lead to circuits with Toffoli gates with high numbers of inputs and thus to high quantum costs. This paper is the first to present a method to synthesize Sequential Quantum Circuits directly from flowcharts. In this paper, we directly map flowcharts to reversible/quantum circuits, using only inverters, 2*2 Feynman gates and 3*3 Toffoli gates, and thus reducing quantum costs. Our method has been confirmed by experiments on several benchmarks of practical flowcharts.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.
Reversible logic circuits have been historically motivated by theoretical research in low-power, and recently attracted interest as components of the quantum algorithm, optical computing and nanotechnology. However due to the intrinsic property of reversible logic, traditional irreversible logic design and synthesis methods cannot be carried out. Thus a new set of algorithms are developed correctly to synthesize reversible logic circuit. This paper presents a comprehensive literature review with comparative study on heuristic based reversible logic synthesis. It reviews a range of heuristic based reversible logic synthesis techniques reported by researchers (BDD-based, cycle-based, search-based, non-search-based, rule-based, transformation-based, and ESOP-based). All techniques are described in detail and summarized in a table based on their features, limitation, library used and their consideration metric. Benchmark comparison of gate count and quantum cost are analysed for each synthesis technique. Comparing the synthesis algorithm outputs over the years, it can be observed that different approach has been used for the synthesis of reversible circuit. However, the improvements are not significant. Quantum cost and gate count has improved over the years, but arguments and debates are still on certain issues such as the issue of garbage outputs that remain the same. This paper provides the information of all heuristic based synthesis of reversible logic method proposed over the years. All techniques are explained in detail and thus informative for new reversible logic researchers and bridging the knowledge gap in this area.
This paper introduces a new synthesis approach called Products of EXOR-sums (POE) and demonstrates its utility when employed in an Exclusive-Or-Sum-of-Products (ESOP) based algorithm for reversible and permutative quantum circuits restricted to single output functions. Unlike previous ESOP approaches such as EXORCISM-4 which realize functions as an EXOR-ed sum of product literals, this new algorithm realizes functions as an EXOR-ed sum of POEs (EPOE). A comparison of EXORCISM-4 and EPOE circuits shows that the latter approach often produces circuits with significantly lower quantum costs.