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

doi:10.3969/j.issn.0372-2112.2018.08.013

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

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

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

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-yun^1,2,3, GUAN Zhi-jin^2,3, XU Hai¹, TAN Ying-ying², LIU Yang²

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

摘要/Abstract

摘要： 为了实现量子线路线性最近邻（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

中图分类号:

TP302

程学云, 管致锦, 徐海, 谈莹莹, 刘洋. 基于MCT可逆线路的量子线路近邻化排布[J]. 电子学报, 2018, 46(8): 1891-1897.

CHENG Xue-yun, GUAN Zhi-jin, XU Hai, TAN Ying-ying, LIU Yang. The Nearest Neighbor Arrangement of Quantum Circuits Based on MCT Reversible Circuits[J]. Acta Electronica Sinica, 2018, 46(8): 1891-1897.

参考文献

[1] Nielsen M,Chuang I.Quantum Computation and Quantum Information[M].Oxford:Cambridge Univ.Press,2000.171-343.
[2] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis[A].Design Automation Conference[C].Piscataway:IEEE,2003.318-323.
[3] Wille R,Grosse D.Fast exact Toffoli network synthesis of reversible logic[A].IEEE/ACM International Conference on Computer-Aided Design[C].Piscataway:IEEE,2007.60-64.
[4] Barenco A,Bennett C H,Cleve R,et al.Elementary gates for quantum computation[J].Physical Review A,1995,52(5):3457-3467.
[5] Miller D M,Wille R,Sasanian Z.Elementary quantum gate realizations for multiple-control toffoli gates[A].IEEE International Symposium on Multiple-Valued Logic[C].Washington DC:IEEE Computer Society,2011.288-293.
[6] Pedram M,Shafaei A.Layout optimization for quantum circuits with linear nearest neighbor architectures[J].IEEE Circuits & Systems Magazine,2016,16(2):62-74.
[7] Linke N M,Maslov D,Roetteler M,et al.Experimental comparison of two quantum computing architectures[J].Proceedings of the National Academy of Sciences of the United States of America,2017,114(13):3305-3310.
[8] Kole A,Datta K,Sengupta I.A heuristic for linear nearest neighbor realization of quantum circuits by SWAP gate insertion using N-Gate lookahead[J].IEEE Journal on Emerging & Selected Topics in Circuits & Systems,2016,6(1):62-72.
[9] Saeedi M,Wille R,Drechsler R.Synthesis of quantum circuits for linear nearest neighbor architectures[J].Quantum Information Processing,2010,10(3):355-377.
[10] Wille R,Lye A,Drechsler R.Optimal SWAP gate insertion for nearest neighbor quantum circuits[A].Design Automation Conference[C].Piscataway:IEEE,2014.489-494.
[11] Wille R,Li B,Schlichtmann U,et al.From biochips to quantum circuits:computer-aided design for emerging technologies[A].IEEE/ACM International Conference on Computer-Aided Design[C].Piscataway:IEEE,2017.132.
[12] Biswal L,Bandyopadhyay C,Wille R,et al.Improving the realization of multiple-control toffoli gates using the NCVW quantum gate library[A].29th International Conference on VlSI Design and 15th International Conference on Embedded Systems[C].Piscataway:IEEE,2016.573-574.
[13] Matsuo A,Yamashita S.Changing the Gate Order for Optimal LNN Conversion[M].Reversible Computation.Berlin Heidelberg:Springer,2012.89-101.
[14] Shafaei A,Saeedi M,Pedram M.Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures[A].Design Automation Conference[C].Piscataway:IEEE,2013.41:1-41:6.
[15] Wille R,Lye A,Drechsler R.Exact reordering of circuit lines for nearest neighbor quantum architectures[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2014,33(12):1818-1831.
[16] 程学云,谈莹莹,管致锦,等.优化的可逆MCT电路化简算法[J].量子电子学报,2017,34(6):713-720. Cheng X,Tang Y,Guan Z,et al.An optimized simplification algorithm for reversible MCT circuits[J].Chinese Journal of Quantum Electronics,2017,34(6):713-720.(in Chinese)
[17] R Wille,D Gro β e,L Teuber,G Dueck,R Drechsler.RevLib:An online resource for reversible functions and reversible circuits[A].Int Symp Multiple-valued Logic[C].Washington DC:IEEE Computer Society,2008.220-225.RevLib is available at http://www.revlib.org.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	鹿玉, 管致锦, 程学云, 谈莹莹, 张宗源. 基于矩阵变换的线性最近邻量子线路综合与优化[J]. 电子学报, 2018, 46(3): 688-694.
[2]	陈雄;陈汉武;刘志昊;李志强. 基于状态向量表示的快速量子仿真算法[J]. 电子学报, 2011, 39(3): 500-504.
[3]	薛希玲;陈汉武;刘志昊;李志强;. 量子线路仿真的分治算法[J]. 电子学报, 2010, 38(2): 439-442.