量子線性卷積及其在圖像處理中的應用

劉興奧 周日貴 郭文宇

線性卷積是科學工程上的重要工具,在圖像處理中發揮了重要作用,例如基于均值濾波器和高斯濾波器實現圖像平滑[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).