通信複雑性
量子通信複雑性は、分散計算に量子効果を適用して通信縮小を定量化しようという試みである。
少なくとも3種類の通信複雑性の量子化手法が提案されている。詳しくは G. Brassard の調査結果を参照(参考文献)。
第1のモデルは量子ビット通信モデルである。これは通信に従来的な手段ではなく、量子通信を用いるものであり、例えば光ファイバー上で光子をやり取りする。
第2のモデルでは、通信は従来的なビットで行われるが、プロトコルの一部として無制限の量子もつれ状態を操作可能とするものである。両者のもつれ状態を測定することにより、分散計算での通信を減らすことができる。
第3のモデルでは量子ビット通信に加えて、過去に共有されたもつれ状態へのアクセスができるとするものだが、3つのモデルの中では最も研究が進んでいない。
f {\displaystyle f} : X × {\displaystyle \times } Y → {\displaystyle \rightarrow } Z としたとき、一般に X = Y = { 0 , 1 } n {\displaystyle X=Y=\{0,1\}^{n}} および Z = { 0 , 1 } {\displaystyle Z=\{0,1\}} と仮定する。アリスは n ビットの文字列 x {\displaystyle x} ∈ {\displaystyle \in } X を持ち、ボブは n ビットの文字列 y {\displaystyle y} ∈ {\displaystyle \in } Y を持つ。1回につき1ビットずつ両者間で通信を行い(何らかの通信プロトコルが適用される)、アリスとボブは最終的にいずれかが f ( x , y ) {\displaystyle f(x,y)} の値を計算できるようにしたい。取り決めとして、一方で答えが判明したらもう一方にあと 1ビットの通信をするだけで全通信が完了するものとする。この通信プロトコルの最悪の通信複雑性( D ( f ) {\displaystyle D(f)} で表される)は次のように定義される。
D ( f ) = {\displaystyle D(f)=} アリスとボブの間で交換されるビット数の最悪ケースの最小値
ここで関数 f {\displaystyle f} を行列 A {\displaystyle A} (入力行列と呼ぶ)として考えるのが便利である。