Japanese / English

文献の詳細

論文の言語 日本語
著者 岩村雅一
論文名 k近傍探索のための量子アルゴリズム
論文誌名 TELECOM FRONTIER
Vol. 107
査読の有無
年月 2020年5月
要約 k近傍探索とは、検索質問データが与えられたとき、それに最も近いk個のデータをデータベースから探し出す問題である。この問題は、時間を掛けさえすれば必ず解ける。しかし、データベースの大規模化や高次元化に伴い、計算時間が大きくなってしまう。この問題を高速に解くために、探索過程に近似を導入し、探索誤りを許容するのが近似k近傍探索である。本研究では、従来用いられている計算機(古典的コンピュータ)ではなく、量子コンピュータで動作するk近傍探索手法の量子アルゴリズムを提案する。提案手法は、データ数がNのとき、O(√kN)の計算量で解を求めることができる。同じオーダーの計算量を持つ既存の量子アルゴリズムもあるが、提案手法は近似計算に適用できる可能性を持つ。
URL http://www.scat.or.jp/frontier/frontier107/mokuji_107.html
一覧に戻る