四量子可逆逻辑电路快速综合算法  

Fast Algorithms for 4-qubit Reversible Logic Circuits Synthesis

作　　者：李志强[1,2] 陈汉武[1] 徐宝文[1] 肖芳英[1] 薛希玲[1] 

机构地区：[1]东南大学计算机科学与工程学院,江苏南京211189 [2]扬州大学信息工程学院,江苏扬州225009

出　　处：《电子学报》2008年第11期2081-2089,共9页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60572071);国家自然科学基金重大研究计划(No.90412014);江苏省自然科学基金(No.BK2007104,BK2008209);江苏省高校自然科学基金(No.06KJB520137)

摘　　要：量子可逆逻辑电路综合是以较小量子代价自动构造所求量子可逆逻辑电路.本文提出了一种新颖高效的4量子电路综合算法,巧妙构造置换的最短编码,通过对量子电路进行特定拓扑变换,无损压缩n量子最优电路占用内存空间近2×n!倍,通过对已生成最优电路的双向级联,可使用多种量子门,采用最小长度标准,以极高效率生成较长的4量子电路,如率先生成基于控制非门、非门、Toffoli门库的全部前8层共3120218828个电路,还可快速综合任意长度不超过16的最优电路,并对4量子标准测试电路进行快速且全面的优化.Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost. We present a novel and efficient algorithm which can construct almost all optimal 4-qubit reversible logic circuits with various types of gates and minimum length cost based on constructing the shortest coding and the specific topological compression, whose lossless compression ratios of the space of n-qubit circuits is near2 × n!. We firstly have created all 3120218828 optimal 4-qubit circuits whose length is less than 9 for the Controlled-Not gate, NOT gate and Toffoli gate library, and our method can achieve 16 steps through cascading created circuits. Our algorithm can not only synthesizes all the 4-qubit bench- mark circuits, but also runs extremely fast.

关 键 词：4量子 可逆逻辑综合 最短编码 拓扑压缩 量子计算 

分 类 号：TP387[自动化与计算机技术—计算机系统结构]