李婧雅,余文斌,劉文杰,王金偉

(南京信息工程大學(xué) a.江蘇省大氣環(huán)境和裝備技術(shù)協(xié)同創(chuàng)新中心; b.計(jì)算機(jī)與軟件學(xué)院,南京 210044)

0 概述

隨著量子信息技術(shù)和量子計(jì)算機(jī)[1-2]的不斷發(fā)展,越來(lái)越多的人開(kāi)始進(jìn)行量子計(jì)算和量子通信[3-4]。由于量子位[5]遵循量子力學(xué)規(guī)律[6],使其具有疊加態(tài)、糾纏態(tài)以及并行性等良好性能,因此,其在計(jì)算和通信速度上相較于經(jīng)典計(jì)算和通信有著顯著優(yōu)勢(shì)。另一方面,和經(jīng)典通信一樣,量子通信在信道環(huán)境中也存在噪聲等影響通信質(zhì)量的因素。在某些精度要求極高的通信中,這些噪聲經(jīng)常會(huì)導(dǎo)致嚴(yán)重后果[7]。在這種情況下,需要找到一種方法使得接收端接收到的信息可以零錯(cuò)區(qū)分,因此,零錯(cuò)信道的概念應(yīng)運(yùn)而生。

在經(jīng)典零錯(cuò)信道[8]中,通信可以用N:X→Y表示。其中,X指信道輸入的集合,Y指信道輸出的集合。N(y|x)指輸入為x時(shí)輸出為y,對(duì)應(yīng)的函數(shù)指出任意輸入x和任意輸出y之間可能的概率關(guān)系。香農(nóng)所給出的零錯(cuò)信道概念指通過(guò)該信道傳輸?shù)男畔⒉粫?huì)互相混淆,即不同信息需要滿足當(dāng)輸入x不同時(shí),通過(guò)函數(shù)N(·|x)得到的輸出結(jié)果之間不相交。在經(jīng)典零錯(cuò)信道概念被提出后,其容量上限被研究并產(chǎn)生了Lovász值的計(jì)算方法[9]。

近年來(lái),對(duì)量子零錯(cuò)信道的研究主要集中在信道容量方面。文獻(xiàn)[10-11]針對(duì)量子零錯(cuò)信道的可行性進(jìn)行研究,發(fā)現(xiàn)在量子通信中零錯(cuò)信道依然可行。在確定了可行性后,需要找出量子零錯(cuò)信道容量的定義式并確定Lovász值,文獻(xiàn)[12-14]對(duì)量子零錯(cuò)信道中的Lovász值進(jìn)行研究并確定了其計(jì)算公式,然后給出關(guān)于無(wú)交互的量子零錯(cuò)信道容量。在此之后,文獻(xiàn)[15]提出量子反饋信道Lovász值的計(jì)算方法。目前,針對(duì)量子零錯(cuò)信道編碼的研究正處于起步階段,文獻(xiàn)[16]提出利用量子零錯(cuò)信道容量遍歷相應(yīng)矩陣的方法進(jìn)行信源編碼。

本文基于量子五符號(hào)混淆信道模型解決其相應(yīng)的零錯(cuò)信道編碼問(wèn)題?；仡櫧?jīng)典五符號(hào)混淆信道模型及其編碼,建立與經(jīng)典五符號(hào)對(duì)應(yīng)的量子五符號(hào)混淆信道模型,然后利用量子疊加態(tài)特性,提出一種量子模型的零錯(cuò)信道編碼方法,最后通過(guò)實(shí)例對(duì)比驗(yàn)證該量子零錯(cuò)信道編碼方法的性能優(yōu)勢(shì)。

1 經(jīng)典五符號(hào)混淆信道模型與編碼

文獻(xiàn)[8]提出的經(jīng)典五符號(hào)混淆信道模型如圖1所示。

圖1 經(jīng)典五符號(hào)混淆信道模型

在圖1中,輸入方所傳輸信息用五符號(hào)表示,分別為x0、x1、x2、x3和x4,這5個(gè)符號(hào)信息通過(guò)上述信道后也得到5個(gè)輸出,分別為y0、y1、y2、y3和y4。這5個(gè)輸入分別轉(zhuǎn)換成5個(gè)輸出的概率用pij表示(i和j可以取0～4之間的任意正整數(shù)),例如,p03代表輸入為x0、輸出為y3的概率。根據(jù)信道特征可知,此處滿足式(1)所示的條件。

(1)

其中,pij∈[0,1]。

(2)

在經(jīng)典通信中,通過(guò)圖的同構(gòu)理論和矩陣向量相結(jié)合的方法確定信道的編碼方式[9]。編碼步驟如下:

步驟1由于在經(jīng)典信道中,無(wú)論輸入轉(zhuǎn)換成對(duì)應(yīng)輸出的概率是多少,都會(huì)使輸出結(jié)果混淆從而無(wú)法進(jìn)行區(qū)分,這意味著信道中的概率對(duì)零錯(cuò)通信沒(méi)有影響。因此,可以將圖1信道中的概率去除,轉(zhuǎn)化成圖2所示的信道。

圖2 經(jīng)典五符號(hào)信道二分圖

步驟2計(jì)算該信道的零錯(cuò)信道容量,即經(jīng)典零錯(cuò)信道的Lovász值,以確定編碼一位經(jīng)典比特所需的碼字位數(shù)。假設(shè)上述信道計(jì)算出的Lovász值為m,則需要m比特來(lái)進(jìn)行編碼。

步驟3通過(guò)圖來(lái)確定編碼方案。當(dāng)需要m個(gè)比特進(jìn)行編碼時(shí),從5m個(gè)可能輸入中,找出對(duì)應(yīng)輸出集合不相交的5個(gè)輸入,這5個(gè)輸入即為編碼。

例如,假定m的值為3,則可以先選擇一個(gè)輸入為000,再?gòu)?0?(?代表0～4之間的任意正整數(shù))中找輸出集合不相交的輸入,如果在10?中沒(méi)找到,就從11?中找,直到找到與000輸出集合不相交的輸入為止。確定第1個(gè)和第2個(gè)輸入后,再通過(guò)迭代找與第1個(gè)和第2個(gè)輸出集合不相交的輸入,直到找到所有輸入,這些輸入即是所要求的編碼方案。

2 基于量子疊加態(tài)五符號(hào)混淆信道零錯(cuò)編碼

2.1 量子五符號(hào)混淆信道模型

本文編碼方法適用的信道模型,即量子五符號(hào)混淆信道模型如圖3所示。

圖3 量子五符號(hào)混淆信道模型

量子五符號(hào)混淆信道模型由3部分組成,分別為輸入基態(tài)集合{|0>,|1>,|2>,|3>,|4>}、輸出基態(tài)集合{|0>,|1>,|2>,|3>,|4>}以及輸入基態(tài)集合和輸出基態(tài)集合之間的系數(shù)關(guān)系,也即任意輸入基態(tài)|i>(i∈[0,4]中任意正整數(shù),下同)。通過(guò)該混淆信道后,形成疊加態(tài):

(3)

其中,|j>表示輸出基態(tài)中的任意基態(tài),取值范圍與|i>相同,αij是信道中的任意輸入基態(tài)|i>與任意輸出基態(tài)|j>對(duì)應(yīng)關(guān)系的系數(shù),例如輸入基態(tài)|0>與輸出基態(tài)|1>之間的關(guān)系可以用α01表示。αij滿足以下條件:

αij∈[-1,1]中的任意復(fù)數(shù)

(4)

(5)

假設(shè)一個(gè)輸入集合由k個(gè)疊加態(tài)組成,記為{|x0>,|x1>,…,|xl>,…,|xk>},其中,任意輸入|xl>如下:

(6)

滿足歸一化條件:

(7)

將式(6)帶入式(3)中,得到該輸入通過(guò)信道后的對(duì)應(yīng)輸出為:

(8)

2.2 編碼方法步驟

本文基于同構(gòu)法的量子五符號(hào)混淆信道零錯(cuò)編碼方法步驟如下:

步驟1將信道圖轉(zhuǎn)換為信道系數(shù)矩陣A。其中,系數(shù)矩陣表示如下:

(9)

系數(shù)矩陣中的任意值αij代表任意輸入基態(tài)|i>到輸出基態(tài)|j>的系數(shù),與信道圖中的αij一致。

步驟2計(jì)算該矩陣的線性無(wú)關(guān)向量組以及個(gè)數(shù)k,并且組成新矩陣C。算出5×5維的系數(shù)矩陣A的秩,記為k(k∈[1,5]中的任意正整數(shù),下同),根據(jù)矩陣論相關(guān)知識(shí),如矩陣消元法,可找出該矩陣中對(duì)應(yīng)的k個(gè)5階線性無(wú)關(guān)向量:

(10)

其中,l∈[0,k-1]。這k個(gè)線性無(wú)關(guān)向量和5-k個(gè)零向量組成一個(gè)新矩陣C:

(11)

步驟3確定系數(shù)矩陣A與矩陣C之間的關(guān)系。依據(jù)線性代數(shù)理論[16],C和A這2個(gè)矩陣之間總能找到一個(gè)如式(12)所示的矩陣B,使得式(13)成立。

(12)

AB=C

(13)

將式(9)和式(12)帶入式(13)中,可得到矩陣C任意元素Cgf滿足式(14)。

Cgf=α0fbg0+α1fbg1+α2fbg2+α3fbg3+α4fbg4=

(14)

由此可知,k個(gè)無(wú)關(guān)向量中的任意向量cl也可由式(15)表示:

(15)

步驟4利用同構(gòu)向量確定輸入、輸出。通過(guò)上述矩陣求線性無(wú)關(guān)向量組的過(guò)程,可以得出實(shí)現(xiàn)量子信道零錯(cuò)的編碼方案。在步驟3中,已經(jīng)得出該信道的k個(gè)線性無(wú)關(guān)向量組。根據(jù)量子態(tài)與向量之間的同構(gòu)性可知這k個(gè)線性無(wú)關(guān)向量(即k個(gè)輸出)的量子態(tài)的矩陣形式。k個(gè)輸出和對(duì)應(yīng)的k個(gè)輸入可以用式(16)和式(17)表示。

(16)

(17)

根據(jù)量子態(tài)可零錯(cuò)分辨的條件,任意2個(gè)態(tài)應(yīng)當(dāng)正交,他們之間的任意內(nèi)積為0,即k個(gè)線性無(wú)關(guān)向量組應(yīng)該滿足:

(18)

(19)

由此可證,任意2個(gè)輸出之間可分辨。

3 實(shí)例對(duì)比與算法分析

3.1 實(shí)例對(duì)比

3.1.1 五符號(hào)鄰邊混淆信道

經(jīng)典五符號(hào)鄰邊混淆信道和量子五符號(hào)鄰邊混淆信道分別如圖4、圖5所示。

圖4 經(jīng)典五符號(hào)鄰邊混淆信道

圖5 量子五符號(hào)鄰邊混淆信道

分別按照前文提到的經(jīng)典信道零錯(cuò)編碼方法和本文量子信道零錯(cuò)編碼方法,求解編碼輸入如下:

2)量子信道零錯(cuò)編碼方法的5個(gè)輸入為:

(20)

該方法一量子疊加態(tài)編碼一位比特信息,信道容量為5。

3.1.2 五符號(hào)多邊混淆信道

經(jīng)典五符號(hào)多邊混淆信道和量子五符號(hào)多邊混淆信道分別如圖6、圖7所示。

圖6 經(jīng)典五符號(hào)多邊混淆信道

圖7 量子五符號(hào)多邊混淆信道

同樣按照前文提到的經(jīng)典信道零錯(cuò)編碼方法和本文量子信道零錯(cuò)編碼方法,求解編碼輸入分別如下:

1)經(jīng)典信道零錯(cuò)編碼方法的8個(gè)輸入為:000,001,010,011,100,101,110,111,信道容量為2。

2)量子信道零錯(cuò)編碼方法的4個(gè)輸入為:

|x0>=|0>

|x3>=|4>

(21)

該編碼方法的信道容量為4。

3.2 算法分析

定理1對(duì)于經(jīng)典多邊混淆信道,其零錯(cuò)信道容量CC

因此,CC

定理2量子多邊混淆信道的信道容量CQ=d。

證明:由前文提出的線性變換算法可知,零錯(cuò)信道容量與所求解的可分辨向量組個(gè)數(shù)一致,且為信道矩陣最大線性無(wú)關(guān)向量組的個(gè)數(shù),即系數(shù)矩陣的秩d。

因此,CQ=d。

定理3經(jīng)典多邊混淆信道的編碼算法復(fù)雜度大于等于O(2n),其中,n為信道矩陣的維數(shù)。

證明:根據(jù)文獻(xiàn)[5]的編碼算法和本文第2節(jié)的分析可知,經(jīng)典信道零錯(cuò)編碼分為2個(gè)部分:

1)計(jì)算Lovász值,這需要多次遍歷矩陣空間,其算法復(fù)雜度大于等于O(2n)。

2)采用遍歷算法搜索碼字空間,求得具體的碼字。設(shè)Lovász值為θ,則遍歷次數(shù)為nθ,故其復(fù)雜度為O(nθ)。

因此,經(jīng)典多邊混淆信道的編碼算法總體復(fù)雜度大于等于O(nθ+2n),即大于等于O(2n),該算法是一個(gè)NP問(wèn)題。

定理4量子多邊混淆信道的編碼算法復(fù)雜度為O(n2)。

證明:量子信道零錯(cuò)編碼的算法復(fù)雜度為4個(gè)獨(dú)立步驟復(fù)雜度的總和。步驟1和步驟4的算法復(fù)雜度是n,步驟2和步驟3的算法復(fù)雜度是n(n-1)/2。由此可知,算法總的復(fù)雜度為:

(22)

由定理1和定理2可知,量子信道容量CQ大于經(jīng)典信道容量CC。另一方面,由定理3和定理4可知,量子零錯(cuò)編碼方案的算法復(fù)雜度僅為O(n2)。這意味著在相同條件下,采用量子通信的方式可以傳遞更多的零錯(cuò)信息并具有更快的編碼速度。因此,本文提出的量子信道零錯(cuò)編碼方法相較于經(jīng)典方法具有更高的編碼效率。

4 結(jié)束語(yǔ)

本文提出基于量子疊加態(tài)的五符號(hào)混淆信道零錯(cuò)編碼方法。該方法利用量子疊加態(tài)與向量之間、信道與矩陣之間的對(duì)應(yīng)關(guān)系以及矩陣和向量的轉(zhuǎn)化關(guān)系,實(shí)現(xiàn)在量子五符號(hào)混淆信道下的零錯(cuò)信道編碼。分析結(jié)果表明,相較于經(jīng)典信道編碼方法,該方法具有更高的信道容量和編碼效率。本文雖然總結(jié)了編碼的理論推導(dǎo)式,但具體編碼線路仍有待確定,解決該問(wèn)題將是今后的研究方向。