电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1891-1897.DOI: 10.3969/j.issn.0372-2112.2018.08.013

• 学术论文 • 上一篇    下一篇

基于MCT可逆线路的量子线路近邻化排布

程学云1,2,3, 管致锦2,3, 徐海1, 谈莹莹2, 刘洋2   

  1. 1. 南通大学电子信息学院, 江苏南通 226019;
    2. 南通大学计算机科学与技术学院, 江苏南通 226019;
    3. 江苏省专用集成电路设计重点实验室, 江苏南通 226019
  • 收稿日期:2017-03-13 修回日期:2018-04-03 出版日期:2018-08-25
    • 通讯作者:
    • 管致锦
    • 作者简介:
    • 程学云 女,1978年生,江苏南通人.副教授,博士生.主要研究方向为量子计算和逻辑综合.E-mail:chen.xy@ntu.edu.cn.
    • 基金资助:
    • 国家自然科学基金 (No.61403216); 江苏省基础研究计划 (自然科学基金)面上项目 (No.BK20151274); 江苏省研究生科研与实践创新计划项目 (No.KYCX17-1916)

The Nearest Neighbor Arrangement of Quantum Circuits Based on MCT Reversible Circuits

CHENG Xue-yun1,2,3, GUAN Zhi-jin2,3, XU Hai1, TAN Ying-ying2, LIU Yang2   

  1. 1. College of Electronics and Information, Nantong University, Nantong, Jiangsu 226019, China;
    2. College of Computer Science and Technology, Nantong University, Nantong, Jiangsu 226019, China;
    3. Jiangsu Key Laboratory of Asic Design, Nantong University, Nantong, Jiangsu 226019, China
  • Received:2017-03-13 Revised:2018-04-03 Online:2018-08-25 Published:2018-08-25

摘要: 为了实现量子线路线性最近邻(LNN)排布,给出了可逆MCT门的最近邻Toffoli门级联方法.为了解决线路近邻化中额外插入的SWAP门增加量子代价的问题,引入NNTS门减少插入的SWAP门数,并给出了MCT门基于NNTS门的最近邻线路排布.提出了量子线路近邻化排布算法,将多控制MCT门通过交换线路的顺序得到其最近邻线路排布,然后将每个NNTS门替换为其最优的LNN量子线路实现,得到该MCT线路的LNN量子线路,该方法可以减少量子线路的长度和量子代价.通过Benchmark例题测试,并与现有的线路近邻化结果进行比较,所需插入的SWAP门数平均减少42.83%,量子代价平均改善率达14.80%.

关键词: 量子线路, 可逆线路, MCT门, 线性最近邻(LNN), 最近邻线路排布

Abstract: In order to realize the linear nearest neighbor (LNN) arrangement of a quantum circuit,the nearest neighbor Toffoli gates cascade method of an MCT gate is given.To solve the issue of the increased quantum cost resulted from the extra inserted SWAP gates during the process of nearest neighbor,the NNTS gate is introduced to decrease the number of the inserted SWAP gates,and the LNN line arrangement using NNTS gates of an MCT gate is obtained.The line arrangement algorithm is proposed.The LNN line arrangement of each MCT gate can be realized by the exchange of the order of the lines,and each NNTS gate is replaced by its optimal LNN form,then the LNN quantum circuit is obtained directly,which can greatly reduce the length of the quantum circuit and the quantum cost.Test on benchmark circuits,and compared with the existing relevant results,the average improvement rate is almost 42.83% in SWAP gate count,and 14.80% in terms of quantum cost.

Key words: quantum circuit, reversible circuit, MCT gate, linear nearest neighbor(LNN), nearest neighbor line arrangement

中图分类号: