Japanese / English

Detail of Publication

Text Language Japanese
Authors Masakazu Iwamura
Title A Quantum Algorithm for k-Nearest Neighbor Search
Journal TELECOM FRONTIER
Vol. 107
Reviewed or not Not reviewed
Month & Year May 2020
Abstract k近傍探索とは、検索質問データが与えられたとき、それに最も近いk個のデータをデータベースから探し出す問題である。この問題は、時間を掛けさえすれば必ず解ける。しかし、データベースの大規模化や高次元化に伴い、計算時間が大きくなってしまう。この問題を高速に解くために、探索過程に近似を導入し、探索誤りを許容するのが近似k近傍探索である。本研究では、従来用いられている計算機(古典的コンピュータ)ではなく、量子コンピュータで動作するk近傍探索手法の量子アルゴリズムを提案する。提案手法は、データ数がNのとき、O(√kN)の計算量で解を求めることができる。同じオーダーの計算量を持つ既存の量子アルゴリズムもあるが、提案手法は近似計算に適用できる可能性を持つ。
URL http://www.scat.or.jp/frontier/frontier107/mokuji_107.html
Back to list