量子ネットワーク符号
西村治道（大阪府立大学理学系研究科）
２０１０年１１月６日
IBIS2010，東京大学 生産技術研究所

ネットワーク上での効率的通信• ネットワーク符号 [Ahlswede-Cai-Li-Yeung. 2000]– 通信理論とネットワーク上での配送理論の融合分野– 情報理論，通信理論の研究者が研究の中心
通信理論

主に１対１の（ノイズを含む通信路における）通信に関する理論
データ圧縮
エラー訂正
セキュリティ

ネットワーク上での配送問題
複雑なネットワーク上での効率的配送に関する理論

液体フロー (Liquid Flow)
s1
1

s0

1

s2

1

1

1

1

t0

1

ボトルネックにより配送問題としては解なし

t1

t2
Butterfly Network情報フロー (Information Flow)[Ahlswede et al. 2000]

s1yxx

s0

POINT 1
情報はコピー可能

xy=x⊕x⊕yt0s2yx⊕yx⊕yt2y

POINT 2
情報は符号化可能x⊕yt1x=y⊕x⊕yネットワーク符号問題[A. Lehman PhD, 2005 より]• 入力例– （有向かつ非環式）グラフ G=(V, E)– Capacity c(e) for 各辺 e
– k 個の品種(commodity)からなる集合 I– 各品種 i ∊I に対するソースの集合 S(i)とシンクの集合 T(i)• Network code– Alphabet ∑– 各辺 e に対しての関数 f[e]: ∑(eの出発点の入次数) -> ∑c(e)• Network codeの解– f[e] は e=(u,v) へ入ってくる辺上の関数及び uがソースの場合のメッセージから計算可能な関数– 各品種 i の各シンク v ∊T(i)に対し，vへの辺上の関数から S(i)に与えられるメッセージ M(i) ∊∑が復号可能

解が存在するネットワーク符号問題の例
xs1

全ての辺のcapacityは 1s2

y

２つの品種 X, YがあってS(X)={s1}, S(Y)={s2},e2e1e3

T(X)={t1}, T(Y)={t2}e4e5e6e7yxt2

Butterfly networkt1

解（の１つ）はアルファベットとして{0,1} を取り，各辺に対する関数としてf[e1](z)=z （f[e2], f[e3], f[e4], f[e6],f[e7] も同様）
f[e5](w,z)=w+zである．

ネットワーク符号問題の例
x, y, zxyyx

x, y, zx, y, zx, y, zMulticast 問題：

k-ペア通信問題 (Multiple Unicast)：

ソースが持つメッセージ全てを全てのシンクが要求するk品種のそれぞれが１つのソースと１つのシンクを持つ．Butterfly networkは2-通信問題の一種

Multicast問題の例
x, yxyxyxx+yx+yx, yMax-flow Min-cut 定理
ソースとシンクが各1個の場合，Min-cutを達成するような（ルーティングによる）Max-flowが存在する

yMax-flow=2
Min-cut=2Multicast問題の場合，符号化を（しかも線形符号を）使ってMincutを達成するようなMax-flowが存在する [Ahlswede et al. 2000, Lix+yx, yet al. 2003]※しかも多項式時間アルゴリズム
存在 [Jaggi et al. 2005]

kペア通信問題• kがグラフサイズに依存する場合，可解性は計算可能か否かさえ未解決• 線形符号に限ってもNP完全 [Lehman-Lehman 2004]• k=2の場合，多項式時間アルゴリズム存在 [Wang-Shorff2007]• kが3以上の定数の場合未解決– 体のサイズ有限の線形符号に限ると，多項式時間アルゴリズム存在[Iwama et al. 2008]

情報フローの量子化（量子ネットワーク符号）s1|Ψ2>|Ψ1>s2s0• 流すべき情報は量子状態• 各頂点で量子的操作が可能

POINT 1
量子情報はコピーできない(No-cloningtheorem)t2• すべてのチャネルは量子通信路

t0

POINT 2
量子情報を如何に符号化するか？

t1Q. 古典で可解なネットワーク符号問題は量子でも可解か？

量子ビット• 量子ビットはBloch球と呼ばれる単位球の表面上（及び内部の）点として表現可能|0>|->

2θ ψ = cos θ 0 + e|-’>iπγ

sin θ 1|+’>=(|0> + i |1>)/√2γ|+>|1>=(|0>+|1>)/√2どうやってコピーするか？
•ユニタリ変換を使ってコピーできればよいが，しかし・・(No-cloning theorem: Wootters-Zurek) 未知の量子状態は，正確にコピーすることは不可能．

X0 a ⎯⎯→ 00 ϕ ,UU
1 a ⎯⎯→11 φU(α 0 + β 1 ) a ⎯⎯→α 00 ϕ + β 11 φ≠ (α 0 + β 1 )(α 0 + β 1 ) χネットワーク符号問題の例|φ1>, |φ2>, |φ3>

|φ1>

|φ2>

|φ1>, |φ2>, |φ3>|φ1>, |φ2>, |φ3>|φ1>, |φ2>, |φ3>

|φ2>

|φ1>

Multicast 問題：

k-ペア通信問題 (Multiple Unicast)：

ソースが持つメッセージ全てを全てのシンクが要求するk品種のそれぞれが１つのソースと１つのシンクを持つ

c.f. Shi-Soljanin 2006, Kobayashi et al. 2010

どうやって量子情報を符号化するか？

s1

|Ψ1>

b|Ψ1>

s0bs2

b=0 なら U, b=1 なら V を行う
U|Ψ1>＝V |Ψ1> のとき，b=0かb=1か識別不可能|Ψ1> と b を同時にかつ正確に送ることは不可能

t0t2t1

不可能性に関する結果
１量子ビット１量子ビット|φ1>|φ2>m量子ビット|φ1>

ネットワーク 1 回使用（one shot）

|φ2>

|φ1>

m量子ビット|φ2>

ネットワーク n 回使用

|φ2>

|φ1>

ネットワークの１回の使用のもと，１量子ビットを忠実に送ることは１量子ビットを忠実に送ることは不可能

漸近的にも（つまりm/nが漸近的に１に近づく）[Hayashi et al. 2007]

不可能 [Hayashi 2007, Leung et al. 2010]

不可能性に関する結果
m量子ビットE3(significant share)は|φ1>

E1"secret"のサイズ以上

E3|φ2>"secret" |φ1>, |φ2> を回復できる(authorized set)
"secret" |φ1>, |φ2> を回復できない(unauthorized set)

|φ1>

E2|φ1>|φ2>m量子ビット|φ2>

ネットワーク n 回使用

|φ2>

|φ1>

１量子ビットを忠実に送ることは漸近的にも（つまりm/nが漸近的に１に近づく）
不可能 [Hayashi 2007, Leung et al. 2010]

不可能性に関する結果
|φ1>

|φ2>

R1

R2m量子ビットm量子ビット

|φ1>

E1

|φ2>

E2

E3

ネットワーク n 回使用|φ2> B2
I(R1R2:B1B2) ≤ I(R1R2:E1E2E3)

B1

|φ1>

(単調性)

＝I(R1R2:E3|E1E2)+I(R1R2:E1E2) (Chain Rule)

|φ2>

|φ1>

≤ 2H(E3) + I(R1:E1)+I(R2:E2)

１量子ビットを忠実に送ることは≤ 2n + 2H(R1)－I(R1:B1)+2H(R2)－I(R2:B2)

漸近的にも（つまりm/nが漸近的に１に近づく）
不可能 [Hayashi 2007, Leung et al. 2010]

不可能性に関する結果
|φ1>

|φ2>

R1

R2m量子ビットm量子ビット

|φ1>

|φ2>

I(R1R2:E3|E1E2)
E1=H(R1R2E1E2)+H(E3R1R2)－H(E3R1R2E1E2)－H(E1E2)
E2

E3≤2H(E3)(Araki-Liebの不等式 H(A)－H(AB) ≤ H(B)より)
ネットワーク n 回使用|φ2> B2→ 2m+2m

I(R1R2:E1E2)－I(R1:E1)－I(R2:E2)|φ1>=H(R1R2)+H(E1E2)－H(R1R2E1E2)－H(R1)－H(E1)+H(R1E1)
B1－H(R2)－H(E2)+H(R2E2)=－I(R1:R2)－I(E1:E2)+I(R1E1:R2E2)
I(R1R2:B1B2) ≤ I(R1R2:E1E2E3)
(単調性)
|φ2>
=0
(R1E1とR2E2は独立)＝I(R1R2:E3|E1E2)+I(R1R2:E1E2)(Chain Rule)|φ1>≤ 2H(E3) + I(R1:E1)+I(R2:E2)

１量子ビットを忠実に送ることは≤ 2n + 2H(R1)－I(R1:B1)+2H(R2)－I(R2:B2)

漸近的にも（つまりm/nが漸近的に１に近づく）=2m→ 2m=2m→ 2m

不可能 [Hayashi 2007, Leung et al. 2010]

補助的なリソースを認めると・・・• エンタングルメント– ソース間 [Hayashi 2007]– 各辺の間 [Leung-Oppenheim-Winter 2010]• 古典通信路 [Leung et al. 2010, Kobayashi et al., 2009, 2010]– 量子通信路より安価 『 LOCC(Local Operation & ClassicalCommunication)は量子通信より易しい（？）』– 古典通信を自由に認めることで，量子通信路の使用回数を減らせるなら・・・

Q. 古典で可解なネットワーク符号問題は，古典通信を自由に許すことで量子でも可解となるか？
A. 古典のネットワーク符号問題の解が線形符号化で実現されているなら，量子でも可解 [Kobayashi et al. 2009]

線形符号によるネットワーク符号
X

aX+bY

Y

cX+dY

各頂点での出力が入力の線形結合であるとき，線形というプロトコル• 基本アイデア– 各ノードごとに古典の操作を模倣– フーリエ基底による測定– 測定により生じた位相エラーをシンクで修正
古典x1

量子x2

∑αx1 ,.., xk

x1 ,..., xk

x1 ,.., xkxk

ソース

ソース

シンクx1x2xk∑αx1 ,.., xk

シンクx1 ,.., xk

x1 ,..., xk

各中間ノードでの操作①
古典解が体 Fp上での線形符号量子で実現されていると仮定
y2|y1>P1|y2>P2···|ym>Pmym

y1

P2P2
Pm

P1v
|y1>P1|y2>P2···|ym>Pm|f1>
Q1|f2>Q2···|fm>Qmv
Q1
Q2
f1:=f1(y1,...,ym)
f2=f2(y1,...,ym)

Pm

P1

Q1

Qn

Q2

Qn

fn=fn(y1,...,ym)① ユニタリ変換

U f 1,.., fm y1,..., ym 0,...,0:= y1,..., ym f 1,..., fmを施す

各中間ノードでの操作②古典解が体 Fp上での線形符号量子で実現されていると仮定
y2ym

y1

P2P2PmP1

v|y1>P1|y2>P2···|ym>Pm|f1>
Q1|f2>Q2···|fm>Qmv
Q1
Q2
f1:=f1(y1,...,ym)
f2=f2(y1,...,ym)

Pm

P1Qn

fn=fn(y1,...,ym)

Q1
Q2Qn

⎛yjzj ⎞∑
1j⎜
⎟ z1 L zm
exp 2πi∑Pm⎜p ⎟ P1p m z1,.., zm⎝⎠② P1,P2,...,Pmにフーリエ変換

F y :=⎛yz ⎞1⎟⎟ z⎜i
exp2π∑⎜
pp z⎠⎝を施した後測定し，測定値 z1,..,zm をシンクに送る各シンクでの操作
古典

量子

y2y2ymy1ymy1P2

P2Pm

P1Pm

P1tｊ

レジスタ Tｊtｊxｊxｊ

中間ノード同様の操作に加えて，位相訂正前()

各中間ノードからの測定値情報をもとに

exp 2πi ∑v hv ( x1 ,..., xk ) x1 ,..., xk T ,...,T
1hv ( x1 ,..., xk ) = hv ,1 ( x1 ) + ... + hv ,k ( xk )k

位相エラーの訂正を行う

x a exp(− 2πiht ( x) ) x
位相エラー

具体例
|Ψ>P1,P2=∑xyaxy|x>P1|y>P2
P1

P2
R2

R1

R5

R6Q2

R4

R3

R7

Q1

P1をR1,R2に「コピー」
P2をR3,R4に「コピー」

具体例|Ψ>P1,P2=∑xyaxy|x>P1|y>P2

P1P2R2

R1

R5R6Q2

R4

R3

R7Q1

P1をR1,R2に「コピー」
P2をR3,R4に「コピー」

具体例

P1

P2
R2

R4

∑xyaxy|x>P1|x>R1|x>R2|y>P2|y>R3|y>R4
R1

R5

R6Q2

R3

R7

Q1

P1をR1,R2に「コピー」
P2をR3,R4に「コピー」

フーリエ変換後
測定

具体例

P1

P2
R2

R4

∑xyaxy|x>P1|x>R1|x>R2|y>P2|y>R3|y>R4
R1

R5

R6

Q2

R3

R7

Q1

フーリエ変換後
測定

具体例
フーリエ変換後
測定

P1

p1

P2
R2

p2

R4

∑xyaxy|x>P1|x>R1|x>R2|y>P2|y>R3|y>R4∑xy(-1)p1x+p2yaxy|x>R1|x>R2|y>R3|y>R4
R1

R5

R6Q2

フーリエ変換後
測定

R3

R7Q1

具体例
フーリエ変換後
測定

P1

p1

P2
R2

フーリエ変換後
測定
p2

R4∑xy(-1)p1x+p2yaxy|x>R1|x>R2|y>R3|y>R4
R1

R5

R6

p2

Q2

R3

R7

Q1

p1

具体例
フーリエ変換後
測定

P1

p1

R2, R4の和をR5へ書く
R2

P2

フーリエ変換後
測定
p2

R4∑xy(-1)p1x+p2yaxy|x>R1|x>R2|y>R3|y>R4
R1

R5

R6

p2

Q2

R3

R7

Q1

p1

具体例
P1

R2, R4の和をR5へ書く
R2

P2

R4

∑xy(-1)p1x+p2yaxy|x>R1|x>R2|y>R3|y>R4|x+y>R5
R1

R5R6

p2

Q2

R3

R7

Q1p1

具体例
P1
R2,R4をフーリエ変換後
測定

P2
R2

R4r2r4∑xy(-1)p1x+p2y+r2x+r4yaxy|x>R1|y>R3|x+y>R5
R1

R5

R6r4

p2

Q2

R3

R7

Q1

p1r2

具体例

R5をR6,R7に「コピー」

P1

P2
R2

R1

R4

R5

R3

∑xy(-1)p1x+p2y+r2x+r4yaxy|x>R1|y>R3|x+y>R5|x+y>R6|x+y>R7
R6

r4

p2

Q2

R7

Q1

p1r2

具体例
P1
R5をフーリエ変換後
測定

P2
R2

R1

R4

R5r5

R3

∑xy(-1)p1x+p2y+r2x+r4y+r5(x+y)axy|x>R1|y>R3|x+y>R6|x+y>R7
R6r5r4

p2

Q2

R7

Q1

p1

r2r5

R7, R3の和をQ1へ書く
R1, R6の和をQ2へ書く

具体例

P1

P2
R2

R1

R4

R5

R3

R6

∑xy(-1)p1x+p2y+r2x+r4y+r5(x+y)axy|x>R1|y>R3|x+y>R6|x+y>R7|x>Q1|y>Q2
r5r4

p2

Q2

Q1

p1

r2r5

具体例
P1
R1,R6,R7,R3をフーリエ変換後測定

r1

P2
R2

R1

R4

R5

r6 R6

R3r3

R7 r7

∑xy(-1)p1x+p2y+r2x+r4y+r5(x+y)+r1x+r6(x+y)+r3y+r7(x+y)axy|x>Q1|y>Q2
r5r4p2r3r6r7Q2

Q1

p1r2r5r1r6r7

具体例
P1

P2R2

R1

Q1,Q2で位相エラーを訂正

R4R5

R3R6r5r4

p2

r3

r6r7

Q2|Ψ>Q1,Q2=∑xyaxy|x>Q1|y>Q2

Q1

p1

r2

r5

r1

r6r7

今後の課題（狭い意味で）[補助的リソースが何も利用できない場合]

あるネットワーク符号問題が量子で可解ならば，その解はルーティングで達成可能？ ←ある非常に限られたクラスのネットワークのみ肯定的に証明[Leung et al. 2010][補助的に古典通信が利用できる場合]あるネットワーク符号問題が古典で可解?

自由に古典通信を認めたとき量子で可解実は・・・古典の未解決問題と関連するかも？

無向グラフにおけるｋペア通信問題が可解ならば，かならずルーティングによる解が存在する？
量子テレポーテーションを使うことで，有向辺の逆向きに量子情報を送ることが可能になるので，実質無向グラフ

今後の課題• 一般のグラフにおける達成可能なレート• 応用（古典のワイヤレス通信のような）• セキュリティや計算量的側面における優位性• 損失のある量子チャネルなどなど・・・

参考文献（古典のネットワーク符号関連）
••
•
•
•
•
•

R. Alhswede, N. Cai, S.-Y. R. Li, R. Yeung. Network information flow. IEEETransactions on Information Theory 46(4), pp.1204-1216, 2000.
K. Iwama, H. Nishimura, M. Paterson, R. Raymond, S. Yamashita.
Polynomial-time construction of linear network coding. Proc. ICALP2008(Lecture Notes in Computer Science 5125), pp.271-282, 2008.
S. Jaggi, P. Sanders, P.A. Chou, M. Effros, S. Egner, K. Jain, L. Tolhuizen.
Polynomial time algorithms for multicast network coding construction. IEEETransactions on Information Theory 51(6), pp.1973-1982, 2005.
A. R. Lehman. Network Coding. Ph.D. dissertation, MIT, 2005.
A. Lehman, E. Lehman. Complexity classification of network information flow
problems. Proc. SODA2004, pp.142-150, 2004
S.-Y. R. Li, R. Yeung, N. Cai. Linear network coding. IEEE Transactions onInformation Theory 49(2), pp.371-381, 2003.
C.-C. Wang, N. B. Shroff. Beyond the butterfly – a graph-theoreticcharacterization of the feasibility of network coding with two simple unicast
sessions. Proc. ISIT2007, pp. 121-125, 2007.

参考文献（量子ネットワーク符号関連）
••
••

•
•

M. Hayashi. Prior entanglement between senders enables perfect quantum
network coding with modification. Physical Review A76(4), 040301(R), 2007.
M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, S. Yamashita. Quantum
network coding. Proc. STACS2007 (Lecture Notes in Computer Science4393), pp.610-621, 2007. quant-ph/0601088.
H. Kobayashi, F. Le Gall, H. Nishimura, M. Roetteler. Perfect quantum
network communication protocol based on classical network coding. Proc.
ISIT2010, pp.2686-2690, 2010. arXiv:0902.1299.
H. Kobayashi, F. Le Gall, H. Nishimura, M. Roetteler. General scheme for
perfect quantum network coding with free classical communication. Proc.
ICALP2009 (Lecture Notes in Computer Science 5555), pp.622-633, 2009.
arXiv:0908.1457.
D. Leung, J. Oppenheim, A. Winter. Quantum network communication –thebutterfly and the beyond. IEEE Transactions on Information Theory 56(7),pp.3478-3490, 2010. quant-ph/0608223.
Y. Shi, E. Soljanin. On multicast in quantum networks. Proc. CISS2006,
pp.871-876, 2006.