A Quantum Algorithm for k-Nearest Neighbor Search
| Language | Japanese |
|---|---|
| Type | Surveys and Articles |
| Authors | Masakazu Iwamura |
| Title | A Quantum Algorithm for k-Nearest Neighbor Search |
| Journal | TELECOM FRONTIER |
| Vol. | 107 |
| Reviewed | Not reviewed |
| Date | May 2020 |
| Research fields | Quantum Computing, Nearest Neighbor Search |
| URL | http://www.scat.or.jp/frontier/frontier107/mokuji_107.html |
| Key | Iwamura2020_TELECOM (id=1746) |
Abstract
k近傍探索とは、検索質問データが与えられたとき、それに最も近いk個のデータをデータベースから探し出す問題である。この問題は、時間を掛けさえすれば必ず解ける。しかし、データベースの大規模化や高次元化に伴い、計算時間が大きくなってしまう。この問題を高速に解くために、探索過程に近似を導入し、探索誤りを許容するのが近似k近傍探索である。本研究では、従来用いられている計算機（古典的コンピュータ）ではなく、量子コンピュータで動作するk近傍探索手法の量子アルゴリズムを提案する。提案手法は、データ数がNのとき、O(√kN)の計算量で解を求めることができる。同じオーダーの計算量を持つ既存の量子アルゴリズムもあるが、提案手法は近似計算に適用できる可能性を持つ。
Files
- …
Export this publication
Format definition
How to write the definition
Insert a field with braces like {authors}. A part enclosed in [ ... ] is omitted entirely when any field inside it is empty. Available fields:
{authors}{authors_and}{authors_ja}{authors_ja_tight}{authors_en}{authors_en_and}{authors_tight}{first_author}{title}{title_ja}{title_en}{journal}{journal_ja}{journal_en}{book_title}{volume}{number}{series}{presen_id}{pages}{pp}{num_pages}{year}{month}{month_en}{month_short}{ym}{date}{date_ja}{date_en}{publisher}{address}{location}{review}{review_ja}{review_en}{reviewed_mark}{presen_type}{type}{type_label}{doi}{url}{key}{awards}