量子非局域性與量子通信復雜度研究

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

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

0 概述

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

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

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

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

1 量子非局域性

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

(1)

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

(2)

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

(3)

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

(4)

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

根據量子非局域性特征,存在可以產生正確結論的策略。假設3個參與者各持有一個糾纏態粒子,該粒子是3個量子位的合并態:

(5)

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

(6)

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

(7)

(8)

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

(9)

2 量子通信復雜度

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

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

(10)

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

文獻[11]提到算法協議是文獻[2]中經典Deutsch-Jozsa算法的分布式版本。

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

圖1 Deutsch-Jozsa算法線路模型

圖中Uf為向后傳播算子:

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

(11)

(12)

其中,Uf將函數值傳遞到相位上。

(13)

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

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

(14)

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

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

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

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

根據經典Deutsch-Jozsa算法,B測量后的狀態為:

(15)

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

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

3 非局域性和通信復雜度的關聯

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

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

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

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

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

(16)

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

(17)

A作用一個局域變換UA(x)T,測量其狀態,B作用一個局域變換UB(y),測量其狀態。若A測出狀態l,B測出狀態k,那么對應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將測量結果k送給B,則B可以計算出f(x,y)。

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

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

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

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

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

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

4 SMP模型

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

針對等價性問題,近似最優經典協議算法思想如下:

(19)

則有:

(20)

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

5 結束語

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