講演名	2004-07-28 完全グラフ上での量子ランダムウォークによる検索(フレッシュマンセッション)(フレッシュマン,一般) 秋葉 喜一郎, 宮寺 隆之, 大矢 雅則,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	N個のデータの中から古典コンピュータを用いて特定のデータを探すのに平均N/2の試みが必要であるので,検索するのにO(N)の時間がかかった.ところが,量子ランダムウォークによる検索を行ったとき、それを完全グラフ上で行うとO(√)の時間で検索することができる.しかし,検索の際に誤差が生じてしまった場合,検索結果にどのような影響を与えるのだろうか.本研究では,完全グラフ上で量子ランダムウォークによる検索を行う際に誤差が生じたとき,検索結果にどのような影響を与えるのかについて調べる.まず,量子ランダムウォークによる検索が完全グラフ上ではどのようになるかについて述べ,そして検索の際に誤差が生じた場合,検索結果にどのような影響を与えるのかについて述べる.
抄録(英)	It is well-known that searching one particular data out of TV data requires a classical computer to run O(N) steps. Recently, on the other hand, a novel algorithm using a so-called quantum walk was proposed and shown to take only O(√) steps. However, if we consider its realization, effects of unavoidable error should be taken into account. We investigate how the various types of errors give an influence upon the result of the searching algorithm on the complete graph.
キーワード(和)	量子アルゴリズム / 量子ランダムウォーク / 完全グラフ
キーワード(英)	Quantum Algorithm / Quantum Walk / Complete Graph
資料番号	IT2004-17
発行日

研究会情報
研究会	IT
開催期間	2004/7/21(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Information Theory (IT)
本文の言語	JPN
タイトル（和）	完全グラフ上での量子ランダムウォークによる検索(フレッシュマンセッション)(フレッシュマン,一般)
サブタイトル（和）
タイトル（英）	Search by Quantum Walk on the Complete Graph
サブタイトル（和）
キーワード(1)（和/英）	量子アルゴリズム / Quantum Algorithm
キーワード(2)（和/英）	量子ランダムウォーク / Quantum Walk
キーワード(3)（和/英）	完全グラフ / Complete Graph
第 1 著者 氏名（和/英）	秋葉 喜一郎 / Kiichiro AKIBA
第 1 著者 所属（和/英）	東京理科大学理工学部情報科学科 Department of Information Sciences, Tokyo University of Science
第 2 著者 氏名（和/英）	宮寺 隆之 / Takayuki MIYADERA
第 2 著者 所属（和/英）	東京理科大学理工学部情報科学科 Department of Information Sciences, Tokyo University of Science
第 3 著者 氏名（和/英）	大矢 雅則 / Masanori OHYA
第 3 著者 所属（和/英）	東京理科大学理工学部情報科学科 Department of Information Sciences, Tokyo University of Science
発表年月日	2004-07-28
資料番号	IT2004-17
巻番号（vol）	vol.104
号番号（no）	228
ページ範囲	pp.-
ページ数	6
発行日