通信複雑性

通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。

もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。

この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。

形式的定義

$f$: X $\times$ Y $\rightarrow$ Z としたとき、一般に $X=Y=\{0,1\}^n$ および $Z=\{0,1\}$ と仮定する。アリスは n ビットの文字列 $x$ $\in$ X を持ち、ボブは n ビットの文字列 $y$ $\in$ Y を持つ。一度に 1ビットずつ両者間で通信を行い（何らかの通信プロトコルが適用される）、アリスとボブは最終的にいずれかが $f(x,y)$ の値を計算できるようにしたい。取り決めとして、一方で答えが判明したらもう一方にあと 1ビットの通信をするだけで全通信が完了するものとする。この通信プロトコルの最悪の通信複雑性（$D(f)$ で表される）は次のように定義される。

$D(f) =$ アリスとボブの間で交換されるビット数の最悪ケースの最小値

ここで関数 $f$ を行列 $A$（入力行列と呼ぶ）として考えるのが便利である。この行列の行は $x$ $\in$ X に対応して並んでおり、列は $y$ $\in$ Y に対応して並んでいる。入力行列の各要素は $A_{\mathrm{x,y}}=f(x,y)$ である。初期状態でアリスもボブも行列 A 全体を知っている（つまり、両者は関数 $f$ を知っている）。そうすると、関数の値の計算問題は対応する行列の要素を選び取る問題に変換される。この問題はアリスかボブのどちらかが $x$ と $y$ の両方を知った時点で答えがわかる。通信を開始するとき、答えとしてありうるのは行列の全要素なので $n^2$ 個存在する。その後、互いに 1ビットずつ通信すると、解ではあり得ない行や列が除外されていく。

より形式的に表現すると、集合 R $\subseteq$ X $\times$ Y があり、$(x_1,y_1)$ $\in$ R かつ $(x_2,y_2)$ $\in$ R のとき常に $(x_1,y_2)$ $\in$ R ならば、R を長方形であるという。また、R を R = M $\times$ N （ただし、M $\subseteq$ X かつ N $\subseteq$ Y）であるような A の部分行列と見ることもできる。既に $k$ ビットの情報をやり取りした状態を考えて見よう。ある $h$ $\in$ $\{0,1\}^k$ について、次のように行列が定義される。

$T_{\mathrm{h}} = \{ (x, y) :$ 入力 $(x , y)$ でやり取りされた k ビットが $h$ である}

ここで、$T_{\mathrm{h}}$ $\subseteq$ X $\times$ Y であり、$T_{\mathrm{h}}$ は長方形であると同時に A の部分行列である。

例: EQ

ここでは、アリスとボブが同じ文字列を持っているかどうかを決定する問題を例として示す。つまり、$x$ と $y$ が等しいかどうかを判定しようということである。$x$ と $y$ が完全に等しいことを確認するには最悪ケースで $n$ ビットの通信が常に必要になることは証明するのも簡単である。$x$ と $y$ がそれぞれ 3ビットという簡単な場合を考えて見よう。この場合の等価関数は下記のような行列で表される。行はありうべき $x$ の値が並び、列には同様に $y$ が並ぶ。

EQ	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

見ての通り、この関数は $x$ と $y$ が等しい場所（対角線上）だけで 1 となる。1 ビット通信する毎に可能性が半分に分割されていく。$y$ の最初のビットが 1 であると知っている場合、列の半分だけを考慮すればよい（$y$ は 100, 101, 110, 111 のいずれかになる）。

定理: $D(EQ) = n$.

証明。$D(EQ) \leq n-1$ と仮定する。その場合、同じ履歴 $h$ を共有する $(x, x)$ と $(x', x')$ が存在する。この履歴は長方形を定義するので、$f(x, x')$ も 1 でなければならない。定義から $x \neq x'$ であるが、等しいということは $a = b$ であるような $(a, b)$ を意味する。従って矛盾する。直感的に $n$ より小さい $D(EQ)$ があるなら、1つより多い要素を持つ EQ 行列の長方形が定義できるはずである。その長方形の全要素は 1 でなければならず、それによって ractangle が 1 であると言うことができる。しかし、そのような等価行列の長方形は存在しえない。

乱択通信複雑性

上述の定義では、通信は決定論的に行われると見なしている。両者が乱数発生器にアクセスする場合、$f$ の値をなるべく少ない通信量で決定することはできるだろうか？ ヤオは彼の論文[1979]で乱択通信複雑性を定義することでこの問題の回答を与えた。

関数 $f$ のための乱択プロトコル $R$ は、以下の両側誤りを持つ。

$\Pr[R(x,y) = 0] \ge \frac{1}{2}, \textrm{if }\, f(x,y) = 0$

$\Pr[R(x,y) = 1] \ge \frac{1}{2}, \textrm{if }\, f(x,y) = 1$

乱択プロトコルは通常の入力以外に追加のランダム列を使用する決定論的プロトコルである。これには二種類のモデルがある。両者が事前に同じランダム列を共有している「公開ランダム列」と、一方が生成して他方に通信によって伝える必要のある「秘密ランダム列」である。後に説明する定理によれば、秘密ランダム列プロトコルで本来より O(log n) のビットを追加することで公開ランダム列プロトコルをシミュレート可能である。

乱択複雑性とは単にこのようなプロトコルで交換するビット数として定義される。

乱択プロトコルを片側誤りを持つような形式で定義することもでき、それに従って複雑性も同様に定義される。

例: EQ

再び、EQ の例である。確実性が求められないなら、アリスとボブは等しいかどうかの判定を O(log n) 個のメッセージで行うことができる。次のようなプロトコルを考える。アリスとボブは同じランダム列 $z \in \{0,1\}^n$ にアクセスできるものとする。アリスは $z \cdot x$ を計算し、そのビット（b と呼ぶ）をボブに送信する。なお、$(\cdot)$ はGF(2)のドット積である。ボブは b と $z \cdot y$ を比較する。もし等しいならボブは x と y が等しいと言う事ができる。

明らかに $x = y$ なら $z \cdot x = z \cdot y$ であり、従って $Prob_z[Accept] = 1$ である。x と y が等しくない場合でも $z \cdot x = z \cdot y$ である可能性はあり、その場合ボブは答えを間違う。これはどんなとき発生するだろうか？

x と y が等しくない場合、それらの一部の位置で以下のように値が異なっているはずである:

$x = c_1 c_2 \ldots p \ldots p' \ldots x_n$
$y = c_1 c_2 \ldots q \ldots q' \ldots y_n$
$z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n$

$x$ と $y$ が等しいなら、$z_i * x_i = z_i * c_i = z_i * y_i$ であり、これによりドット積も等しくなる。従って、等しい項は無視して $x$ と $y$ が異なる部分だけを注目すればよい。さらに、ドット積が等しいかどうかに関わらず、ビット $x_i$ とビット $y_i$ を入れ替えることができる。つまり、$x$ に 0 であるビットを集め、$y$ に 1 であるビットを集めるよう入れ替えを行うこともできる。

$x' = 0 0 \ldots 0$
$y' = 1 1 \ldots 1$
$z' = z_1 z_2 \ldots z_{n'}$

この場合、$z' \cdot x' = 0$ および $z' \cdot y' = \Sigma_i z'_i$ となる。問題は、$\Sigma_i z'_i = 0$ であるようなランダム列 $z'$ が存在する可能性である。各 $z'_i$ は $0$ である可能性と $1$ である可能性が同じであるため、これを満足する文字列である可能性は単に $1/2$ となる。以上より、$x$ と $y$ が等しくない場合、$Prob_z[Accept] = 1/2$ となる。アルゴリズムを繰り返すことによって、その正確性を上げていくことが可能である。これは、乱択通信アルゴリズムの要求にも合っている。

以上により、「アリスとボブが n ビットのランダム列を共有した場合」に互いに 1 ビットを送ることで $EQ(x,y)$ を計算できることを示した。次節では、n ビットのランダム列を共有するのと同程度に O(log n) ビットのやり取りで目的を達成する方法を示す。それにより、EQ が O(log n) 個のメッセージで計算できることを示す。

公開硬貨と秘密硬貨

両者がランダム列を共有できれば（共有ランダム列プロトコル）、乱択プロトコルを作成するのは簡単である。ランダム列を共有しない場合でも（秘密ランダム列プロトコル）、小さな通信コストで乱択プロトコルを構築することが可能である。n ビットの文字列を使った共有ランダム列乱択プロトコルは、追加の O(log n) ビットの通信を行う秘密ランダム列プロトコルでシミュレート可能である。

直感的に、若干の誤りの増加を伴えば十分なランダム性を持った文字列の集合で乱択プロトコルを実行することができる。この集合は事前に両者で共有しておく。従って、アリスとボブはその集合のうち、どの文字列を使用するかに関して合意すればよい。このとき、文字列の集合は選択のための通信を効率的に行うためにも最小限でよい。形式的な証明は以下の通り。

最大エラー率 0.1 の乱択プロトコル P を考える。$R$ は長さ $n$ の文字列が $100n$ 個存在する集合であり、各文字列には $r_1, r_2, ..., r_{100n}$ と番号が振られている。$R$ を使った新たなプロトコル $P'_R$ は、無作為に $r_i$ 番の文字列を選択した上で、それを共有ランダム列として P を実行する。$r_i$ を選択するのに必要な通信ビット数は O(log 100n) = O(log n) である。

入力 $(x,y)$ について、$P$ と $P'_R$ が正しい値を得る確率をそれぞれ $p(x,y)$ と $p'_R(x,y)$ と定義する。

ある固定の $(x,y)$ について、Hoeffdingの不等式を使うと、次のような式が得られる:

$\Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) < 2^{-2n}$

従って、$(x,y)$ を任意とした場合、次のようになる:

$\Pr_R[\exists (x,y):\, |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] < \sum_{(x,y)} 2^{-2n} = 1$

最後の等号は、$(x,y)$ の組み合わせが $2^{2n}$ 個あるからである。全ての $(x,y)$ について以下が成り立つ $R_0$ が存在する。

$|p'_{R_0}(x,y) - p(x,y)| < 0.1$

$P$ の最大エラー率は 0.1 であることから、$P'_{R_0}$ のエラー率は最大で 0.2 となる。

量子通信複雑性

量子通信複雑性は、分散計算に量子効果を適用して通信縮小を定量化しようという試みである。

少なくとも3種類の通信複雑性の量子化手法が提案されている。詳しくは G. Brassard の調査結果を参照（参考文献）。

第一のモデルは量子ビット通信モデルである。これは通信に従来的な手段ではなく、量子通信を用いるものであり、例えば光ファイバー上で光子をやり取りする。

第二のモデルでは、通信は従来的なビットで行われるが、プロトコルの一部として無制限の量子もつれ状態を操作可能とするものである。両者のもつれ状態を測定することにより、分散計算での通信を減らすことができる。

第三のモデルでは量子ビット通信に加えて、過去に共有されたもつれ状態へのアクセスができるとするものだが、3つのモデルの中では最も研究が進んでいない。

未解決の問題

0/1 入力行列 $M_f=[f(x,y)]_{x,y\in \{0,1\}^n}$ について、$f$ を決定するのにやり取りが必要な最小ビット数の最悪ケース $D(f)$ は、行列 $M_f$ の階数の対数が下限となっている。対数階数予想（log rank conjecture）によれば、$M_f$ の通信複雑性 $D(f)$ の上限は、$M_f$ の階数の対数のべき乗である。D(f) の上限と下限が $(M_f)$ の階数の対数の多項式であることから、D(f) は $(M_f)$ の階数の対数に多項式的に関連していると考えられる。行列の階数は、そのサイズに対する多項式時間で計算可能であるため、通信複雑性の上限は多項式時間で計算可能と考えられる。ただし、行列のサイズは入力文字列の長さに対して指数的に増加する。

乱択プロトコルでは、やり取りするビット数の最悪ケース R(f) は以下の式に多項式的に関連すると推測される:

$\min(\textrm{rank}(M'_f): M'_f\in \mathbb{R}^{2^n\times 2^n}, (M_f - M'_f)_\infty\leq 1/3)$.

このような対数階数予想は、行列の通信複雑性の問題を行列の線形独立な行（または列）の問題に帰着させるという点で有意義である。これは通信複雑性問題の本質を明らかにする。例えば、上述の EQ の場合でもそうだが、入力が等しいかどうかを判定するために、入力が行列のどの要素に対応するかを解明する問題に帰着させていたのであった。

参考文献

• Kushilevitz, E. and N. Nisan. Communication complexity. Cambridge University Press, 1997.
• Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005
• Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory. Steven Rudich and Avi Wigderson, eds. American Mathematical Society Institute for Advanced Study, 2004. 129-137.
• A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209-213, 1979. 14
• I. Newman, Private vs. Common Random Bits in Communication Complexity, Information Processing Letters 39, 1991, pp. 67-71.