An Efficient Conversion of Quantum Circuits to a Linear Nearest Neighbor Architecture

Yuichi Hirata (0751100)

Recently, variety of quantum circuits have been designed. Most of them assume that arbitrary pairs of quantum bits can interact with each other. However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this presentation gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of it. The proposed method achieves the small additional circuit and time complexity compared with naive techniques. To develop the method, two key theorems, that may be interesting on their own, are introduced. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.