基于量子五符號混淆信道模型的零錯編碼方法

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

(南京信息工程大學 a.江蘇省大氣環境和裝備技術協同創新中心; b.計算機與軟件學院,南京 210044)

0 概述

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

在經典零錯信道[8]中,通信可以用N:X→Y表示。其中,X指信道輸入的集合,Y指信道輸出的集合。N(y|x)指輸入為x時輸出為y,對應的函數指出任意輸入x和任意輸出y之間可能的概率關系。香農所給出的零錯信道概念指通過該信道傳輸的信息不會互相混淆,即不同信息需要滿足當輸入x不同時,通過函數N(·|x)得到的輸出結果之間不相交。在經典零錯信道概念被提出后,其容量上限被研究并產生了Lovász值的計算方法[9]。

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

本文基于量子五符號混淆信道模型解決其相應的零錯信道編碼問題?；仡櫧浀湮宸柣煜诺滥Ｐ图捌渚幋a,建立與經典五符號對應的量子五符號混淆信道模型,然后利用量子疊加態特性,提出一種量子模型的零錯信道編碼方法,最后通過實例對比驗證該量子零錯信道編碼方法的性能優勢。

1 經典五符號混淆信道模型與編碼

文獻[8]提出的經典五符號混淆信道模型如圖1所示。

圖1 經典五符號混淆信道模型

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

(1)

其中,pij∈[0,1]。

(2)

在經典通信中,通過圖的同構理論和矩陣向量相結合的方法確定信道的編碼方式[9]。編碼步驟如下:

步驟1由于在經典信道中,無論輸入轉換成對應輸出的概率是多少,都會使輸出結果混淆從而無法進行區分,這意味著信道中的概率對零錯通信沒有影響。因此,可以將圖1信道中的概率去除,轉化成圖2所示的信道。

圖2 經典五符號信道二分圖

步驟2計算該信道的零錯信道容量,即經典零錯信道的Lovász值,以確定編碼一位經典比特所需的碼字位數。假設上述信道計算出的Lovász值為m,則需要m比特來進行編碼。

步驟3通過圖來確定編碼方案。當需要m個比特進行編碼時,從5m個可能輸入中,找出對應輸出集合不相交的5個輸入,這5個輸入即為編碼。

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

2 基于量子疊加態五符號混淆信道零錯編碼

2.1 量子五符號混淆信道模型

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

圖3 量子五符號混淆信道模型

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

(3)

其中,|j>表示輸出基態中的任意基態,取值范圍與|i>相同,αij是信道中的任意輸入基態|i>與任意輸出基態|j>對應關系的系數,例如輸入基態|0>與輸出基態|1>之間的關系可以用α01表示。αij滿足以下條件:

αij∈[-1,1]中的任意復數

(4)

(5)

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

(6)

滿足歸一化條件:

(7)

將式(6)帶入式(3)中,得到該輸入通過信道后的對應輸出為:

(8)

2.2 編碼方法步驟

本文基于同構法的量子五符號混淆信道零錯編碼方法步驟如下:

步驟1將信道圖轉換為信道系數矩陣A。其中,系數矩陣表示如下:

(9)

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

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

(10)

其中,l∈[0,k-1]。這k個線性無關向量和5-k個零向量組成一個新矩陣C:

(11)

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

(12)

AB=C

(13)

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

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

(14)

由此可知,k個無關向量中的任意向量cl也可由式(15)表示:

(15)

步驟4利用同構向量確定輸入、輸出。通過上述矩陣求線性無關向量組的過程,可以得出實現量子信道零錯的編碼方案。在步驟3中,已經得出該信道的k個線性無關向量組。根據量子態與向量之間的同構性可知這k個線性無關向量(即k個輸出)的量子態的矩陣形式。k個輸出和對應的k個輸入可以用式(16)和式(17)表示。

(16)

(17)

根據量子態可零錯分辨的條件,任意2個態應當正交,他們之間的任意內積為0,即k個線性無關向量組應該滿足:

(18)

(19)

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

3 實例對比與算法分析

3.1 實例對比

3.1.1 五符號鄰邊混淆信道

經典五符號鄰邊混淆信道和量子五符號鄰邊混淆信道分別如圖4、圖5所示。

圖4 經典五符號鄰邊混淆信道

圖5 量子五符號鄰邊混淆信道

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

2)量子信道零錯編碼方法的5個輸入為:

(20)

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

3.1.2 五符號多邊混淆信道

經典五符號多邊混淆信道和量子五符號多邊混淆信道分別如圖6、圖7所示。

圖6 經典五符號多邊混淆信道

圖7 量子五符號多邊混淆信道

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

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

2)量子信道零錯編碼方法的4個輸入為:

|x0>=|0>

|x3>=|4>

(21)

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

3.2 算法分析

定理1對于經典多邊混淆信道,其零錯信道容量CC

因此,CC

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

證明:由前文提出的線性變換算法可知,零錯信道容量與所求解的可分辨向量組個數一致,且為信道矩陣最大線性無關向量組的個數,即系數矩陣的秩d。

因此,CQ=d。

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

證明:根據文獻[5]的編碼算法和本文第2節的分析可知,經典信道零錯編碼分為2個部分:

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

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

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

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

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

(22)

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

4 結束語

本文提出基于量子疊加態的五符號混淆信道零錯編碼方法。該方法利用量子疊加態與向量之間、信道與矩陣之間的對應關系以及矩陣和向量的轉化關系,實現在量子五符號混淆信道下的零錯信道編碼。分析結果表明,相較于經典信道編碼方法,該方法具有更高的信道容量和編碼效率。本文雖然總結了編碼的理論推導式,但具體編碼線路仍有待確定,解決該問題將是今后的研究方向。