ISSN 
-
可逆逻辑综合[1-2]是可逆计算研究的关键问题之一，也是量子计算和量子信息技术的重要组成部分。最初可逆计算的提出是为了解决计算机中的能量消耗问题，文献[3]指出在传统计算过程中，由于擦除信息的不可逆造成了能耗的产生。文献[4]证明了对所有不可逆图灵机都有一个可逆图灵机，即计算机中的每步操作均可变为可逆操作，且可逆逻辑计算可避免传统计算过程中的能量消耗。
所有的量子计算都是可逆计算，量子计算的算法可以通过量子可逆线路表示。可逆逻辑线路分解与优化是量子线路设计过程中至关重要的步骤，选取合适的分解与优化方法能够有利于将高级量子线路分解为低级量子线路，以进一步转换为已有不同量子计算机可执行量子线路。因此，可逆逻辑线路的分解与优化研究是量子计算技术的重要内容。
现有的可逆电路化简方法有基于规则的方法[5-7]与基于模板[8-9]的方法。文献[6]提出Toffoli电路的约简规则，根据移动规则对可逆电路进行扫描，寻找满足约简规则的进行优化，直到电路不发生变化为止。文献[9]提出了可逆电路优化模板，通过模板等价替换某部分逻辑门，达到减少逻辑门的目的。但现有研究多针对量子线路进行设计优化[1, 2, 8-15]，没有把高级量子可逆线路转换为接近物理量子计算机执行的低级量子线路，且时间代价较高，如何把高级量子线路如MCT门（Multiple Control Target）更高效地分解并优化为低级量子线路如NCV门的研究较少。
本文提出了一种MCT门分解为NCV门的模板，与现有分解方法相比，能降低量子代价和分解时间，提高分解效率。
-
MCT门是指多控制单目标的量子门，可逆门电路由可逆逻辑门级联组成，MCT门是最常见的可逆逻辑门，属于高级量子线路。常用的MCT门包括NOT门、CNOT门、Toffoli门等。一个MCT门可表示为MCT({xi,···,xj},xk)，其中i,j,k={1,2,···,n}，k≠i,j。
为了表述方便，本文Toffoli门特指控制位为2的MCT门，MCT门特指控制位大于等于3的MCT门，图1中
$ \bullet $ 代表控制位，$ \oplus $ 代表目标位。
图 1 常见MCT门
能够被量子计算机执行的是基础量子门。常见的基础量子门有NCV门，其图形符号如图2所示。
图 2 NCV门库
-
在量子线路中，一根量子线代表一个量子位，几根量子线之间的量子门代表这几个量子位之间的量子运算。如图3a所示线路表示当L1、L2线都为1时，L3线取反，相当于电子线路中一个与非门。
图 3 Toffoli门的两种分解形式
量子算法可以通过量子线路来表示，所有可逆量子门都可以通过量子门串并联得到。因此可将可逆线路中每一个可逆电路分解为等价的由基础量子门组成的量子门电路[16]。常见的分解办法是先将MCT门分解为Toffoli线路，再将Toffoli线路分解为NCV线路。
Toffoli门可等价分解为NCV门组成的线路[16]，如图3b所示。由文献[17]可知，可逆线路中，V门和V+门可以相互交换位置且不影响线路功能，因此Toffoli门还可分解为另一种形式，如图3c所示。
-
一般常用量子代价对可逆电路的复杂度进行度量。量子代价指构建可逆量子电路所需的基础量子门的数量。由于NCV门是基础量子门，所以NCV电路中NCV门的数量即为其量子代价。所有可逆门均可通过基础可逆门构造[8]。如图3所示，Toffoli门可由5个NCV门组成，其量子代价为5。
量子代价是可逆电路优化程度的重要指标，本文用量子代价来评价MCT门分解为NCV门的效果。
-
交换规则：对于变量域集合{x1,x2,···,xn}，广义MCT门可表示为MCT(C,T)，其中控制线集C={xi1,xi2,···,xim}，目标位T={xk}。对于两个相邻的门G1=MCT(C1,T1)和G2=MCT(C2,T2)，若存在C1∩T2=
$\varnothing $ 且C2∩T1=$\varnothing$ ，即两个门的控制位不会影响对方的目标位，则交换这两个门的位置不会影响原线路的逻辑功能[8]。图4中G1的控制位与G2的目标位在同一量子位线上，因此不可交换；G5和G6的控制位都不影响对方的目标位，可以进行交换。同理，G5也可与G7～G10进行交换。
图 4 交换规则
删除规则：线路中相邻的（或移动后相邻的）具有相同控制位和目标位的两个门，能够形成单位映射，如图5所示。如两个相邻的CNOT门，由于其控制位和目标位一致，当控制位为1时，目标位经两次取反后结果与原值相同，因此可以删除该门对而不影响原线路功能[6]，称为门删除规则。
图 5 删除规则
-
MCT线路是高级量子线路，需分解为基础量子线路如NCV才能在量子计算机中实现对应功能。目前许多研究工作围绕着分解后的NCV线路进行优化，若能将分解与优化同时进行，可减少后续线路优化的工作量，大幅提高量子电路的优化效果。本文提出了针对特定的MCT门分解为NCV门的分解模板，对MCT分解后产生的Toffoli门同时进行优化和分解，得到量子代价低的NCV线路，同时也能有效降低时间复杂度。
-
以下表述中，n表示线路数，m表示一个MCT门的控制位数，n∈{4,5,···,n}，m∈{3,4,···,m}。
为了实现MCT线路中逻辑门的分解[18]，若m=n–1，则需在原线路上的控制位和目标位间添加一条辅助线（空线），如图6所示。
图 6 添加辅助线
由文献[16]可知，若量子可逆线路线数n≥5，m∈{3,4,···,n/2}，则含有m个控制位的MCT门可分解为如下形式的含有4(m−2)个Toffoli门的线路。如m=4，n=7，n/2取4，则m∈{3,4}，该MCT门可以分解为8个Toffoli门，分解结果如图7所示。
图 7 MCT门分解为Toffoli线路
图7所示的MCT门中，m=4，n=7，将GMCT=MCT({x1,x2,x3,x4},x7)分解为Toffoli门的组合，G1=MCT({x4,x6},x7)、G2=MCT({x3,x5},x6)、G3=MCT({x1,x2},x5)、G4=MCT({x3,x5},x6)、G5=MCT({x4,x6},x7)、G6=MCT({x3,x5},x6)、G7=MCT({x1,x2},x5)、G8=MCT({x3,x5},x6)。
观察分解出的Toffoli线路，发现其存在一定的规律和对称性。将电路分成3组，每组有左右对称的Toffoli电路，如G1、G2和G4、G5以G3对称；之后把G1、G2用图3b，G4、G5用图3c的分解方法，分解为两种不同NCV电路。结果如图8所示。
图8中由于G1和G2的控制位与目标位不相同，因此分解出的NCV所在的控制位与目标位也不相同。根据1.4节化简规则，G10和G11的控制位和目标位无交集，即C10∩T11=
$\varnothing $ 且C11∩T10=$\varnothing $ ，可以将两门位置互换。同理，G10与G12～G15逐个交换后，与G16相邻并形成映射门对，可同时删除G10与G16。遍历该电路后，删除所有可以形成（或移动后可形成）单位映射的门对，最终线路如图9所示。对比图8和图9可发现，使用MCT分解规则后，分解出的Toffoli存在对称性，用化简规则处理后，可得到Toffoli分解模板。其他符合MCT分解规则的MCT门亦可分解为有规则的Toffoli线路，因此均可按上述方法进行Toffoli线路分解为优化的NCV线路。
图 8 一般方法的分解结果
图 9 优化后的结果
-
基于上述2.1节的分析，本文提出一种MCT分解模板，对分解出的Toffoli线路套用模板后可同时完成分解和优化工作。
分解模板1：使用MCT分解规则后，若分解出的Toffoli门是第m−1个或第3m−5个Toffoli门时，称其为特殊Toffoli门。此种情况下，可将Toffoli门使用模板替换为量子代价为4的NCV线路。如图10所示。
图 10 特殊Toffoli门优化分解模板
分解模板2：当分解出的Toffoli门不是特殊门时，称为一般的Toffoli门。此时的Toffoli门可使用模板直接替换为图11所示的3量子代价的NCV线路。
图 11 普通Toffoli门优化分解模板
-
根据提出的MCT分解为NCV的优化模板，给出了MCT分解优化算法：先对MCT门进行判断，若符合MCT分解规则，则应用Toffoli分解模板1、2进行处理。设欲优化的MCT门输入线数为n，控制位数为m。MCT门优化分解算法如下。
Input: MCT线路 G，线数n，控制位数m
Output: NCV线路
$G' $ begin
if (m∈{3,4,···,n/2})
分解成4(m−2)个Toffoli门
for(i=0 to i<4(m−2)) do
if 是特殊门 应用分解模板1
else 应用分解模板2
i++
end
本算法的时间复杂度为O(m)。在传统的方法中，文献[18]先将MCT门分解为NCV线路，遍历所有分解后的NCV门，逐个查找后面是否有可以删除的可逆门对，直到线路无变化为止，所需时间复杂度为O(m2)。
-
为了验证所提优化模板的有效性，使用C++语言实现了本文描述的算法，实验环境为Intel(R) Core(TM) i5-7200U CPU@2.5 GHz、8 GB内存及Windows10操作系统。分别用本文算法和已有算法对m∈{3,10}的MCT门进行测试，结果如表1所示。
为测试在实际应用中的效果，分别用本文算法和已有算法对Benchmark部分例题进行实验，结果如表2所示。可以看出，本算法的量子代价与文献[18]方法优化后的量子代价基本一致，但运行时间有较大改善。结果表明，本算法对于控制位越多的MCT门，分解时量子代价、执行时间的优化效果越好，整体优化效果越明显。
表 1 MCT门分解效果
Benchmark 量子代价 执行时间/s 分解后未化简 先分解，再优化[18] 本文算法 分解后未化简 先分解，再优化[18] 本文算法 3_17_13 14 14 14 - 0.002 0.002 4gt10-va_81 48 36 36 - 0.012 0.005 4gt11_84 7 7 7 - 0.003 0.001 4gt4-v0_80 58 44 44 - 0.025 0.006 4gt5_75 28 22 22 - 0.008 0.003 ham15_108 642 458 458 - 1.76 0.079 Ham7_104 111 87 87 - 0.061 0.010 Hwb4_52 23 23 23 - 0.007 0.002 Hwb6_58 170 144 146 - 0.142 0.021 Mod5adder_128 111 87 87 - 0.105 0.012 表 2 Benchmark分解效果
-
本文提出了一种MCT门分解模板，套用该模板可快速完成MCT转NCV的分解与优化。与文献[12]中先得到传统方法分解出的NCV线路，再对NCV线路进行优化的方法相比，时间复杂度由O(m2) 降为O(m)。通过对控制位m∈{3,10}的MCT门与部分Benchmark例题进行测试，验证了该算法的有效性。今后将尝试其进一步分解，同时也考虑加入Peres或Fredkin等新门，进一步降低量子代价。
A Method for Decomposing and Optimizing MCT Gate Quantum Reversible Circuits
-
摘要: 为提高可逆线路中MCT门的分解和优化效率，提出了一种MCT门的优化分解方法，根据该方法得出MCT分解模板并验证了正确性。基于该模板给出了相应的分解与优化算法，算法对MCT门分解出的Toffoli线路进行分类，使用优化分解模板将其分解为NCV线路。该算法的时间复杂度为O(m)，优于传统算法的复杂度O(m2)。通过对控制位m∈{3,10}的MCT门与Benchmark可逆线路的实验，验证了该算法优化和分解的有效性。Abstract: One of the key problems in reversible logic synthesis is optimizing the reversible circuits, and the focus of research is on how to decompose advanced reversible gates into basic reversible gates more efficiently. To improve the decomposition and optimization efficiency of Multiple Control Target (MCT) gates, an optimal decomposition method of MCT gates is proposed in the paper, along with an MCT decomposition template which correctness is verified. Based on this template, the corresponding decomposition and optimization algorithm is given. Using the optimal decomposition template, the algorithm classifies the Toffoli circuits decomposed by MCT gates and decomposes them into NCV circuits. The time complexity of the algorithm is O(m), which is better than O(m2) for the conventional algorithm. Experiments on MCT gates with benchmark reversible circuits for control bits m∈{3,10} show the effectiveness of the algorithm’s optimization and decomposition.
-
Key words:
- circuit optimization /
- MCT gate /
- NCV gate /
- quantum circuit /
- reversible logic synthesis
-
表 1 MCT门分解效果
Benchmark 量子代价 执行时间/s 分解后未化简 先分解，再优化[18] 本文算法 分解后未化简 先分解，再优化[18] 本文算法 3_17_13 14 14 14 - 0.002 0.002 4gt10-va_81 48 36 36 - 0.012 0.005 4gt11_84 7 7 7 - 0.003 0.001 4gt4-v0_80 58 44 44 - 0.025 0.006 4gt5_75 28 22 22 - 0.008 0.003 ham15_108 642 458 458 - 1.76 0.079 Ham7_104 111 87 87 - 0.061 0.010 Hwb4_52 23 23 23 - 0.007 0.002 Hwb6_58 170 144 146 - 0.142 0.021 Mod5adder_128 111 87 87 - 0.105 0.012 
下载: 导出CSV
-
[1] 陈汉武, 李文骞, 阮越, 等. 基于汉明距离递减变换的可逆逻辑综合算法[J]. 计算机学报, 2014, 37(8): 1840-1845. CHEN H W, LI W Q, RUAN Y, et al. A synthesis algorithm of reversible logic circuit based on the decreasing transform of Hamming distance[J]. Chinese Journal of Computers, 2014, 37(8): 1840-1845. [2] GAOFENG L, SHEXIANG J, LIANG Z. Quantum image filtering and its reversible logic circuit design[J]. International Journal of Embedded Systems, 2021, 14(3): 248-258. doi: 10.1504/IJES.2021.116111 [3] LANDAUER R. Irreversibility and heat generation in the computing process (reprinted from IBM research and development, vol 5, 1961)[J]. IBM Journal of Research and Development, 2000, 44(1/2): 261-269. [4] BENNET M A, SELVI TM, PRIYA S M, et al. Efficient approaches for designing the logical reversibility of computation[J]. International Journal on Smart Sensing and Intelligent Systems, 2017, 10(4): 46-61. [5] ARABZADEH M, SAEEDI M, ZAMANI M S. Rule-Based optimization of reversible circuits[C]//2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC 2010). New York: IEEE, 2010: 853-858. [6] 程学云, 谈莹莹, 管致锦, 等. 优化的可逆MCT电路化简算法[J]. 量子电子学报, 2017, 34(6): 713-720. CHENG X Y, TAN Y Y, GUAN Z J, et al. An optimized siplification algorithm for reversible MCT circuits[J]. Chinese Journal of Quantum Electroincs, 2017, 34(6): 713-720. [7] 王艺臻, 管致锦, 管海宇. 基于预评价的量子电路线性最近邻综合算法[J]. 量子电子学报, 2021, 38(1): 75-85. WANG Y Z, GUAN Z J, GUAN H Y. Linear nearest neighbor synthesis algorithm of quantum circuits based on pre-evaluation[J]. Chinese Journal of Quantum Electronics, 2021, 38(1): 75-85. [8] GOLUBITSKY O, MASLOV D. A study of optimal 4-bit reversible Toffoli circuits and their synthesis[J]. IEEE Transactions on Computers, 2012, 61(9): 1341-1353. doi: 10.1109/TC.2011.144 [9] MASLOV D, DUECK G W, MILLER D M. Techniques for the synthesis of reversible Toffoli networks[J]. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2007, 12(4): 42-62. doi: 10.1145/1278349.1278355 [10] PHILIPP N, de ALEXANDRE A A A, GERHARD D, et al. Template-Based mapping of reversible circuits to IBM quantum computers[J]. Microprocessors and Microsystems, 2022, 90: 104487. doi: 10.1016/j.micpro.2022.104487 [11] ESLAMY M, HOUSHMAND M, SEDIGHI M, et al. Optimization of one-way quantum computation measurement patterns[J]. International Journal of Theoretical Physics, 2018, 57(11): 3296-3317. doi: 10.1007/s10773-018-3844-x [12] SLIMANI A, BENSLAMA A, MISRA N K. Optimal designs of reversible/quantum decoder circuit using new quantum gates[J]. International Journal of Theoretical Physics, 2022, 61: 72-91. doi: 10.1007/s10773-022-05017-w [13] ADISA I A, WONG T G. Implementing quantum gates using length-3 dynamic quantum walks[J]. Physical Review Research, 2021, 104(4): 042604. doi: 10.1103/PhysRevA.104.042604 [14] EZAWA M. Universal quantum gates, artificial neurons, and pattern recognition simulated by LC resonators[J]. Physical Review Research, 2021, 3(2): 023051. doi: 10.1103/PhysRevResearch.3.023051 [15] ALI M B, RAHMAN M M, RAHMAN H A. Design and optimization of nanometric reversible 4 bit numerical comparator[C]//2012 International Conference on Informatics, Electronics & Vision (ICIEV). New York: IEEE, 2012: 577-581. [16] BARENCO A, BENNETT CH, CLEVE R, et al. Elementary gates for quantum computation[J]. Physical Review A, 1995, 52(5): 3457-3467. doi: 10.1103/PhysRevA.52.3457 [17] MILLER D M, WILLE R, SASANIAN Z. Elementary quantum gate realizations for multiple-control Toffoli gates[C]//2011 41st IEEE International Symposium on Multiple-Valued Logic (ISMVL). Los Alamitos: IEEE, 2011: 288-293. [18] TAN Y Y, CHENG X Y, GUAN Z J, et al. Multi-Strategy based quantum cost reduction of linear nearest-neighbor quantum circuit[J]. Quantum Information Processing, 2018, 17(3): 61-73. doi: 10.1007/s11128-018-1832-y -
点击查看大图
图(11) / 表(2)
计量
- 文章访问数: 4723
- HTML全文浏览量: 1287
- PDF下载量: 52
- 被引次数: 0
