基于量子算法的量子態(tài)層析新方案*

楊樂 李凱 戴宏毅 張明?

1)(國防科技大學,智能科學學院,長沙 410073)

2)(國防科技大學,文理學院物理系,長沙 410073)

3)(國防科技大學,量子信息交叉中心,長沙 410073)

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 整體量子算法簡明過程Fig.2.Concise process of the whole quantum algorithm.

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

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

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

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

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

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

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

此算法是基于矩陣求逆量子算法的部分過程實現(xiàn)的,相比于矩陣求逆量子算法,由于沒有引入輔助量子比特并進行測量,所以該量子算法的時間復雜度為

3.4 量子排序算法

圖4 量子算法過程2Fig.4.Quantum algorithm process 2.

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

4 經(jīng)典和量子求解思路的時間復雜度對比

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

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

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

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

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

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

4.2 量子算法各個環(huán)節(jié)時間復雜度分析

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

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

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

4.2.2 矩陣乘法量子算法的時間復雜度

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

4.2.3 矩陣求逆量子算法的時間復雜度

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

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

4.2.5 本征值排序量子算法的時間復雜度

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

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

5 算 例

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

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

以下對照圖2—圖4敘述量子算法過程.

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

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

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

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

由于 XT的奇異值均為同一量子算法過程的估計精度相同,因而矩陣 XT奇異值的估計值相等.為簡明表達計算過程,假定估計值與待估計值相等,即最終得到

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

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

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

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

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

記

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

5.3 計算目標重構(gòu)矩陣

設方程(24)中

可以計算得到

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

其中

6 結(jié) 論

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

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

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

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

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