一种量子线路二维近邻实现方法

量子电子学报 ›› 2019, Vol. 36 ›› Issue (4): 476-482.

一种量子线路二维近邻实现方法

沈鸣燕1，程学云1,2，管致锦1* ，陈加庆1，何娴雅1

1 南通大学计算机科学与技术学院，江苏南通 226019； 2 南通大学电子信息学院，江苏南通 226019

收稿日期:2019-01-03 修回日期:2019-03-08 出版日期:2019-07-28 发布日期:2019-07-11
通讯作者: 程学云（1978-），女，江苏南通人，硕士，副教授，研究生导师，主要从事可逆计算和量子线路综合方面的研究。 E-mail:chen.xy@ntu.edu.cn
作者简介:沈鸣燕（1995-），女，江苏南通人，研究生，主要从事可逆计算和量子线路综合方面的研究。E-mail：1171204484@qq.com
基金资助:
Supported by National Natural Science Foundation of China (国家自然科学基金, 61403216), Natural Science Foundation of Jiangsu Province (江苏省自然科学基金, BK20151274),Application and Research Program of Nantong(南通市应用研究计划项目，GY12017024),Postgraduate Research and Practice Innovation Program of Jiangsu Province (江苏省研究生科研与实践创新计划项目, SJCX18_0820)

A Realization Method of Two-Dimensional Nearest Neighbor for Quantum Circuit

SHEN Mingyan1, CHENG Xueyun1,2, GUAN Zhijin1*, CHEN Jiaqing1, HE Xianya1

1 College of Computer Science and Technology, Nantong University, Nantong 226019, China; 2 College of Electronics and Information, Nantong University, Nantong 226019, China

Received:2019-01-03 Revised:2019-03-08 Published:2019-07-28 Online:2019-07-11

摘要/Abstract

摘要： 为了解决一些量子技术中二维量子线路量子位最近邻约束问题，提出了一种基于优先级的最近邻交互代价度量模型，并基于和谐搜索（HS）算法得到量子位在二维体系结构中的最优布局，然后通过给出的局部排序方法来执行交换门的插入，最终使得量子线路在二维体系结构下实现最近邻交互。通过实验对算法进行了验证，并与最新的相关结果进行比较。实验结果表明，该方法与文献报道的二维网格体系结构中的交换门数相比，平均降低了14.42%。

关键词: 量子计算, 量子线路综合, 最近邻排布, 二维体系结构, 和谐搜索算法

Abstract: In order to solve the problem of qubit nearest neighbor constraint in some quantum techniques, In this paper, a priority-based nearest neighbor interaction cost measurement model is proposed, and the optimal layout of the qubit in two-dimensional architecture is obtained based on the harmony search (HS) algorithm, and then the insertion of the SWAP gate is performed by the given local sorting method. Finally, the quantum circuit realizes the nearest neighbor interaction under the two-dimensional architecture. The algorithm is verified by experiments and compared with the latest results. The experimental results show that the average decrease of SWAP gates in the proposed method is 14.42% compared with that in the two-dimensional grid architecture reported in the literature.

Key words: quantum computation, quantum circuit synthesis, nearest neighbor arrangement, two-dimensional architecture, harmonious search algorithm

中图分类号:

TP302.2

沈鸣燕1，程学云1,2，管致锦1*,陈加庆1，何娴雅1. 一种量子线路二维近邻实现方法[J]. 量子电子学报, 2019, 36(4): 476-482.

SHEN Mingyan1, CHENG Xueyun1,2, GUAN Zhijin1*, CHEN Jiaqing1, HE Xianya1. A Realization Method of Two-Dimensional Nearest Neighbor for Quantum Circuit[J]. Chinese Journal of Quantum Electronics, 2019, 36(4): 476-482.

参考文献

[1] Nielsen M, Chuang I. Quantum Computation and Quantum Information [M]. Cambridge: Cambridge University Press, 2000. [2] Monroe C, Kim J. Scaling the ion tap quantum processor[J]. Science, 2013, 339(6124):1164-1169. [3] Córcoles A D, Magesan E, Srinivasan S J, et al. Demonstration of a quantum error detection code using a square lattice of four superconducting qubits[J]. Nature Communications, 2015, 6: 6979. [4] Cheng Xueyun, Guan Zhijin. Linear nearest neighbor quantum circuit synthesis based on valid Boolean matrix[J]. Chinese Journal of Quantum Electroincs（量子电子学报）, 2016, 33(6): 743-750(in Chinese). [5] Shafaei A, Saeedi M, Pedram M. Qubit placement to minimize communication overhead in 2D quantum architectures[C]. Design Automation Conference, IEEE, 2014: 495-500. [6] Lye A, Wille R, Drechsler R. Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits[C]. Design Automation Conference, IEEE, 2015: 178-183. [7] Kole A, Datta K, Sengupta I. A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems, 2017, 99: 1. [8] Shrivastwa R R, Datta K, Sengupta I. Fast qubit placement in 2D architecture using nearest neighbor realization[C].IEEE International Symposium on Nanoelectronic and Information Systems, 2015: 95-100. [9] Wille R, Keszocze O, Walter M, et al. Look- ahead schemes for nearest optimization of 1D and 2D quantum circuits[C]. Asia and South Pacific Design automation Conference, IEEE, 2016:292-297. [10] Alfailakwi M G, Ahmdan S. Harmony-search algorithm for 2D nearest neighbor quantum circuits realization[J]. Expert Systems with Applications, 2016, 61: 16-27. [11] Alfailakawi M, Alterkawi L, Ahmad I, et al. Line ordering of reversible circuits for linear nearest neighbor realization[J]. Quantum Information Processing, 2013, 12(10): 3319-3339. [12] Geem Z W, Kim J H, Loganathan G. A new heuristic optimization algorithm: Harmony search[J]. Simulation, 2001, 76(2): 60-68. [13] Cheng Xueyun, Tan Yingying, Guan Zhijin. An optimized simplification algorithm for reversible MCT circuits[J]. Chinese Journal of Quantum Electroincs（量子电子学报）, 2017, 34(6): 713-720(in Chinese). [14] Tan Y Y, Cheng X Y, Guan Z J, et al. Multi-strategy based quantum cost reduction of linear nearest-neighbor quantum circuit[J]. Quantum Information Processing, 2018, 17(3):61.