量子通信路符号化
古典通信路における符号化,復号化
情報理論では一回当りの通信で送られるアルファベット数の桁数をレートと呼ぶ.
このレートが大きければ多きいほどたくさんの情報が送れることになる.
一方,通信にはノイズはつきものである.
このノイズに対抗するために用いられるのが符号化,復号化による誤り訂正である.
これは,もとの情報をそのまま送るのではなく,
適当に冗長させることによって,
ノイズが入った場合にも,下の情報を復元できるようにする方法である.
例えば,1 か 0 の2つに1つの情報を送る場合,
0 の代りに 0 0 0 , 1 の代りに 1 1 1 を送るとの受信者との約束の下で
通信を行ったとする.
このとき受けて側は 0 1 0 や 1 0 0 を受け取ったとすると,
送り手は 0 を送ったのだと推測する.
一方 1 1 0 や 0 1 0 を受け取ると 1 を送ったのだと推測する.
このような取り決めの下で情報のやり取りをすると,
そのまま 0 や 1 を送る場合に比べて誤り確率が小さくなる.
このように,適当に情報を冗長させることによって
誤り確率を小さくすることができる.
なお, 0 を 0 0 0 に変換する約束のことを符号化と呼び,
0 1 0 や 1 0 0 を受け取ると 0 を送ったのだと推測する
約束のことを復号化と呼ぶ.
しかし,このような通信の方法を用いると誤り確率を減らすことはできるが,
一回当りの通信で送られるアルファベット数の桁数すなわちレートは
もとの3分の1に減ってしまう.
現実の通信にはレートはなるだけ大きく,
誤り確率はできる限り小さくするという,
要請がある.
しかし,
一般にはこの2つの要請は相反するものであり同時に
満たすことは難しいと考えられる.
この問題に対する1つの答が通信路符号化定理である.
なおこのような問題設定では通信路は
条件付き確率で表される.
-
(順定理)
- レートが通信路容量より小さい場合は
いくらでも 0 に近い符号化と復号化の組が存在する.
(しかし,誤り確率を 0 に近づけるためには
計算量が極めて多い符号化と複合化を行わなければならない.
そのため,実際に誤り確率を 0 に近づけるためには
処理速度の早い計算機が必要となる.)
- (有本-Blahutのアルゴリズム)
- 通信路容量とは
通信路の数学的な性質から定義される量で,
一般には通信路に対応する遷移行列から
解析的に導くことはできない.
通信路容量を計算するアルゴリズムとして
有本-Blahutのアルゴリズムが知られている.
- (強逆定理)
- 通信路容量を越えるレートを用いた
符号化,復号化を用いた通信を行う場合,
メッセージが十分に長いと,
誤ってメッセージが復号化される確率が
ほぼ1になることが知られている.
- (信頼性関数)
- Shanonn による順定理の証明は
信頼性関数を用いると大変に簡略化できることが知られている.
- (タイプ理論)
- さらに Shanonn による順定理は
信頼性関数を用いた証明も含め random coding を用いて証明されているが,
Cizsar and Korner によりタイプ理論と呼ばれる手法を用いることによって
random coding を用いない証明が考案された.
なお,上記の Shanonn による通信路符号化定理における
メッセージとは文章のようなものを表している.
文章の場合では,誤ってメッセージが伝えられることは,
その文章の中の1文字でも誤って復号化されることを意味します.
量子通信路
先の古典的な通信路の場合は
我々が通信の際に能動的に選択できることは
古典的符号化(どのアルファベットをどの信号の組に対応させるか)と
古典的復号化(受信者が得た信号の組をどのアルファベットに対応させるか)
だけであった.
しかし,実際の通信路では送信者は信号を何らかの物理状態に変換する.
そして,受信者は送られてきた物理状態を測定して,
信号に変換する.
したがって,
我々は個々の信号をどのような物理状態に変換し,
またどのような測定器で信号を受信するか
能動的に選択することができる.
このような問題設定の場合,
通信路として与えられるものは条件付き確率ではない.
個々の入力状態の候補にを送った際,
出力状態が如何なる物理状態になるか定める,
入力状態から出力状態への写像で与えられる.
特に,光通信などの量子力学に従う物理状態を通信に使う場合,
入力の量子状態から出力の量子状態への写像が
通信路となる.
量子力学によると各量子系での状態は表現空間上の密度演算子で
記述され,
通信路は完全正写像の双対写像で記述されることが知られている.
したがって,
量子通信路では符号化は各アルファベットを
量子状態に変換するプロセスと考える.
また,復号化は出力状態として送られてきた量子状態を
測定して最終的な測定値として,
各アルファベットを対応させるプロセスと考える.
なお,符号化の際には各アルファベットを複数の量子状態に
変換することも可能であるとする.
したがって符号化のレートは1個の量子状態当りの
アルファベットの桁数で与えられる.
そして,量子的な通信路を経て送られてきた受信状態は複数の
量子状態からなる.この受信状態を測定して
最終的な測定値として,各アルファベットに戻す作業が復号化である.
このとき,複数ある量子状態の間の量子力学的な干渉効果を用いるような
測定も用いてもよいことにする.
この問題設定は入力の際には量子力学的相関を許さず,
出力の際にのみ量子力学的相関を許すため,
classical quantum coding と呼ばれる.
(入力の際にも量子相関を許す問題設定は
quantum quantum coding と呼ばれほとんど十分な解析がなされていない.)
classical quantum coding は
20年以上も前に提案され,そのような問題設定の下で
通信路容量
(誤り確率が 0 に近づけることが可能なレートの限界)
が
どのような量で特徴づけられるかが問題であった.
Holevo は20年以上も前にこの量をある不等式で上から評価することに成功した.
しかし,ここで与えられた上限が通信路容量と一致するか否かは
長い間不明であった.
以下に,ここ数年の間になされた結果をまとめておく.
-
(順定理の classical quantum 版)
- 近年[1]により純粋状態の場合に限ったときについてこの Holevo の上限が
通信路容量と一致することが示された。
さらに,1996年11月15日になって Holevo 自身によって一般に
Holevo の上限が通信路容量と一致することが示された[2].
この preprint [2] の Acknowledgements によると、
96年の9月に箱根で行われた国際会議において
R.Jozsa や A.Yu.Kitaev と[1] に関して活発な情報交換が有ったようである。
実際,国際会議の当日今回の講演内容に関して,
Holevo 自身,非常におもしろい内容が多かったと感想を語っていた.
さらに,Schumacher and Westmoreland により独立に同様に内容が示された[3].
-
(有本-Blahutのアルゴリズムの
classical quantum 版)
- さらに,長岡により classical quantum 通信路での通信路容量を
計算するアルゴリズムが提案された.
これは有本のアルゴリズムを改良したもので,
ISIT'98 で発表された[4].
-
(強逆定理の classical quantum 版)
- そして,長岡は小川と共同で
通信路符号化定理の逆定理の
classical quantum 版を証明することに成功した[5].
-
(信頼性関数の classical quantum 版)
-
信頼性関数を用いる
順定理の証明は
[1]で扱われた純粋状態のときのみ成功している.
これは Burnashev and Holevo により
なされた[6].
-
(擬古典性)
-
藤原,長岡は受信過程のところで量子相関を用いても
レートが上がらない通信路を擬古典通信路と名付けた.
彼らは,量子通信路が擬古典となるための必要十分条件を導いた[7].
-
(タイプ理論を用いた別証明)
-
最近になって,Winter[10]は先に述べたタイプ理論を用いることによって,
量子通信路符号化定理に対して別証明を与えた。さらに同時に
強逆性についても同時に別証明を与えた.
-
(量子通信路符号化のシュミレーション)
-
文献[9]においては量子通信路での符号化に関するシュミレーションが行われている.
そこでは,文献[2]で提案された復号化やその復号化法を改良した復号化についてシュミレーションを行って比較検討している.
なお量子通信路符号化の定式化を入門的な部分から取り扱った文献としては Fujiwara and Nagaoka [8]
が優れている.
参考文献
- [1] P.Hausladen, P.Jozsa, B.Schumacher, M.Westmoreland, W.Wooters,
- Classical information capacity of a quantum channel,
- Phys. Rev. A 54, 1869-1876(1996).
- [2] A.S.Holevo,
- The Capacity of Quantum Channel with General Signal States ,
- IEEE Trans. IT 44, 269-273 (1998),
E-print quant-ph/9611023
[ src ,
ps ](1996).
- [3] B. Schumacher, M. Westmoreland,
-
Sending classical information via noisy quantum channels,
- Phys. Rev. A 56, 131-138(1997).
- [4] Hiroshi Nagaoka,
- Algorithms of Arimoto-Blahut Type for Computing Channel Capacity,
- ISIT 1998, Cambridge, MA, USA, August 16 - August 21.
- [5] Tomohiro Ogawa, Hiroshi Nagaoka ,
- Strong Converse to the Quantum Channel Coding Theorem ,
- E-print quant-ph/9808063
[ src ,
ps ](1998).
- [6] M.V.Burnashev, A.S.Holevo ,
- On Reliability Function of Quantum Communication Channel ,
- Problems of Information Transmission, Vol. 34, No. 2, 97-107 (1998),
- E-print quant-ph/9703013
[ src ,
ps ](1997).
- (E-print 版は1998年7月最終訂正.最終訂正前のものが論文に掲載されたようである.)
- [7] Akio Fujiwara, Hiroshi Nagaoka ,
- Operational Capacity and Pseudoclassicality of a Quantum Channel,
- IEEE Trans. IT 44, 1071-1086 (1998).
- [8] Akio Fujiwara, Hiroshi Nagaoka ,
- Capacity of a Memoryless Quantum Communication Channel,
- METR 94-22,
[ ps ,
pdf ] (1994).
- この ps file の入手には少し注意が必要である.
リンクされいる file 名が .gz となっており,あたかも gz であるかのように思われるが,
リンクされている file は生の ps file である.)
- [9] 林 勝美,
-
量子通信路における符号化システムの最適化,
- 電気通信大学大学院 情報システム学研究科 修士論文 (1998).
- [10] Andreas Winter,
-
Coding Theorem and Strong Converse for Quantum Channels,
- Diskrete Strukturen in der Mathematik 98-074(1998).
このホームページのご意見ご感想をお待ちしています.
masahito@brain.riken.go.jp