基于Visio的量子电路矢量图自动绘制

2015-07-18 13:31王秋里等
电脑知识与技术 2015年12期
关键词:真值表

王秋里等

摘要:目前量子可逆逻辑电路的绘制工作十分复杂。虽然现有的自动绘图工具只能满足基本的绘图需求,但是它们绘制出的是低分辨率的点阵图,而这种点阵图很难满足研究者们在论文发表时对高清图像的要求。因此,用C#对Visio绘图功能进行二次开发,解析并描述用户提供的量子电路TFC文件, C#读取用户对电路多种格式的自定义参数,依次画出所需的量子门,则可自动绘制出符合高清要求的矢量量子电路图。因为可逆逻辑量子电路的操作是为了得到特定的信号,所以真值表的计算可以验证这个电路是否已经达到事先设置的要求。所以还提供该量子电路的真值表,方便用户查看并分析产生的量子电路。

关键词:量子电路;点阵图;量子门;TFC文件;Visio二次开发;真值表

中图分类号:TN91 文献标识码:A 文章编号:1009-3044(2015)12-0237-04

Visio-based Automatically Drawing of Vector Quantum Circuit

WANG Qiu-li, CAI Song-cheng, JI Yan-yu, CHEN Zhou-ling, WU Yang-yang, LI Zhi-qiang, FENG Xiao-xia

(College of Information Engineering, Yangzhou University, Yangzhou 225009, China)

Abstract: Drawing quantum reversible logic circuits are very complicated at present. The existing automatic drawing tools meet the needs of the basic drawing, but it can only draw the low-resolution bitmaps. But these kinds of bitmaps are difficult to meet the requirements of high-definition images when the paper was published. Therefore, further development of the Visios drawing function is achieved by using C#, the description files of quantum circuits--TFC files are parsed, the parameters of many user-defined formats for circuits are read by c#, then the required quantum gates are drawn in turn, finally the high-definition vector graphs meeting the requirements are drew automatically. The operation of quantum reversible logic circuits is for a specific signal, so the truth table can verify whether the circuit has to meet the requirements set in advance. It also provides a truth table of the quantum circuit for users to view and analyze the result of quantum circuits.

Key words: quantum circuit; bitmaps; quantum gates; TFC file; Visio secondary development; truth table

量子逻辑门的组合与级联是组成量子计算机的基本元素,科研人员做了大量的工作来研究构造代价最小的量子电路[1-3]。但是量子电路的绘制一直是一项繁琐的工作,如果动手绘制,工作效率低下;如果使用现有的绘图工具,只能得到清晰度不高的点阵图,不能够满足科研人员撰写论文的需要。

Microsoft Office Visio[4]是一款功能强大的矢量图绘图与建模工具。它能够提供多样的模板和形状,使用户能以拖拽的方式绘制流程图和类图等图形。Visio绘制出来的图也可以直接进行拖拽修改,而且清晰度高、图像质量好,能满足各期刊发表论文的要求。由于Visio提供了编程接口,因此我们可以使用C#编程语言调用这些接口对Visio进行二次开发[5],将复杂的绘图工作交给计算机自动实现。

1 基本概念

1.1 量子电路可逆逻辑综合

量子电路可逆逻辑综合,主要是研究在给定量子门及给定量子电路的约束条件及限制下,生成代价最小的量子可逆逻辑电路,以及它的可逆逻辑综合理论和电路生成方法。它包含合成和优化两个方面,现在很多方法是将合成与优化这两个过程同时进行,在不改变可逆电路函数功能的条件下,对电路进行重组、替换,来减少电路逻辑门数量,从而降低量子可逆电路的代价。当然,如果使用不同的实现技术,通常量子可逆门的代价是不相同的。为此人们提出了若干可逆逻辑电路综合的算法,如穷举法[6-8]、基于代数的方法、基于模板的方法、基于真值表的方法等。这些方法各有优缺点,但不管专家们用何方法生成了最优量子电路,最终需要将生成的量子电路图绘制出来,方便检查、核对、展现。本文则根据专家们生成的最优量子电路的TFC文件,完成量子电路图的绘图功能。

1.2 量子逻辑门

在经典计算机中,二进制信息以比特(bit)形式存储,物理上可以是在晶体管电子电路中的电压信号;数学上可以是布尔值或者变量。但在量子计算领域中,这样的二进制信息均以量子状态形式存储,比如光子的偏振和围绕单个原子核电子的两种状态(基态/激发态)或者均匀电磁场中的电子/原子核的自旋(向上/向下)等。不同于经典比特,量子比特能够以其经典比特的叠加态的形式存在。量子门的操作可以用代表量子门的矩阵与代表量子比特状态的向量相乘来表示。

量子逻辑门是处理量子信息的基本单元,其级联构成可逆的量子电路。量子计算中,一个量子逻辑门对应一个幺正变换。量子门常使用矩阵表示,例如操作K个量子比特门可以表示成2k * 2k的酉矩阵[9]。一个量子电路的输入与输出数量必须相等。根据量子输入输出的个数,逻辑门可分为单量子比特门[10]与多量子比特门。

1)非门(NOT门)

如图1所示。非门为单量子门,即一个输入与一个输出。输入的a经过非门之后则输出a的相反状态。

此类单量子门很多,如:Hadamard门、Pauli-X门、Pauli-Y门等都是单量子门。多比特量子系统则是单比特系统的推广,量子力学的基本原理指出单独的状态向量可以通过张量积形式和其他状态向量结合起来。

2)控制V门

控制V门如图2所示,两个输入与两个输出则为2比特量子门。a为控制端,b为受控端。当控制信号a=0时,则b的输出不变,即Q=b。当控制信号a=1时,则输出为[V=i+12 1-i -i 1],是b的幺正操作,即Q=V(b)。

3)量子异或门

即控制非门(CNOT门),它和经典异或门非常类似。如图3所示,它有2个输入比特,a表示控制比特,b表示受控条件反转比特。当控制比特等于1,即在上能级时,受控比特状态发生反转,否则保持不变。

4)Toffoli量子门

Toffoli是CNOT门的受控行为的推广,是一个具有两个控制量子比特、一个目标量子比特的常用量子门。不同于CNOT门,Toffoli门目标量子比特只有在两个控制量子比特都置为“1”时才翻转,即实现变换[A,B;C→A,B;AB⊕C]。如图4所示。

5)控制交换门

如图5所示,即Fredkin门。当C=0时,a与b的输出保持不变,当C =1时,a与b的值交换。

2 Visio编程接口的各种函数的功能与调用方法

为了实现软件的画图功能,需要引用各类命名空间来配置系统。其中一些特殊的命名空间所包含的功能对实现程序功能起着重要作用。

程序需要用到Visio命名空间,在这个命名空间里包含了所有画图所需要的方法。比如DrawOval方法,这个方法可以画出一个圆,一共四个参数,前面两个参数为坐标,后面两个参数为高度和宽度。除此之外,我们还用到了其他的方法让程序更适合用户使用。

在使用Visio的时候,如果打开了Visio软件窗口,在自动完成绘图的情况下,窗口难免显得多余,所以调用了InvisibleAppClass方法,创建一个不可见的应用程序,也就是在不打开Visio窗口的情况下打开Visio软件,并控制程序的环境。让画图过程在后台完成,保证了程序界面的简洁。

在程序中,使用了Document方法[11-12]。Document表示一个绘图、模具或模板文件。在打开Visio文档或创建新文档时,都会创建一个新的Document对象,并将其添加到Application对象的Documents集合中。在绘制图像的时候,使用Page 对象表示前景或背景的绘图区域,也就是当前绘制电路图的绘图区域。利用Shape创建一个图形对象,这个对象可以接收画出的线条或者图形,并通过调用相应方法对这个对象进行一定的调整。然后再利用DrawOval、DrawRect等方法画出需要的图形。在图像中所需要的文字信息的字体和大小,分别用void set_CharProps和Cell get_CellsSRC方法来设置。

3 量子电路描述的TFC文件格式

TFC文件是一种包含量子电路信息的文件。它为量子电路提供了一种统一的、格式化的文件存储方式,方便我们快速地读取、识别并画出量子电路图。

TFC文件主要可以分为两个部分。第一部分为前四行,主要描述了电路的基本信息。第一行.v给出所绘制的电路图的行数;第二行.i给出输入端(即Input);第三行.o给出输出端(即Output);第四行.c给出剩余电路的标号。第二部分在BEGIN和END之间为需要绘制的量子逻辑门,量子逻辑门的每一行先给出所要画的门的种类,再给出其控制端和受控端信号。

如图6所示为TFC文件内容格式,第一行.v包含a,b,c,d,表示这个电路一共有a,b,c,d四行;第二行.i包含a,b,c,表示信号由a,b,c这三个端口输入;第三行.o包含d,表示信号由d端输出;剩余的电路信息则为0。紧接着BEGIN和END之间则是画出完整电路图的内容格式。下一节具体介绍门电路的绘制。

4 系统实现

4.1 TFC文件的算法

程序在识别TFC文件时,以行为单位进行逐行读取。当读完TFC文件的第一部分时绘制出电路的基本框架,当读到BEGIN时则开始正式画门及电路。以行为单位,每一行的开头如T1,f3,V,p3等均表示量子门的门类型,程序通过量子门名称的匹配判断分别调用相应电子门绘制函数,其后的端口信息则作为参数传递给所调用的绘制函数,画出相应的门电路。

本软件所能识别的量子逻辑门种类包括T门、F门、H门、V门、V+门、P3门、S门、T门以及T+门。T类门可识别T1~T21这21种门,对应的端口个数分别为1~21。F类门可识别F2,F3,F4,F5四种门,对应的端口个数分别2个,3个,4个和5个。H门、S门、T门、T+门对应的端口个数均为1个。V门、V+门的端口个数为2个。P3门端口个数为3个。

4.2 调用Visio接口函数绘制电路图的算法

同一类型的量子门为一个类(如所有以通用Toffoli门的形式画出的量子门为一个类),在类里面实现一个量子门的绘制。在正式介绍各类门画法之前要设置绘制量子门时的参数变量,如控制点半径,受控点半径,行间距,门间距,换行基数,这些变量都可以自行设置来调整电路图的美观。

程序在匹配并调用相应的量子门绘制函数后,若控制端和受控端的个数与已匹配的量子门所应有的个数不符,则出错。上述TFC文件将如何调用量子门函数:首先,程序识别到.v a b c d时,确定整个电路的行数,接着确定电路的输入与输出标识并画出,如图7的a,b,c等;再判断BEGIN后面一共几个函数(即一共几个门),用门数确定整个电路横线的长度并画出;接着依次调用门函数画出量子电路门。得到的量子电路图如图7所示。接下来介绍程序如何依次调用门函数画出所需的量子电路图。

1)通用Toffoli门

绘图过程中,若将绘制的门在电路图中为第一个门(如图7第一个门)则规定它在纵向上为第一个位置,横向由控制端与受控端决定。

当通用Toffoli类门只含一个参数时,如T1(a),则被认定为受控端,即一个非门。

如图7中,第一个门调用函数为T2(b,d),即控制非门。在图中,b点为控制点,d点为受控点。通用Toffoli类规定最后一个参数对应的是受控制端,其他均为控制端。

图7中,第二个门调用函数为T3 (a,c,b),此通用Toffoli门为电路的第二个门,从开始位置将纵轴将向后移一个门的位置开始绘制。前面两个参数a, c对应的是控制端,其中a表示一个空心圆的控制端,即表示非,c用实心圆表示(注:此文章中所有带单引号的参数都表示空心圆);b则对应受控制端,受控制端则用一个带“十”字的圆来表示。然后比较三个参数的大小,确定一个最大值和一个最小值,此处最小值为a,最大值为c。在a和c所代表的两条水平线上画一条竖线,从而形成一个Toffoli量子门。当参数变多时,绘图的过程也是如此。

由上述可知,带三个参数的Toffoli量子门相应的函数见算法1:

[算法1 类通用Toffoli量子门图形的绘制函数Toffoli(c1,c2,c3)\&输入:控制端c1,c2和受控端c3

输出:Toffoli门

1. MAX=max(c1,c2,c3) //取c1,c2,c3的最高点

2. MIN=min(c1,c2,c3) //取c1,c2,c3的最低点

3. Drawline(MIN,MAX)//最高点最低点之间画一条竖线

4. DrawControlCircle(c1)//画控制端c1

5. DrawControlCircle(c2)//画控制端c2

6.. CrossCircle(c3)//画受控端c3\&]

2)Fredkin门

如图7所示,Fredkin门为电路的第三个门,从开始位置将纵轴将向后移二个门的位置开始绘Fredkin门。Fredkin门至少有三个参数。当Fredkin门有三个参数或多个参数时,最后两个参数均为受控制端,前面剩余的参数作为控制端,可有多个控制端。此时受控制端用一个“X”形表示。

图7中,第三个门调用函数为f3(b,c,d),此时控制端为b,受控端为c和d。然后比较三个参数的大小,同理通用Toffoli门。从而画出一个Fredkin门。当参数变多时,绘图的过程也是如此。三个参数的Fredkin门相应的函数见算法2。

3)控制V门

如图7,控制V门为电路的第四个门,从开始位置将纵轴将向后移三个门的位置开始绘V门。V门只有两个参数,第一个参数代表控制端,第二个参数代表受控制端,受控端用带“V”的矩形框表示。控制V+量子门同样只有两个参数,与控制V门不同的是,用带“V+”的矩形框表示受控制端。

[算法2 类Fredkin量子门图形的绘制函数Fredkin(c1,c2,c3)\&输入:控制端c1和受控端c2,c3

输出:Fredkin门

1. MAX=max(c1,c2,c3) //取c1,c2,c3的最高点

2. MIN=min(c1,c2,c3) //取c1,c2,c3的最低点

3. Drawline(MIN,MAX) //最高点最低点之间画一条竖线

4. DrawControlCircle(c1)//画控制端c1

5. Cross(c2)//画受控端c2

6. Cross(c3)//画受控端c3\&]

图7中,第四个门调用函数为v(b,a),此时b表示控制端,a表示受控端。然后比较两个参数的大小,同理通用Toffoli门,则画出一个控制V门。对应的函数见算法3:

[算法3 类控制V量子门图形的绘制函数V(c1,c2)\&输入:控制端c1和受控端c2

输出:V门

1. DrawRectangle(c2)//在c2处画矩形

2.Shape1.Text=”V”//给矩形标注”V”

3. Drawline(c1,c2)//在c1,c2之间画竖线

4.DrawControlCircle(c1)//画控制端c1\&]

5 真值表生成算法

因为可逆逻辑量子电路的操作是为了得到特定的信号,所以真值表的计算可以验证这个电路是否已经达到事先设置的要求。关于生成真值表,只阐述通用Toffoli类门生成真值表。本软件对其他类型门的生成真值表暂时不支持。

量子电路的传输信号可以分为两类:0和1。通用Toffoli类门的传输信号由控制端和受控制端提供。所以求真值表的过程,实际上就是对数字信号进行组合,直到输出符合的信号为止。

控制端可分为实心圆和空心圆,空心圆表示若接受的控制信号为“1”,则将控制信号转换为“0”;若接收的控制信号为“0”,则将控制信号转换为“1”。实心圆表示接受的控制信号为“1”,控制信号就为“1”;接收的控制信号为“0”,控制信号就为“0”。在计算真值表的时候,输入端输入的信号种类按照2n来计算,即如果输入端有2个输入信号,则输入的信号有22=4种,以此类推。

图7所示电路中第一个门,控制端是实心圆,所以当b接收的控制信号为“1”时,则d信号输出翻转。当b接收的信号为“0”时,d信号输出则不变。图7电路中第一个门的真值表为表1所示。

如果出现空心的控制端和实心的控制端同时出现的情况,则受控端的信号同时受两种控制端控制。受控制端信号置反的条件是:实心控制端接收“1”信号,空心控制端接收“0”信号,即为两种控制端分别接受相匹配的信号。如图7中第二个门的真值表如表2所示。

程序中,得到2n个信号种类之后,将0到2n依次转化为2进制,再将2进制信号与控制端激发信号匹配,如果所有控制端的信号都能够匹配,则改变受控制端的信号。如果不能完全匹配,则不改变信号。

6 结束语

本软件采用C#语言编写,是为将来能够更好的移植到web平台做准备。用户已经可以利用本软件得到自定义的高清电路图,满足他们画图需求。接下来我们会把这款软件移植到web平台,并建立数据库。这样不仅能够画出用户需要的图像,还能对已经绘出的图像进行分析,将不同的电路图进行对比,计算出它们的垃圾输出与量子代价等信息,并与历史最优结果进行比较,得出这些电路的各种统计报表,为优化量子电路的综合算法提供参考数据,更好地为量子电路的研究人员提供画图和对比服务。

参考文献:

[1] 李志强, 冯小霞, 陈汉武. 基于量子可逆逻辑的桶型位移器设计[J]. 量子电子学报, 2014, 31(6): 720-727.

[2] 李志强, 冯小霞, 陈汉武. 基于控制K次平方根非门的类Toffoli门构造方法[J]. 数据采集与处理, 2014, 29(6): 975-980.

[3] Li, Zhiqiang; Song, Xiaoyu; Perkowski, et al. Realization of a new permutative gate library using controlled-kth-root-of-NOT quantum gates for exact minimization of quantum circuits[J]. International Journal of Quantum Information, 2014, 12(5): 34-52.

[4] 何凯. 基于Visio的CAPP绘图工具的研究与开发[D]. 成都: 西华大学, 2010.

[5] 朱昊, 雷鸣, 高山. Visio二次开发技术在电气工程教学图形化中的应用[J]. 电气电子教学学报, 2006, 28(1): 95-97.

[6] Shende V V, Prasad A K, Markov I L, et al. Synthesis of reversible logic circuits[J]. Computer Aided Design of integrated circuits and systems, 2003, 22(6): 710-722.

[7] Iwama K, Kambayashi Y, Yamashita S. Transformation rules for designing CNOT-based quantum circuits[C]// Proceedings of 39th Design Automation Conference. New Orleans, LA, 2002.

[8] Gupta P, Agrawal A, Jha N K. An algorithm for synthesis of reversible logic circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(11): 2317-2330.

[9] 王冬, 陈汉武, 朱皖宁等. 多值逻辑量子置换门的酉矩阵表示[J]. 计算机学报, 2012, 35(3):639-644.

[10] 施教芳. 量子计算机前瞻:量子门与量子电路模型[J]. 微电子技术, 2002, 30(4): 25-28.

[11] 王飞漩, 魏清新, 王坤明. 基于Visio二次开发的故障树存储方法研究[J]. 计算机测量与控制, 2013, 21(9): 372-374.

[12] 刘强, 刘向君, 马旭勃. 利用Visio二次开发实现逻辑图自动分析[J]. 软件导刊, 2009, 8(1): 13-15.

猜你喜欢
真值表
电子技术教学中实验环节的有效利用
四识简单逻辑电路
任务引领的组合逻辑电路应用教学设计
基于粒矩阵的多输入多输出真值表快速并行约简算法
浅谈电气控制线路的逻辑代数设计方法
写真法、写假法探析