量子线性卷积及其在图像处理中的应用

刘兴奥 周日贵 郭文宇

线性卷积是科学工程上的重要工具,在图像处理中发挥了重要作用,例如基于均值滤波器和高斯滤波器实现图像平滑[1],基于拉普拉斯算子实现图像锐化[1],基于索伯梯度算子实现图像边缘检测,使用基于对称式扩充卷积的残差网络进行图像去噪[2].对于M×M图像和N×N滤波器,其卷积操作的时间复杂度是O(M2N2).虽然经典计算能求出线性卷积结果,但是在处理海量高分辨率图像时,求解线性卷积会消耗大量计算资源.量子计算为解决该问题提供了一种新的解决方案.

量子力学的量子叠加和量子纠缠特性使得量子计算在处理某些特定问题上具有显著的速度优势,例如大数因子分解算法(Shor 算法)[3],数据库搜索算法(Grover 算法)[4],线性方程求解算法(HHL 算法)[5],粗糙集核属性求解算法[6],映射量子模型[7],孪生支持向量机[8]和量子主成分分析[9-10].目前关于量子线性卷积的研究集中在量子一维卷积(Quantum one-dimensional convolution,QOC)和量子二维卷积(Quantum two-dimensional convolution,QTC).Lomont[11]证明,如果使用振幅编码将两个一维序列制备成两个量子态,那么在允许使用线性算子(酉算子和测量算子)和辅助量子比特的情况下,基于量子力学不能计算它们的量子循环卷积|c〉⊗|g〉, 其中|c〉表示卷积结果,|g〉表示垃圾项.闫茜茜等[12]提出量子一维窄卷积,首先使用振幅编码信息,利用量子态张量积性质获取振幅的乘积,接着使用置换矩阵实现振幅的置换,然后使用哈达玛门(Hadamard,H)量子门进行加法计算,最终获得量子态|c〉⊗|0〉+|g〉⊗|0〉⊥,|c〉是卷积结果.随后闫茜茜等[13]又提出量子二维窄卷积,其实现过程同量子一维窄卷积相似.另外,量子图像滤波[14-17]和量子图像边缘检测[18-29]等算法使用量子算术计算线性卷积.虽然上面三种方案都可以实现量子线性卷积,但各有不足.闫茜茜等提出的量子一维和二维线性卷积方法不适用于求解量子线性宽卷积和量子线性等宽卷积,量子图像滤波和量子图像边缘检测中的量子二维线性卷积算法需要消耗大量的量子比特资源.

本文研究内容包括量子线性卷积的实现和应用两方面.首先提出单通道,单位步长,零补充情况的量子一维宽卷积(Quantum one-dimensional wide convolution,QOWC),量子一维等宽卷积(Quantum one-dimensional equal-width convolution,QOEC),量子一维窄卷积(Quantum one-dimensional narrow convolution,QONC),量子二维宽卷积(Quantum two-dimensional wide convolution,QTWC),量子二维等宽卷积(Quantum two-dimensional equal-width convolution,QTEC),量子二维窄卷积(Quantum two-dimensional narrow convolution,QTNC).然后实现多通道,非单位步长,非零补充情况的QOWC,同样适用于QOEC,QONC,QTWC,QTEC,QTNC.最后基于量子二维线性卷积实现量子图像平滑(Quantum image smoothing,QISM),量子图像锐化(Quantum image sharpening,QISH) 和量子图像边缘检测(Quantum image edge detection,QIED)算法,并在Qiskit 上进行仿真实验.理论分析证明了在时间和资源消耗方面量子线性卷积相比于经典线性卷积呈指数下降.

本文后续部分组织结构如下.第1 节介绍线性卷积和量子计算的相关知识.第2 节实现QOWC,QOEC,QONC,QTWC,QTEC,QTNC.第3 节实现QTC 在QISM,QISH 和QIED 上的应用.第4 节总结和展望.附录A 给出置换电路的优化方法.附录B 给出量子态制备方法.

1 预备知识及符号说明

1.1 线性卷积

为避免因读者研究背景不同导致的对相关术语理解存在部分歧义的问题,本文将在此节中对相关学术名词及符号做合理规范,读者的阅读请务必参考此规范开展.根据维度d,补充p, 步长s,通道数c参数的不同,线性卷积存在多种变体.本节重点介绍单通道,零补充,单位步长的一维,二维线性卷积.在单通道,单位步长,零补充情况下,线性卷积根据补零的数量又可以划分成宽线性卷积(宽卷积),等宽线性卷积(等宽卷积)和窄线性卷积(窄卷积).

1.1.1 一维线性卷积

令输入序列X=[x0,x1,···,xM-1], 卷积核Y=[y0,y1,···,yN-1],M＞N.当M＜N,则将Y作为输入序列,X作为卷积核.

一维宽卷积结果是Zw=[z0,z1,···,zM+N-2],满足展开成矩阵形式可以写成

一维等宽卷积结果是Ze=[z0,z1,···,zM-1],满足展开成矩阵形式可以写成

一维窄卷积结果是Zn=[z0,z1,···,zM-N],满足i=0,1,···,M -N展.开成矩阵形式可以写成

1.1.2 二维线性卷积

二维卷积是一维卷积的扩展,可以看成是在行和列上分别做一维卷积.在不影响上下文理解的情况下,我们使用与一维卷积相同的变量表示物理含义.令输入序列X=[xi1,i2]M×M,卷积核Y=[yj1,j2]N×N,M＞N.当M＜N时,将Y作为输入序列,X作为卷积核即可.

1.2 量子计算

量子计算模型有很多,例如量子电路模型,量子绝热计算,量子图灵机,拓扑量子计算等[30],这些量子计算模型是等价的.本文采用量子电路模型,其模型易理解且接受范围最广.量子比特用于存储信息,它除了可以表示|0〉,|1〉, 还可以是|0〉和|1〉的叠加态.常用的基础门有单量子比特门X,Y,Z,H,S,T 和双量子比特门受控非门(Controlled-not gate,CNOT).这些基础门之间存在等价性关系,例如XZX=-Z.任意一种酉操作能以任意精度分解成一系列基础门.利用这些等价关系和分解方法可以简化复杂的量子电路[31].量子测量是不可逆的过程,它会引发量子态坍缩,通过量子态层析,量子过程层析,量子压缩感知等技术可以重构出量子态和量子操作的相关信息[31-32].本文使用时间复杂度和空间复杂度来衡量量子电路的性能.下面给出几种后续行文必需的量子操作:

引理 1.(量子随机存取存储器(Quantum random access memory,QRAM)[33-36]) 量子随机存取存储器可以以相干量子叠加形式执行内存访问.如果量子计算机需要访问一个叠加的存储单元,地址寄存器a必须包含一个地址的叠加量子随机存取存储器将在 O(log(MN)) 时间内,返回数据寄存器d中与地址寄存器相关的数据的叠加

引理 2.(量子振幅放大(Quantum amplitude amplification,QAA)[37]) 设U是酉操作,a是期望量子态的振幅.令其中θa满足sin2(θa)=a, 0＜θa ≤π/2.如果在量子系统中执行酉操作QmU|0〉并测量它,那么测量结果是期望量子态的概率至少是 max(1-a,a).

引理 3.(实数量子模拟数字转换器(Real quantum analog-to-digital conversion,Real QADC)[38]) 设是一串m比特数字写成它近似于cj的实数部分.一个m比特实数量子模拟数字转换器可以将模拟量子态转化成数字量子态该转换器需要使用 O(1/ε) 受控UA操作和O((log2N)/ε)个单、双量子比特门,并以 1-O(poly(ε)) 的保真度输出结果,其中ε表示输出精度.

2 量子线性卷积算法

本节研究单通道,单位步长,零补充情况下的量子一维和二维线性卷积,包括宽卷积,等宽卷积和窄卷积.第2.1 节实现了量子一维宽线性卷积,分析了它的时间复杂度和空间复杂度,并将其扩展到量子一维等宽卷积,量子一维窄卷积.第2.2 节实现了量子二维宽线性卷积,分析了它的时间复杂度和空间复杂度,并将其扩展到量子二维等宽卷积,量子二维窄卷积.我们在第2.3 节讨论了多通道,非单位步长,非零补充的情况.

2.1 量子一维线性卷积

把R0作为首行向量构造出一个Lt×Lt的循环矩阵w:

当i ＞N时,yN-1-i=0,P∈RLt×Lt是一个置换矩阵,矩阵形式是:

P†是它的共轭转置矩阵.那么一维宽卷积计算过程可以改写成,其中

行向量Zw的前M+N -1 个元素是所求的宽卷积结果,后Lt-M -N+1 个元素都是0,本文中称之为垃圾元素.将修改后的输入序列Xw与首行向量R0存储到量子随机存取存储器中.

图1 量子一维线性卷积实现电路Fig.1 Quantum circuit of one-dimensional linear convolution

在QR1⊗QR0上分别执行酉操作O1⊗O0:

设 eιθi=yN-1-i/|yN-1-i|表示R0中每个元素的符号位信息,在QR1上执行受控相位操作(CP):

基于量子一维宽卷积的实现框架,有两种不同的方法可以实现量子一维等宽卷积和量子一维窄卷积.第一种方法是在量子一维宽卷积的量子电路上再增加若干个置换操作,对于量子一维等宽卷积而言,额外增加操作(图1(b)所示),对于量子一维窄卷积而言,额外增加N-1个P†操作(图1(c)所示).第二种方法是仿照量子一维宽卷积算法,对于量子一维等宽卷积,重新制备,对于量子一维窄卷积,重新制备,使用它们替代方法一是基于量子一维宽卷积,会保留一些垃圾元素,而方法二不会保留垃圾元素.

通常输入序列的尺寸M和卷积核的尺寸N满足M≫N.量子一维线性卷积算法的空间复杂度是 O(logM).由于酉操作O0和O1的时间复杂度分别是 O(logM) 和 O(logN), 受控相位CP操作的时间复杂度是O(logN),受控置换操作的时间复杂度是逆操作的时间复杂度是O(logN),故量子一维线性卷积算法的时间复杂度是

相对于经典卷积时间复杂度 O(M),量子一维线性卷积算法实现了指数加速.文献[12]从卷积定义角度出发,首先以卷积核长度向输入序列截取对应长度进行内积计算,之后保持输入序列不变,卷积核进行一步移位操作,直到短向量最后一个元素与输入序列最后一个元素对齐并计算其内积,最终得到量子一维窄卷积结果.它的时间复杂度是,但算法无法扩展到量子一维宽卷积和等宽卷积.而本文从线性代数的角度出发,首先给出了量子一维宽卷积算法,并且可以很容易地将其推广到量子一维等宽卷积和量子一维窄卷积上.

2.2 量子二维线性卷积

如式(2)所示,二维宽卷积可以写成矩阵形式UwX=Zw,其中Uw是一般矩阵,为了使量子计算能够求解该线性方程组,我们需要重新调整该数据结构形式.在矩阵X四周进行补0 操作得到矩阵,然后将其向量化

其中前N2个元素来自于卷积核Y行向量化,把R0作为首行向量,构造循环矩阵

量子二维宽卷积的实现方法可以直接扩展到量子二维等宽卷积和量子二维窄卷积的量子实现上,有两种不同的实现方法.第一种方法是重新制备和以替代第二种方法是基于量子二维宽卷积的量子电路,分别在水平方向向左平移次,垂直方向向上平移1)次, 这种平移操作可以使用P†操作来实现.

通常输入序列的尺寸M和卷积核的尺寸N满足M≫N.量子二维线性卷积的空间复杂度是O(2logM), 时间复杂度是相对于经典二维线性卷积时间复杂度,量子二维线性卷积展现了其指数加速的优势.文献[13]给出了量子二维窄卷积算法,输入序列的量子态与卷积核的量子态进行张量积计算,使用两种置换操作共同完成量子卷积振幅置换,对置换后的卷积核量子态的量子比特执行H 门操作,输入序列量子态的量子比特执行单位矩阵操作,对卷积核量子态进行测量.该算法的空间复杂度和时间复杂度与本文相同,但其思考角度与本文不同,且其实现不适用于量子二维宽卷积和量子二维等宽卷积.

2.3 量子卷积算法讨论及扩展

上文介绍了单通道,单位步长,零填充情况下的量子一维宽卷积,等宽卷积,窄卷积,量子二维宽卷积,等宽卷积,窄卷积的量子实现.下面我们重点讨论量子一维宽卷积算法的实现和扩展,其他几种量子卷积实现和扩展与它相似.

在没有对输入序列进行填充的情况下,一维宽线性卷积可以写成线性方程形式(见式(1)),其中Uw∈R(M+N-1)×M.有三种量子算法可以求解这样的线性方程.第一种方法是使用类HHL 算法[5,40],首先将矩阵Uw变成厄米矩阵:

本文提出的量子一维宽线性卷积适用于扩展到多通道,非单位步长,非零补充的情况.以三通道为例,量子电路实现如图2(a)所示,在量子一维宽卷积的量子电路的基础上,额外再添加一个两量子比特的量子寄存器QR2, 此时QR0用于存储输入序列信息,QR1用于存储卷积核信息,QR2用于存储通道信息.实现步骤如下,首先应用两个H 门在QR2,接着根据通道信息在图像上使用不同的卷积核,最后再在QR2使用两个H 门,实现卷积结果融合.以步长为2 为例,量子电路见图2(b)在量子一维宽卷积的量子电路基础上,再增加一个置换矩阵:

图2 三通道/两步长的量子一维宽卷积实现电路Fig.2 Three-channel/two-stride quantum one-dimensional wide convolution realization circuit

图A1(d)给出了Γ1∈R8×8时的量子电路.以补充值是1 为例,此时式(3)改写成

3 量子卷积在图像处理中的应用

本节研究量子二维线性卷积在量子图像中的应用,例如量子图像平滑,量子图像锐化和量子图像边缘检测,旨在验证量子卷积算法本身的正确性及基于量子卷积实现量子图像处理算法的可行性.首先分别给出它们的量子算法,然后在Qiskit[43]上使用QasmSimulator 进行模拟,最后将它们和已有的量子图像处理算法比较.仿真平台的参数是操作系统Ubuntu 20.04.2 LTS 64 位,处理器CPU I9-10900X 10 核20 进程3.70 GHz,内存是62.5 GB,Qiskit 版本是0.26.2.

3.1 量子图像平滑

图像平滑常见操作有模糊处理和降噪处理,通常用于图像预处理任务中.模糊处理可在大目标之前去除图像中的一些琐碎细节,连接直线或曲线的缝隙.通过线性滤波和非线性滤波模糊处理,可以降低噪声.本节研究量子图像平滑,其基本流程是首先编码量子图像和卷积核(见附录B),接着使用量子二维线性卷积实现量子图像平滑.

以图3 为例,图3(a)是含有泊松噪声的实验图像Ip,图3 (c)是含有高斯噪声(均值为0,方差为0.01)的实验图像Ig, 它们的尺寸是 60×60.图3 (b)是均值滤波器,图3 (d)是高斯滤波器,它们的尺寸是 3×3.量子图像平滑算法对应的量子电路图如图4 (a)所示,最上面的10 个量子比特(QR0)用于存储量子图像信息,最下面的4 个量子比特(QR1)用于存储卷积核信息,最后一个是经典寄存器(CR),它有四个比特用于存储量子测量后坍缩的经典信息.需要特别指出,不同于前面描述的量子卷积的量子电路,由于本节使用的两个平滑滤波器的元素都是正数,因此在量子电路设计过程中,受控相位操作被省略.我们使用Qiskit 的QasmSimulator模拟量子图像平滑算法,其中参数shots设置为1 024,实现代码见1,https://github.com/liuxingao/SimulateCode/blob/main/NORMAL/mean_filter.ipynb2https://github.com/liuxingao/SimulateCode/blob/main/NORMAL/gaussian_filter.ipynb.模拟结果输出状态向量(状态向量的前1 024 个元素表示平滑滤波后的图像)以及量子寄存器QR1是全0 的概率.

图3 量子图像平滑的实验图像和平滑滤波器Fig.3 Experimental image and smoothing filter for quantum image smoothing

图4(b) 表明了均值滤波时输出0 的概率是0.935,图4(c)显示了量子模拟器输出的均值滤波后的图像,图4(d)显示了经典计算机使用SciPy3SciPy 包:https://docs.scipy.org/doc/scipy/reference/输出的均值滤波后的图像.两者在视觉上没有差异且抑制了泊松噪声.同样地,图4(e)表明了高斯滤波器时输出0 的概率是0.905,图4(f)显示了量子模拟器输出的高斯滤波后的图像,图4(g)显示了经典计算机使用SciPy 输出的高斯滤波后的图像,两者在视觉上没有差异且能抑制了高斯噪声.相比于均方误差(Mean-square error,MSE)和峰值信噪比(Peak signal-to-noise ratio,PSNR),结构相似性(Structural similarity,SSIM)的评价性能有明显提高[44],所以本文使用SSIM 评估两幅图像的相似性.均值滤波后的两幅图像的SSIM 是0.999 856 7,高斯滤波后的两幅图像的SSIM 是0.999 923 3,这表明两幅图像相同,同时,验证了量子图像平滑算法和量子卷积算法的可行性和正确性.

3.2 量子图像锐化

图像锐化可以补偿图像的轮廓,增强图像的边缘及灰度跳变的部分,使图像变得清晰.本节研究量子图像锐化,其基本步骤是首先对图像和卷积核编码,接着使用量子二维卷积算法对图像滤波,需要注意的是,与平滑滤波算子全是正数元素不同,锐化滤波算子存在负数元素,需要使用受控相位操作给负数元素项增加相对相位,可以得到量子态:

以图5 为例,图5(a)是实验图像,尺寸是 60×60,图5(b)是锐化算子,尺寸是 3×3.经典计算机模拟量子计算时,它的内存资源消耗和运行时间随量子电路深度、电路宽度变化呈指数增长.受现有量子实验设备以及仿真平台环境的约束,我们只能使用Qiskit 仿真实现步骤1,至于步骤2、3 将在步骤一的基础上按照逻辑进行经典运算,实现代码见4https://github.com/liuxingao/SimulateCode/blob/main/NORMAL/sharpen_filter.ipynb.量子图像锐化算法步骤一对应的量子电路图如图6(a)所示,未优化分解之前量子电路的电路宽度是20,电路深度是23.值得注意的是,受控相位操作中,除了量子态(下标是1,3,5,7)的相对相位翻转,还有其他量子态(下标是2,4,6,8)的相对相位也偏转成负值.相对相位对量子算法的结果影响很大,因此需要额外的受控相位门将量子态(下标是2,4,6,8)的相对相位恢复成正相位.我们使用Qiskit的QasmSimulator 模拟量子图像锐化算法,其中参数shots设置为1 024.模拟结果输出状态向量(状态向量的前1 024 个元素表示锐化后的图像)以及量子寄存器QR1是全0 的概率.图6(b)表明输出0 的概率是0.026,图6(c)显示了量子模拟器输出的锐化后图像,图6(d) 显示了经典计算机使用SciPy 输出的锐化后图像.两者在视觉上没有差异,且两幅图像的SSIM 是1.0,这表明两幅图像相同,同时,验证了量子图像锐化算法和量子卷积算法的可行性和正确性.

图5 量子图像锐化的实验图像和锐化滤波器Fig.5 Experimental image and sharpening filter for quantum image sharpening

图6 量子图像锐化的仿真电路和仿真结果Fig.6 Simulation circuit and simulation results of quantum image sharpening

3.3 量子图像边缘检测

边缘检测是图像处理和计算机视觉中的基本问题,边缘检测的目的是标识数字图像中亮度变化明显的点.图像边缘检测可大幅度地减少数据量,剔除不相关的信息,保留图像重要的结构属性.本节研究量子图像边缘检测,使用水平和垂直方向的Sobel 算子,最终获得的梯度图像是量子图像边缘检测的实现过程如下:

步骤 1.准备6 个量子寄存器,最左边表示第1个量子寄存器,最右边表示第6 个量子寄存器,q1表示存储卷积核所需量子比特数,q2表示存储图像所需量子比特数:

步骤 2.对第2 个量子寄存器执行H 门操作:

步骤 3.当第2 个量子寄存器是|0〉时,对第3个和第4 个量子寄存器执行量子卷积操作,卷积核是水平方向Sobel 算子(Sobelx),在第5 和6 个量子寄存器执行同样的量子卷积操作;当第2 个量子寄存器是|1〉时,对第3 个和第4 个量子寄存器执行量子卷积操作,卷积核是垂直方向Sobel 算子(Sobely),在第5 和6 个量子寄存器上执行同样的量子卷积操作:

步骤 4.第2 个量子寄存器执行H 门操作:

步骤 5.把第6 个量子寄存器中量子比特作为控制比特,第4 个量子寄存器中的量子比特作为目标比特,执行q2个受控非门操作:

其中,x=x1=x2,y=y1=y2,ξ=ξx=ξy,ρ=x=y=0,···,Lt-1,该量子态对应的状态向量的前Lt个元素就是.

步骤 6.使用Real QADC 方法将振幅添加到基态中:

步骤 7.使用量子比较器[45]比较第1 个量子寄存器与预设的阈值thre,如果大于阈值则第1 个量子寄存器设置为1,否则第1 个量子寄存器置为0:

以图7 为例,图7(a) 是实验图像,尺寸是12×12,图7(b)是水平方向的Sobel 算子,尺寸是3×3,图7(c) 是垂直方向的Sobel 算子,尺寸是3×3.受仿真平台环境约束,我们只使用Qiskit 仿真实现步骤1 至5,步骤6、7 将在此基础上按逻辑进行经典运算,实现代码见5.图8(a)给出了量子图像边缘检测步骤1 到5 的量子电路图,使用Qasm-Simulator 对它进行模拟,参数shots设置为1 024.模拟结果输出状态向量(状态向量的前256 个元素是边缘检测后的图像)以及量子寄存器QR1是0 的概率.图8(b)显示了输出是0 的概率,图8(c)显示量子模拟器输出的图像,图8(d)显示了经典计算机使用SciPy 输出的图像.两者在视觉上没有差异且两幅图像的SSIM 是1.0,这说明两幅图像相同,同时,验证了量子卷积算法的正确性和量子图像边缘检测算法的可行性.

图7 量子图像边缘检测的实验图像和 Sobel 算子Fig.7 Experimental image and Sobel operator of quantum image edge detection

图8 量子图像边缘检测的仿真电路和仿真结果Fig.8 Simulation circuit and simulation results of quantum image edge detection

量子图像边缘检测的效果受许多因素影响,例如算子,方向,阈值等.本节提出的基于水平垂直两个方向Sobel 算子的量子图像检测算法可以很容易扩展到四个方向Sobel 算子.

3.4 量子图像处理的讨论

基于量子卷积操作的量子图像处理算法已被广泛研究,主要涉及量子图像滤波,量子图像特征提取,量子图像边缘检测.这些算法实现量子卷积操作的思路大致如下,首先获取邻域像素值,接着根据滤波器的元素,使用量子算术实现卷积计算.其中邻域像素值获取方法可以细分为三类.假设卷积核算子的尺寸为 3×3,图像尺寸是M×M,M=2m, 图像灰度值范围是 [0,2q-1],q=1 表示二值图像,q=8表示灰度图像,q=24 表示彩色图像.第一类方法是制备9 份完全相同的量子图像,将循环操作分别作用于8 份量子图像,坐标信息相同的量子态构成邻域像素.第二类方法是制备1 份量子图像和用于存储像素值的8 个量子寄存器,依次使用循环操作和复制操作来获取相邻像素值.第三类方法是制备1 份量子图像和用于存储量子图像的8 个量子寄存器,依次使用量子比较器和复制操作获取相邻像素值.如表1 所示,这些算法的空间复杂度和时间复杂度都比较高.此外,第二类算法存在错误,量子图像的位置信息和像素值信息是纠缠的,移位后再复制的像素值都是相同的,通过理论推导或Qiskit 仿真可以验证.文献[27]中给出的量子图像检测算法只适用于二值图像,因此这里不做比较.

量子图像平滑算法需要 2m+4 个量子比特,时间复杂度是量子图像锐化算法需要2m+2log(1/ε)+5个量子比特,时间复杂度是O(4m2/ε+16log(1/ε)-3),ε是计算精度;量子图像边缘检测需要(4m+2log(1/ε)+7 个量)子比特,时间复杂度是 O16m2/ε+16log(1/ε)-3.本文提出的量子图像滤波(平滑和锐化)算法,量子图像边缘检测算法相比于其对应的经典算法,在存储能力和计算效率上都实现了指数加速;对比表1 中量子算法,在时间复杂度方面处于相同数量级,在消耗的量子比特数方面占有明显优势,使得它更有希望在目前的量子计算机上实现.但是基于本文提出的量子二维卷积操作的量子图像处理算法不适用于非线性量子图像滤波情况[46-50].

表1 已被提出的量子图像滤波和量子图像特征边缘检测算法.假设卷积核算子的尺寸为3 × 3,图像尺寸是 M ×M, M =2m,q 表示图像的灰度值范围Table 1 Quantum image filtering and quantum image feature edge detection algorithms have been proposed.Suppose the size of the convolution kernel operator is 3 × 3,and the image size is M ×M, M =2m,q represents the range of gray values

4 总结及未来工作

本文提出了单通道,单位步长和零补充情况下的QOWC,QOEC,QONC,QTWC,QTEC,QTNC.当通道,步长,补充值等参数发生变化时,其对应的算法实现只需轻微调整.理论分析证明量子线性卷积的空间复杂度 O(logM) 和时间复杂度O(log2M)较经典线性卷积有指数级下降.另外,本文基于量子线性卷积和振幅编码方式提出了QISM,QISH,QIED 三种量子图像处理算法.理论分析证明了提出的量子图像处理算法相比于经典算法,在存储能力和计算效率上都实现了指数加速,相比于其他编码方式的量子图像处理算法,在消耗的量子比特数方面占有明显优势.

研究过程中我们发现两种情况,一是量子图像锐化的获取概率较低,为0.026,二是最高获取概率0.367 对应的量子态也能重构出锐化效果的量子图像.因此,未来思考如何提高获取概率以及探究最高概率对应量子态能重构出锐化效果量子图像的背后原因.另外,量子卷积操作是量子神经网络的重要步骤,如量子卷积网络和量子生成对抗网络[51],这些都是未来值得深入研究的方向.

附录A 置换矩阵的量子电路及优化

任意置换矩阵的量子电路可使用量子可逆逻辑方法获得[52-53].置换矩阵P的量子电路如图A1(a)所示,P†的量子电路如图A1(b)所示,Γ1∈R8×8的量子电路如图A1(d)所示,置换矩阵Q8 (文献[12,13]使用它置换振幅)的正确量子电路应该是如图A1(c)所示.量子电路图中,低位量子比特在上面,高位量子比特在下面.由文献[54]可以推导出下面的结论:

图A1 置换矩阵的量子电路Fig.A1 Quantum circuit of permutation matrix

推论 1.假设输入量子态是|a〉=|an-1an-2···a1a0〉,执行b=bn-1bn-2···b0次置换操作P† ∈R2n×2n后,那么输出的量子态当b可以写成指数形式b=2m,m=0,1,2,···,n-1 时,其中ah和al满足a=ah*2m+al.

证明.当b不可以写成指数形式时,

其中 ∨ 表示或运算, ∧ 表示与运算.当b可以写成指数形式时,

推论1 可用于简化量子电路,降低电路深度,例如P† ∈R64×64时,(P†)64对应的量子电路可以简化成图A1(e),(P†)130对应的量子电路可以简化成图A1(f),它们将用于Qiskit 仿真实验中,可以简化量子电路,缩短模拟仿真时间.

附录B 量子态制备和量子图像编码

根据已知的经典信息制备相应的量子态,是量子算法设计过程中重要的步骤.一方面,量子态制备过程有时会统治整个量子算法的时间复杂度,另一方面,量子态制备方法决定了后续采取什么样的量子操作.量子态的一般形式可以写成经典信息可以存储在基态|0〉,|1〉, 相对相位φ,还有振幅中.根据存储位置的不同,量子态制备方法分为三类,基态编码(Basic code,BC)[33,55-56],相位编码(Phase code,PC)[57]和振幅编码(Amplitude code,AC)[26,57-60].对于相同类型的量子态制备方法,不同的研究领域里使用的定义存在差异.

在量子图像处理研究领域,量子图像编码方法有基态编码,如新型数字图像增强量子表示(A novel enhanced quantum representation of digital images,NEQR)[55],广义量子图像表示(The generalized quantum image representation,GQIR)[61]),振幅编码,如灵活表示的量子图像 (A flexible representation of quantum images,FRQI)[58],量子概率图像编码(Quantum probability image encoding,QPIE)[27], n -qubit 正常任意叠加态(n-qubit normal arbitrary superposition state,NASS)[57].其中NEQR,FRQI,NASS 最为常用,三种方法各有优劣[62].假设图像的尺寸是M×M,灰度值的范围是 [0,2q -1].NEQR 时间复杂度(O(2qM2logM+1))低,酉操作方便,但空间复杂度(O(2logM+q))高;FRQI 的时间复杂度 (O(2M2logM)) 和空间复杂度 (O(2logM+1)) 都低,但是酉操作不方便;NASS 的空间复杂度 (O(2logM))低,但是它的时间复杂度(O(2M2log2M))高.为了充分利用三者的优劣,有时我们会将三种编码变法进行转换,文献[63]中首先使用QDAC[38]方法将NEQR 转化成FRQI,然后在FRQI 基础上实现频域滤波.

QRAM 在量子机器学习中常被使用[10].此处我们考虑使用QRAM 方法来降低量子图像编码的时间复杂度.首先将图像通过QRAM 存储制备成量子态表示位置信息,|ψi〉表示像素值信息,时间复杂度是 O(2logM),然后使用QADC 方法[38]制备量子态时间复杂度是 O(2logM),故总的时间复杂度是 O(4logM).