林小蝶，魏朝暉

(1. 清華大學(xué)交叉信息研究院 北京 海淀區(qū) 100084；2. 清華大學(xué)丘成桐數(shù)學(xué)科學(xué)中心 北京 海淀區(qū) 100084；3. 北京雁棲湖應(yīng)用數(shù)學(xué)研究院 北京 海淀區(qū) 100084)

在信息處理任務(wù)中，分隔各地的不同參與方常常需要協(xié)同完成計(jì)算任務(wù)。在這一過程中，多方之間共享計(jì)算資源往往是不可或缺的，如隨機(jī)變量或量子糾纏，其中前者也被稱作經(jīng)典關(guān)聯(lián)(classical correlation)。因此，如何高效地制備這些共享計(jì)算資源是一個(gè)重要問題。本文將介紹近期在經(jīng)典關(guān)聯(lián)生成這一任務(wù)上的一系列進(jìn)展。經(jīng)典關(guān)聯(lián)生成問題主要研究的是：為了生成一個(gè)目標(biāo)共享經(jīng)典關(guān)聯(lián)，最少需要涉及多少數(shù)量的初始共享隨機(jī)性或者量子糾纏？本文主要討論兩方參與的情形，并將介紹經(jīng)典場景、量子場景以及量子、經(jīng)典混合場景下的經(jīng)典關(guān)聯(lián)生成協(xié)議[1-3]。

考慮這樣一個(gè)具體的場景：分隔兩地的Alice和Bob 二人想要從目標(biāo)經(jīng)典關(guān)聯(lián)P=(X,Y)中進(jìn)行采樣，即二人各自輸出隨機(jī)變量X和Y，使得 (X,Y)的聯(lián)合概率分布與P完全一致。那么，對(duì)于一個(gè)任意的經(jīng)典關(guān)聯(lián)P，如何刻畫生成其所需要的最小代價(jià)？

關(guān)聯(lián)復(fù)雜度(correlation complexity)和通訊復(fù)雜度(communication complexity)是與此相關(guān)的兩個(gè)量。對(duì)于兩體的共享經(jīng)典隨機(jī)變量P′=(X′,Y′)，可將其大小 size(P′)定義為(「log2X?+「log2Y?)/2，其中 X 和 Y 分別是隨機(jī)變量X′和Y′采樣集合的大??；對(duì)于兩體的量子態(tài)σ∈HA?HB，其大小size(σ)則定義為 ( 「log2DA?+「log2DB?)/2，其中DA和DB分別對(duì)應(yīng)希爾伯特空間(Hilbert space) HA和 HB的維度。對(duì)于經(jīng)典關(guān)聯(lián)生成問題，Alice 和Bob 可以共享一個(gè)關(guān)聯(lián)種子P′=(X′,Y′)，并且每個(gè)人都可以在自己的系統(tǒng)上進(jìn)行本地操作(local operation, LO)以最終生成目標(biāo)經(jīng)典關(guān)聯(lián)P。 稱P的隨機(jī)關(guān)聯(lián)復(fù)雜度(randomized correlation complexity)為 最 小 的 size(P′)，記 作R(P) 。 若Alice 和Bob 共享的是量子態(tài) σ，并且他們通過在自己的系統(tǒng)上進(jìn)行本地量子操作，最終通過量子測量成功生成目標(biāo)經(jīng)典關(guān)聯(lián)P。那么稱P的量子關(guān)聯(lián)復(fù)雜度(quantum correlation complexity)為最小的s ize(σ)， 記作Q(P)。

除了共享關(guān)聯(lián)種子以外，Alice 和Bob 還可以利用通訊的方式來生成目標(biāo)經(jīng)典關(guān)聯(lián)P。在協(xié)議的一開始，Alice 和Bob 并不共享任何資源，而是在協(xié)議的執(zhí)行過程中通過進(jìn)行相互間的通訊，最終協(xié)同生成目標(biāo)經(jīng)典關(guān)聯(lián)P。若Alice 和Bob 進(jìn)行的是經(jīng)典通訊，則稱P的隨機(jī)通訊復(fù)雜度(randomized communication complexity)為二者交換的最少比特?cái)?shù)，記作 RComm(P)；若Alice 和Bob 進(jìn)行的是量子通訊，則稱P的量子通訊復(fù)雜度(quantum communication complexity)為二者交換的最少量子比特?cái)?shù)，記作 QComm(P)。有研究結(jié)果證明，對(duì)于任意的量子態(tài)ρ，其量子關(guān)聯(lián)復(fù)雜度和量子通訊復(fù)雜度總是相等的，也即Q(P)=QComm(P)且R(P)=RComm(P)[1]。因此，下文將直接使用R和Q的記號(hào)，不對(duì)關(guān)聯(lián)復(fù)雜度和通訊復(fù)雜度進(jìn)行嚴(yán)格的區(qū)分。

1 預(yù)備知識(shí)

作用在希爾伯特空間 H 上的量子態(tài) ρ是跡(trace)為1 的半正定算子。若該算子秩為1，則其為純態(tài)，可寫作 ρ=|ψ〉〈ψ|， 其中 |ψ〉是模為1 的向量。對(duì)于量子態(tài) ρ ∈HA， |ψ〉∈HA?HB， 若有trHB(|ψ〉〈ψ|)=ρ， 則稱 |ψ〉是 ρ的一個(gè)純化(purification)。其中， trHB代表在 HB空間上的部分跡(partial trace)。對(duì)任意的量子態(tài)而言，總可以對(duì)其進(jìn)行純化操作。

2 經(jīng)典場景

這里最后的概率是基于rA還 是基于rB取決于最后一輪由誰通訊。此外，由于給定信息m后，Alice 和Bob 的輸出是相互獨(dú)立的，條件概率為：

給定m， 第一個(gè)括號(hào)中的乘積項(xiàng)只與x有關(guān)，第二個(gè)括號(hào)中的乘積項(xiàng)只與y有關(guān)，因此每一個(gè)求和項(xiàng)對(duì)應(yīng)一個(gè)秩為1 的矩陣。此外，由于矩陣中的元素對(duì)應(yīng)概率的乘積，因此該矩陣為非負(fù)矩陣。換句話說，可以將P分 解為 2c項(xiàng)秩為1 的非負(fù)矩陣之和，c為傳輸?shù)目偙忍財(cái)?shù)。 由此得證，「log2rank+(P)?≤RComm(P)。

3 量子場景

3.1 量子關(guān)聯(lián)復(fù)雜度Q(P)

顯而易見，S?rank(|ψ〉)≤r， 并可驗(yàn)證 |ψ〉 是ρ 的一個(gè)純化。因此，Alice 和Bob 可以在計(jì)算基下測量各自的第一部分系統(tǒng)，并拋棄后面兩部分的系統(tǒng)，最終生成P。

此外，對(duì)于Q(P)的下界，上面的引理意味著：存在 ρ的 純化 |ψ〉滿 足S?rank(|ψ〉)=r且 Q(P)=r。因此，只要證明r≥rankpsd(P)，即可完成論證。令：

3.2 隨機(jī)、量子關(guān)聯(lián)復(fù)雜度 R(P) 與Q (P)的對(duì)比

由于量子可模擬經(jīng)典行為，有Q(P)≤R(P)。此外，Alice 和Bob 可直接共享經(jīng)典關(guān)聯(lián)P，從而平凡地生成P。因此，對(duì)于P的關(guān)聯(lián)復(fù)雜度有如下這一簡單關(guān)系：

那么一個(gè)自然的問題就是，Q(P)與R(P)之間的差距有多大？根據(jù)前文介紹的結(jié)果，這一問題等價(jià)于 刻 畫 非負(fù) 矩陣P的 rankpsd(P)和 rank+(P)之 間 的 差距。以下展示兩個(gè)極具代表性的例子。

4 量子、經(jīng)典混合場景

在純經(jīng)典、量子的場景對(duì)比中，量子展示了極大的優(yōu)勢。但從目前的實(shí)驗(yàn)水平看來，距離實(shí)現(xiàn)大規(guī)模的量子計(jì)算這一目標(biāo)，仍有相當(dāng)長的路要走[12-13]。對(duì)于近期可實(shí)現(xiàn)的量子設(shè)備，其能操作的量子系統(tǒng)規(guī)模有限，通常為幾十個(gè)量子比特。因此，對(duì)于需要更多量子比特才能完成的任務(wù)而言，一個(gè)亟待解決的問題就是：如何在可操作的量子資源有限的情況下，既能充分利用現(xiàn)有的量子資源，又能順利完成任務(wù)？

在量子、經(jīng)典混合場景中，主要考慮先進(jìn)行經(jīng)典操作，后根據(jù)經(jīng)典結(jié)果給定量子態(tài)的經(jīng)典?量子混合協(xié)議；以及先給定固定的量子態(tài)(與經(jīng)典信息無關(guān))，而后才進(jìn)行經(jīng)典操作的量子?經(jīng)典混合協(xié)議。

4.1 經(jīng)典?量子混合協(xié)議

4.2 量子?經(jīng)典混合協(xié)議

在經(jīng)典?量子混合協(xié)議中，Alice 和Bob 擁有在看到經(jīng)典采樣i后再對(duì)應(yīng)選擇共享量子態(tài) ρi的自由度，即他們可以隨意要求不同的初始共享量子態(tài)ρi。但在某些時(shí)候，這一自由度仍是不易實(shí)現(xiàn)的。因此，這里考慮一個(gè)更為嚴(yán)格的場景，即Alice 和Bob 只能在協(xié)議一開始獲得一個(gè)固定的量子態(tài)，該量子態(tài)與經(jīng)典信息無關(guān)，而后二人才能進(jìn)行經(jīng)典操作，或在該量子態(tài)上進(jìn)行本地操作以達(dá)成目的。在這一限制之下，前文提出的經(jīng)典?量子混合協(xié)議就自然失效了。同樣限制Alice 和Bob 具有的量子能力為s。由于這里是先有的量子態(tài)，而后才介入經(jīng)典操作，故考慮量子?經(jīng)典混合協(xié)議來處理這一經(jīng)典關(guān)聯(lián)生成問題。

為了解決該問題，文獻(xiàn)[3]將共享的量子態(tài)設(shè)定為純態(tài)。對(duì)于任意的關(guān)聯(lián)，若其能被Cd?Cd上的混態(tài)生成，那么一定存在Cd?Cd上的純態(tài)同樣可以生成這一關(guān)聯(lián)[15]。因此，共享量子態(tài)為純態(tài)這一假定依然發(fā)揮了量子能力范圍內(nèi)該有的作用。

5 結(jié) 束 語

隨著量子計(jì)算和量子信息的興起，越來越多的研究工作聚焦于對(duì)比量子資源和經(jīng)典資源在計(jì)算能力上的差距[17-20]。本文從經(jīng)典關(guān)聯(lián)生成問題入手，首先介紹了完成該任務(wù)的經(jīng)典協(xié)議和量子協(xié)議的完整數(shù)學(xué)刻畫。通過將經(jīng)典協(xié)議所需的經(jīng)典資源與非負(fù)秩建立聯(lián)系，并將量子協(xié)議所需的量子資源與半正定秩對(duì)標(biāo)，把該問題轉(zhuǎn)化為對(duì)比非負(fù)矩陣的非負(fù)秩與半正定秩的問題。在此基礎(chǔ)之上，本文介紹了兩個(gè)區(qū)分量子和經(jīng)典資源計(jì)算能力的例子，其中，事先共享量子糾纏甚至能比事先共享隨機(jī)性有指數(shù)級(jí)的優(yōu)勢。

此外，針對(duì)近期量子設(shè)備規(guī)模，本文還介紹了量子、經(jīng)典混合場景下的經(jīng)典關(guān)聯(lián)生成問題。根據(jù)在協(xié)議中提供初始共享量子態(tài)的時(shí)間點(diǎn)，分別討論了經(jīng)典?量子混合協(xié)議和量子?經(jīng)典混合協(xié)議。與純經(jīng)典協(xié)議和純量子協(xié)議類似，在量子、經(jīng)典混合場景下，其所需的經(jīng)典比特?cái)?shù)與k區(qū)塊半正定秩相關(guān)。在這一量子、經(jīng)典混合場景中，仍然可以看到量子相對(duì)經(jīng)典的優(yōu)勢。因此，經(jīng)典關(guān)聯(lián)生成問題是對(duì)比量子資源和經(jīng)典資源之間計(jì)算能力的一個(gè)極佳視角。

總體而言，經(jīng)典關(guān)聯(lián)生成問題中蘊(yùn)含著豐富的數(shù)學(xué)結(jié)構(gòu)。并且由于其與半正定秩的性質(zhì)密切相關(guān)，而半正定秩的研究尚處于初期階段，因此該問題仍有極大的探討空間，希望后續(xù)能有更豐富的研究結(jié)果誕生。