Quantum Information and Computation

An efficient conversion of quantum circuits to a linear nearest neighbor architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima

Published Jan 1, 2011• 61 citations

Abstract

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 paper 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 the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.

DOI: 10.26421/qic11.1-2-10

Related papers

An Efficient Method to Convert Arbitrary Quantum Circuits to Ones on a Linear Nearest Neighbor Architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.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 technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)Feb 1, 200971 citations

An efficient conversion of quantum circuits to a linear nearest neighbor architecture

HirataYuichi, NakanishiMasaki, YamashitaShigeru +1 more

Quantum Information and ComputationJan 1, 201148 citations

Reducing CNOT count in quantum Fourier transform for the linear nearest-neighbor architecture

Byeongyong Park, Doyeol Ahn

Physical limitations of quantum hardware often necessitate nearest-neighbor (NN) architecture. When synthesizing quantum circuits using the basic gate library, which consists of CNOT and single-qubit gates, CNOT gates are required to convert a quantum circuit into one suitable for an NN architecture. In the basic gate library, CNOT gates are considered the primary cost of quantum circuits due to their higher error rates and longer execution times compared to single-qubit gates. In this paper, we propose a new linear NN (LNN) circuit design for quantum Fourier transform (QFT), one of the most versatile subroutines in quantum algorithms. Our LNN QFT circuit has only about 40% of the number of CNOT gates compared to previously known LNN QFT circuits. Subsequently, we input both our QFT circuits and conventional QFT circuits into the Qiskit transpiler to construct QFTs on IBM quantum computers, which necessitate NN architectures. Consequently, our QFT circuits demonstrate a substantial advantage over conventional QFT circuits in terms of the number of CNOT gates. This outcome implies that the proposed LNN QFT circuit design could serve as a novel foundation for developing QFT circuits implemented in quantum hardware that demands NN architecture.

Scientific ReportsMay 27, 202329 citations

Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning

Amlan Chakrabarti, Susmita Sur‐Kolay, Ayan Chaudhury

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.

arXiv:1112.0564Dec 2, 201148 citations

An Algorithm of Optimization for Linear Nearest Neighbor Quantum Circuits by Parallel Processing

Zongyuan Zhang, Zhijin Guan, Hong Zhang

In order to realize the linear nearest neighbor(LNN) of quantum circuits and reduce the quantum cost of the linear reversible quantum circuits, a method of synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication is proposed. This method shows the matrix representation of linear quantum circuits by proposing the matrix representation of the CNOT gate and the SWAP gate. The rule of judging whether a two-qubit quantum circuit is in LNN state is proposed. The LNN realization by adding SWAP gates is proposed and the equivalence of two ways of adding SWAP gates is proved. The elimination rules of SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose a particular algorithm to realize the LNN, which can effectively reduce the quantum cost and improve calculation efficiency by inserting the SWAP gates on parallel computing devices. Experiments show that the quantum cost can be improved by 34.31% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)Jul 1, 20182 citations

An Efficient 2D Mapping of Quantum Circuits to Nearest Neighbor Designs

Anirban Bhattacharjee, Hafizur Rahaman

In the last few years, tremendous improvement in the field of quantum computing has been witnessed. Although quantum technologies such as ion-trap, NMR, quantum dots have emerged as the promising platforms for implementing quantum circuits but these technologies have faced several design issues. One such important design problem is the nearest neighbor condition, which requires the qubits to interact with adjacent neighbors. This problem can be addressed by adding SWAP gates in the circuit. By doing so, the overhead in the circuit increases thus NN designs with minimum number of SWAP gates need to be developed. Focusing on this, here, in this work, we introduce a heuristic design method for efficient NN realization of quantum circuits in 2D architecture. Our NN transformation process is carried out in two phases, where initially in the first phase, the input circuit is mapped to 2D configuration using a qubit placement strategy and then in the second phase NN designs are obtained through SWAP gate insertion. At the end, the design algorithm has been evaluated over a large set of benchmark functions and the results are compared with some of the existing works. From this comparison, it is seen that our proposed method performs better than the reported works.

IEEE International Symposium on Smart Electronic Systems (iSES)Dec 1, 20212 citations