楊樂(lè) 李凱 戴宏毅 張明?

1)(國(guó)防科技大學(xué),智能科學(xué)學(xué)院,長(zhǎng)沙 410073)

2)(國(guó)防科技大學(xué),文理學(xué)院物理系,長(zhǎng)沙 410073)

3)(國(guó)防科技大學(xué),量子信息交叉中心,長(zhǎng)沙 410073)

在經(jīng)典信息可有效制備為量子態(tài)和量子算法可物理實(shí)現(xiàn)的條件下,深入研究了量子算法如何有效改善基于線性回歸估計(jì)的量子態(tài)層析算法的時(shí)間復(fù)雜度問(wèn)題.在已有的量子算法基礎(chǔ)上,形成了量子態(tài)層析的新方案.與現(xiàn)有的經(jīng)典算法相比,本文所提方案需要引入量子態(tài)制備和額外的測(cè)量環(huán)節(jié),但能顯著降低量子態(tài)層析的時(shí)間復(fù)雜度.對(duì)于維數(shù)為d的待重構(gòu)密度矩陣,當(dāng)所用的量子算法涉及的矩陣的條件數(shù)κ和估計(jì)精度ε的倒數(shù)的復(fù)雜度均為O(polylogd),且所需同時(shí)制備的量子態(tài)數(shù)目規(guī)模是O(d)時(shí),本方案可將量子態(tài)層析整體算法的時(shí)間復(fù)雜度從O(d4)降為O(dpolylogd).

1 引 言

量子態(tài)層析(quantum state tomography),也稱為量子態(tài)估計(jì)(quantum state estimation)[1],是通過(guò)測(cè)量數(shù)據(jù)來(lái)推斷被測(cè)量子態(tài)的方法.對(duì)于n量子比特構(gòu)成的量子系統(tǒng),其維數(shù) d=2n,因而量子態(tài)層析任務(wù)的時(shí)間復(fù)雜度隨著問(wèn)題規(guī)模的增加成指數(shù)增長(zhǎng).量子態(tài)層析分為2個(gè)階段,即測(cè)量階段和使用測(cè)量數(shù)據(jù)重構(gòu)量子態(tài)階段.當(dāng)面對(duì)的量子系統(tǒng)維數(shù)較高時(shí),這2個(gè)環(huán)節(jié)的時(shí)間復(fù)雜度會(huì)很大.例如文獻(xiàn)[2]的研究者面對(duì)8離子的量子系統(tǒng),耗費(fèi)10多個(gè)小時(shí)在測(cè)量和數(shù)據(jù)采集的環(huán)節(jié),而又花費(fèi)了將近一周時(shí)間使用數(shù)據(jù)進(jìn)行量子態(tài)重構(gòu).因此,選擇合適的測(cè)量集及重構(gòu)方法是解決量子態(tài)層析問(wèn)題的關(guān)鍵.量子態(tài)重構(gòu)有多種方法,如線性估計(jì)[3]、線性回歸估計(jì)[4,5]、極大似然估計(jì)[6,7]、貝葉斯均值估計(jì)[8,9]等,這些方法各有優(yōu)勢(shì)和不足.

量子算法是應(yīng)用在量子計(jì)算機(jī)上的算法.對(duì)于經(jīng)典算法的難解問(wèn)題,有些可以找到量子算法使其在有效時(shí)間內(nèi)解決[10,11]; 有些在一定條件下可以加速問(wèn)題的求解,從而顯現(xiàn)出量子算法的優(yōu)勢(shì)[12,13].從機(jī)器學(xué)習(xí)的角度,可以將量子算法整體看作是一個(gè)黑盒,把測(cè)量數(shù)據(jù)及態(tài)生成源的數(shù)據(jù)作為訓(xùn)練集合,訓(xùn)練得到量子態(tài)重構(gòu)的模型.這屬于使用量子算法解決量子問(wèn)題的范疇[14].一個(gè)自然的問(wèn)題是:對(duì)于量子態(tài)層析的重構(gòu)過(guò)程,使用量子算法能否使其得到加速,從而使時(shí)間復(fù)雜度下降? 目前使用量子算法實(shí)現(xiàn)量子態(tài)重構(gòu)的相關(guān)研究還不多,并且還未發(fā)現(xiàn)從時(shí)間復(fù)雜度角度來(lái)分析量子態(tài)重構(gòu)的量子算法與經(jīng)典算法相比是否有優(yōu)勢(shì)的研究?jī)?nèi)容.

量子態(tài)重構(gòu)過(guò)程的經(jīng)典算法有多種,不同算法又分為多個(gè)環(huán)節(jié),不同環(huán)節(jié)中的步驟涉及不同的操作,這些操作對(duì)應(yīng)的量子算法也有不同的實(shí)現(xiàn)方法,因而并沒(méi)有一個(gè)統(tǒng)一的量子算法來(lái)實(shí)現(xiàn)重構(gòu)過(guò)程.本文關(guān)注的問(wèn)題是: 對(duì)于使用線性回歸模型估計(jì)未知狀態(tài)參數(shù)的量子態(tài)重構(gòu)過(guò)程,使用量子算法進(jìn)行處理是否值得,在什么條件下使用量子算法會(huì)加速任務(wù)的完成.選擇使用線性回歸算法的估計(jì)過(guò)程,原因在于它是幾種重構(gòu)算法中重構(gòu)速度快于極大似然估計(jì)和貝葉斯估計(jì)的一種,并且通過(guò)求解受約束的優(yōu)化問(wèn)題[15],避免了線性估計(jì)算法的重構(gòu)矩陣可能存在負(fù)本征值的問(wèn)題.通過(guò)在重構(gòu)算法的不同步驟中選擇相應(yīng)的量子算法,可以形成一個(gè)實(shí)現(xiàn)量子狀態(tài)重構(gòu)的整體量子算法,然后從時(shí)間復(fù)雜度的角度將其與經(jīng)典算法進(jìn)行對(duì)比分析.

當(dāng)要求的精度和重構(gòu)過(guò)程涉及到的矩陣條件數(shù)等指標(biāo),滿足使用量子算法進(jìn)行加速的條件,且所需制備的量子態(tài)數(shù)目與系統(tǒng)維數(shù)成正比時(shí),整個(gè)量子算法實(shí)現(xiàn)過(guò)程可以將目前使用線性回歸估計(jì)實(shí)現(xiàn)量子態(tài)重構(gòu)過(guò)程的總體時(shí)間復(fù)雜度,由O(d4)降低為 O (dpolylog(d)).

本文后續(xù)內(nèi)容安排如下: 第2部分?jǐn)⑹龌诰€性回歸估計(jì)的經(jīng)典重構(gòu)算法,第3部分展示使用量子算法處理量子態(tài)重構(gòu)的基本流程,第4部分對(duì)比分析研究了分別使用經(jīng)典算法和量子算法的時(shí)間復(fù)雜度,第5部分是算例,第6部分是結(jié)論.

2 基于線性回歸估計(jì)的經(jīng)典重構(gòu)算法

在測(cè)量存在高斯噪聲時(shí),可以使用基于線性回歸估計(jì)的重構(gòu)算法,來(lái)高效地重構(gòu)量子狀態(tài)[4].要通過(guò)測(cè)量數(shù)據(jù)得到系統(tǒng)密度矩陣 ρ 的重構(gòu)矩陣,可以使用如圖1所示的2個(gè)環(huán)節(jié)來(lái)進(jìn)行.

圖1 基于線性回歸估計(jì)的經(jīng)典重構(gòu)算法Fig.1.Classical algorithm of quantum state tomography via linear regression.

下面分別敘述如何得到方程(1)和方程(2),以及它們的求解過(guò)程.

2.1 使用測(cè)量數(shù)據(jù)重構(gòu)偽線性估計(jì)矩陣(環(huán)節(jié)1)

可以使用線性回歸估計(jì)[4],通過(guò)5個(gè)步驟得到量子狀態(tài)中的未知參數(shù),并使用估計(jì)出的參數(shù)重構(gòu)出.下面對(duì)這5個(gè)步驟進(jìn)行簡(jiǎn)要敘述.

1)設(shè)量子系統(tǒng)的維數(shù)是d.選取劉維爾空間(Liouville space)中的一組完備正交基,記為

2)分別將待重構(gòu)的量子狀態(tài)和測(cè)量基在劉維爾空間中展開(kāi),得到相應(yīng)的由展開(kāi)系數(shù)構(gòu)成的向量.

3)計(jì)算測(cè)量算子作用于量子態(tài)所得到的測(cè)量結(jié)果的概率,可以使用2)中的量子態(tài)和測(cè)量基在劉維爾空間中的展開(kāi)系數(shù)表示測(cè)量結(jié)果概率.

4)結(jié)合測(cè)量結(jié)果概率和實(shí)際測(cè)量的頻率,得到描述量子狀態(tài)的未知參數(shù) Θ 的線性估計(jì)模型:

2.2 求與矩陣最接近的目標(biāo)矩陣(環(huán)節(jié)2)

這個(gè)問(wèn)題可以表述為[15]: 給定一個(gè)跡為1的厄米矩陣,在2-范數(shù)下可以找到與其最接近的密度矩陣(跡為1且只含有非負(fù)本征值的厄米矩陣)

要求解這個(gè)最小二乘的估計(jì)問(wèn)題,計(jì)算量比較大[15].但文獻(xiàn)[15]根據(jù)表達(dá)式的物理意義,給出了如下的優(yōu)化解決方法.

2)令i=d ,累加器 a=0 .

3 量子態(tài)重構(gòu)的量子算法處理過(guò)程

整個(gè)使用量子算法處理量子態(tài)重構(gòu)的過(guò)程如圖2所示,可以分為以下幾個(gè)環(huán)節(jié):

準(zhǔn)備環(huán)節(jié) 根據(jù)測(cè)量數(shù)據(jù)及選定劉維爾空間中的基,制備相應(yīng)的量子態(tài)

圖2 整體量子算法簡(jiǎn)明過(guò)程Fig.2.Concise process of the whole quantum algorithm.

對(duì)于量子態(tài)層析,對(duì)量子態(tài)產(chǎn)生源進(jìn)行測(cè)量,得到的數(shù)據(jù)是經(jīng)典數(shù)據(jù),因而需要在環(huán)節(jié)1)之前引入準(zhǔn)備環(huán)節(jié),來(lái)制備量子數(shù)據(jù)這里對(duì)于矩陣的量子數(shù)據(jù)的符號(hào)仍使用原符號(hào),例如矩陣X和 Ωi即表示它們各自的量子數(shù)據(jù); 對(duì)于向量的量子數(shù)據(jù),使用右矢形式,例如 | Y〉 表示向量Y的量子數(shù)據(jù).暫不考慮量子態(tài)制備的量子算法實(shí)現(xiàn)過(guò)程,而假設(shè)能夠有效制備量子態(tài).圖2中環(huán)節(jié)1)和環(huán)節(jié)2)并行處理多個(gè)量子態(tài),其中每個(gè)單獨(dú)過(guò)程與量子態(tài)重構(gòu)的經(jīng)典算法基本一致,但注意到在經(jīng)過(guò)本征值和本征態(tài)的估計(jì)算法之后,需要引入測(cè)量以及量子態(tài)制備環(huán)節(jié),以與后面調(diào)用量子算法過(guò)程相銜接.

圖2涉及的量子算法,可歸納為以下幾種:1)矩陣乘法的量子算法[16]; 2)矩陣求逆使用到的求解線性方程的量子算法[17]; 3)求解矩陣本征值和本征態(tài)的相位估計(jì)算法[17]; 4)對(duì)本征值進(jìn)行排序的排序算法[18,19].使用量子算法的具體過(guò)程如圖3和圖4所示,下面簡(jiǎn)要敘述相應(yīng)的量子算法.

圖3 量子算法過(guò)程1: 基于線性回歸模型重構(gòu)算法的量子算法Fig.3.Quantum algorithm process 1: quantum algorithm based on quantum state tomography via linear regression.

3.1 矩陣乘法的量子算法[16]

其中 σi的估計(jì)值滿足設(shè)輸入態(tài)則輸出態(tài)即為 A |b〉 .包含測(cè)量后選擇操作在內(nèi)的整個(gè)矩陣乘法的量子算法的時(shí)間復(fù)雜度是κ 是矩陣A的條件數(shù),ε是精度.在計(jì)算矩陣間的乘法 A ×B 時(shí),可以將B按列展開(kāi)為 { bi} ,然后使用量子算法并行處理A|bi〉.

3.2 矩陣求逆的量子算法[17]

3.3 求解矩陣本征值和本征態(tài)的相位估計(jì)算法[17]

此算法是基于矩陣求逆量子算法的部分過(guò)程實(shí)現(xiàn)的,相比于矩陣求逆量子算法,由于沒(méi)有引入輔助量子比特并進(jìn)行測(cè)量,所以該量子算法的時(shí)間復(fù)雜度為

3.4 量子排序算法

圖4 量子算法過(guò)程2Fig.4.Quantum algorithm process 2.

以量子比較邏輯門(comparison gate)為基本單元,可以構(gòu)造排序算法的黑盒[18].將量子態(tài)形式的矩陣的所有本征值的估計(jì)值作為黑盒的輸入得到的輸出結(jié)果是按本征值大小排列的量子態(tài).文獻(xiàn)[19]則指出,通過(guò)使用受控的比較邏輯門可以實(shí)現(xiàn)歸并排序過(guò)程,同樣可以實(shí)現(xiàn)量子態(tài)本征值的排序.在排序之后,使用與第2.2節(jié)中的第1)到5)相對(duì)應(yīng)的量子操作,即可得到目標(biāo)密度矩陣.

4 經(jīng)典和量子求解思路的時(shí)間復(fù)雜度對(duì)比

量子算法與經(jīng)典算法過(guò)程的不同環(huán)節(jié)的時(shí)間復(fù)雜度如表1所示.

下面分別具體分析量子態(tài)層析任務(wù)各個(gè)過(guò)程的經(jīng)典算法和量子算法的時(shí)間復(fù)雜度.

4.1 經(jīng)典算法各環(huán)節(jié)的時(shí)間復(fù)雜度

在第2節(jié)描述的使用經(jīng)典算法進(jìn)行量子態(tài)重構(gòu)的2個(gè)環(huán)節(jié),第1)個(gè)環(huán)節(jié)使用最小二乘法求解模型,在信息完備的測(cè)量集合下,X是d2×(d2-1)矩陣,Y是d2×1列向量,因此XTX以及XTY的計(jì)算復(fù)雜度均是O(d4);(XTX)-1的時(shí)間復(fù)雜度一般是O(d6),但在選擇的測(cè)量集合滿足一定條件下,(XTX)-1的時(shí)間復(fù)雜度可以降為O(d4).第1)環(huán)節(jié)最后1步中,通過(guò)估計(jì)出的參數(shù),使用方程(1)重構(gòu)偽線性估計(jì)矩陣的時(shí)間復(fù)雜度是O(d4),原因是集合{Ωi}有d2個(gè)元素,而每個(gè)元素Ωi是d×d矩陣,中的(d2-1)個(gè)數(shù)與{Ωi}(i/=0)相乘.但正如文獻(xiàn)[15]指出的,若使用Pauli算子的張量積作為量子系統(tǒng)劉維爾空間中的一組基,由于每一個(gè)d×d的基矩陣都只有d個(gè)非0元,則使用方程(1)的重構(gòu)過(guò)程的時(shí)間復(fù)雜度可以降低為O(d3).第2)個(gè)環(huán)節(jié)計(jì)算方程(2),使用文獻(xiàn)[15]的算法,在尋找與矩陣最接近的過(guò)程中,需要求解矩陣的本征值和本征態(tài),該步驟的時(shí)間復(fù)雜度通常是O(d3).對(duì)得到的的本征值進(jìn)行排序,常用的經(jīng)典排序算法時(shí)間復(fù)雜度是O(d).在排序之后,使用基本的加法和除法操作,得到矩陣的本征值{λi},該過(guò)程時(shí)間復(fù)雜度是O(d).最后,通過(guò){λi}和的本征態(tài)重構(gòu)出目標(biāo)矩陣,此過(guò)程的時(shí)間復(fù)雜度是O(d3).

總結(jié)整個(gè)過(guò)程,經(jīng)典算法的最大時(shí)間復(fù)雜度出現(xiàn)在對(duì)矩陣(XTX)-1求逆的步驟當(dāng)中,一般為O(d6).選擇合適的測(cè)量集時(shí),可以使該步驟復(fù)雜度降低為O(d4).

下面分析量子算法實(shí)現(xiàn)過(guò)程的時(shí)間復(fù)雜度.

4.2 量子算法各個(gè)環(huán)節(jié)時(shí)間復(fù)雜度分析

4.2.1 量子態(tài)制備的時(shí)間復(fù)雜度

在使用量子算法處理量子態(tài)重構(gòu)過(guò)程的3個(gè)環(huán)節(jié)中，有2個(gè)環(huán)節(jié)涉及使用測(cè)量得到的經(jīng)典數(shù)據(jù)制備量子態(tài): i)準(zhǔn)備階段; ii)在環(huán)節(jié)2)中,測(cè)量得到本征值后,為在后續(xù)使用量子算法進(jìn)行排序,須制備量子態(tài)以存儲(chǔ)本征值.不同制備量子態(tài)的量子算法時(shí)間復(fù)雜度不同.文獻(xiàn)[16]給出了幾種不同量子算法的時(shí)間復(fù)雜度:其 中是向量 x 的最大值與最小值的比率,d是向量維數(shù),ε是要求的精度,c是某個(gè)常數(shù); 2)O (log(d)/ε2);可以觀察到,1)是對(duì)數(shù)的多項(xiàng)式時(shí)間復(fù)雜度; 1),2)和4)是d的對(duì)數(shù)的時(shí)間復(fù)雜度; 3)是精度 1 /ε 的對(duì)數(shù)時(shí)間復(fù)雜度.但還沒(méi)有發(fā)現(xiàn)使,d,1/ε 同時(shí)實(shí)現(xiàn)對(duì)數(shù)時(shí)間復(fù)雜度的量子算法.當(dāng)1/ε=O(polylogd)時(shí),1),2),4)均可以實(shí)現(xiàn) O (polylogd)的時(shí)間復(fù)雜度.但由于1)與4)均與 κ 有關(guān),因此在表1中,選取了 O (log(d)/ε2)作為量子態(tài)制備的時(shí)間復(fù)雜度的代表.

在圖2所示的準(zhǔn)備環(huán)節(jié),可以使用測(cè)量得到的經(jīng)典數(shù)據(jù)制備N個(gè)量子態(tài),后續(xù)可以使用量子算法過(guò)程1以及估計(jì)本征值和本征態(tài)的量子算法,對(duì)這些量子態(tài)并行處理.但是制備多份量子態(tài)會(huì)導(dǎo)致在準(zhǔn)備環(huán)節(jié)以及環(huán)節(jié)2)中的量子態(tài)制備過(guò)程的時(shí)間復(fù)雜度增大.制備N個(gè)量子態(tài)相應(yīng)的時(shí)間復(fù)雜度是 O (Nlog(d)/ε2).若制備的量子態(tài)個(gè)數(shù)N的規(guī)模是 O (d),則相應(yīng)的時(shí)間復(fù)雜度為 O (dlog(d)/ε2).這里假定N的規(guī)模是 O (d),是考慮到對(duì)d維量子系統(tǒng)來(lái)說(shuō),其本征值個(gè)數(shù)不超過(guò)d,在不同本征值之間大小相差不是特別懸殊時(shí)[11],測(cè)量得到這些本征值所需制備的量子態(tài)個(gè)數(shù)是 O (d).當(dāng) 1 /ε 是log(d)的多項(xiàng)式規(guī)模時(shí),量子態(tài)制備過(guò)程的最大時(shí)間復(fù)雜度是 O (dpolylogd).

4.2.2 矩陣乘法量子算法的時(shí)間復(fù)雜度

表1 量子態(tài)重構(gòu)過(guò)程不同環(huán)節(jié)的量子算法與經(jīng)典算法時(shí)間復(fù)雜度的對(duì)比Table 1.Time complexity comparison of each step between quantum algorithm and classical algorithm for reconstructing quantum state.

4.2.3 矩陣求逆量子算法的時(shí)間復(fù)雜度

使用基于奇異值估計(jì)量子算法的矩陣求逆算法,文獻(xiàn)[17]分析了其時(shí)間復(fù)雜度,為O(κ2polylog(d)‖A‖F(xiàn)/ε).對(duì)于求解量子線性系統(tǒng)的算法[12],可以假設(shè)在量子態(tài)層析任務(wù)中,如果選擇正四面體測(cè)量基和正六面體測(cè)量基,可以得到矩陣A是對(duì)角矩陣[4],同樣有成立.因此在量子態(tài)重構(gòu)過(guò)程中,使用基于奇異值估計(jì)量子算法解矩陣求逆過(guò)程的時(shí)間復(fù)雜度是當(dāng)κ和1/ε都是log(d)的多項(xiàng)式規(guī)模時(shí),使用矩陣求逆量子算法的最大時(shí)間復(fù)雜度是

下面解釋為何要在估計(jì)本征值之后引入測(cè)量環(huán)節(jié)以及量子態(tài)制備環(huán)節(jié).通過(guò)量子算法得到矩陣的本征值量子態(tài)、本征態(tài),不同的本征值量子態(tài)、本征態(tài)之間是糾纏的,而后續(xù)的量子排序算法要求輸入全部的本征值量子態(tài).因而需要引入測(cè)量環(huán)節(jié)得到本征值,再將其轉(zhuǎn)化為量子態(tài)數(shù)據(jù).例如,通過(guò)表2的量子算法后,若得到的態(tài)是是存儲(chǔ)了本征值估計(jì)值的量子態(tài),是相應(yīng)的本征態(tài).對(duì)處于寄存器中的本征值估計(jì)值進(jìn)行測(cè)量,當(dāng)測(cè)量結(jié)果是時(shí),態(tài) | Ψ〉 塌縮到上; 測(cè)量結(jié)果是時(shí),| Ψ 〉 塌縮到上.因此,在求解矩陣的本征值和本征態(tài)的量子算法之后,通過(guò)引入測(cè)量環(huán)節(jié)提取出本征值信息并且分別進(jìn)行存儲(chǔ); 為與后續(xù)的排序量子算法銜接,還要將測(cè)量得到的本征值信息制備成量子態(tài),從而貫通整個(gè)使用量子算法處理量子態(tài)層析的過(guò)程.

4.2.5 本征值排序量子算法的時(shí)間復(fù)雜度

4.2.6 量子態(tài)重構(gòu)過(guò)程整體量子算法的時(shí)間復(fù)雜度

總結(jié)上述分析過(guò)程,當(dāng)不考慮實(shí)現(xiàn)的資源代價(jià),而只追求降低整個(gè)過(guò)程的時(shí)間復(fù)雜度時(shí),若相關(guān)矩陣的條件數(shù) κ 及要求的精度 1 /ε 都是log(d)的多項(xiàng)式規(guī)模時(shí),準(zhǔn)備環(huán)節(jié)及環(huán)節(jié)2)中的量子態(tài)制備過(guò)程是整體量子算法中時(shí)間復(fù)雜度最大的過(guò)程,相應(yīng)的時(shí)間復(fù)雜度是 O (Npolylogd).當(dāng)制備的量子態(tài)的個(gè)數(shù)N的復(fù)雜度是 O (d)時(shí),整個(gè)量子算法過(guò)程的時(shí)間復(fù)雜度是 O (dpolylogd).矩陣乘法的量子算法的時(shí)間復(fù)雜度也是 O (dpolylogd).

5 算 例

本節(jié)用一個(gè)算例來(lái)說(shuō)明整體量子算法的可行性.考慮單qubit的量子態(tài)層析,記生成源為 ρ ,此時(shí)系統(tǒng)的維數(shù) d=2 .選取劉維爾空間中的一組基{Ωl}:

其中,l=0,1,2,3;σ0=I2×2,σx,σy,σz分別為Pauli算子.選擇信息完備的正四面體測(cè)量基對(duì)ρ進(jìn)行測(cè)量,得到測(cè)量基在劉維爾空間展開(kāi)系數(shù)構(gòu)成的可逆矩陣X以及不同測(cè)量結(jié)果的頻率構(gòu)成的向量Y:

以下對(duì)照?qǐng)D2—圖4敘述量子算法過(guò)程.

5.1 準(zhǔn)備環(huán)節(jié)

5.2 調(diào)用量子算法過(guò)程1求解中間重構(gòu)矩陣

量子算法過(guò)程1如圖3所示.首先調(diào)用矩陣乘法量子算法由 X ,XT,|Y〉 計(jì) 算出 | XTY〉, XTX.

使用矩陣乘法量子算法[16]計(jì)算矩陣與向量的乘積,輸入態(tài)由矩陣右奇異向量表示,輸出態(tài)由矩陣左奇異向量表示,即可以得到以下輸入態(tài)到輸出態(tài)的變換過(guò)程:

由于 XT的奇異值均為同一量子算法過(guò)程的估計(jì)精度相同,因而矩陣 XT奇異值的估計(jì)值相等.為簡(jiǎn)明表達(dá)計(jì)算過(guò)程,假定估計(jì)值與待估計(jì)值相等,即最終得到

對(duì)于 XTX ,設(shè) X=[X1X2X3],可使用矩陣乘法量子算法同時(shí)求解|XTX1〉,|XTX2〉,|XTX3〉,得到

2)使用矩陣求逆量子算法計(jì)算得到|Θ〉

設(shè)A=XTX,|b〉=|XTY〉,A|Θ〉=|b〉,要得到|Θ〉=|A-1b〉.基于奇異值估計(jì)的量子算法的存儲(chǔ)結(jié)構(gòu)要求存儲(chǔ)的是矩陣列向量元素,以及矩陣行向量的2-范數(shù)[20].由矩陣乘法量子算法計(jì)算得到的|XTX1〉,|XTX2〉,|XTX3〉對(duì)應(yīng)矩陣A的列向量.由于選取的測(cè)量基使得A是對(duì)角矩陣,由對(duì)角矩陣對(duì)稱性可知|XTXi〉中的元素相當(dāng)于矩陣A的行向量中的元素,因而滿足使用奇異值估計(jì)量子算法的存儲(chǔ)結(jié)構(gòu),可以使用|XTXi〉 直接參與后續(xù)量子算法運(yùn)算過(guò)程,而不必經(jīng)過(guò)轉(zhuǎn)置操作.因而

對(duì)方程(13)輸出量子態(tài)的輔助量子比特位進(jìn)行測(cè)量,若結(jié)果為 |0〉 ,則輸出態(tài)塌縮到所需的矩陣求逆結(jié)果:

其中,γA=O(1/κ),κ 是矩陣A的條件數(shù).A是正定厄米矩陣,對(duì)A進(jìn)行奇異值分解,可以得到A的奇異值進(jìn)而得到相應(yīng)的本征值tXT/2,因而

記

以方程(16)得到的結(jié)果為輸入態(tài),調(diào)用矩陣乘法量子算法,可以得到如下變換:

5.3 計(jì)算目標(biāo)重構(gòu)矩陣

設(shè)方程(24)中

可以計(jì)算得到

將方程(9),(14),(25)及(28)的表示代入到方程(34),并去掉因子即得到最終的使用輸入數(shù)據(jù)Y=[y1y2y3y4]T表示的重構(gòu)矩陣:

其中

6 結(jié) 論

本文深入探討了處理量子態(tài)重構(gòu)的整體量子算法.通過(guò)在重構(gòu)過(guò)程的不同步驟使用相應(yīng)的量子算法,得到了實(shí)現(xiàn)量子態(tài)重構(gòu)的整體量子算法新方案.對(duì)比分析表明: 對(duì)于d維密度矩陣,經(jīng)典算法的最大時(shí)間復(fù)雜度出現(xiàn)在矩陣乘法過(guò)程中,為O(d4); 而對(duì)于量子算法,在精度 ε 和矩陣的條件數(shù)κ等指標(biāo)滿足使用量子算法進(jìn)行加速的條件下,即1/ε, κ 的復(fù)雜度均為 O (polylogd)時(shí),量子算法的最大時(shí)間復(fù)雜度出現(xiàn)在量子態(tài)制備過(guò)程中,為O(Npolylogd),其中N為制備量子態(tài)的數(shù)目.當(dāng)制備的量子態(tài)數(shù)N的規(guī)模是 O (d),即可得到中間重構(gòu)矩陣所有的本征值時(shí),量子算法的時(shí)間復(fù)雜度為 O (dpolylogd).

通俗地說(shuō),本文主要試圖回答如下問(wèn)題: 如果量子計(jì)算機(jī)可物理實(shí)現(xiàn)且量子算法可以在量子計(jì)算機(jī)上物理實(shí)現(xiàn),那么量子算法在多大程度上可以降低量子態(tài)層析的時(shí)間復(fù)雜度? 研究表明,如果量子態(tài)可以高效制備,那么采用量子算法可將量子態(tài)層析整體算法的時(shí)間復(fù)雜度從 O (d4)降為O(dpolylogd); 如果量子態(tài)無(wú)法高效制備,量子態(tài)層析整體算法的時(shí)間復(fù)雜度從 O (d4)降 為 O (d3).因?yàn)閷?duì)于量子態(tài)制備問(wèn)題，制備維數(shù)為d2、規(guī)模為O(d)的量子態(tài)，時(shí)間復(fù)雜度是 O(d3).因此本研究從一個(gè)側(cè)面證明了量子態(tài)能否高效制備已成為量子算法降低時(shí)間復(fù)雜度的瓶頸。

最后簡(jiǎn)要探討本文所提方案的物理實(shí)現(xiàn)可行性.文獻(xiàn)[20]的作者討論了奇異值估計(jì)量子算法能夠?qū)崿F(xiàn)的前提是構(gòu)造出一種合適的存儲(chǔ)經(jīng)典數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),并在文章最后給出了具體的構(gòu)造形式,因而是能夠物理實(shí)現(xiàn)的.由于方案涉及的矩陣乘法、矩陣求逆以及本征值和本征態(tài)估計(jì)的量子算法均是基于奇異值估計(jì)的量子算法,因而理論上是可以物理實(shí)現(xiàn)的.方案涉及到的其他過(guò)程,即量子態(tài)制備、測(cè)量以及量子排序,是理論上能夠?qū)崿F(xiàn)或已經(jīng)實(shí)現(xiàn)的[14,19,21].因此總體來(lái)說(shuō),本文所提方案具有物理實(shí)現(xiàn)的可行性.

若A為正定厄米方陣,矩陣的奇異值分解也就是矩陣的本征分解,矩陣A的奇異向量 | vi〉 與 其本征向量 | μi〉 相等.若A為非正定厄米方陣,將矩陣A分別用本征分解和奇異值分解來(lái)表示,有

表A1 求解厄米矩陣本征值和本征態(tài)的量子算法[17]Table A1.Quantum algorithm for calculating the eigenvalues and eigenstates of Hermite matrix[17].