量子非局域性與量子通信復(fù)雜度研究

張弘弛,劉百祥,,,文 捷,,

(1.復(fù)旦大學(xué)a.計算機科學(xué)技術(shù)學(xué)院 上海市智能信息處理重點實驗室; b.校園信息化辦公室,上海 200433;2.復(fù)旦-眾安區(qū)塊鏈與信息安全聯(lián)合實驗室,上海 200433)

0 概述

量子計算的優(yōu)勢在于大幅縮短所需信息的時間,比如文獻[1-2]提出Shor因數(shù)分解算法和Deutsch算法。但量子通信[3-4]仍存在較多問題,例如同時消息傳遞(Simultaneous Message Passing,SMP)模型下的k等價性問題(k-equality problem),此問題可描述為:有k個團體,每個團體都有一個串,表示為x1,x2,…,xk,他們之間不能直接通信,而是通過傳遞消息給第k+1個團體,讓第k+1個團體判定k個人手上的串是否相等。此問題是SMP模型的基本問題,對問題難易度的刻畫是量子通信復(fù)雜度[5],表示在計算過程中傳輸?shù)牧孔颖忍?quantum bit)數(shù)目。量子非局域性和量子通信復(fù)雜度可以建立一種量子通信方法,兩者對復(fù)雜度的刻畫不同。

量子非局域性是在空間上相互分離的糾纏態(tài)粒子能夠相互告知各自狀態(tài)。若允許參與團體持有糾纏態(tài)的量子比特(entanglement quantum bit),則在物理上測量量子的可觀測量時會引起另一個糾纏粒子的狀態(tài)發(fā)生改變,進而完成任務(wù)。在此基礎(chǔ)上,國內(nèi)外學(xué)者提出諸多應(yīng)用場景,如文獻[6]提出GHZ問題場景。

在量子通信復(fù)雜度方面,參與團體傳遞量子位(qubit)告訴對方信息,進而完成通信。文獻[7]提出分布式Deutsch-Jozsa算法,解決等價性問題(Equality Problem,EQ),與經(jīng)典通信相比,量子通信有較高的效率。

本文闡述量子通信近年來的主要研究成果,列舉量子非局域性和量子通信經(jīng)典問題,并給出解決辦法,研究量子通信復(fù)雜度與量子的非局域性之間的關(guān)聯(lián)關(guān)系。通過將量子通信中的分布式Deutsch-Jozsa算法轉(zhuǎn)化為量子非局域性上的算法,以解決通信協(xié)議問題轉(zhuǎn)換為量子非局域性的問題。

1 量子非局域性

局域性原則描述為:如果2個系統(tǒng)之間不存在因果關(guān)系,那么對其中一個系統(tǒng)測量得到的結(jié)果,不可能影響對第2個系統(tǒng)的測量。但若對分離的糾纏態(tài)粒子中的一個進行測量,則另一個粒子必然會產(chǎn)生對應(yīng)的結(jié)果。根據(jù)文獻[8],自旋態(tài)粒子|ψ〉可表示為:

(1)

假設(shè)存在3個空間分離的參與者A、B、C。每個人接收輸入s、t、u,對應(yīng)輸出a、b、c,輸入滿足s⊕t⊕u=0(⊕代表異或),參與者接收到信息后不可互相交流。參與者的目標(biāo)共同計算如下:

(2)

經(jīng)典方法不存在完美的策略使輸出滿足式(2),每個人只能根據(jù)接收到的信息進行輸出。假設(shè)每個人對于輸入0輸出a0、b0、c0,對于輸入1輸出a1、b1、c1,則有:

(3)

從式(3)可以看出,4個等式不能同時成立,但其中3個可以同時滿足。因此,利用隨機策略,開始時3個參與者協(xié)商確定隨機串r,根據(jù)串確定4個等式中哪3個成立,分離后按策略計算,則該隨機策略正確率是3/4。隨機策略成功的概率表示為:

(4)

其中,qr為隨機串r被選中的概率,不等式右側(cè)為該策略下式(3)回答正確的概率,且在經(jīng)典情況下正確概率至多為3/4。

根據(jù)量子非局域性特征,存在可以產(chǎn)生正確結(jié)論的策略。假設(shè)3個參與者各持有一個糾纏態(tài)粒子,該粒子是3個量子位的合并態(tài):

(5)

在該策略中,3個人可以對糾纏態(tài)比特進行操作。即用幺正變換來改變粒子狀態(tài),一個幺正算子即一個幺正矩陣,行和列為正交歸一的。則2×2的幺正矩陣可表示為:

(6)

引入Hadamard算子H和單位算子I。為別為:

(7)

(8)

當(dāng)輸入1時,作用Hadamard算子,輸入0時,作用I。當(dāng)輸入stu=011時,則有:

(9)

2 量子通信復(fù)雜度

通信的2個團體可以通過比特或者量子比特傳遞信息。在經(jīng)典通信框架中[9],假設(shè)2個團體A、B,需要計算函數(shù)f:D→{0,1},其中D?X×Y。在通常情況下,X=Y={0,1}n,A、B分別獲得n比特輸入串x、y。因為函數(shù)基于x、y,所以A、B進行通信合力計算f(x,y)。在協(xié)議算法中,A、B分別獨立計算,相互發(fā)送消息給對方,每一條消息稱為一輪,幾輪過后輸出結(jié)果。

經(jīng)典情況主要研究等價性問題,判斷2個人手上的信息是否一致:

(10)

文獻[5]將通信復(fù)雜度擴展到量子計算領(lǐng)域,狀態(tài)由A的私有狀態(tài)、信道狀態(tài)和B的私有狀態(tài)3部分構(gòu)成。因此,初始狀態(tài)表述為|x〉|0〉|y〉。當(dāng)A獲得輸入x后,用幺正算子對私有狀態(tài)和信道進行操作,A對自己的信息計算的同時把消息放入信道,B用幺正算子操作信道和私有狀態(tài)進行接收和計算。文獻[10]通信過程中一個量子比特可以被非局域性特征中一個糾纏態(tài)比特加2個經(jīng)典比特替換,且提出問題:在不共享糾纏情況下,量子通信協(xié)議是否與非局域性特征等價。

文獻[11]提到算法協(xié)議是文獻[2]中經(jīng)典Deutsch-Jozsa算法的分布式版本。

經(jīng)典Deutsch-Jozsa算法可解決問題[12]:對于函數(shù)f:{0,1}n→{0,1},其輸出是否為常量,或輸出中0和1有相同的個數(shù)。Deutsch-Jozsa算法線路模型如圖1所示。

圖1 Deutsch-Jozsa算法線路模型

圖中Uf為向后傳播算子:

Uf|x〉|y〉=|x〉|y⊕f(x)〉

(11)

(12)

其中,Uf將函數(shù)值傳遞到相位上。

(13)

其中,x·y=xn-1yn-1⊕…⊕x0y0。

Deutsch-Jozsa算法線路模型把(H?n?I)Uf(H?n?H)作用在|00 … 0〉|1〉后產(chǎn)生輸出:

(14)

因為((-1)f(x)+x·y)2=(-1)2f(x)=1,所以測量必定得到狀態(tài)|00 … 0〉,如果f為常數(shù),該狀態(tài)的概率為1。若函數(shù)f對應(yīng)一半輸入輸出為0,另一半輸入輸出為1,則觀測到狀態(tài)|00 … 0〉概率為0。

該算法的分布式通信版本可以要求其滿足x=y,或x、y恰好在n/2個位上不相同,則存在一個簡單的量子協(xié)議使用lbn個量子位解決問題。具體描述如下:

2)B作用相位算子|i〉→(-1)yi|i〉,再作用H?lb n。

3)如果測量給出|0lb n〉,則B輸出1,其他情況B輸出0。

根據(jù)經(jīng)典Deutsch-Jozsa算法,B測量后的狀態(tài)為:

(15)

從式(15)可以看出,如果x=y,則觀測到|0lb n〉,如果x、y恰好在n/2個位上不相同時,則是其他結(jié)果。

在經(jīng)典情況下,文獻[10]通過組合[13]分析證明在該問題中每一個沒有誤差的協(xié)議至少要傳送0.007n比特數(shù),量子通信在該方面有較大改進。若允許有小概率誤差,經(jīng)典情況可以做到傳輸O(lbn)比特數(shù)達到誤差限。

3 非局域性和通信復(fù)雜度的關(guān)聯(lián)

4)對A、B分別進行測量。

當(dāng)x=y,結(jié)果為1/n,其他情況a≠b的概率為0,即a=b。當(dāng)x、y在n/2個位上不相同時,結(jié)果為0,必有a≠b。因此,A只要把結(jié)果a送給B,B就可以算出結(jié)果,該過程中傳送的量子位為lbn比特數(shù)。

3.1 單向量子通信復(fù)雜度和非局域性問題的映射

單向量子通信復(fù)雜度問題可以全部映射到非局域性問題[14]。存在A、B2個團體,從A到B在單向量子通信中交換的量子比特數(shù)q小于其經(jīng)典模型的比特數(shù)c。在通信過程中,假設(shè)A從狀態(tài)|k〉開始,A先作用變換UA(x)在私有態(tài)和信道上,其中,UA(x)變換只與A的輸入x相關(guān)。B獲得信道上的信息,變換UB(y)在私有態(tài)上,然后對其進行測量,得到結(jié)果為l的概率為:

|〈l|UB(y)UA(x)|k〉|2

(16)

根據(jù)l、k、y值確定方程f(x,y)的值。對于量子非局域性,A和B共享一個糾纏態(tài):

(17)

A作用一個局域變換UA(x)T,測量其狀態(tài),B作用一個局域變換UB(y),測量其狀態(tài)。若A測出狀態(tài)l,B測出狀態(tài)k,那么對應(yīng)x,y觀測到l,k的概率為:

P(k,l|x,y)= |〈l|UB(y)UA(x)T|k〉|2=

2-q|〈l|UB(y)UA(x)|k〉|2

(18)

如果A將測量結(jié)果k送給B,則B可以計算出f(x,y)。

3.2 多團體量子通信復(fù)雜度與非局域性

單向量子通信復(fù)雜度問題映射到非局域性問題條件比較苛刻,2個團體參加且必須只進行一輪通信。文獻[15]在使用共享隨機變量的情況下,將通信復(fù)雜度和非局域性關(guān)聯(lián)擴到多團體量子通信,描述了多團體與2團體通信的不同,兩者不完全相同,但只相差一個系數(shù)。共享隨機變量使兩者之間的通信不再依靠經(jīng)典信道通信,只需將糾纏態(tài)通過操作到目標(biāo)態(tài)。

現(xiàn)假設(shè)有k個團體,A1,A2,…,Ak。在非局域情況下,他們共享一個糾纏態(tài),初始為σ,每位用算子操作使初始態(tài)達到計算目標(biāo)ρ。定義量子非局域性復(fù)雜度QNonl(ρ)為所有可達成計算目標(biāo)ρ中長度最短的σ。在量子通信情況下,可定義QComm(ρ)為k個團體之間交換的量子位數(shù)目,關(guān)系如下:

文獻[16]在兩人通信情況下一個復(fù)雜度為Q-qubit的量子通信協(xié)議可以轉(zhuǎn)換為一個不使用本地存儲的Q2+2Q-qubit的量子通信協(xié)議。轉(zhuǎn)換過程中的主要思路是將一輪Q-qubit通信轉(zhuǎn)換為一個Q輪的1-qubit通信。通過非局域性與通信協(xié)議在沒有本地存儲的情況下的等價性,給出問題在非局域性與通信協(xié)議下的等價性。結(jié)論表明,若一個不使用本地存儲通信協(xié)議通過Q-qubit成功計算函數(shù)f的概率p≥1/2+ε,ε>0,則可以在非局域模型下使用O(Q2)個經(jīng)典比特以概率p≥1/2+(1-2-Q)2Qε成功計算函數(shù)f。因此,一個需要Q-qubit的通信協(xié)議,在非局域性模型下可能需要O(Q4)經(jīng)典比特通信。

此轉(zhuǎn)換過程說明針對函數(shù)f(x,y),如果一個量子協(xié)議比經(jīng)典協(xié)議能用更低的復(fù)雜度解決,則貝爾不等式不能完全滿足,相應(yīng)的量子通信復(fù)雜度和非局域性復(fù)雜度等價。

量子非局域性和量子通信協(xié)議在特定情況下等價,例如共享隨機變量情況下的多人通信,以及任何情況下的2人通信。等價有2個優(yōu)點:1)給將來量子通信的基礎(chǔ)構(gòu)建指明方向,量子通信復(fù)雜度和非局域性構(gòu)建的通信方案,其復(fù)雜度差別不大;2)給今后量子通信復(fù)雜度提供研究方法。但在一些情況下的等價性仍未知,例如SMP模型。

4 SMP模型

除了相互通信外,研究者會關(guān)注將消息發(fā)給第三方。此模型有一個裁判作為第三方,A和B同時獲得n比特輸入,他們需要各自發(fā)送一輪消息ma和mb給第三方裁判,然后第三方裁判基于消息ma和mb計算出f(x,y),該模型稱為SMP模型或裁判模型[17]。

針對等價性問題,近似最優(yōu)經(jīng)典協(xié)議算法思想如下:

(19)

則有:

(20)

當(dāng)x=y時,px(i)=py(i),必為1。當(dāng)x≠y,最多有n-1個點相同,其概率不超過1/3。其中,|Fx〉由2lbm=2 lbn+O(1)個量子比特組成,需要發(fā)送的信息量為O(lb 2n),比經(jīng)典通信效率高。

5 結(jié)束語

本文描述了目前量子通信的主要研究成果,闡述并驗證了量子非局域性問題和量子通信復(fù)雜度問題之間的關(guān)聯(lián)關(guān)系。分析結(jié)果表明,量子非局域性問題與量子通信復(fù)雜度問題可以轉(zhuǎn)換,量子通信復(fù)雜度相近,且量子通信比經(jīng)典通信效率高。同時研究了SMP模型,與經(jīng)典通信相比,該模型效率較高。但量子通信相應(yīng)的量子計算模型還沒有定論,這將是下一步的研究方向。