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

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

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

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

  1. 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 Yu1, GUAN Zhi-jin1,2, CHENG Xue-yun1,2, TAN Ying-ying2, ZHANG Zong-yuan2   

  1. 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
    • Supported by:
    • National Natural Science Foundation of China (No.61402244); General Program of Basic Research Project of Jiangsu Provicne  (Natural Science Foundation) (No.BK20151274); Open project of Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,  Jilin University (No.93K172016K03); Graduate Science and Technology Innovation Program of Nantong University (No.KYC15016)

摘要: 为了构造线性最近邻量子线路,降低线性量子可逆线路的量子代价,提出了一种基于矩阵变换的线性量子线路综合与优化方法.该方法给出了线路的矩阵表示和基于矩阵的近邻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

中图分类号: