劉興奧 周日貴 郭文宇

線性卷積是科學(xué)工程上的重要工具,在圖像處理中發(fā)揮了重要作用,例如基于均值濾波器和高斯濾波器實(shí)現(xiàn)圖像平滑[1],基于拉普拉斯算子實(shí)現(xiàn)圖像銳化[1],基于索伯梯度算子實(shí)現(xiàn)圖像邊緣檢測(cè),使用基于對(duì)稱式擴(kuò)充卷積的殘差網(wǎng)絡(luò)進(jìn)行圖像去噪[2].對(duì)于M×M圖像和N×N濾波器,其卷積操作的時(shí)間復(fù)雜度是O(M2N2).雖然經(jīng)典計(jì)算能求出線性卷積結(jié)果,但是在處理海量高分辨率圖像時(shí),求解線性卷積會(huì)消耗大量計(jì)算資源.量子計(jì)算為解決該問(wèn)題提供了一種新的解決方案.

量子力學(xué)的量子疊加和量子糾纏特性使得量子計(jì)算在處理某些特定問(wèn)題上具有顯著的速度優(yōu)勢(shì),例如大數(shù)因子分解算法(Shor 算法)[3],數(shù)據(jù)庫(kù)搜索算法(Grover 算法)[4],線性方程求解算法(HHL 算法)[5],粗糙集核屬性求解算法[6],映射量子模型[7],孿生支持向量機(jī)[8]和量子主成分分析[9-10].目前關(guān)于量子線性卷積的研究集中在量子一維卷積(Quantum one-dimensional convolution,QOC)和量子二維卷積(Quantum two-dimensional convolution,QTC).Lomont[11]證明,如果使用振幅編碼將兩個(gè)一維序列制備成兩個(gè)量子態(tài),那么在允許使用線性算子(酉算子和測(cè)量算子)和輔助量子比特的情況下,基于量子力學(xué)不能計(jì)算它們的量子循環(huán)卷積|c〉?|g〉, 其中|c〉表示卷積結(jié)果,|g〉表示垃圾項(xiàng).閆茜茜等[12]提出量子一維窄卷積,首先使用振幅編碼信息,利用量子態(tài)張量積性質(zhì)獲取振幅的乘積,接著使用置換矩陣實(shí)現(xiàn)振幅的置換,然后使用哈達(dá)瑪門(Hadamard,H)量子門進(jìn)行加法計(jì)算,最終獲得量子態(tài)|c〉?|0〉+|g〉?|0〉⊥,|c〉是卷積結(jié)果.隨后閆茜茜等[13]又提出量子二維窄卷積,其實(shí)現(xiàn)過(guò)程同量子一維窄卷積相似.另外,量子圖像濾波[14-17]和量子圖像邊緣檢測(cè)[18-29]等算法使用量子算術(shù)計(jì)算線性卷積.雖然上面三種方案都可以實(shí)現(xiàn)量子線性卷積,但各有不足.閆茜茜等提出的量子一維和二維線性卷積方法不適用于求解量子線性寬卷積和量子線性等寬卷積,量子圖像濾波和量子圖像邊緣檢測(cè)中的量子二維線性卷積算法需要消耗大量的量子比特資源.

本文研究?jī)?nèi)容包括量子線性卷積的實(shí)現(xiàn)和應(yīng)用兩方面.首先提出單通道,單位步長(zhǎng),零補(bǔ)充情況的量子一維寬卷積(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).然后實(shí)現(xiàn)多通道,非單位步長(zhǎng),非零補(bǔ)充情況的QOWC,同樣適用于QOEC,QONC,QTWC,QTEC,QTNC.最后基于量子二維線性卷積實(shí)現(xiàn)量子圖像平滑(Quantum image smoothing,QISM),量子圖像銳化(Quantum image sharpening,QISH) 和量子圖像邊緣檢測(cè)(Quantum image edge detection,QIED)算法,并在Qiskit 上進(jìn)行仿真實(shí)驗(yàn).理論分析證明了在時(shí)間和資源消耗方面量子線性卷積相比于經(jīng)典線性卷積呈指數(shù)下降.

本文后續(xù)部分組織結(jié)構(gòu)如下.第1 節(jié)介紹線性卷積和量子計(jì)算的相關(guān)知識(shí).第2 節(jié)實(shí)現(xiàn)QOWC,QOEC,QONC,QTWC,QTEC,QTNC.第3 節(jié)實(shí)現(xiàn)QTC 在QISM,QISH 和QIED 上的應(yīng)用.第4 節(jié)總結(jié)和展望.附錄A 給出置換電路的優(yōu)化方法.附錄B 給出量子態(tài)制備方法.

1 預(yù)備知識(shí)及符號(hào)說(shuō)明

1.1 線性卷積

為避免因讀者研究背景不同導(dǎo)致的對(duì)相關(guān)術(shù)語(yǔ)理解存在部分歧義的問(wèn)題,本文將在此節(jié)中對(duì)相關(guān)學(xué)術(shù)名詞及符號(hào)做合理規(guī)范,讀者的閱讀請(qǐng)務(wù)必參考此規(guī)范開(kāi)展.根據(jù)維度d,補(bǔ)充p, 步長(zhǎng)s,通道數(shù)c參數(shù)的不同,線性卷積存在多種變體.本節(jié)重點(diǎn)介紹單通道,零補(bǔ)充,單位步長(zhǎng)的一維,二維線性卷積.在單通道,單位步長(zhǎng),零補(bǔ)充情況下,線性卷積根據(jù)補(bǔ)零的數(shù)量又可以劃分成寬線性卷積(寬卷積),等寬線性卷積(等寬卷積)和窄線性卷積(窄卷積).

1.1.1 一維線性卷積

令輸入序列X=[x0,x1,···,xM-1], 卷積核Y=[y0,y1,···,yN-1],M＞N.當(dāng)M＜N,則將Y作為輸入序列,X作為卷積核.

一維寬卷積結(jié)果是Zw=[z0,z1,···,zM+N-2],滿足展開(kāi)成矩陣形式可以寫成

一維等寬卷積結(jié)果是Ze=[z0,z1,···,zM-1],滿足展開(kāi)成矩陣形式可以寫成

一維窄卷積結(jié)果是Zn=[z0,z1,···,zM-N],滿足i=0,1,···,M -N展.開(kāi)成矩陣形式可以寫成

1.1.2 二維線性卷積

二維卷積是一維卷積的擴(kuò)展,可以看成是在行和列上分別做一維卷積.在不影響上下文理解的情況下,我們使用與一維卷積相同的變量表示物理含義.令輸入序列X=[xi1,i2]M×M,卷積核Y=[yj1,j2]N×N,M＞N.當(dāng)M＜N時(shí),將Y作為輸入序列,X作為卷積核即可.

1.2 量子計(jì)算

量子計(jì)算模型有很多,例如量子電路模型,量子絕熱計(jì)算,量子圖靈機(jī),拓?fù)淞孔佑?jì)算等[30],這些量子計(jì)算模型是等價(jià)的.本文采用量子電路模型,其模型易理解且接受范圍最廣.量子比特用于存儲(chǔ)信息,它除了可以表示|0〉,|1〉, 還可以是|0〉和|1〉的疊加態(tài).常用的基礎(chǔ)門有單量子比特門X,Y,Z,H,S,T 和雙量子比特門受控非門(Controlled-not gate,CNOT).這些基礎(chǔ)門之間存在等價(jià)性關(guān)系,例如XZX=-Z.任意一種酉操作能以任意精度分解成一系列基礎(chǔ)門.利用這些等價(jià)關(guān)系和分解方法可以簡(jiǎn)化復(fù)雜的量子電路[31].量子測(cè)量是不可逆的過(guò)程,它會(huì)引發(fā)量子態(tài)坍縮,通過(guò)量子態(tài)層析,量子過(guò)程層析,量子壓縮感知等技術(shù)可以重構(gòu)出量子態(tài)和量子操作的相關(guān)信息[31-32].本文使用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量量子電路的性能.下面給出幾種后續(xù)行文必需的量子操作:

引理 1.(量子隨機(jī)存取存儲(chǔ)器(Quantum random access memory,QRAM)[33-36]) 量子隨機(jī)存取存儲(chǔ)器可以以相干量子疊加形式執(zhí)行內(nèi)存訪問(wèn).如果量子計(jì)算機(jī)需要訪問(wèn)一個(gè)疊加的存儲(chǔ)單元,地址寄存器a必須包含一個(gè)地址的疊加量子隨機(jī)存取存儲(chǔ)器將在 O(log(MN)) 時(shí)間內(nèi),返回?cái)?shù)據(jù)寄存器d中與地址寄存器相關(guān)的數(shù)據(jù)的疊加

引理 2.(量子振幅放大(Quantum amplitude amplification,QAA)[37]) 設(shè)U是酉操作,a是期望量子態(tài)的振幅.令其中θa滿足sin2(θa)=a, 0＜θa ≤π/2.如果在量子系統(tǒng)中執(zhí)行酉操作QmU|0〉并測(cè)量它,那么測(cè)量結(jié)果是期望量子態(tài)的概率至少是 max(1-a,a).

引理 3.(實(shí)數(shù)量子模擬數(shù)字轉(zhuǎn)換器(Real quantum analog-to-digital conversion,Real QADC)[38]) 設(shè)是一串m比特?cái)?shù)字寫成它近似于cj的實(shí)數(shù)部分.一個(gè)m比特實(shí)數(shù)量子模擬數(shù)字轉(zhuǎn)換器可以將模擬量子態(tài)轉(zhuǎn)化成數(shù)字量子態(tài)該轉(zhuǎn)換器需要使用 O(1/ε) 受控UA操作和O((log2N)/ε)個(gè)單、雙量子比特門,并以 1-O(poly(ε)) 的保真度輸出結(jié)果,其中ε表示輸出精度.

2 量子線性卷積算法

本節(jié)研究單通道,單位步長(zhǎng),零補(bǔ)充情況下的量子一維和二維線性卷積,包括寬卷積,等寬卷積和窄卷積.第2.1 節(jié)實(shí)現(xiàn)了量子一維寬線性卷積,分析了它的時(shí)間復(fù)雜度和空間復(fù)雜度,并將其擴(kuò)展到量子一維等寬卷積,量子一維窄卷積.第2.2 節(jié)實(shí)現(xiàn)了量子二維寬線性卷積,分析了它的時(shí)間復(fù)雜度和空間復(fù)雜度,并將其擴(kuò)展到量子二維等寬卷積,量子二維窄卷積.我們?cè)诘?.3 節(jié)討論了多通道,非單位步長(zhǎng),非零補(bǔ)充的情況.

2.1 量子一維線性卷積

把R0作為首行向量構(gòu)造出一個(gè)Lt×Lt的循環(huán)矩陣w:

當(dāng)i ＞N時(shí),yN-1-i=0,P∈RLt×Lt是一個(gè)置換矩陣,矩陣形式是:

P?是它的共軛轉(zhuǎn)置矩陣.那么一維寬卷積計(jì)算過(guò)程可以改寫成,其中

行向量Zw的前M+N -1 個(gè)元素是所求的寬卷積結(jié)果,后Lt-M -N+1 個(gè)元素都是0,本文中稱之為垃圾元素.將修改后的輸入序列Xw與首行向量R0存儲(chǔ)到量子隨機(jī)存取存儲(chǔ)器中.

圖1 量子一維線性卷積實(shí)現(xiàn)電路Fig.1 Quantum circuit of one-dimensional linear convolution

在QR1?QR0上分別執(zhí)行酉操作O1?O0:

設(shè) eιθi=yN-1-i/|yN-1-i|表示R0中每個(gè)元素的符號(hào)位信息,在QR1上執(zhí)行受控相位操作(CP):

基于量子一維寬卷積的實(shí)現(xiàn)框架,有兩種不同的方法可以實(shí)現(xiàn)量子一維等寬卷積和量子一維窄卷積.第一種方法是在量子一維寬卷積的量子電路上再增加若干個(gè)置換操作,對(duì)于量子一維等寬卷積而言,額外增加操作(圖1(b)所示),對(duì)于量子一維窄卷積而言,額外增加N-1個(gè)P?操作(圖1(c)所示).第二種方法是仿照量子一維寬卷積算法,對(duì)于量子一維等寬卷積,重新制備,對(duì)于量子一維窄卷積,重新制備,使用它們替代方法一是基于量子一維寬卷積,會(huì)保留一些垃圾元素,而方法二不會(huì)保留垃圾元素.

通常輸入序列的尺寸M和卷積核的尺寸N滿足M?N.量子一維線性卷積算法的空間復(fù)雜度是 O(logM).由于酉操作O0和O1的時(shí)間復(fù)雜度分別是 O(logM) 和 O(logN), 受控相位CP操作的時(shí)間復(fù)雜度是O(logN),受控置換操作的時(shí)間復(fù)雜度是逆操作的時(shí)間復(fù)雜度是O(logN),故量子一維線性卷積算法的時(shí)間復(fù)雜度是

相對(duì)于經(jīng)典卷積時(shí)間復(fù)雜度 O(M),量子一維線性卷積算法實(shí)現(xiàn)了指數(shù)加速.文獻(xiàn)[12]從卷積定義角度出發(fā),首先以卷積核長(zhǎng)度向輸入序列截取對(duì)應(yīng)長(zhǎng)度進(jìn)行內(nèi)積計(jì)算,之后保持輸入序列不變,卷積核進(jìn)行一步移位操作,直到短向量最后一個(gè)元素與輸入序列最后一個(gè)元素對(duì)齊并計(jì)算其內(nèi)積,最終得到量子一維窄卷積結(jié)果.它的時(shí)間復(fù)雜度是,但算法無(wú)法擴(kuò)展到量子一維寬卷積和等寬卷積.而本文從線性代數(shù)的角度出發(fā),首先給出了量子一維寬卷積算法,并且可以很容易地將其推廣到量子一維等寬卷積和量子一維窄卷積上.

2.2 量子二維線性卷積

如式(2)所示,二維寬卷積可以寫成矩陣形式UwX=Zw,其中Uw是一般矩陣,為了使量子計(jì)算能夠求解該線性方程組,我們需要重新調(diào)整該數(shù)據(jù)結(jié)構(gòu)形式.在矩陣X四周進(jìn)行補(bǔ)0 操作得到矩陣,然后將其向量化

其中前N2個(gè)元素來(lái)自于卷積核Y行向量化,把R0作為首行向量,構(gòu)造循環(huán)矩陣

量子二維寬卷積的實(shí)現(xiàn)方法可以直接擴(kuò)展到量子二維等寬卷積和量子二維窄卷積的量子實(shí)現(xiàn)上,有兩種不同的實(shí)現(xiàn)方法.第一種方法是重新制備和以替代第二種方法是基于量子二維寬卷積的量子電路,分別在水平方向向左平移次,垂直方向向上平移1)次, 這種平移操作可以使用P?操作來(lái)實(shí)現(xiàn).

通常輸入序列的尺寸M和卷積核的尺寸N滿足M?N.量子二維線性卷積的空間復(fù)雜度是O(2logM), 時(shí)間復(fù)雜度是相對(duì)于經(jīng)典二維線性卷積時(shí)間復(fù)雜度,量子二維線性卷積展現(xiàn)了其指數(shù)加速的優(yōu)勢(shì).文獻(xiàn)[13]給出了量子二維窄卷積算法,輸入序列的量子態(tài)與卷積核的量子態(tài)進(jìn)行張量積計(jì)算,使用兩種置換操作共同完成量子卷積振幅置換,對(duì)置換后的卷積核量子態(tài)的量子比特執(zhí)行H 門操作,輸入序列量子態(tài)的量子比特執(zhí)行單位矩陣操作,對(duì)卷積核量子態(tài)進(jìn)行測(cè)量.該算法的空間復(fù)雜度和時(shí)間復(fù)雜度與本文相同,但其思考角度與本文不同,且其實(shí)現(xiàn)不適用于量子二維寬卷積和量子二維等寬卷積.

2.3 量子卷積算法討論及擴(kuò)展

上文介紹了單通道,單位步長(zhǎng),零填充情況下的量子一維寬卷積,等寬卷積,窄卷積,量子二維寬卷積,等寬卷積,窄卷積的量子實(shí)現(xiàn).下面我們重點(diǎn)討論量子一維寬卷積算法的實(shí)現(xiàn)和擴(kuò)展,其他幾種量子卷積實(shí)現(xiàn)和擴(kuò)展與它相似.

在沒(méi)有對(duì)輸入序列進(jìn)行填充的情況下,一維寬線性卷積可以寫成線性方程形式(見(jiàn)式(1)),其中Uw∈R(M+N-1)×M.有三種量子算法可以求解這樣的線性方程.第一種方法是使用類HHL 算法[5,40],首先將矩陣Uw變成厄米矩陣:

本文提出的量子一維寬線性卷積適用于擴(kuò)展到多通道,非單位步長(zhǎng),非零補(bǔ)充的情況.以三通道為例,量子電路實(shí)現(xiàn)如圖2(a)所示,在量子一維寬卷積的量子電路的基礎(chǔ)上,額外再添加一個(gè)兩量子比特的量子寄存器QR2, 此時(shí)QR0用于存儲(chǔ)輸入序列信息,QR1用于存儲(chǔ)卷積核信息,QR2用于存儲(chǔ)通道信息.實(shí)現(xiàn)步驟如下,首先應(yīng)用兩個(gè)H 門在QR2,接著根據(jù)通道信息在圖像上使用不同的卷積核,最后再在QR2使用兩個(gè)H 門,實(shí)現(xiàn)卷積結(jié)果融合.以步長(zhǎng)為2 為例,量子電路見(jiàn)圖2(b)在量子一維寬卷積的量子電路基礎(chǔ)上,再增加一個(gè)置換矩陣:

圖2 三通道/兩步長(zhǎng)的量子一維寬卷積實(shí)現(xiàn)電路Fig.2 Three-channel/two-stride quantum one-dimensional wide convolution realization circuit

圖A1(d)給出了Γ1∈R8×8時(shí)的量子電路.以補(bǔ)充值是1 為例,此時(shí)式(3)改寫成

3 量子卷積在圖像處理中的應(yīng)用

本節(jié)研究量子二維線性卷積在量子圖像中的應(yīng)用,例如量子圖像平滑,量子圖像銳化和量子圖像邊緣檢測(cè),旨在驗(yàn)證量子卷積算法本身的正確性及基于量子卷積實(shí)現(xiàn)量子圖像處理算法的可行性.首先分別給出它們的量子算法,然后在Qiskit[43]上使用QasmSimulator 進(jìn)行模擬,最后將它們和已有的量子圖像處理算法比較.仿真平臺(tái)的參數(shù)是操作系統(tǒng)Ubuntu 20.04.2 LTS 64 位,處理器CPU I9-10900X 10 核20 進(jìn)程3.70 GHz,內(nèi)存是62.5 GB,Qiskit 版本是0.26.2.

3.1 量子圖像平滑

圖像平滑常見(jiàn)操作有模糊處理和降噪處理,通常用于圖像預(yù)處理任務(wù)中.模糊處理可在大目標(biāo)之前去除圖像中的一些瑣碎細(xì)節(jié),連接直線或曲線的縫隙.通過(guò)線性濾波和非線性濾波模糊處理,可以降低噪聲.本節(jié)研究量子圖像平滑,其基本流程是首先編碼量子圖像和卷積核(見(jiàn)附錄B),接著使用量子二維線性卷積實(shí)現(xiàn)量子圖像平滑.

以圖3 為例,圖3(a)是含有泊松噪聲的實(shí)驗(yàn)圖像Ip,圖3 (c)是含有高斯噪聲(均值為0,方差為0.01)的實(shí)驗(yàn)圖像Ig, 它們的尺寸是 60×60.圖3 (b)是均值濾波器,圖3 (d)是高斯濾波器,它們的尺寸是 3×3.量子圖像平滑算法對(duì)應(yīng)的量子電路圖如圖4 (a)所示,最上面的10 個(gè)量子比特(QR0)用于存儲(chǔ)量子圖像信息,最下面的4 個(gè)量子比特(QR1)用于存儲(chǔ)卷積核信息,最后一個(gè)是經(jīng)典寄存器(CR),它有四個(gè)比特用于存儲(chǔ)量子測(cè)量后坍縮的經(jīng)典信息.需要特別指出,不同于前面描述的量子卷積的量子電路,由于本節(jié)使用的兩個(gè)平滑濾波器的元素都是正數(shù),因此在量子電路設(shè)計(jì)過(guò)程中,受控相位操作被省略.我們使用Qiskit 的QasmSimulator模擬量子圖像平滑算法,其中參數(shù)shots設(shè)置為1 024,實(shí)現(xiàn)代碼見(jiàn)1,https://github.com/liuxingao/SimulateCode/blob/main/NORMAL/mean_filter.ipynb2https://github.com/liuxingao/SimulateCode/blob/main/NORMAL/gaussian_filter.ipynb.模擬結(jié)果輸出狀態(tài)向量(狀態(tài)向量的前1 024 個(gè)元素表示平滑濾波后的圖像)以及量子寄存器QR1是全0 的概率.

圖3 量子圖像平滑的實(shí)驗(yàn)圖像和平滑濾波器Fig.3 Experimental image and smoothing filter for quantum image smoothing

圖4(b) 表明了均值濾波時(shí)輸出0 的概率是0.935,圖4(c)顯示了量子模擬器輸出的均值濾波后的圖像,圖4(d)顯示了經(jīng)典計(jì)算機(jī)使用SciPy3SciPy 包:https://docs.scipy.org/doc/scipy/reference/輸出的均值濾波后的圖像.兩者在視覺(jué)上沒(méi)有差異且抑制了泊松噪聲.同樣地,圖4(e)表明了高斯濾波器時(shí)輸出0 的概率是0.905,圖4(f)顯示了量子模擬器輸出的高斯濾波后的圖像,圖4(g)顯示了經(jīng)典計(jì)算機(jī)使用SciPy 輸出的高斯濾波后的圖像,兩者在視覺(jué)上沒(méi)有差異且能抑制了高斯噪聲.相比于均方誤差(Mean-square error,MSE)和峰值信噪比(Peak signal-to-noise ratio,PSNR),結(jié)構(gòu)相似性(Structural similarity,SSIM)的評(píng)價(jià)性能有明顯提高[44],所以本文使用SSIM 評(píng)估兩幅圖像的相似性.均值濾波后的兩幅圖像的SSIM 是0.999 856 7,高斯濾波后的兩幅圖像的SSIM 是0.999 923 3,這表明兩幅圖像相同,同時(shí),驗(yàn)證了量子圖像平滑算法和量子卷積算法的可行性和正確性.

3.2 量子圖像銳化

圖像銳化可以補(bǔ)償圖像的輪廓,增強(qiáng)圖像的邊緣及灰度跳變的部分,使圖像變得清晰.本節(jié)研究量子圖像銳化,其基本步驟是首先對(duì)圖像和卷積核編碼,接著使用量子二維卷積算法對(duì)圖像濾波,需要注意的是,與平滑濾波算子全是正數(shù)元素不同,銳化濾波算子存在負(fù)數(shù)元素,需要使用受控相位操作給負(fù)數(shù)元素項(xiàng)增加相對(duì)相位,可以得到量子態(tài):

以圖5 為例,圖5(a)是實(shí)驗(yàn)圖像,尺寸是 60×60,圖5(b)是銳化算子,尺寸是 3×3.經(jīng)典計(jì)算機(jī)模擬量子計(jì)算時(shí),它的內(nèi)存資源消耗和運(yùn)行時(shí)間隨量子電路深度、電路寬度變化呈指數(shù)增長(zhǎng).受現(xiàn)有量子實(shí)驗(yàn)設(shè)備以及仿真平臺(tái)環(huán)境的約束,我們只能使用Qiskit 仿真實(shí)現(xiàn)步驟1,至于步驟2、3 將在步驟一的基礎(chǔ)上按照邏輯進(jìn)行經(jīng)典運(yùn)算,實(shí)現(xiàn)代碼見(jiàn)4https://github.com/liuxingao/SimulateCode/blob/main/NORMAL/sharpen_filter.ipynb.量子圖像銳化算法步驟一對(duì)應(yīng)的量子電路圖如圖6(a)所示,未優(yōu)化分解之前量子電路的電路寬度是20,電路深度是23.值得注意的是,受控相位操作中,除了量子態(tài)(下標(biāo)是1,3,5,7)的相對(duì)相位翻轉(zhuǎn),還有其他量子態(tài)(下標(biāo)是2,4,6,8)的相對(duì)相位也偏轉(zhuǎn)成負(fù)值.相對(duì)相位對(duì)量子算法的結(jié)果影響很大,因此需要額外的受控相位門將量子態(tài)(下標(biāo)是2,4,6,8)的相對(duì)相位恢復(fù)成正相位.我們使用Qiskit的QasmSimulator 模擬量子圖像銳化算法,其中參數(shù)shots設(shè)置為1 024.模擬結(jié)果輸出狀態(tài)向量(狀態(tài)向量的前1 024 個(gè)元素表示銳化后的圖像)以及量子寄存器QR1是全0 的概率.圖6(b)表明輸出0 的概率是0.026,圖6(c)顯示了量子模擬器輸出的銳化后圖像,圖6(d) 顯示了經(jīng)典計(jì)算機(jī)使用SciPy 輸出的銳化后圖像.兩者在視覺(jué)上沒(méi)有差異,且兩幅圖像的SSIM 是1.0,這表明兩幅圖像相同,同時(shí),驗(yàn)證了量子圖像銳化算法和量子卷積算法的可行性和正確性.

圖5 量子圖像銳化的實(shí)驗(yàn)圖像和銳化濾波器Fig.5 Experimental image and sharpening filter for quantum image sharpening

圖6 量子圖像銳化的仿真電路和仿真結(jié)果Fig.6 Simulation circuit and simulation results of quantum image sharpening

3.3 量子圖像邊緣檢測(cè)

邊緣檢測(cè)是圖像處理和計(jì)算機(jī)視覺(jué)中的基本問(wèn)題,邊緣檢測(cè)的目的是標(biāo)識(shí)數(shù)字圖像中亮度變化明顯的點(diǎn).圖像邊緣檢測(cè)可大幅度地減少數(shù)據(jù)量,剔除不相關(guān)的信息,保留圖像重要的結(jié)構(gòu)屬性.本節(jié)研究量子圖像邊緣檢測(cè),使用水平和垂直方向的Sobel 算子,最終獲得的梯度圖像是量子圖像邊緣檢測(cè)的實(shí)現(xiàn)過(guò)程如下:

步驟 1.準(zhǔn)備6 個(gè)量子寄存器,最左邊表示第1個(gè)量子寄存器,最右邊表示第6 個(gè)量子寄存器,q1表示存儲(chǔ)卷積核所需量子比特?cái)?shù),q2表示存儲(chǔ)圖像所需量子比特?cái)?shù):

步驟 2.對(duì)第2 個(gè)量子寄存器執(zhí)行H 門操作:

步驟 3.當(dāng)?shù)? 個(gè)量子寄存器是|0〉時(shí),對(duì)第3個(gè)和第4 個(gè)量子寄存器執(zhí)行量子卷積操作,卷積核是水平方向Sobel 算子(Sobelx),在第5 和6 個(gè)量子寄存器執(zhí)行同樣的量子卷積操作;當(dāng)?shù)? 個(gè)量子寄存器是|1〉時(shí),對(duì)第3 個(gè)和第4 個(gè)量子寄存器執(zhí)行量子卷積操作,卷積核是垂直方向Sobel 算子(Sobely),在第5 和6 個(gè)量子寄存器上執(zhí)行同樣的量子卷積操作:

步驟 4.第2 個(gè)量子寄存器執(zhí)行H 門操作:

步驟 5.把第6 個(gè)量子寄存器中量子比特作為控制比特,第4 個(gè)量子寄存器中的量子比特作為目標(biāo)比特,執(zhí)行q2個(gè)受控非門操作:

其中,x=x1=x2,y=y1=y2,ξ=ξx=ξy,ρ=x=y=0,···,Lt-1,該量子態(tài)對(duì)應(yīng)的狀態(tài)向量的前Lt個(gè)元素就是.

步驟 6.使用Real QADC 方法將振幅添加到基態(tài)中:

步驟 7.使用量子比較器[45]比較第1 個(gè)量子寄存器與預(yù)設(shè)的閾值thre,如果大于閾值則第1 個(gè)量子寄存器設(shè)置為1,否則第1 個(gè)量子寄存器置為0:

以圖7 為例,圖7(a) 是實(shí)驗(yàn)圖像,尺寸是12×12,圖7(b)是水平方向的Sobel 算子,尺寸是3×3,圖7(c) 是垂直方向的Sobel 算子,尺寸是3×3.受仿真平臺(tái)環(huán)境約束,我們只使用Qiskit 仿真實(shí)現(xiàn)步驟1 至5,步驟6、7 將在此基礎(chǔ)上按邏輯進(jìn)行經(jīng)典運(yùn)算,實(shí)現(xiàn)代碼見(jiàn)5.圖8(a)給出了量子圖像邊緣檢測(cè)步驟1 到5 的量子電路圖,使用Qasm-Simulator 對(duì)它進(jìn)行模擬,參數(shù)shots設(shè)置為1 024.模擬結(jié)果輸出狀態(tài)向量(狀態(tài)向量的前256 個(gè)元素是邊緣檢測(cè)后的圖像)以及量子寄存器QR1是0 的概率.圖8(b)顯示了輸出是0 的概率,圖8(c)顯示量子模擬器輸出的圖像,圖8(d)顯示了經(jīng)典計(jì)算機(jī)使用SciPy 輸出的圖像.兩者在視覺(jué)上沒(méi)有差異且兩幅圖像的SSIM 是1.0,這說(shuō)明兩幅圖像相同,同時(shí),驗(yàn)證了量子卷積算法的正確性和量子圖像邊緣檢測(cè)算法的可行性.

圖7 量子圖像邊緣檢測(cè)的實(shí)驗(yàn)圖像和 Sobel 算子Fig.7 Experimental image and Sobel operator of quantum image edge detection

圖8 量子圖像邊緣檢測(cè)的仿真電路和仿真結(jié)果Fig.8 Simulation circuit and simulation results of quantum image edge detection

量子圖像邊緣檢測(cè)的效果受許多因素影響,例如算子,方向,閾值等.本節(jié)提出的基于水平垂直兩個(gè)方向Sobel 算子的量子圖像檢測(cè)算法可以很容易擴(kuò)展到四個(gè)方向Sobel 算子.

3.4 量子圖像處理的討論

基于量子卷積操作的量子圖像處理算法已被廣泛研究,主要涉及量子圖像濾波,量子圖像特征提取,量子圖像邊緣檢測(cè).這些算法實(shí)現(xiàn)量子卷積操作的思路大致如下,首先獲取鄰域像素值,接著根據(jù)濾波器的元素,使用量子算術(shù)實(shí)現(xiàn)卷積計(jì)算.其中鄰域像素值獲取方法可以細(xì)分為三類.假設(shè)卷積核算子的尺寸為 3×3,圖像尺寸是M×M,M=2m, 圖像灰度值范圍是 [0,2q-1],q=1 表示二值圖像,q=8表示灰度圖像,q=24 表示彩色圖像.第一類方法是制備9 份完全相同的量子圖像,將循環(huán)操作分別作用于8 份量子圖像,坐標(biāo)信息相同的量子態(tài)構(gòu)成鄰域像素.第二類方法是制備1 份量子圖像和用于存儲(chǔ)像素值的8 個(gè)量子寄存器,依次使用循環(huán)操作和復(fù)制操作來(lái)獲取相鄰像素值.第三類方法是制備1 份量子圖像和用于存儲(chǔ)量子圖像的8 個(gè)量子寄存器,依次使用量子比較器和復(fù)制操作獲取相鄰像素值.如表1 所示,這些算法的空間復(fù)雜度和時(shí)間復(fù)雜度都比較高.此外,第二類算法存在錯(cuò)誤,量子圖像的位置信息和像素值信息是糾纏的,移位后再?gòu)?fù)制的像素值都是相同的,通過(guò)理論推導(dǎo)或Qiskit 仿真可以驗(yàn)證.文獻(xiàn)[27]中給出的量子圖像檢測(cè)算法只適用于二值圖像,因此這里不做比較.

量子圖像平滑算法需要 2m+4 個(gè)量子比特,時(shí)間復(fù)雜度是量子圖像銳化算法需要2m+2log(1/ε)+5個(gè)量子比特,時(shí)間復(fù)雜度是O(4m2/ε+16log(1/ε)-3),ε是計(jì)算精度;量子圖像邊緣檢測(cè)需要(4m+2log(1/ε)+7 個(gè)量)子比特,時(shí)間復(fù)雜度是 O16m2/ε+16log(1/ε)-3.本文提出的量子圖像濾波(平滑和銳化)算法,量子圖像邊緣檢測(cè)算法相比于其對(duì)應(yīng)的經(jīng)典算法,在存儲(chǔ)能力和計(jì)算效率上都實(shí)現(xiàn)了指數(shù)加速;對(duì)比表1 中量子算法,在時(shí)間復(fù)雜度方面處于相同數(shù)量級(jí),在消耗的量子比特?cái)?shù)方面占有明顯優(yōu)勢(shì),使得它更有希望在目前的量子計(jì)算機(jī)上實(shí)現(xiàn).但是基于本文提出的量子二維卷積操作的量子圖像處理算法不適用于非線性量子圖像濾波情況[46-50].

表1 已被提出的量子圖像濾波和量子圖像特征邊緣檢測(cè)算法.假設(shè)卷積核算子的尺寸為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 總結(jié)及未來(lái)工作

本文提出了單通道,單位步長(zhǎng)和零補(bǔ)充情況下的QOWC,QOEC,QONC,QTWC,QTEC,QTNC.當(dāng)通道,步長(zhǎng),補(bǔ)充值等參數(shù)發(fā)生變化時(shí),其對(duì)應(yīng)的算法實(shí)現(xiàn)只需輕微調(diào)整.理論分析證明量子線性卷積的空間復(fù)雜度 O(logM) 和時(shí)間復(fù)雜度O(log2M)較經(jīng)典線性卷積有指數(shù)級(jí)下降.另外,本文基于量子線性卷積和振幅編碼方式提出了QISM,QISH,QIED 三種量子圖像處理算法.理論分析證明了提出的量子圖像處理算法相比于經(jīng)典算法,在存儲(chǔ)能力和計(jì)算效率上都實(shí)現(xiàn)了指數(shù)加速,相比于其他編碼方式的量子圖像處理算法,在消耗的量子比特?cái)?shù)方面占有明顯優(yōu)勢(shì).

研究過(guò)程中我們發(fā)現(xiàn)兩種情況,一是量子圖像銳化的獲取概率較低,為0.026,二是最高獲取概率0.367 對(duì)應(yīng)的量子態(tài)也能重構(gòu)出銳化效果的量子圖像.因此,未來(lái)思考如何提高獲取概率以及探究最高概率對(duì)應(yīng)量子態(tài)能重構(gòu)出銳化效果量子圖像的背后原因.另外,量子卷積操作是量子神經(jīng)網(wǎng)絡(luò)的重要步驟,如量子卷積網(wǎng)絡(luò)和量子生成對(duì)抗網(wǎng)絡(luò)[51],這些都是未來(lái)值得深入研究的方向.

附錄A 置換矩陣的量子電路及優(yōu)化

任意置換矩陣的量子電路可使用量子可逆邏輯方法獲得[52-53].置換矩陣P的量子電路如圖A1(a)所示,P?的量子電路如圖A1(b)所示,Γ1∈R8×8的量子電路如圖A1(d)所示,置換矩陣Q8 (文獻(xiàn)[12,13]使用它置換振幅)的正確量子電路應(yīng)該是如圖A1(c)所示.量子電路圖中,低位量子比特在上面,高位量子比特在下面.由文獻(xiàn)[54]可以推導(dǎo)出下面的結(jié)論:

圖A1 置換矩陣的量子電路Fig.A1 Quantum circuit of permutation matrix

推論 1.假設(shè)輸入量子態(tài)是|a〉=|an-1an-2···a1a0〉,執(zhí)行b=bn-1bn-2···b0次置換操作P? ∈R2n×2n后,那么輸出的量子態(tài)當(dāng)b可以寫成指數(shù)形式b=2m,m=0,1,2,···,n-1 時(shí),其中ah和al滿足a=ah*2m+al.

證明.當(dāng)b不可以寫成指數(shù)形式時(shí),

其中 ∨ 表示或運(yùn)算, ∧ 表示與運(yùn)算.當(dāng)b可以寫成指數(shù)形式時(shí),

推論1 可用于簡(jiǎn)化量子電路,降低電路深度,例如P? ∈R64×64時(shí),(P?)64對(duì)應(yīng)的量子電路可以簡(jiǎn)化成圖A1(e),(P?)130對(duì)應(yīng)的量子電路可以簡(jiǎn)化成圖A1(f),它們將用于Qiskit 仿真實(shí)驗(yàn)中,可以簡(jiǎn)化量子電路,縮短模擬仿真時(shí)間.

附錄B 量子態(tài)制備和量子圖像編碼

根據(jù)已知的經(jīng)典信息制備相應(yīng)的量子態(tài),是量子算法設(shè)計(jì)過(guò)程中重要的步驟.一方面,量子態(tài)制備過(guò)程有時(shí)會(huì)統(tǒng)治整個(gè)量子算法的時(shí)間復(fù)雜度,另一方面,量子態(tài)制備方法決定了后續(xù)采取什么樣的量子操作.量子態(tài)的一般形式可以寫成經(jīng)典信息可以存儲(chǔ)在基態(tài)|0〉,|1〉, 相對(duì)相位φ,還有振幅中.根據(jù)存儲(chǔ)位置的不同,量子態(tài)制備方法分為三類,基態(tài)編碼(Basic code,BC)[33,55-56],相位編碼(Phase code,PC)[57]和振幅編碼(Amplitude code,AC)[26,57-60].對(duì)于相同類型的量子態(tài)制備方法,不同的研究領(lǐng)域里使用的定義存在差異.

在量子圖像處理研究領(lǐng)域,量子圖像編碼方法有基態(tài)編碼,如新型數(shù)字圖像增強(qiáng)量子表示(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 正常任意疊加態(tài)(n-qubit normal arbitrary superposition state,NASS)[57].其中NEQR,FRQI,NASS 最為常用,三種方法各有優(yōu)劣[62].假設(shè)圖像的尺寸是M×M,灰度值的范圍是 [0,2q -1].NEQR 時(shí)間復(fù)雜度(O(2qM2logM+1))低,酉操作方便,但空間復(fù)雜度(O(2logM+q))高;FRQI 的時(shí)間復(fù)雜度 (O(2M2logM)) 和空間復(fù)雜度 (O(2logM+1)) 都低,但是酉操作不方便;NASS 的空間復(fù)雜度 (O(2logM))低,但是它的時(shí)間復(fù)雜度(O(2M2log2M))高.為了充分利用三者的優(yōu)劣,有時(shí)我們會(huì)將三種編碼變法進(jìn)行轉(zhuǎn)換,文獻(xiàn)[63]中首先使用QDAC[38]方法將NEQR 轉(zhuǎn)化成FRQI,然后在FRQI 基礎(chǔ)上實(shí)現(xiàn)頻域?yàn)V波.

QRAM 在量子機(jī)器學(xué)習(xí)中常被使用[10].此處我們考慮使用QRAM 方法來(lái)降低量子圖像編碼的時(shí)間復(fù)雜度.首先將圖像通過(guò)QRAM 存儲(chǔ)制備成量子態(tài)表示位置信息,|ψi〉表示像素值信息,時(shí)間復(fù)雜度是 O(2logM),然后使用QADC 方法[38]制備量子態(tài)時(shí)間復(fù)雜度是 O(2logM),故總的時(shí)間復(fù)雜度是 O(4logM).