| 講演抄録／キーワード |
| 講演名 |
2005-10-19 09:00
アダマールグラフのグラフ彩色ゲームに対する量子プロトコル
David Avis（McGill Univ.）・長谷川 淳（東大）・○菊地洋右（JST）・佐々木勇也（東大） |
| 抄録 |
（和） |
本論文ではグラフ彩色ゲームについて述べる．グラフ彩色ゲームは
pseudo-telepathyの一つであり，二人の証明者がグラフ$G$が$c$彩色可能で
あると検証者を信じこませるというものである．ここで，$c$は$G$の彩色数
よりも小さい整数とする．
そして，証明者が検証者を信じこませることができれば証明者の勝ちとなる．
証明者が古典情報のみを共有する場合は証明者は勝つことができないが，
エンタングルメントを証明者が共有する場合は勝つことができる場合がある．
エンタングルメントの共有を許すか許さないかで勝敗に差が生じる知られている
最小のグラフは
Galliard, Tapp, Wolfによって発見され，$32,768$頂点の頂点からなるグラフである．
このグラフはアダマールグラフ$G_N$の連結成分であり，$N=c=16$とした場合である．
彼らのプロトコルは$N$が$2$のべきという制約がある．
ここでは全てのアダマールグラフに適用できるプロトコルを提案する．
我々のプロトコルとFranklの結果から，$G_{12}$の$1,609$頂点からなる任意の
誘導部分グラフに対して$c=12$の場合，エンタングルメントの共有を許した場合
証明者は勝つことができる．この$G_{12}$, $c=12$の場合が勝敗に差が生じる
最小のアダマールグラフである．
さらに，Frankl, Rodlの結果と我々の結果から証明者が全ての十分大きな
アダマールグラフ$G_N$に対して$N$彩色可能であると
検証者に信じこませられることがわかる． |
| （英） |
This paper deals with graph colouring games, an example of pseudo-telepathy,
in which
two provers can convince a verifier
that a graph $G$ is $c$-colourable
where $c$ is less than the chromatic number of
the graph.
They win the game if they convince the verifier.
It is known that the players cannot win if they
share only classical information,
but they can win in some cases by sharing entanglement.
The smallest known graph where the players win in the quantum setting, but not in the classical setting,
was found by Galliard, Tapp and Wolf and has 32,768 vertices.
It is a connected component of the Hadamard graph $G_N$ with $N=c=16$.
Their protocol applies only to Hadamard graphs where $N$ is a power of 2.
We propose a protocol that applies to all Hadamard graphs. Combined with a result of Frankl,
this shows that the players can win on any induced subgraph of $G_{12}$ having 1609 vertices, with $c=12$.
Combined with a result of Frankl and Rodl, our result shows that all sufficiently large Hadamard graphs
yield pseudo-telepathy games. |
| キーワード |
（和） |
グラフ彩色ゲーム / pseudo-telepathｙ / アダマールグラフ / 量子彩色数 / / / / |
| （英） |
graph colouring game / pseudo-telepathy / Hadamard graph / quantum chromatic number / / / / |
| 文献情報 |
信学技報, vol. 105, no. 344, COMP2005-44, pp. 1-6, 2005年10月. |
| 資料番号 |
COMP2005-44 |
| 発行日 |
2005-10-12 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
|