量子信號處理
2008-01-01 00:00:00王鵬李建平
計算機應用研究 2008年4期
摘要：對量子系統的基本原理以及建立在對這一理論體系進行仿真基礎上的量子信號處理算法的理論框架進行了分析和研究，提出了量子信號處理在信號處理和圖像處理領域的應用方法，并根據量子信號處理的理論框架得到了更為通用的量子算法設計模型，指出了量子算法所具有的并行化特性，為算法并行化提供了一種新的思路。
關鍵詞：量子力學; 量子信號處理; 量子算法; 量子態
中圖分類號：TN911.7文獻標志碼：A
文章編號：1001－3695(2008)04－1033－03
量子信號處理是信號處理領域最新的研究方向之一，首次提出這一概念和理論是在2001年，相關的工作主要由MIT的Yonina C.Eldar等人完成[1，2]。這一思想將量子力學的數學框架應用于信號處理領域，建立新的基于量子力學的算法并改進現有算法。這一思想與人們通常所說的量子計算有較大的區別[3~6]。通常人們所說的量子計算是利用物質實體的量子效應來完成相應的處理，這種方法要受量子物理的公理和約束所限制。本文所說的量子信號處理只是利用量子力學的數學框架和思想，并依據量子力學中相應公理建立與之對應的處理算法，這種方法不會實質性地受到量子物理規律的限制，它的實現實體為普通的計算機系統；這一思想與遺傳算法十分相似，是一種自然仿真算法框架。
量子力學是一種反映自然規律的物理理論[7，8]，經過一百多年的實踐檢驗，解決了大量的物理問題，現在人們日常生活中使用的很多物品都離不開量子力學的貢獻。量子力學真實地反映了自然的奧秘，因此量子力學的數學框架和思想是十分深刻的。信號作為自然界中客觀存在的物理實體，它在物理上也是受量子力學原理約束的，將量子力學的數學思想框架應用于信號處理領域也是非常自然的想法。
1量子系統
1．1Dirac符號
Dirac符號是由Dirac[9]提出的。在這一基礎上，能夠建立起量子力學規律的一種普遍的數學形式，它適用于一切量子體系。量子體系的各種狀態，包括描述空間運動與非空間運動的狀態在內，它們的某些性質可以是不同的。但是，各種狀態都有一個共同的性質，即都滿足狀態疊加原理。可將狀態稱為態矢量；量子體系的一切可能狀態構成一種態矢量空間；無限維態矢量空間具有Hilbert空間的性質。空間中所有的態矢都用一個右矢|>來表示，它的對偶態矢量空間，所有的態矢都用一個左矢<|來表示。
設基底為|n＞(1，2，3，…)，基底中的基矢是分立可數的，數目可以是有限或無限。由無限可數的抽象基底所生成的空間就是一個抽象的Hilbert空間。空間中的任意矢量|ψ>皆可表示為|ψ>=∑nan|n>，如果
1．2量子測量
對量子系統中一個或多個粒子進行測量，將會把量子系統的狀態投射到與測量值相對應的狀態空間中去，同時也會對投射的幅度進行縮放。結果態矢的長度為1，測量結果出現的概率等于測量所用基的復數平方和。
量子測量是一個非線性映射，通常可以用一個測量矢量{μi，i∈I}來描述，這一矢量張成一個子空間{SiH，i∈I}。其中：I為索引集。量子力學要求μi必須正交。更一般情況的量子測量可用投影算符Pψ來描述：定義Pψ=|ψ><ψ|稱Pψ為對|ψ>的投影算符。將Pψ作用在任意右矢|χ>上，則
Pψ|χ>=|ψ><ψ|χ>=<ψ|χ>|ψ>
按照投影算符的概念可以看出，展開式|ψ>=∑n|n>
1．3測量一致性
測量一致性是量子力學的一個基本假設，對一個處于定態的系統進行重復測量將產生相同的輸出。因此系統狀態在測量后應該保持不變，反復進行測量后系統最后的狀態應該與第一次測量后的狀態相同。
1．4量子化
測量輸出的量子化是一致性要求的直接結果，一致性要求將導致測量后形成一種被稱為定態的量子態。這些由測量得到的量子態由概率決定，這些態屬于測量子空間Si。甚至當系統不處于定態時對系統進行測量后系統也會量子化到其中一個定態，即測量結果一定會是這些定態中的其中一個，而得到其中一個定態的概率可由系統量子態和這一定態的內積決定。
1．5量子疊加原理
定態（stationary state）在量子力學中定義為如下的波函數：
ψ(r，t)=ψE(r)e-iEt/h
處于定態下的粒子具有如下特征：a)粒子空間的概率密度ρ(r)=|ψE(r)|2以及概率流密度j不隨時間變化；b)任何力學量的平均值不隨時間變化；c)任何力學量的測量概率分布不隨時間變化。
由若干個能量不同本征態疊加所形成的態稱為非定態（nonstationary state）。
量子疊加原理是波的疊加性和波函數完全描述一個體系的量子態兩個概念的概括。非定態就是由許多本征態的某種相干疊加，而粒子可部分地處于其中的某一個態。這從經典物理的概念來看是無法理解的，但只有這種解釋才能說明測量結果的不確定性，各個定態可以按一定概率在多次測量時都有可能得到。
一般來說對一個量子態ψ=∑nan|φn>進行測量時，這一量子態就以相對概率an坍縮到某一定態|φn>，量子力學中把這種現象稱為量子態坍縮，即在測量過程中疊加態坍縮到某一能量本征態。態的疊加導致疊加態下觀測結果的不確定性，疊加原理是與測量密切聯系在一起的一個基本原理。這也是量子計算中很重要的一個原理，它是實現量子并行計算的理論依據。
2QSP理論體系
2．1QSP的建立
Eldar等人認為量子信號處理主要是借鑒量子力學理論以及它的一些公理和約束形成新的算法或者改進已有的信號處理算法，它并不依靠真實量子物理體系來實現。這與量子計算和量子信息學的研究內容有本質區別，可以認為QSP只是一種仿真的量子計算。他們認為量子力學的理論體系與信號處理存在三種內在聯系：一是量子力學中的測量概念；二是量子測量一致性原理；三是測量輸出的量子化原理。在進行算法設計時，QSP算法理論架構就對量子力學的本身的理論架構進行了擴展并且突破了它的一些約束條件，進而拓寬了QSP的應用范圍。圖1描述了這種關系。
2．2QSP中的測量
QSP中對信號的測量對應于采用一種算法作用到信號上，采用QSP算法進行測量等效于對信號進行相應的處理或在不同信號空間對信號進行表示。測量的輸出則對應于算法的輸出。
Hilbert空間中的一階測量（rank－one QSP measurement）M可定義為一個測量向量{qi，i∈I}，它是Hilbert空間的一個子空間{SiH，i∈I}。由于QSP算法并不受量子力學中物理定理的約束，這些向量并不保證要相互正交。Hilbert子空間QSP測量定義為子空間{SiH，i∈I}上的一組投影操作符。由于不受實際物理定律約束，投影算符和子空間Si不要求是正交的。對信號x的測量可用M(x)表示。
QSP中的測量一致性可用數學形式表示為M(M(x))=M(x)。根據筆者的定義，假如x是Hilbert信號空間中的信號，那么M(x)也是Hilbert空間的信號，因此能對它進行多次測量。
測量輸出的量子化要求輸出信號M(x)為這組信號中的一個，對應于量子力學中的定態，可以定義定態信號集。這一定態信號集屬于某一個測量子空間{Si，i∈I}。
一階測量可以定義為一個測量向量集{qi，i∈I}，它張成的子空間{SiH，i∈I}為H和定態信號集M間的一個非線性映射。用Ei來表示一個Si上的投影，如果x是一個定態信號，那么M(x)=Eix=x；否則M(x)=Eix。其中i=fM({〈x，qk〉，k∈I})。這里fM是信號x到索引I之間的一個映射。
子空間測量則被定義為一個測量投影集{Ei，i∈I}，它張成的子空間{SiH，i∈I}為H和定態信號集M間的一個非線性映射。如果x是一個定態信號，那么M(x)=Eix=x；否則M(x)=Eix。其中i=fM({〈Ekx，Ekx〉，k∈I})。這里fM是信號x到索引I之間的一個映射。
2．3QSP算法設計
基于QSP的信號處理算法可以采用以下幾個步驟進行設計：
a)定義測量向量qi或測量算符Ei。
b)使測量向量屬于H空間，并且如果被處理信號x不屬于H空間，則通過變換Tx將信號映射到H空間。
c)對信號進行測量。假如x是定態信號，則測量輸出y=M(x)=x；否則采用映射fM得到定態信號y。
d)如果需要，可將測量輸出通過變換Ty映射為算法的輸出。
3QSP的應用和擴展
QSP算法在信號處理領域可以得到廣泛應用，如匹配濾波、線性估計、CDMA多用戶探測等。Eldar等人在這方面做了大量的工作，奠定了QSP算法的基礎，具體算法可參見文獻[10~13]。
3．1基于QSP的圖像處理
數字圖像作為信號處理的一個重要方向，曾建誠等人根據Eldar提出的QSP算法框架對QSP在數字圖像中的應用進行了研究[14]，提出了量子圖像halftoning算法、量子邊緣提取算法和量子圖像密碼技術。這些算法的思想都是將圖像的每一個像素x(m，n)轉換為量子位(qubit)：
|q(m，n)>=∑iai|i>
即將每一個像素看做是i個定態的疊加態，而每一種定態可能出現的概率為ai。例如在圖像邊緣提取算法中每一個像素都可能處于邊緣和非邊緣兩種狀態的疊加狀態，這兩種狀態分別以不同的概率在測量中出現，歸一化后∑iai=1。構造一個函數f(x)，由f(x)可得到各個ai的值，采用隨機選擇方法對|q(m，n)>進行測量得到輸出|o(m，n)>。通常|o(m，n)>為|q(m，n)>中的一個定態|i>，它出現的幾率為ai，所以在測量結果中ai越大的態出現的幾率越大，并且在這一算法中結果也可以為多個定態的疊加，其出現的概率為多個定態的ai之和。最后將得到的結果根據其映射關系在圖像中標出，如某一像素測量輸出為邊緣態則將它標注為邊緣。這一算法的關鍵在于如何使人們希望得到的輸出對應的態以最大概率在測量結果中出現，即使其ai值盡可能大。
3．2量子算法
QSP算法是基于量子力學建立的一種算法框架，但并不受限于量子力學，如它可以突破對向量正交性的要求。所以筆者可以根據實際問題的需要對這一算法框架進行改進，這樣可以拓寬QSP算法的應用范圍。從QSP算法的結構可以看出，這一算法的應用決不僅僅是在信號處理上，從算法體系上看它是一個通用的算法模型，現實中絕大多數算法都可以抽象成為由輸入態通過相應的處理得到符合要求的輸出這種模式。這一類算法模式在人工智能、數據挖掘、圖像處理中有著廣泛的應用，所以都可考慮用類QSP算法進行處理，可以將這一類算法叫做量子算法。采用量子算法的處理方法與QSP非常相似。首先，將要求解的問題映射為量子態的疊加ψ=∑nan|φn>;然后，對這一疊加態進行測量操作M(ψ)；最后將測量結果映射為所求問題的結果。為了得到筆者希望的測量結果，在進行問題映射時即要求使希望得到的輸出|φi>對應的概率幅ai越大越好。圖2為QA算法的工作模型。
這一算法的兩個關鍵問題是：a)如何將所求問題映射為量子態疊加的形式；b)測量方法的設計。這兩個問題是QSP和QA算法的研究核心。為拓展QSP和QA算法的應用能力，筆者還可以定義作用在量子疊加態上的操作算符。這一算符作用在疊加態上的預期效果為，使希望的輸出定態|φi>對應的概率幅ai變大。這樣在進行測量時|φi>將以較大的概率被檢測出來作為求解結果。構造操作算符將是量子算法的研究重點。
3．3量子并行算法
由QSP的理論框架以及其擴展的QA算法可以看到，量子疊加原理在QSP理論體系中具有極為重要的作用，因此量子疊加原理在量子算法中也起著重要的作用，而量子態疊加是在量子計算機技術中利用的一個重要量子現象，這一物理現象使量子計算機具有驚人的并行計算能力[15]。一個量子位可以由許多可數定態|φn>疊加而成∑nan|φn>，作用于這個量子疊加態的操作相當于對這一量子位的n個疊加態同時進行操作，這一操作過程具有強大的并行效果。Eldar等人提出的QSP算法正是對量子疊加這一現象的仿真。由于疊加原理在物理上具有天然的并行性，基于對量子系統進行仿真的量子算法也相應具有天然的并行性能，它為普通算法的并行化提供了一種新的途徑和模式，即對映射到量子系統后的問題按量子態對任務進行劃分，將不同的量子態分配到不同的處理器上進行相關操作，得到疊加的結果。這一并行化思想通過多個處理器仿真一個量子疊加態，對這一疊加態的各種操作同時在各個處理器上并行執行，最后通過對各處理器進行測量，使疊加態塌縮到其中一個定態，從而得到相應疊加態的輸出結果，而各定態|φn>在結果中出現的概率由各自an
的大小決定。
4結束語
本文對量子系統以及建立在量子力學理論基礎上的量子信號處理的算法框架進行了研究和介紹，提出了量子算法在信號處理、圖像處理和程序并行化上的應用，并給出了量子算法的應用模式，建立了量子算法的理論基礎。
作為人類發現的最偉大的理論之一——量子力學真實地反映了自然界的本質。量子信號處理是一種新興的仿真量子系統進行信號處理的算法框架和思路，它利用了量子力學所取得的成果已經在信號處理的多個領域得到應用。由于這一算法框架的通用性，它在數據挖掘、圖像處理、大規模并行計算等領域也有著廣泛的應用前景。量子力學是一個巨大的知識寶庫，對于量子算法的開發研究還有很多工作需要人們去做，如對量子糾纏現象的仿真算法等。量子計算機是計算機技術今后發展的一個重要方向，量子算法作為對量子系統的模擬算法框架，可直接應用于量子計算機中，為今后量子計算技術做好理論和方法的儲備。
參考文獻：
[1]ELDAR Y C， OPPENHEIM A V. Quantum signal processing[J]. Signal Processing， 2002，19（6）:12－32.
[2]ELDAR Y C. Quantum signal processing[D].[S.l.]: Mass Inst Technol， 2001.
[3]NIELSEN M A， CHUANG I L. Quantum computation and quantum information[M]. Cambridge: Cambridge University Press， 2000.
[4]郭光燦，郭濤，鄭軼.量子計算機[J].量子光學學報，1997，3(1):1－14.
[5]BROOKS M. Quantum computing and communication[M]. Berlin， Heidelberg: Springer－Verlag， 1999.
[6]SHOR P W. Polynomial－time algorithms for prime factoriation and discrete logarithms on a quantum computer[J]. SIAM J Comput， 1997，26(5):1484－1590.
[7]FEYNMAN R P， LEIGHTON R B， SANDS M. The Feynman lectures on physics[M].[S.l.]: Addision－Wesley， 1965.
[8]FEYNMAN R P. Simulating physics with computers[J]. International Journal of Theoretical Physics， 1982，21(6/7):467－488.
[9]DIRAC P A M. The principles of quantum mechanics[J]. 4th ed. Oxford: Oxford University Press， 1958.
[10]ELDAR Y C， OPPENHEIM A V， EGNOR D. Orthogonal and projected orthogonal matched filter detection[J]. Signal Processing， 2004，84(4):677－693.
[11]ELDER Y C， OPPENHEIM A V， EGNOR D. Orthogonal matched filter detection[C]//Proc of ICASSP.Salt Lake City:[s.n.]， 2001:2837－2840.
[12]ELDAR Y C， OPPENHEIM A V. Orthogonal multiuser detection[J]. Signal Processing， 2002，82(2):321－325.
[13]ULUKUS S， YATES R D. Optimum multiuser detection is tractable for synchronous CDMA systems using m－sequences[J]. IEEE Commun Lett， 1998，2(4):89－91.
[14]TSENG C C， HWANG T M. Quantum digital image processing algorithms[C]//Proc of the 16th IPPR Conference on Computer Vision， Graphics and Image Processing. 2003:827－834.
[15]陳國良，吳俊敏.并行計算機體系結構[M].北京:高等教育出版社，2002.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
