量子コンピュータと量子計算 : 7.量子通信計算量理論 --花子から太郎へ--

全文

(1)特集. 7）量子通信計算量理論─花子から太郎へ. 量子コンピュータと量子計算. 7. 量子通信計算量理論 ─花子から太郎へ西村治道〔大阪府立大学理学系研究科〕レイモンドルディ〔日本 IBM 東京基礎研究所〕 1993 年の Yao による導入以降，量子通信計算量理論は量子計算量理論における重要なトピックの 1 つであり続けている．特に，ラウンド数制限のもとでの量子通信計算量理論は近年多くの興味深い結果が生み出されている．本稿では，量子通信計算量理論に関する近年の成果のいくつかを紹介する．. 通信計算量理論とは. である場合は使えない．実は，この一見非常に簡単そうな問題でさえ花子がデータそのものを送るより通信量を. 今日のインターネット時代において，利用可能なデー. 減らす方法はない．さらには，花子と太郎がお互いに情. タ量は日々巨大化していて，1 つの計算機にすべてのデ. 報のやり取りを行うことで何とかしようとしても，結局. ータを保存することは不可能である．それゆえ，何らか. 通信量を減らすことはできないことが知られている．. の問題を解決する上で，複数の計算機にまたがるデータ. このように書くと，通信プロトコルは大抵の問題で少. を必要とすることはそう珍しい話ではない．そのような. なくともどちらかの入力の長さ分だけの通信量を必要と. 状況において，問題を高速に解決する上で鍵となるのは，. し，あまり面白みのあることができないのではないかと. いかに計算機間の通信量を削減できるかにある．この. 考えられるかもしれない．実際，通信計算量理論は通信. ような分散されたデータを入力とする問題を解決するた. 量の下限を回路計算量の下限のような計算量理論などに. めに，複数の計算機が行う計算を通信プロトコルといい，. 応用することがより重要な一側面である．では，通信計. 必要な通信の量（通信計算量）を研究するのが，通信計算. 算量の上限はほとんど自明で研究意義がないのか，とい. 量理論. である．最も分かりやすい例として，2 つのデ. うとそうではない．特に，確率的通信プロトコル，つま. ータ x と y が 2 台の計算機に分散されていて，それらが. り乱数（ランダムな数）の使用のもとで少しの誤りを認. 等しいかどうかを判定する問題（等価性判定問題）を考え. めた通信プロトコルでは通信計算量が劇的に減少する場. よう．問題を考える上で計算機 1，計算機 2 とするので. 合がある．たとえば前述の等価性判定問題を再考しよう．. は味気ないので，データ x は花子が，データ y は太郎が. 前述の観察よりデータの長さが異なる場合はあまり通信. 6）. ☆1. 持つものとする. 6）. ．この場合，最も安易な方法は花子. 量を必要としないので，x および y の長さが共に n（つ. が x そのものを太郎に送ってしまうことである．しかし. まり uxu 5 uyu 5 n）である場合を考えよう．通常の誤りの. この方法は，データそのものを送るという意味で非常に. ない通信プロトコルではデータをそのまま送る以外なく，. 通信量的には非効率的な方法である．ではよりよい方法. n の通信計算量が必要である．ところが，確率的通信プ. は存在するのか？もし太郎のデータ y が x と違う長さ. ロトコルでは O(log n) という指数的に少ない通信計算量. であるなら，花子が彼女の x の長さを表すビット列を送. で解くことが可能となる．アイディアは，多少の誤りが. ることで，指数的に少ない通信量で正しく等価性判定問. 認められると，花子と太郎は自らのデータを少し冗長に. 題を解ける．しかし，この手は彼らのデータが同じ長さ. することで，花子と太郎のどのデータ内の対応するビッ. ☆1. トも同じかどうかを高確率で判定できる点にある．具体. 量子情報では Alice と Bob がお馴染みだが，本稿は日本語なので日本人に登場していただくことにしよう．. 的には，誤り訂正符号 E : {0, 1} → {0, 1} として，任意 n. m. IPSJ Magazine Vol.47 No.12 Dec. 2006. 1347.

(2) 特集：量子コンピュータと量子計算. の 2 つの符号語 E(x) と E(y) のハミング距離が (1 2 d )m 以上で m 5 cn （d と c は適当な定数）となるようなもの（た. data X. data Y. data X. data Y. とえば Justesen 符号）があるので，花子はランダムに選んだ i [ [m] 5 {1, 2,…, m} に対して E(x) の i 番目のビット Ei (x) と i そのものを太郎に送る．太郎は Ei (y)（これは花子が i を送るので計算可能）と Ei (x) が等しければ 1 （等しいという判断），等しくなければ 0（等しくないという判断）を出力する．この通信プロトコルは x 5 y の場合，どんな i に対しても Ei (x) 5 Ei (y) なので常に正しい答えを与える．また，x  y の場合，誤り訂正符号 E. No data. の取り方より Ei (x) 5 Ei (y) となる確率はせいぜい d であり，それゆえこの通信プロトコルの誤り確率は d である．誤り確率を e まで小さくしたければこの計算を O(log. 1 E. ). 回並列に行えばよく，その場合でも通信量は O(log. 1 E. ). 個のペア (i, Ei (x)) を送るためのビット長 O(log n)（e が定数である限り）で十分となる．一般的に通信計算量はラウンドの回数，つまり花子から太郎（または太郎から花子）への通信を 1 ラウンドとし. data X. data Y. 図 -1 通信プロトコルにおける通信の流れ．上から順にラウンド数に制限のない通信プロトコル，一方向通信プロトコル， SMP プロトコル．. た場合の回数に依存する．通常のネットワークでは同じ通信量でもラウンド数が多ければより多くの時間がかかることを鑑みると，効率的なのは 1 ラウンドの通信プロ. 方向通信プロトコルにおける量子通信の優位性を紹介す. トコルであり，一方向通信プロトコルと呼ばれる．たと. る．第 3 に，通信プロトコルにおける異なる量子的方法. えば上記の等価性判定問題に関する確率的通信プロトコ. の利用とその優位性を紹介する．最後に，量子通信計算. ルは一方向通信プロトコルである．さらに，一方向通信. 量理論における重要な基礎技術である量子ランダムアク. プロトコルの亜種として，次のような 3 者間の一方向通. セス符号を紹介する．. 信（以下，通常の一方向通信プロトコルと区別するため ☆2. に SMP. プロトコルと呼ぶ）に限定された場合の通信プ. ロトコルがある．花子と太郎がそれぞれ自分の入力に関. SMP プロトコルにおける量子通信の優位性. するビット列を第三者である次郎（彼は自分の入力を持. 1993 年に Yao は，通信においてビットのような古典. たない）に送って，太郎の代わりに次郎が計算結果を出. 情報を用いる代わりに量子ビットのような量子情報を用. 力する（図 -1）．このような通信プロトコルは中央集中. いる通信プロトコルの概念を提案した．量子通信を用い. 型ネットワークをイメージしている．ところが興味深い. たプロトコルでの通信計算量は量子通信路を通じて送ら. ことに，SMP プロトコルのもとでは等価性判定問題に. れる量子ビットの数であり，量子通信計算量と呼ばれる．. 対して指数的な通信計算量の削減を達成することができ. その比較上しばしば従来の通信計算量は古典通信計算. ず，Θ ( n ) の通信計算量を必要とすることが知られて. 量と呼ばれる．Yao の提案後，1998 年の Buhrman-Cleve-. いる．. Wigderson による平方的な通信量削減を与える問題や. その誕生以来，通信計算量理論は計算量理論における. 1999 年の Raz による指数的な通信計算量の削減を与え. 重要なトピックであり続けている．そのため，量子情報. る問題の発見によって，量子通信の通信プロトコルにお. および量子計算の研究が進むと，自然に量子の力を利用. ける有用性が明らかになった．そしてこれらの結果に劣. した通信計算量理論（量子通信計算量理論）が展開される. らないインパクトを与えたのが，2001 年の Buhrman ら. こととなった．以下では，量子通信計算量理論に関する. の等価性判定問題に対する通信プロトコルである．前. 4 つのトピックを紹介したい．第 1 に SMP プロトコル. 章で述べたとおり，等価性判定問題は SMP プロトコル. における量子通信利用の優位性を紹介する．第 2 に，一. のもとでは確率的プロトコルでさえ通信計算量 Θ ( n ). 6）. 3）. である．ところが Buhrman らは，量子通信を利用すれ ☆2. SMP は Simultaneous Message Passing の略である．. 1348. 47 巻 12 号情報処理 2006 年 12 月. ば SMP プロトコルのもとでさえ量子通信計算量 O(log.

(3) 7）量子通信計算量理論─花子から太郎へ. n) により高確率で等価性判定問題を解けることを示し. 2. 1. た．彼らの通信プロトコルは比較的シンプルだが，Shor のアルゴリズムとも Grover のアルゴリズムともまった. 3. く異なる．ここでは簡単に彼らの通信プロトコルを紹介したい．. 4. 彼らの通信プロトコルは，前章の等価性判定問題に対する確率的通信プロトコルのアイディアを利用している．誤り訂正符号 E を前章で与えたものと同一のものとす. 6. 5 7. る．このとき，花子と太郎は (log(m)11) 個の量子ビッ. 8. トからなる状態を表すベクトル uhx および uhy をそれぞれ次郎に量子通信路を通じて送る．ここで，任意の z に対して uhz はペア (i, Ei(z)) の量子的重ね合わせ，つまり. 図 -2 完全マッチング M の例：n 5 8 の場合で M 5 {(1, 6),(2, 4),(3, 5),(7, 8)}．. ベクトル uiuEi(x) 5 ui ⊗ uEi(x) の各係数が均等であるような線型結合 h z =. 1 m. の通信プロトコルを O(log. m. !. i. Ei ( x ). 1 E. ) 回並列で行えばよい．そ. のときの量子通信計算量は O(log. i=1. 1 E. ) 3 (log(m) 1 1) 5. であり，量子指紋 (quantum fingerprinting) と呼ばれる．. O(log n) である．. x 5 y のとき，uhx 5 uhy であり，x  y のとき，ベクト. この等価性判定問題に対する通信プロトコルを確率的. ル uhx とベクトル uhy の内積はせいぜい d m/m 5 d であ. 通信プロトコルに変形できないのかというのは自然な. ることに注目すると，次郎は 2 人から受け取った量子指. 疑問である．実際，ポイントとなっているのは花子はペ. 紋が同じか内積が d 以下かを高確率で判定する量子的手. ア (i, Ei(x)) のすべてを，太郎はペア (j, Ej(y)) のすべてを. 続きがあれば等価性判定問題を解くことに成功する．そ. 量子重ね合わせにして送っている部分であり，それら 2. のような量子手続きは以下の通りである．（1）次郎は 2. 人からの量子重ね合わせから i 5 j となるような部分の. 人から得た状態から状態 u0uhxuhy を準備し，最初の量. Ei(x) と Ej(y) の比較を可能にする方法にある．確率的通. 子ビット（すなわち u0）にアダマール変換 H を施す．こ. 信プロトコルでは重ね合わせのまま情報を送れない以上. のとき H は u0 を. 1 2. (u0 1 u1)，u1 を. 1 2. (u0 2 u1) に. いといけないが，そのようなペアのインデックス i と j. 変換するので， . 花子と太郎は個々にペア (i, Ei(x)) と (j, Ej(x)) を選択しなが合致する確率は指数的に小さい．この点において上記. 1 ^ 0 + 1 h hx hy 2. の通信プロトコルは量子状態特有の利点を最大に活かし. を得る．（2）次郎は最初の量子ビットが u1 の場合，uhx. たものである．. と uhy の順番を入れ替える（制御スワップ）．このとき， . 1 ^ 0 hx hy + 1 hy hx h 2. 一方向通信プロトコルにおける量子通信の優位性. を得る．（3）最初の量子ビットに H を施してから最初の. 前章では，SMP プロトコルに関する量子通信利用の. 量子ビットを標準基底 {u0, u1} で測定する．このとき，. 優位性を紹介したが，一方向通信プロトコルに関して古. 測定前の状態は. 典と量子の指数的ギャップを示すことは近年まで未解決. 1 2. u0(uhxuhy 1 uhyuhx) 1. 1 2. u1(uhxuhy 2 uhyuhx). であった．2004 年に Bar-Yossef ら. 2）. は以下の問題 HMn. であり，この状態の最初の量子ビットから 1 を得る確. (Hidden Matching) において，一方向通信プロトコルの通. 1 率はベクトル 2. (uhxuhy 2 uhyuhx) の長さの 2 乗，すなわ. 信計算量は量子のそれが古典よりも指数的に小さいこと. hx hy 2. である．この確率は x 5 y のとき 0 で，x. ち2 2 1. 2. 2  y のとき (1 2 d )/2 以上なので，0 を得たときに次郎. を示した．問題 HMn. は 2 人のデータが等しいと判定すればこの通信プロトコ. 花子のデータ：x [ {0, 1}. 2 ルの誤り確率は 1 より小さい定数 (1 1 d )/2 である．や. 太郎のデータ：[n]（で番号付けられた頂点）上の完全マ. はり誤り確率を十分小さな定数 e まで減らすには，こ. ッチング M（図 -2 参照のこと）. n. IPSJ Magazine Vol.47 No.12 Dec. 2006. 1349.

(4) 特集：量子コンピュータと量子計算. 出力：b 5 xi ⊕ xj かつ (i, j) [ M であるような組 (i, j, b). 題を考えよう．花子と太郎が事前に乱数を共有していれ. 問題 HMn を解く通信プロトコルは，以下のとおり非. ばペアのインデックス i を共同で選択できる．このとき，. 常にシンプルであるが，やはり量子重ね合わせという量. 前述の誤り訂正符号 E のもと Ei (x) と Ei (y) を次郎に送り，. 子特有の性質をうまく利用したプロトコルである．. 次郎はそれらが等しいかどうかをチェックすれば x 5 y かどうかを一定の確率で判定できる．よって，それを定. HMn に対する通信プロトコル（1）花子は量子状態 uc  5. 1 n. ! i (- 1 ). （2）太郎は量子状態 uc  を基底 $. 1 2. 数回並列的に繰り返せば高確率で等価性判定問題を解け xi. i を太郎に送る．. ^ s ! t h ^ s, t h d M .. (us 1 ut)（に対応する測定 1 値）を得た場合，(s, t, 0) を出力する．状態 2 (us 2 ut) を得た場合，(s, t, 1) を出力する．のもとで測定し，状態. 1 2. る．この場合の通信計算量はたかだか O(1) であり，事前共有された乱数がない場合の通信計算量 Q(. n )に. 比べはるかに優れていることが分かる．このように考えると，量子的に興味深いのは事前共有しているものが量子状態である場合である．1997 年に. 上記の通信プロトコルの成功確率が 1 であることは，以. Cleve と Buhrman は，花子と太郎があらかじめ量子状態. 下のように簡単に確かめられる．ある (i, j) [ M に対し. を共有するが使用可能な通信路は古典通信路である（つ. て uc  は（1）xi 5 xj の場合，ベクトル. まりビットしか送信できない）という設定のもと，その. （2）xi  xj の場合，ベクトル. 1 n. (ui 1 uj) を含み， (ui 2 uj) を含むことか 1 n. 量子状態のエンタングルメントを利用した通信プロトコ. ら，測定によって 1 つの枝 (i, j) に対して正しい組 (i, j, xi. ルの概念を考案した．それ以来，事前共有された量子状. ⊕ xj) を得る確率はそれらのベクトルの長さの 2 乗，す. 態を持つ通信プロトコルは，エンタングルメントを研. なわち 2/n である．M は [n] 上の完全マッチングである. 究する 1 つの方向として計算機科学の研究者だけでなく，. ため枝の数は n/2 であり，それゆえ正しい組を得る確. 量子情報理論の研究者からも注目を集めてきた．しかし. 率は 2/n 3 n/2 5 1 となる．また，この通信プロトコル. ながら，事前共有された量子状態を持つことがそのよう. の量子通信計算量は明らかに log n である．一方，HMn. な状態を持たない通信プロトコルに比べて大きな優位性. に関する古典通信計算量の下界は W(. を持つ問題の例は，なかなか見つからないままであった．. n ) であり，こ. れは上界と一致することが示されている．この下界の. この歴史はまさに，エンタングルメントという量子力学. アイディアのポイントとなっているのは，次のような. 特有の概念が情報理論的にも計算理論的にも未知な部分. 直感にある．太郎は彼が持つ完全マッチングの中の 1 つ. が多いことを如実に示す一例であった．そんな中，2006. (i, j) に対して，花子のデータの情報 xi ⊕ xj を見つけた. 年に Gavinsky ら. い．しかし，花子はどのような組を太郎が持つか知らな. 実を示した．ある問題において，量子状態が事前共有さ. い．よって，いわゆるバースデーパラドックスを当てに，. れた場合における通信プロトコルは，量子状態を事前共. O(. 有しない通信プロトコルよりも，指数的に通信計算量. 2）. n ) 個の組 (i', j') に対する xi' ⊕ xj' をランダムに選ん. は SMP プロトコルにおいて，次の事. 4）. で送るしかない．この直感は，情報理論的手法と完全マ. を減らすことができる．この問題 HPn (Hidden Parity) は，. ッチングのグラフ構造を利用して証明されている．. 以下のようであり HMn にヒントを得ている．. 量子通信以外の量子的方法の優位性. 問題 HPn. 花子のデータ：x [ {0, 1}. n/2. および [n] 上の完全マッチン. 最初の章では確率的通信プロトコルを用いると，等価. グの集合 M. 性判定問題の通信計算量が誤りのない通信プロトコルに. 太郎のデータ：y [ {0, 1}. 比べ指数的に小さくできることを紹介した．その通信プ. 出力： b1 5 x(i, j) および b2 5 yi ⊕ yj であるような組 (i, j,. ロトコルでは花子と太郎はお互い自らの乱数を個々に用. n. b1, b2)．ただし，x(i, j) は (i, j) に対応する番号を k 5 ki, j [. いていた．その一方で，彼らが共通の（つまり 2 人が参. [n/2] としたときのビット xk を表す．. 照できるような）乱数を用いる通信プロトコルも提唱さ. 実際，この問題は事前共有された量子状態 uf  5. れている．このような事前共有の乱数を認めた通信プロトコルは，ラウンド数に制限のない通信プロトコルや一. 1 2. !. id" 0,1,log n. i. i を使って，以下の通信プロトコル. 方向通信プロトコルでは，個々にしか乱数を使用できな. により古典通信計算量 O(log n)，成功確率 1 で解ける（解. い場合に比べあまり優位性を持たない．ところが，SMP. 析は彼らの論文を参照していただきたい）．. プロトコルでは大きな優位性を持つ．再び等価性判定問. 1350. 47 巻 12 号情報処理 2006 年 12 月. 4）.

(5) 7）量子通信計算量理論─花子から太郎へ. HPn に対する通信プロトコル（1）太郎は uf  を. 1 n. !i. J11. i (- 1 ) yi i に変換する．. j) とする）を得る．. J10. |−>. （2）花子は各枝 (i, j) [ M に対応する射影作用素 Eij 5 uiiu 1ujj u からなる測定を行い，測定結果（仮に (i,. |1>. |+>. J01. J00. （3）花子と太郎はそれぞれの log n 個の量子ビット上で. |0>. アダマール変換を行い，標準基底のもと測定を行う（花子と太郎の測定結果を仮に k, l とする）．（4）花子は i, j, k, x(i, j) を，太郎は l を次郎に送る．. （5）次郎は (i, j, x(i, j), (k 1 l) ? (i 1 j)) を出力する．ここで i, j [ [n] に対し，i ? j は i と j を log n ビットと見なしたときのドット積を表す．一方，Gavinsky らは HPn に対して，事前共有された量子状態を持たない場合，乱数を事前共有しても，量子. 図 -3 (2, 1, 0.85)–QRAC の符号化．量子状態 w x1x2 は x1x2 の符号化である．復号は第 1, 2 ビットに対してそれぞれ基底 {u0, u1} および {u1, u2} に関する測定によってなされる．. 通信を利用できても，高確率で解くために通信計算量が 1/3 少なくとも V((n/log n) ) であることを示した．この証. 明は次章で紹介するランダムアクセス符号の概念や半正. 現できるかもしれないと考え，QRAC の概念を導入した．. 定値計画法による状態識別の困難性の量的特徴付けを利. (n, m, p)–QRAC とは，以下のように x [ {0, 1}n を m 個の. 用しており本稿では紹介しない．しかし，上記の通信プ. 量子ビットの量子状態 r x に写す関数である．任意の i [. ロトコルにおいて事前共有された量子状態 uf  が存在し. [n] に対して，r x から xi を確率 p 以上で得るような測定. ない場合に同じようなことが可能かを考えてみると，通. が存在する．その定義から QRAC は n ビットの文字列. 信計算量が指数的に増えそうなことは感じていただける. を m 個の量子ビットに埋め込む符号であると考えられ. のではないかと思う．. るが，Holevo 限界とは矛盾しない．なぜなら，第 i ビットを取り出す観測による復号では，取り出せるビットの. 量子ランダムアクセス符号（QRAC）. 数が 1 個しか保証されないからである．. 量子通信計算量理論で幅広く使われている手法の 1 つ. なものであろうか．Ambainis らの論文. は量子ランダムアクセス符号（以下，QRAC．Quantum. m に関する次の下限が与えられている．任意の p . 1/2. Random Access Coding の略）である．たとえば，量子. に対して，(n, m, p)–QRAC が存在すれば m $ (1 2 H(p))n. 通信計算量の下限については量子通信計算量と VC 次. が成立する．ここで，H(p) 5 2p log p 2 (1 2 p) log(1 2. 元の関係や前章の Gavinsky らの結果などに使用されて. p) である．逆に，m $ (1 2 H(p))n 1 O(log n) のもと，(n,. いる．また，上限については直接の関係がないものの，. m, p)–QRAC が存在することが知られており 1），特にそ. 問題 HMn のアイディアは局所的復号可能符号 (Locally. のような QRAC は古典的符号および復号で達成可能で. Decodable Codes) に由来するものであり，この局所的復. ある．このため，漸近的には古典通信でも量子通信でも. 号可能符号の結果も QRAC に深く関係する．そのほか. QRAC を実現する上での差はない．. に，QRAC はアドバイス付き量子計算の解析や量子オー. 一方，m が小さい場合に関しては量子通信は古典通. さて，(n, m, p)–QRAC の存在に関する条件はどのよう. 1）. ☆3. トマトンなどにも幅広い応用を持っている. ．. 1）. では，以下の. 信にはできないことを可能にする．m 5 1 に対しては. 量子情報理論で有名な Holevo 限界により，n ビット. Ambainis らは (2, 1, 0.85)–QRAC が可能なことを観察し，. を伝送するのに n 個の量子ビットが必要と知られている．. さらにこの事実は Chuang によって (3, 1, 0.79)–QRAC の. よって，その事実だけを鑑みると量子通信路の使用によ. 構築へと拡張された．これらは 2 つないし 3 つの基底. る利得はないように思える．しかし，Ambainis ら. に関する測定を各ビットに対する復号プロセスとして. 1）. は，. 受信者の必要な 1 ビットのみが伝送されればよいという. 用意し，量子ビットに対する幾何的描像である Bloch 球. 条件なら，量子ビットは古典ビットにできないことを実. の中にそれらの復号プロセスのどれからも正しい値が. ☆3. 復号できるように均等に符号を配置することによって. Google によれば，QRAC 段階で 43 本である．. を参照する論文の合計数は 2006 年 9 月の. 1）. 得られている．(2, 1, 0.85)–QRAC は図 -3 によって与え IPSJ Magazine Vol.47 No.12 Dec. 2006. 1351.

(6) 特集：量子コンピュータと量子計算. られる．たとえば 10 の符号化 w 10 は u1 と u1 5 (u0 1 u1)/ 2 の中間にあり，第 1 ビット 1 を得るためには標準基底 {u0, u1} で測定することで cos. 2 r 8. . 0.85 の確率. で 1 を得る．同様に第 2 ビット 0 を得るには基底 {u1, u2} で測定すればよい（ただし，u2 5 (u0 2 u1)/ 2 である）．1 ビットによる古典的な符号では 0.5 を超える成功確率さえ不可能であるため，これらの符号化は. 誤りなし. ラウンド制限なし n. 一方向通信 n. SMP 2n. Q(log n) Q(log n). Q(log n) Q(log n). Q( n ) Q(log n). 確率的量子的. 表 -1 等価性判定問題に対する通信計算量．n は花子と太郎のデータの長さを表す．いずれも 2 人は乱数または量子状態を事前共有しないものとする．量子的は量子通信を使った場合の量子通信計算量を意味する．. 量子通信のこのタスクにおける優位性を示している．では，1 個の量子ビットで何ビットの QRAC まで可能. 子計算量理論において重要な課題の 1 つである．一方. であろうか？このことに関して以前の下限は，十分. 向通信プロトコルに関する通信計算量に関して，SMP. 小さい e . 0 に対しての (n, 1, 1/2 1 e )–QRAC に対する. プロトコルに対する Gavinsky らの結果のようなギャ. 限界が自明なものとなって，有意な限界を得ることはで. ップが可能か？またラウンド数に制限がない場合は. きない．しかし，最近の研究によって e . 0 がどんなに. どうか？. 1）. 小さくても 4 ビットの QRAC は不可能なことが明らかになった：任意の p . 1/2 に対して，(4, 1, p)–QRAC は存在しない．この結果は (2, 1, 0.85)–QRAC や (3, 1, 5）. 0.79)–QRAC の存在を考えると意外なものであるといえる．さらに文献 5）では一般の m に対しても同様に (m, n, . 1/2)–QRAC が不可能となるような m が存在することを示している．その m の値は n に関して指数的である 2n ため (m 5 2 )，実際には n の多項式程度ですでに不可. 能となるのではないかと考えるかもしれないが，逆に. (2V(n), n, . 1/2)–QRAC の存在は通信計算量理論との関連より示されている．. 今後残された課題. 参考文献 1）Ambainis, A., Nayak, A., Ta-shma, A. and Vazirani, U. : Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata, Proc. 31st STOC, pp.376-383 (1999). Journal version appeared in J. ACM, Vol.49, pp.496-511 (2002). 2）Bar-Yossef, Z., Jayram, T. S. and Kerenidis, I. : Exponential Separation of Quantum and Classical One-way Communication Complexity, Proc. 38th STOC, pp.128-137 (2004). 3）Buhrman, H., Cleve, R., Watrous, J. and de Wolf., R. : Quantum Fingerprinting, Phys. Rev. Lett., Vol.87, Article No.167902 (2001). 4）Gavinsky, D., Kempe, J., Regev, O. and de Wolf, R. : Bounded-error Quantum State Identification and Exponential Separations in Communication Complexity, Proc. 40th STOC, pp.594-603 (2006). 5）Hayashi, M., Iwama, K., Nishimura, H., Raymond, R. and Yamashita, S. : (4, 1)-quantum Random Access Coding Does Not Exist ─ One Qubit Is Not Enough to Recover One of Four Bits, New J. Phys., Vol.8, Article No.129 (2006). 6）Kushilevitz, E. and Nisan, N. : Communication Complexity, Cambridge University Press (1997). （平成 18 年 10 月 30 日受付）. 本稿では量子通信計算量理論について一方向通信プロトコルと SMP プロトコルを中心に近年得られた研究成果のいくつかを紹介した．表 -1 は本稿で主に取り扱った等価性判定問題の通信計算量を表している．最後に，量子通信計算量理論における今後の研究テーマ・未解決問題について述べる．（1）等価性判定問題のようにデータに対して解が常に一意に存在するような問題は全域関数と呼ばれ，理論的興味としても他の理論への応用としても重要視されている．しかし，全域関数における量子通信計算量と古典通信計算量の違いに関して現時点では，複数ラウンドの通信プロトコルの場合さえ量子と古典通信計算量の最大のギャップは平方的でしかない．一方向通信プロトコルに限ると有意なギャップは与えられていない．全域関数においてこれらを超えるギャップが存在するか？（2）本稿で述べた通り，事前共有された量子状態によるエンタングルメントの量子計算における有用性は，量. 1352. 47 巻 12 号情報処理 2006 年 12 月. 西村治道 [email protected] 2001 年名古屋大学大学院人間情報学研究科博士課程修了．2006 年より大阪府立大学理学系研究科講師．量子計算および計算量理論の研究に従事．学術博士．レイモンドルディ [email protected] 2006 年京都大学大学院情報学研究科博士課程修了．同年より日本 IBM 東京基礎研究所（TRL）の研究員．量子計算とアルゴリズムの研究に従事．情報学博士．.

(7)