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

• Following file is available.
1. iwamura.pdf (446.6KB)
• Entry for BibTeX

  @Article{Iwamura2020,
    author =	{Masakazu Iwamura},
    title =	{A Quantum Algorithm for k-Nearest Neighbor Search},
    journal =	{TELECOM FRONTIER},
    year =	2020,
    month =	may,
    volume =	{107},
    URL =		{http://www.scat.or.jp/frontier/frontier107/mokuji_107.html}
  }
  
  
  

Back to list