Conference proceedings - Canadian Conference on Electrical and Computer Engineering

Using autocorrelation coefficient-based cost functions in ESOP-based Toffoloi gate cascade generation

Jacqueline E. Rice, Vivien Suen

Published May 1, 2010• 15 citations

Abstract

A revision of an ESOP-based Toffoli gate cascade synthesis technique is presented. The cost metric used previously was replaced with a new cost metric based on autocorrelation coefficients to determine the placements of Toffoli gates. The algorithm remains capable of generating reversible circuits for large functions within reasonable time.

DOI: 10.1109/ccece.2010.5575167

Related papers

ESOP-based Toffoli Gate Cascade Generation

Kenneth Fazel, Mitchell Aaron Thornton, Jacqueline E. Rice

An ESOP-based Toffoli gate cascade synthesis algorithm is presented. The algorithm is capable of generating a cascade of reversible gates for logic functions with large numbers of qubits. The algorithm is fast as it uses a simple cost metric heuristic during a recursive divide-and-conquer function to determine NOT and Toffoli gate placement.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)Aug 1, 2007191 citations

ESOP-Based Toffoli Network Generation with Transformations

Yasaman Sanaee, Gerhard W. Dueck

In this paper a new Toffoli gate cascade synthesis method is presented. This method is based on previous work and generates a cascade of inverted-control-Toffoli gates from the ESOP representation of a multi-output function. The algorithm first generates a circuit with n + m lines, where n and m are the number of inputs and outputs, respectively. A set of gate transformations are applied to the circuits to remove some of the output lines. The improvements of this new algorithm are twofold: most NOT gates are eliminated and the number of lines is reduced. A significant reduction is the quantum cost of the resulting networks can be observed.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)Jan 1, 201028 citations

Generating Toffoli networks from ESOP expressions

Yasaman Sanaee, Gerhard W. Dueck

In this paper a new heuristic ESOP-based synthesis method for Toffoli networks is proposed. This synthesis method takes advantage of the shared-ESOP cubes among the outputs to generate a cascade of Toffoli gates. The method is suitable to generate circuits for functions with large number of input variables. A greedy approach is utilized to select pairs among the different outputs with common ESOP-cubes. The shared terms need only to be realized once and the result can then be transferred to the second output, and thus reducing the number of Toffoli gates. The synthesis algorithm has been applied to a set of benchmark functions. Experimental results show that the algorithm can generate circuits with reduced quantum cost for virtually all functions. Template applications can further improve the results.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)Aug 1, 200921 citations

An Improved Factorization Approach to Reversible Circuit Synthesis Based on EXORs of Products of EXORs

Linh Hoang Tran, Addison Gronquist, Marek A. Perkowski +1 more

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 20165 citations

A shared-cube approach to ESOP-based synthesis of reversible logic

Noor Muhammed Nayeem, Jacqueline Rice

Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.

Facta universitatis - series Electronics and EnergeticsJan 1, 201141 citations

Ordering techniques for ESOP-based Toffoli cascade generation

Jacqueline E. Rice, Noor Muhammed Nayeem

This paper describes three techniques for ordering ESOP cubes prior to generation of a Toffoli gate generation. Two of these techniques are from earlier work, while the third is a new approach. The new approach applies rules to manipulate the cubes followed by a reordering process. Our experiments demonstrate that the new approach is much more effective than either of the two previous approaches. We apply template matching as a post-processing step, which results in even further reductions in the number of Toffoli gates.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)Aug 1, 201120 citations