Facta Univ. Ser.: Elec. Energ., vol. 24, No. 1, April 2011, pp. 73-89

Synthesis of quantum circuits in Linear Nearest Neighbor model using Positive Davio Lattices

Marek Perkowski, Martin Lukac, Dipal Shah, and Michitaka Kameyama

Abstract: 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.

Keywords: Reversible logic synthesis, lattice, leinear nearest neighbor model.