亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2019-01-02 05:26:38張弘弛劉百祥
        計算機工程 2018年12期
        關(guān)鍵詞:局域通信協(xié)議復雜度

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

        (1.復旦大學a.計算機科學技術(shù)學院 上海市智能信息處理重點實驗室; b.校園信息化辦公室,上海 200433;2.復旦-眾安區(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模型的基本問題,對問題難易度的刻畫是量子通信復雜度[5],表示在計算過程中傳輸?shù)牧孔颖忍?quantum bit)數(shù)目。量子非局域性和量子通信復雜度可以建立一種量子通信方法,兩者對復雜度的刻畫不同。

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

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

        本文闡述量子通信近年來的主要研究成果,列舉量子非局域性和量子通信經(jīng)典問題,并給出解決辦法,研究量子通信復雜度與量子的非局域性之間的關(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(⊕代表異或),參與者接收到信息后不可互相交流。參與者的目標共同計算如下:

        (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)

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

        (9)

        2 量子通信復雜度

        通信的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]將通信復雜度擴展到量子計算領(lǐng)域,狀態(tài)由A的私有狀態(tài)、信道狀態(tài)和B的私有狀態(tài)3部分構(gòu)成。因此,初始狀態(tài)表述為|x〉|0〉|y〉。當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 非局域性和通信復雜度的關(guān)聯(lián)

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

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

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

        單向量子通信復雜度問題可以全部映射到非局域性問題[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 多團體量子通信復雜度與非局域性

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

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

        文獻[16]在兩人通信情況下一個復雜度為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é)議能用更低的復雜度解決,則貝爾不等式不能完全滿足,相應(yīng)的量子通信復雜度和非局域性復雜度等價。

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

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

        5 結(jié)束語

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

        猜你喜歡
        局域通信協(xié)議復雜度
        一種低復雜度的慣性/GNSS矢量深組合方法
        局域積分散列最近鄰查找算法
        電子測試(2018年18期)2018-11-14 02:30:34
        基于Z-Stack通信協(xié)議棧的紅外地溫采集電路設(shè)計
        求圖上廣探樹的時間復雜度
        基于DMX512通信協(xié)議的多路轉(zhuǎn)發(fā)器設(shè)計與研究
        基于NS-3的PLC多頻通信協(xié)議仿真平臺設(shè)計與實現(xiàn)
        電測與儀表(2016年2期)2016-04-12 00:24:52
        某雷達導51 頭中心控制軟件圈復雜度分析與改進
        PET成像的高分辨率快速局域重建算法的建立
        基于局域波法和LSSVM的短期負荷預測
        電測與儀表(2015年7期)2015-04-09 11:39:50
        出口技術(shù)復雜度研究回顧與評述
        国产精品美女自在线观看| 人妻无码一区二区19P| 成人亚洲欧美久久久久| 黄 色 成 年 人 网 站免费| 亚洲精彩视频一区二区| 亚洲福利视频一区二区三区 | 久久国产精品免费专区| 女人被躁到高潮嗷嗷叫免费软| 国产精品一区二区久久精品蜜臀 | 窝窝午夜看片| 久久精品国产www456c0m| 国产精品99久久久久久宅男| 亚洲男人的天堂网站| 亚洲偷自拍另类图片二区| 青青青国产免A在线观看| 女同中文字幕在线观看| 久久午夜精品人妻一区二区三区| 亚洲日韩激情无码一区| 伊人久久大香线蕉亚洲五月天 | 加勒比东京热中文字幕| 日本熟妇美熟bbw| 真多人做人爱视频高清免费| 4444亚洲人成无码网在线观看| 妺妺窝人体色www在线直播| 国内精品九九久久精品小草| 日本人妻精品有码字幕| 伊人久久大香线蕉av不变影院| 日韩精品无码一本二本三本色| 日韩亚洲av无码一区二区三区| 国产成人无码aⅴ片在线观看| 成人无码视频在线观看网站| 亚洲视频在线播放免费视频 | 国产69口爆吞精在线视频喝尿| 激情一区二区三区视频| 你懂的视频网站亚洲视频| 97人妻精品一区二区三区男同| 色偷偷av一区二区三区| 国产在线观看www污污污| 欧美在线成人午夜网站| 午夜av内射一区二区三区红桃视| 少妇太爽了在线观看免费|