アダマールグラフのグラフ彩色ゲームに対する量子プロトコル
スポンサーリンク
概要
- 論文の詳細を見る
本論文ではグラフ彩色ゲームについて述べる.グラフ彩色ゲームは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彩色可能であると検証者に信じこませられることがわかる.
- 社団法人電子情報通信学会の論文
- 2005-10-12
著者
-
長谷川 淳
東京大学大学院工学系研究科:(現)日新製鋼(株)
-
菊地 洋右
(株)科学技術振興機構今井量子計算機構プロジェクト
-
Avis David
Department Of Computer Science Mcgill University
-
菊地 洋右
独立行政法人科学技術振興機構今井量子計算機構プロジェクト
-
佐々木 勇也
東京大学大学院情報理工学系研究科コンピュータ科学専攻
-
長谷川 淳
東京大学大学院情報理工学系研究科コンピュータ科学専攻:独立行政法人科学技術振興機構今井量子計算機構プロジェクト
関連論文
- 無線マルチホップネットワークにおけるVoIP転送のための無音圧縮制御方式(ネットワーク)
- 無線マルチホップネットワークにおけるVoIP転送のための無音圧縮制御方式(ワイヤレス環境でのアプリケーション品質,P2P/アドホックネットワーク,画像符号化ストリーム技術,信頼性,一般)
- マルチホップVoIP転送のためのパケット連結・ネットワークコーディング方式に関する実験的検証(マルチホップ,メッシュネットワーク,ネットワーク符号化,無線通信一般)
- B-17-5 公衆自営連携コグニティブ無線アクセスネットワークのための自営アクセスネットワーク動的構成方式(B-17.ソフトウェア無線,一般セッション)
- B-21-19 パケット連結・ネットワークコーディングを用いたVoIP転送における効率的な再送方式(B-21.アドホックネットワーク,一般セッション)
- B-21-33 アドホックネットワークにおけるパケット結合方式の提案(B-21. アドホックネットワーク,一般セッション)
- B-21-17 多元接続方式(MM-SA)を用いた無線メッシュネットワークにおけるリアルタイム通信(2) : シミュレーションによる基本特性評価(B-21. アドホックネットワーク,一般セッション)
- B-21-16 多元接続方式(MM-SA)を用いた無線メッシュネットワークにおけるリアルタイム通信(1) : リアルタイム通信の課題とMM-SA方式の適用(B-21. アドホックネットワーク,一般セッション)
- アドホックネットワークにおけるVoIP向けトラヒック制御方式の提案(アプリケーション品質,モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- B-21-5 アドホックネットワークにおける端末グループ化による隠れ端末回避手法の提案(B-21.アドホックネットワーク,一般講演)
- M-010 転送リストを用いたフラディング方式の実証実験(M分野:ユビキタス・モバイルコンピューティング)
- 車車間通信における音声配信方法の提案(携帯端末,モバイルアプリケーション,モバイルコンピューティング)
- ABS-1-3 フラディングを用いた車車間情報共有アプリケーション実証実験(ABS-1,マルチホップ無線ネットワークとその応用,シンポジウム)
- B-21-45 アドホックネットワークにおける隠れ端末検知と回避手法(B-21.アドホックネットワーク,一般講演)
- アドホックネットワークにおける高トラヒックによる通信性能劣化改善方式の性能評価 (アドホックネットワーク)
- 転送リストを用いた高効率・ 低負荷フラッディング方式の提案
- 量子和回路の効率化とシミュレーションによるデコヒーレンス耐性の解析
- B-5-114 公衆自営連携コグニティブ無線アクセスネットワーク(II-b) : 優先度制御(B-5.無線通信システムB(ワイヤレスアクセス),一般セッション)
- 正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
- 正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
- MnO-SiO_2-MnS 系スラグの相平衡
- 826 Ti-6Al-2Sn-4Zr-6Mo 合金の超塑性(超塑性, 萌芽・境界技術, 日本鉄鋼協会第 110 回(秋季)講演大会)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
- ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
- ディジタル・ハーフトーニングへの数理工学的アプローチ(OR研究の最前線)
- マルチホップVoIP転送のための無音圧縮制御方式(モバイルネットワーク3)
- A Quantum Protocol to Win the Graph Colouring Game on All Hadamard Graphs(Discrete Mathematics and Its Applications)
- 辺に故障のあるバブルソートグラフのhamiltonian laceability
- バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
- 車車間通信における音声配信方法の提案(携帯端末,モバイルアプリケーション,モバイルコンピューティング)
- 整数分割の列挙(セッション3)
- アダマールグラフのグラフ彩色ゲームに対する量子プロトコル
- 二分決定グラフにおける量子計算能力と通信計算量の関連
- 水中用小型振動計測センサユニットの試作