Paper Abstract and Keywords |
Presentation |
2005-10-19 09:00
A quantum protocol to win the graph colouring game on all Hadamard graphs David Avis (McGill Univ.), Jun Hasegawa (Univ. of Tokyo/JST), Yosuke Kikuchi (JST), Yuuya Sasaki (Univ. of Tokyo) |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
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. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
graph colouring game / pseudo-telepathy / Hadamard graph / quantum chromatic number / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 105, no. 344, COMP2005-44, pp. 1-6, Oct. 2005. |
Paper # |
COMP2005-44 |
Date of Issue |
2005-10-12 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
Download PDF |
|
Conference Information |
Committee |
COMP |
Conference Date |
2005-10-18 - 2005-10-19 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Tohoku Univ. |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2005-10-COMP |
Language |
English (Japanese title is available) |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
A quantum protocol to win the graph colouring game on all Hadamard graphs |
Sub Title (in English) |
|
Keyword(1) |
graph colouring game |
Keyword(2) |
pseudo-telepathy |
Keyword(3) |
Hadamard graph |
Keyword(4) |
quantum chromatic number |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
David Avis |
1st Author's Affiliation |
McGill University (McGill Univ.) |
2nd Author's Name |
Jun Hasegawa |
2nd Author's Affiliation |
The University of Tokyo (Univ. of Tokyo/JST) |
3rd Author's Name |
Yosuke Kikuchi |
3rd Author's Affiliation |
ERATO QCI Project, JST (JST) |
4th Author's Name |
Yuuya Sasaki |
4th Author's Affiliation |
The University of Tokyo (Univ. of Tokyo) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-3 |
Date Time |
2005-10-19 09:00:00 |
Presentation Time |
35 minutes |
Registration for |
COMP |
Paper # |
COMP2005-44 |
Volume (vol) |
vol.105 |
Number (no) |
no.344 |
Page |
pp.1-6 |
#Pages |
6 |
Date of Issue |
2005-10-12 (COMP) |
|