量子信號(hào)處理
2008-01-01 00:00:00王鵬李建平
計(jì)算機(jī)應(yīng)用研究 2008年4期
摘要：對(duì)量子系統(tǒng)的基本原理以及建立在對(duì)這一理論體系進(jìn)行仿真基礎(chǔ)上的量子信號(hào)處理算法的理論框架進(jìn)行了分析和研究，提出了量子信號(hào)處理在信號(hào)處理和圖像處理領(lǐng)域的應(yīng)用方法，并根據(jù)量子信號(hào)處理的理論框架得到了更為通用的量子算法設(shè)計(jì)模型，指出了量子算法所具有的并行化特性，為算法并行化提供了一種新的思路。
關(guān)鍵詞：量子力學(xué); 量子信號(hào)處理; 量子算法; 量子態(tài)
中圖分類號(hào)：TN911.7文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：1001－3695(2008)04－1033－03
量子信號(hào)處理是信號(hào)處理領(lǐng)域最新的研究方向之一，首次提出這一概念和理論是在2001年，相關(guān)的工作主要由MIT的Yonina C.Eldar等人完成[1，2]。這一思想將量子力學(xué)的數(shù)學(xué)框架應(yīng)用于信號(hào)處理領(lǐng)域，建立新的基于量子力學(xué)的算法并改進(jìn)現(xiàn)有算法。這一思想與人們通常所說(shuō)的量子計(jì)算有較大的區(qū)別[3~6]。通常人們所說(shuō)的量子計(jì)算是利用物質(zhì)實(shí)體的量子效應(yīng)來(lái)完成相應(yīng)的處理，這種方法要受量子物理的公理和約束所限制。本文所說(shuō)的量子信號(hào)處理只是利用量子力學(xué)的數(shù)學(xué)框架和思想，并依據(jù)量子力學(xué)中相應(yīng)公理建立與之對(duì)應(yīng)的處理算法，這種方法不會(huì)實(shí)質(zhì)性地受到量子物理規(guī)律的限制，它的實(shí)現(xiàn)實(shí)體為普通的計(jì)算機(jī)系統(tǒng)；這一思想與遺傳算法十分相似，是一種自然仿真算法框架。
量子力學(xué)是一種反映自然規(guī)律的物理理論[7，8]，經(jīng)過一百多年的實(shí)踐檢驗(yàn)，解決了大量的物理問題，現(xiàn)在人們?nèi)粘Ｉ钪惺褂玫暮芏辔锲范茧x不開量子力學(xué)的貢獻(xiàn)。量子力學(xué)真實(shí)地反映了自然的奧秘，因此量子力學(xué)的數(shù)學(xué)框架和思想是十分深刻的。信號(hào)作為自然界中客觀存在的物理實(shí)體，它在物理上也是受量子力學(xué)原理約束的，將量子力學(xué)的數(shù)學(xué)思想框架應(yīng)用于信號(hào)處理領(lǐng)域也是非常自然的想法。
1量子系統(tǒng)
1．1Dirac符號(hào)
Dirac符號(hào)是由Dirac[9]提出的。在這一基礎(chǔ)上，能夠建立起量子力學(xué)規(guī)律的一種普遍的數(shù)學(xué)形式，它適用于一切量子體系。量子體系的各種狀態(tài)，包括描述空間運(yùn)動(dòng)與非空間運(yùn)動(dòng)的狀態(tài)在內(nèi)，它們的某些性質(zhì)可以是不同的。但是，各種狀態(tài)都有一個(gè)共同的性質(zhì)，即都滿足狀態(tài)疊加原理?？蓪顟B(tài)稱為態(tài)矢量；量子體系的一切可能狀態(tài)構(gòu)成一種態(tài)矢量空間；無(wú)限維態(tài)矢量空間具有Hilbert空間的性質(zhì)?？臻g中所有的態(tài)矢都用一個(gè)右矢|>來(lái)表示，它的對(duì)偶態(tài)矢量空間，所有的態(tài)矢都用一個(gè)左矢<|來(lái)表示。
設(shè)基底為|n＞(1，2，3，…)，基底中的基矢是分立可數(shù)的，數(shù)目可以是有限或無(wú)限。由無(wú)限可數(shù)的抽象基底所生成的空間就是一個(gè)抽象的Hilbert空間?？臻g中的任意矢量|ψ>皆可表示為|ψ>=∑nan|n>，如果
1．2量子測(cè)量
對(duì)量子系統(tǒng)中一個(gè)或多個(gè)粒子進(jìn)行測(cè)量，將會(huì)把量子系統(tǒng)的狀態(tài)投射到與測(cè)量值相對(duì)應(yīng)的狀態(tài)空間中去，同時(shí)也會(huì)對(duì)投射的幅度進(jìn)行縮放。結(jié)果態(tài)矢的長(zhǎng)度為1，測(cè)量結(jié)果出現(xiàn)的概率等于測(cè)量所用基的復(fù)數(shù)平方和。
量子測(cè)量是一個(gè)非線性映射，通?？梢杂靡粋€(gè)測(cè)量矢量{μi，i∈I}來(lái)描述，這一矢量張成一個(gè)子空間{SiH，i∈I}。其中：I為索引集。量子力學(xué)要求μi必須正交。更一般情況的量子測(cè)量可用投影算符Pψ來(lái)描述：定義Pψ=|ψ><ψ|稱Pψ為對(duì)|ψ>的投影算符。將Pψ作用在任意右矢|χ>上，則
Pψ|χ>=|ψ><ψ|χ>=<ψ|χ>|ψ>
按照投影算符的概念可以看出，展開式|ψ>=∑n|n>
1．3測(cè)量一致性
測(cè)量一致性是量子力學(xué)的一個(gè)基本假設(shè)，對(duì)一個(gè)處于定態(tài)的系統(tǒng)進(jìn)行重復(fù)測(cè)量將產(chǎn)生相同的輸出。因此系統(tǒng)狀態(tài)在測(cè)量后應(yīng)該保持不變，反復(fù)進(jìn)行測(cè)量后系統(tǒng)最后的狀態(tài)應(yīng)該與第一次測(cè)量后的狀態(tài)相同。
1．4量子化
測(cè)量輸出的量子化是一致性要求的直接結(jié)果，一致性要求將導(dǎo)致測(cè)量后形成一種被稱為定態(tài)的量子態(tài)。這些由測(cè)量得到的量子態(tài)由概率決定，這些態(tài)屬于測(cè)量子空間Si。甚至當(dāng)系統(tǒng)不處于定態(tài)時(shí)對(duì)系統(tǒng)進(jìn)行測(cè)量后系統(tǒng)也會(huì)量子化到其中一個(gè)定態(tài)，即測(cè)量結(jié)果一定會(huì)是這些定態(tài)中的其中一個(gè)，而得到其中一個(gè)定態(tài)的概率可由系統(tǒng)量子態(tài)和這一定態(tài)的內(nèi)積決定。
1．5量子疊加原理
定態(tài)（stationary state）在量子力學(xué)中定義為如下的波函數(shù)：
ψ(r，t)=ψE(r)e-iEt/h
處于定態(tài)下的粒子具有如下特征：a)粒子空間的概率密度ρ(r)=|ψE(r)|2以及概率流密度j不隨時(shí)間變化；b)任何力學(xué)量的平均值不隨時(shí)間變化；c)任何力學(xué)量的測(cè)量概率分布不隨時(shí)間變化。
由若干個(gè)能量不同本征態(tài)疊加所形成的態(tài)稱為非定態(tài)（nonstationary state）。
量子疊加原理是波的疊加性和波函數(shù)完全描述一個(gè)體系的量子態(tài)兩個(gè)概念的概括。非定態(tài)就是由許多本征態(tài)的某種相干疊加，而粒子可部分地處于其中的某一個(gè)態(tài)。這從經(jīng)典物理的概念來(lái)看是無(wú)法理解的，但只有這種解釋才能說(shuō)明測(cè)量結(jié)果的不確定性，各個(gè)定態(tài)可以按一定概率在多次測(cè)量時(shí)都有可能得到。
一般來(lái)說(shuō)對(duì)一個(gè)量子態(tài)ψ=∑nan|φn>進(jìn)行測(cè)量時(shí)，這一量子態(tài)就以相對(duì)概率an坍縮到某一定態(tài)|φn>，量子力學(xué)中把這種現(xiàn)象稱為量子態(tài)坍縮，即在測(cè)量過程中疊加態(tài)坍縮到某一能量本征態(tài)。態(tài)的疊加導(dǎo)致疊加態(tài)下觀測(cè)結(jié)果的不確定性，疊加原理是與測(cè)量密切聯(lián)系在一起的一個(gè)基本原理。這也是量子計(jì)算中很重要的一個(gè)原理，它是實(shí)現(xiàn)量子并行計(jì)算的理論依據(jù)。
2QSP理論體系
2．1QSP的建立
Eldar等人認(rèn)為量子信號(hào)處理主要是借鑒量子力學(xué)理論以及它的一些公理和約束形成新的算法或者改進(jìn)已有的信號(hào)處理算法，它并不依靠真實(shí)量子物理體系來(lái)實(shí)現(xiàn)。這與量子計(jì)算和量子信息學(xué)的研究?jī)?nèi)容有本質(zhì)區(qū)別，可以認(rèn)為QSP只是一種仿真的量子計(jì)算。他們認(rèn)為量子力學(xué)的理論體系與信號(hào)處理存在三種內(nèi)在聯(lián)系：一是量子力學(xué)中的測(cè)量概念；二是量子測(cè)量一致性原理；三是測(cè)量輸出的量子化原理。在進(jìn)行算法設(shè)計(jì)時(shí)，QSP算法理論架構(gòu)就對(duì)量子力學(xué)的本身的理論架構(gòu)進(jìn)行了擴(kuò)展并且突破了它的一些約束條件，進(jìn)而拓寬了QSP的應(yīng)用范圍。圖1描述了這種關(guān)系。
2．2QSP中的測(cè)量
QSP中對(duì)信號(hào)的測(cè)量對(duì)應(yīng)于采用一種算法作用到信號(hào)上，采用QSP算法進(jìn)行測(cè)量等效于對(duì)信號(hào)進(jìn)行相應(yīng)的處理或在不同信號(hào)空間對(duì)信號(hào)進(jìn)行表示。測(cè)量的輸出則對(duì)應(yīng)于算法的輸出。
Hilbert空間中的一階測(cè)量（rank－one QSP measurement）M可定義為一個(gè)測(cè)量向量{qi，i∈I}，它是Hilbert空間的一個(gè)子空間{SiH，i∈I}。由于QSP算法并不受量子力學(xué)中物理定理的約束，這些向量并不保證要相互正交。Hilbert子空間QSP測(cè)量定義為子空間{SiH，i∈I}上的一組投影操作符。由于不受實(shí)際物理定律約束，投影算符和子空間Si不要求是正交的。對(duì)信號(hào)x的測(cè)量可用M(x)表示。
QSP中的測(cè)量一致性可用數(shù)學(xué)形式表示為M(M(x))=M(x)。根據(jù)筆者的定義，假如x是Hilbert信號(hào)空間中的信號(hào)，那么M(x)也是Hilbert空間的信號(hào)，因此能對(duì)它進(jìn)行多次測(cè)量。
測(cè)量輸出的量子化要求輸出信號(hào)M(x)為這組信號(hào)中的一個(gè)，對(duì)應(yīng)于量子力學(xué)中的定態(tài)，可以定義定態(tài)信號(hào)集。這一定態(tài)信號(hào)集屬于某一個(gè)測(cè)量子空間{Si，i∈I}。
一階測(cè)量可以定義為一個(gè)測(cè)量向量集{qi，i∈I}，它張成的子空間{SiH，i∈I}為H和定態(tài)信號(hào)集M間的一個(gè)非線性映射。用Ei來(lái)表示一個(gè)Si上的投影，如果x是一個(gè)定態(tài)信號(hào)，那么M(x)=Eix=x；否則M(x)=Eix。其中i=fM({〈x，qk〉，k∈I})。這里fM是信號(hào)x到索引I之間的一個(gè)映射。
子空間測(cè)量則被定義為一個(gè)測(cè)量投影集{Ei，i∈I}，它張成的子空間{SiH，i∈I}為H和定態(tài)信號(hào)集M間的一個(gè)非線性映射。如果x是一個(gè)定態(tài)信號(hào)，那么M(x)=Eix=x；否則M(x)=Eix。其中i=fM({〈Ekx，Ekx〉，k∈I})。這里fM是信號(hào)x到索引I之間的一個(gè)映射。
2．3QSP算法設(shè)計(jì)
基于QSP的信號(hào)處理算法可以采用以下幾個(gè)步驟進(jìn)行設(shè)計(jì)：
a)定義測(cè)量向量qi或測(cè)量算符Ei。
b)使測(cè)量向量屬于H空間，并且如果被處理信號(hào)x不屬于H空間，則通過變換Tx將信號(hào)映射到H空間。
c)對(duì)信號(hào)進(jìn)行測(cè)量。假如x是定態(tài)信號(hào)，則測(cè)量輸出y=M(x)=x；否則采用映射fM得到定態(tài)信號(hào)y。
d)如果需要，可將測(cè)量輸出通過變換Ty映射為算法的輸出。
3QSP的應(yīng)用和擴(kuò)展
QSP算法在信號(hào)處理領(lǐng)域可以得到廣泛應(yīng)用，如匹配濾波、線性估計(jì)、CDMA多用戶探測(cè)等。Eldar等人在這方面做了大量的工作，奠定了QSP算法的基礎(chǔ)，具體算法可參見文獻(xiàn)[10~13]。
3．1基于QSP的圖像處理
數(shù)字圖像作為信號(hào)處理的一個(gè)重要方向，曾建誠(chéng)等人根據(jù)Eldar提出的QSP算法框架對(duì)QSP在數(shù)字圖像中的應(yīng)用進(jìn)行了研究[14]，提出了量子圖像halftoning算法、量子邊緣提取算法和量子圖像密碼技術(shù)。這些算法的思想都是將圖像的每一個(gè)像素x(m，n)轉(zhuǎn)換為量子位(qubit)：
|q(m，n)>=∑iai|i>
即將每一個(gè)像素看做是i個(gè)定態(tài)的疊加態(tài)，而每一種定態(tài)可能出現(xiàn)的概率為ai。例如在圖像邊緣提取算法中每一個(gè)像素都可能處于邊緣和非邊緣兩種狀態(tài)的疊加狀態(tài)，這兩種狀態(tài)分別以不同的概率在測(cè)量中出現(xiàn)，歸一化后∑iai=1。構(gòu)造一個(gè)函數(shù)f(x)，由f(x)可得到各個(gè)ai的值，采用隨機(jī)選擇方法對(duì)|q(m，n)>進(jìn)行測(cè)量得到輸出|o(m，n)>。通常|o(m，n)>為|q(m，n)>中的一個(gè)定態(tài)|i>，它出現(xiàn)的幾率為ai，所以在測(cè)量結(jié)果中ai越大的態(tài)出現(xiàn)的幾率越大，并且在這一算法中結(jié)果也可以為多個(gè)定態(tài)的疊加，其出現(xiàn)的概率為多個(gè)定態(tài)的ai之和。最后將得到的結(jié)果根據(jù)其映射關(guān)系在圖像中標(biāo)出，如某一像素測(cè)量輸出為邊緣態(tài)則將它標(biāo)注為邊緣。這一算法的關(guān)鍵在于如何使人們希望得到的輸出對(duì)應(yīng)的態(tài)以最大概率在測(cè)量結(jié)果中出現(xiàn)，即使其ai值盡可能大。
3．2量子算法
QSP算法是基于量子力學(xué)建立的一種算法框架，但并不受限于量子力學(xué)，如它可以突破對(duì)向量正交性的要求。所以筆者可以根據(jù)實(shí)際問題的需要對(duì)這一算法框架進(jìn)行改進(jìn)，這樣可以拓寬QSP算法的應(yīng)用范圍。從QSP算法的結(jié)構(gòu)可以看出，這一算法的應(yīng)用決不僅僅是在信號(hào)處理上，從算法體系上看它是一個(gè)通用的算法模型，現(xiàn)實(shí)中絕大多數(shù)算法都可以抽象成為由輸入態(tài)通過相應(yīng)的處理得到符合要求的輸出這種模式。這一類算法模式在人工智能、數(shù)據(jù)挖掘、圖像處理中有著廣泛的應(yīng)用，所以都可考慮用類QSP算法進(jìn)行處理，可以將這一類算法叫做量子算法。采用量子算法的處理方法與QSP非常相似。首先，將要求解的問題映射為量子態(tài)的疊加ψ=∑nan|φn>;然后，對(duì)這一疊加態(tài)進(jìn)行測(cè)量操作M(ψ)；最后將測(cè)量結(jié)果映射為所求問題的結(jié)果。為了得到筆者希望的測(cè)量結(jié)果，在進(jìn)行問題映射時(shí)即要求使希望得到的輸出|φi>對(duì)應(yīng)的概率幅ai越大越好。圖2為QA算法的工作模型。
這一算法的兩個(gè)關(guān)鍵問題是：a)如何將所求問題映射為量子態(tài)疊加的形式；b)測(cè)量方法的設(shè)計(jì)。這兩個(gè)問題是QSP和QA算法的研究核心。為拓展QSP和QA算法的應(yīng)用能力，筆者還可以定義作用在量子疊加態(tài)上的操作算符。這一算符作用在疊加態(tài)上的預(yù)期效果為，使希望的輸出定態(tài)|φi>對(duì)應(yīng)的概率幅ai變大。這樣在進(jìn)行測(cè)量時(shí)|φi>將以較大的概率被檢測(cè)出來(lái)作為求解結(jié)果。構(gòu)造操作算符將是量子算法的研究重點(diǎn)。
3．3量子并行算法
由QSP的理論框架以及其擴(kuò)展的QA算法可以看到，量子疊加原理在QSP理論體系中具有極為重要的作用，因此量子疊加原理在量子算法中也起著重要的作用，而量子態(tài)疊加是在量子計(jì)算機(jī)技術(shù)中利用的一個(gè)重要量子現(xiàn)象，這一物理現(xiàn)象使量子計(jì)算機(jī)具有驚人的并行計(jì)算能力[15]。一個(gè)量子位可以由許多可數(shù)定態(tài)|φn>疊加而成∑nan|φn>，作用于這個(gè)量子疊加態(tài)的操作相當(dāng)于對(duì)這一量子位的n個(gè)疊加態(tài)同時(shí)進(jìn)行操作，這一操作過程具有強(qiáng)大的并行效果。Eldar等人提出的QSP算法正是對(duì)量子疊加這一現(xiàn)象的仿真。由于疊加原理在物理上具有天然的并行性，基于對(duì)量子系統(tǒng)進(jìn)行仿真的量子算法也相應(yīng)具有天然的并行性能，它為普通算法的并行化提供了一種新的途徑和模式，即對(duì)映射到量子系統(tǒng)后的問題按量子態(tài)對(duì)任務(wù)進(jìn)行劃分，將不同的量子態(tài)分配到不同的處理器上進(jìn)行相關(guān)操作，得到疊加的結(jié)果。這一并行化思想通過多個(gè)處理器仿真一個(gè)量子疊加態(tài)，對(duì)這一疊加態(tài)的各種操作同時(shí)在各個(gè)處理器上并行執(zhí)行，最后通過對(duì)各處理器進(jìn)行測(cè)量，使疊加態(tài)塌縮到其中一個(gè)定態(tài)，從而得到相應(yīng)疊加態(tài)的輸出結(jié)果，而各定態(tài)|φn>在結(jié)果中出現(xiàn)的概率由各自an
的大小決定。
4結(jié)束語(yǔ)
本文對(duì)量子系統(tǒng)以及建立在量子力學(xué)理論基礎(chǔ)上的量子信號(hào)處理的算法框架進(jìn)行了研究和介紹，提出了量子算法在信號(hào)處理、圖像處理和程序并行化上的應(yīng)用，并給出了量子算法的應(yīng)用模式，建立了量子算法的理論基礎(chǔ)。
作為人類發(fā)現(xiàn)的最偉大的理論之一——量子力學(xué)真實(shí)地反映了自然界的本質(zhì)。量子信號(hào)處理是一種新興的仿真量子系統(tǒng)進(jìn)行信號(hào)處理的算法框架和思路，它利用了量子力學(xué)所取得的成果已經(jīng)在信號(hào)處理的多個(gè)領(lǐng)域得到應(yīng)用。由于這一算法框架的通用性，它在數(shù)據(jù)挖掘、圖像處理、大規(guī)模并行計(jì)算等領(lǐng)域也有著廣泛的應(yīng)用前景。量子力學(xué)是一個(gè)巨大的知識(shí)寶庫(kù)，對(duì)于量子算法的開發(fā)研究還有很多工作需要人們?nèi)プ?，如?duì)量子糾纏現(xiàn)象的仿真算法等。量子計(jì)算機(jī)是計(jì)算機(jī)技術(shù)今后發(fā)展的一個(gè)重要方向，量子算法作為對(duì)量子系統(tǒng)的模擬算法框架，可直接應(yīng)用于量子計(jì)算機(jī)中，為今后量子計(jì)算技術(shù)做好理論和方法的儲(chǔ)備。
參考文獻(xiàn)：
[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ì)算機(jī)[J].量子光學(xué)學(xué)報(bào)，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]陳國(guó)良，吳俊敏.并行計(jì)算機(jī)體系結(jié)構(gòu)[M].北京:高等教育出版社，2002.
“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”
