基于矩阵变换的线性最近邻量子线路综合与优化

doi:10.3969/j.issn.0372-2112.2018.03.026

电子学报 ›› 2018, Vol. 46 ›› Issue (3): 688-694.DOI: 10.3969/j.issn.0372-2112.2018.03.026

基于矩阵变换的线性最近邻量子线路综合与优化

鹿玉¹, 管致锦^1,2, 程学云^1,2, 谈莹莹², 张宗源²

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

收稿日期:2016-08-11 修回日期:2017-03-01 出版日期:2018-03-25
- 作者简介:
- 鹿玉,女,1991年生于江苏徐州.现为南通大学电子信息学院研究生.主要研究方向为线性可逆逻辑综合.E-mail:luyu102591@163.com;管致锦,男,1962年生,江苏连云港人.博士,教授,博士生导师.主要研究方向为逻辑综合、智能计算与信息安全.E-mail:guan_zj617@163.com;程学云,女,1978年出生于江苏南通.现为南通大学副教授、博士生.主要研究方向为可逆计算和可逆电路优化.E-mail:chen.xy@ntu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61402244）; 江苏省基础研究计划 (自然科学基金）面上项目 (No.BK20151274）; 符号计算与知识工程教育部重点实验室开放基金项目 (No.93K172016K03）; 南通大学研究生科技创新计划项目 (No.KYC15016）

Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix

LU Yu¹, GUAN Zhi-jin^1,2, CHENG Xue-yun^1,2, TAN Ying-ying², ZHANG Zong-yuan²

1. College of Electoronics and Information, Nantong University, Nantong, Jiangsu 226019, China;
2. College of Computer Science and Technology, Nantong University, Nantong, Jiangsu 226019, China

Received:2016-08-11 Revised:2017-03-01 Online:2018-03-25 Published:2018-03-25

摘要/Abstract

摘要： 为了构造线性最近邻量子线路，降低线性量子可逆线路的量子代价，提出了一种基于矩阵变换的线性量子线路综合与优化方法.该方法给出了线路的矩阵表示和基于矩阵的近邻CNOT（Controlled NOT Gate）门判定，并提出矩阵分组的最佳方案，保证了线路综合中CNOT门数量最优.为了实现量子线路近邻化，提出了swap门的矩阵表示及线路近邻化规则，证明了两种swap门添加方式的等效性；提出了不同情况下swap门的消除规则，降低了近邻化后量子线路的量子代价.选择benchmark例题库中具有代表性的线路进行实验，与已有的量子线路近邻化算法相比，线路量子代价平均优化率为34.31%.

关键词: 量子线路, 矩阵变换, 线性最近邻, 线路综合, 优化, 量子代价

Abstract:

In order to construct linear nearest neighbor(LNN) quantum circuit and reduce its total quantum cost, a matrix-based synthesis and optimization method is proposed. The linear reversible circuit is represented by matrix, and the CNOT(Controlled NOT Gate) analysis based on the matrix is put forward. The best strategy of matrix partition is given, which ensures the number of CNOT gate used in the circuit synthesis is optimal. The matrix representation of swap gate and the NN(Nearest Neighbor) rules are proposed to realize the LNN circuits. The equivalence of two insertion methods of swap gates is proven. Deletion rules of swap gates which are used to make gates adjacent to NN in different cases are proposed, and they can reduce the quantum cost. Experimental results on typical benchmark circuits and comparison against previous algorithms for LNN quantum circuit optimization, the average optimization rate in quantum cost is 34. 31%.

Key words: quantum circuit, matrix transformation, linear nearest neighbor, circuit synthesis, optimization, quantum cost

中图分类号:

TP302

鹿玉, 管致锦, 程学云, 谈莹莹, 张宗源. 基于矩阵变换的线性最近邻量子线路综合与优化[J]. 电子学报, 2018, 46(3): 688-694.

LU Yu, GUAN Zhi-jin, CHENG Xue-yun, TAN Ying-ying, ZHANG Zong-yuan. Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix[J]. Acta Electronica Sinica, 2018, 46(3): 688-694.

参考文献

[1] B Schaeffer,M Perkowski.Linear reversible circuit synthesis in the linear nearest-neighbor model[J].IEEE International Symposiumon Multiple-Valued Logic,2012,19(10):157-160.
[2] Z Sasanian,R Wille,DM Miller.Realizing reversible circuits using a new class of quantum gate[J].Design Automation Conference,2012,8(8):36-41.
[3] O Golubitsky,D Maslov.A study of optimal 4-bit reversible Toffoli circuits and their synthesis[J].IEEE Transactions on Computers,2011,61(6):1341-1353.
[4] VV Shende,SS Bullock,IL Markov.Synthesis of quantum-logic circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2006,25(6):1000-1010.
[5] 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.
[6] K Patel,I Markov,J Hayes.Optimal synthesis of linear reversible circuits[J].Quantum Information and Computation,2008,8(3):282-294.
[7] P Yu,Y Yan,J Lin,H Huang,W Wu.An efficient method to synthesize reversible logic by using positive-davio decision diagrams[J].Circuits,Systems,and Signal Processing,2014,33(7):3107-3121.
[8] R Wille,R Drechsler.The SyReC hardware description language:Enabling scalable synthesis of reversible circuits[A].2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS)[C].Boise:IEEE,2013.1063-1066.
[9] M Saeedi,R Wille,R Drechsler.Synthesis of quantum circuits for linear nearest neighbor architectures[J].Computer Science,2012,10(3):355-377.
[10] Abhoy Kole,Kamalika Datta,Indranil Sengupta.A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using N-gate lookahead[J].IEEE Journal on Emerging and Selected Topics in Circuits and Systems,2016,6(1):62-72.
[11] Lye A,Will R,Drechsler R.Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits[A].Design Automation Conference (ASP-DAC),201520th Asia and South Pacific[C].Austin:IEEE,2015.178-183.
[12] Md.Mazder Rahman,Gerhard W.Dueck,Anupam Chattopadhyay.Integrated synthesis of linear nearest neighbor ancilla-free MCT circuits[A].2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL)[C].Japan:IEEE,2016.144-149.

[1]	陇盛, 陶蔚, 张泽东, 陶卿. 非光滑强凸情形Adam型算法的最优收敛速率[J]. 电子学报, 2022, 50(9): 2049-2059.
[2]	杨小龙, 李欣玥, 周牧, 王勇, 何维. 基于多维模糊映射AP优化的WLAN室内定位方法[J]. 电子学报, 2022, 50(8): 1875-1884.
[3]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[4]	魏振春, 傅宇, 马仲军, 吕增威, 石雷, 张本宏. 带时间窗的无线可充电传感器网络多目标路径规划算法[J]. 电子学报, 2022, 50(8): 1819-1829.
[5]	王波, 王悦, 王伟, 侯嘉尧. 开放环境下自适应聚类优化包络的相机来源取证[J]. 电子学报, 2022, 50(8): 1840-1850.
[6]	谢青松, 刘晓庆, 安志勇, 李博. 基于前景优化的视觉目标跟踪算法[J]. 电子学报, 2022, 50(7): 1558-1566.
[7]	穆磊, 王鹏. 量子启发式优化算法的尺度动态调速机制[J]. 电子学报, 2022, 50(7): 1664-1673.
[8]	王鼎, 尹洁昕, 郑娜娥, 聂福全. 信号传播速度未知下基于运动单站到达频率的定位新方法[J]. 电子学报, 2022, 50(5): 1181-1191.
[9]	窦子铮, 姚铮, 陆明泉. 无线电区域定位系统的分布式空间基准自主建立技术[J]. 电子学报, 2022, 50(4): 841-848.
[10]	蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.
[11]	汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717.
[12]	余若峰, 杨威, 付耀文, 张文鹏. 面向不同雷达任务的认知波形优化综述[J]. 电子学报, 2022, 50(3): 726-752.
[13]	董明, 李敬, 索永录, 唐恩贤, 马宏伟, 陈渊, 张广明, 万翔. 基于改进果蝇优化算法正交匹配追踪的超声信号降噪方法[J]. 电子学报, 2022, 50(2): 493-501.
[14]	蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展[J]. 电子学报, 2022, 50(2): 480-492.
[15]	史宏强, 李岳衡, 黄平, 谭跃跃, 刘陕陕, 居美艳. 基于APD与PIN接收机的UWOC系统误码率性能优化研究[J]. 电子学报, 2022, 50(2): 446-454.

基于矩阵变换的线性最近邻量子线路综合与优化

Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics