IEEE Congress on Evolutionary Computation (CEC)

Synthesis of quantum arrays with low quantum costs from Kronecker Functional Lattice Diagrams

Dipal Shah, Marek A. Perkowski

Published Jul 1, 2010• 4 citations

Abstract

Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.

DOI: 10.1109/cec.2010.5586298

Related papers

Synthesis of Quantum Arrays from Kronecker Functional Lattice Diagrams

Martin Lukáč, Dipal Shah, Marek A. Perkowski +1 more

Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.

IEICE Transactions on Information and SystemsJan 1, 20143 citations

Synthesis of quantum circuits in Linear Nearest neighbor Model using Positive Davio Lattices

Marek A. Perkowski, Martin Lukáč, Dipal Shah +1 more

We present a logic synthesis method based on lattices that realize quantum arrays in One-Dimensional Ion Trap technology. This means that all gates are built from 2x2 quantum primitives that are located only on neighbor qubits in a one-dimensional space (called also vector of qubits or Linear Nearest Neighbor (LNN) architecture). The Logic circuits designed by the proposed method are realized only with 3*3 Toffoli, Feynman and NOT quantum gates and the usage of the commonly used multi-input Toffoli gates is avoided. This realization method of quantum circuits is different from most of reversible circuits synthesis methods from the literature that use only high level quantum cost based on the number of quantum gates. Our synthesis approach applies to both standard and LNN quantum cost models. It leads to entirely new CAD algorithms for circuit synthesis and substantially decreases the quantum cost for LNN quantum circuits. The drawback of synthesizing circuits in the presented LNN architecture is the addition of ancilla qubits.

Facta universitatis - series Electronics and EnergeticsJan 1, 201132 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOct 30, 2006379 citations

One Hot Encoding Synthesis of Quantum Automata from Flowcharts

Yuchen Huang, Marek A. Perkowski

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.

Journal of Quantum Information ScienceJan 1, 20232 citations

An Implementation of KFDD based Reversible Logic using IBM-Q Experience

P. Sangeetha, Prameela Kumari

Reversible logic is a circuit which has the ability to reduce the power dissipation. This type of logic circuit is used for the process of running the system both forward and backward.One of the main advantages of using any reversible logic is to get back the original data and to reduce the garbage output. Logic synthesis based on the Kronecker Functional Decision Diagram (KFDD) are generated for different reversible cascade methods both complemented and uncomplemented edge by using different reversible gates such as the CNOT (Controlled NOT), NOT, Toffoli gates, Peres gates, etc., and implemented in a quantum processor. In order to reduce the qubits which in turn reduces the quantum cost, it is implemented using reversible logic synthesis in KFDD method.The proposed method shows the implementation of these reversible circuits in an IBM quantum computer to find the probabilities, as it gives less quantum cost and also consumes less time when compared to other decision diagram. Reversible logic finds a wide range of applications in quantum computing and also in areas which deals with the low power design.This paper presents the implementation of KFDD using quantum circuits in IBM Quantum (IBM-Q) processor using different reversible logics and the output is discussed.

International Conference on Computing for Sustainable Global DevelopmentMar 1, 20204 citations

Synthesis of Reversible and Quantum Circuit Using ROCBDD and Mixed-Polarity Toffoli Gate

Hieu Nguyen, Linh Hoang Tran

In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.

IEEE AccessJan 1, 20215 citations