Mapping a Quantum Circuit to 2D Nearest Neighbor Architecture by Changing the Gate Order

Wakaki HATTORI  Shigeru YAMASHITA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.11   pp.2127-2134
Publication Date: 2019/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7439
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
Nearest Neighbor Architecture (NNA),  gate order,  

Full Text: FreePDF(602.4KB)


Summary: 
This paper proposes a new approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on a two-dimensional (2D) NNA. Our new idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the sub-circuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.