文献の詳細
| 論文の言語 | 英語 |
|---|---|
| 著者 | Kohei Miyamoto, Masakazu Iwamura and Koichi Kise |
| 論文名 | A Quantum Algorithm for Finding k-Minima |
| 論文誌名 | Proc. 19th Asian Quantum Information Science Conference (AQIS2019) |
| ページ数 | 4 pages |
| 発表場所 | Seoul, Korea |
| 査読の有無 | 有 |
| 発表の種類 | ポスター発表 |
| 年月 | 2019年8月 |
| 要約 | We propose a new \textit{finding $k$-minima} algorithm and prove that the query complexity is $\mathcal{O}(\sqrt{kN})$, where $N$ is the number of data indices. The primary difficulty of the problem is that it requires to return $k$ answers. For the problem, an extension of the Amplitude Amplification (we call it \textit{searching all marked $k$ indices} algorithm) finds all $k$ data with the query complexity of $\mathcal{O}(\sqrt{kN})$ if an appropriate threshold is given. We give a quantum algorithm that searches a good threshold with the complexity of $\mathcal{O}(\sqrt{N}\log{k})$. In addition, we briefly prove the query complexity of the \textit{searching all marked $k$-indices} algorithm, which is not well discussed so far. Our algorithm can be directly adapted to distance-related problems like $k$-Nearest Neighbor Search, clustering and classification. |
- 注記
Full version of the paper is available at <a href="https://arxiv.org/abs/1907.03315">https://arxiv.org/abs/1907.03315</a> - 次のファイルが利用可能です．
- BibTeX用エントリー
@InProceedings{Miyamoto2019, author = {Kohei Miyamoto and Masakazu Iwamura and Koichi Kise}, title = {A Quantum Algorithm for Finding k-Minima}, booktitle = {Proc. 19th Asian Quantum Information Science Conference (AQIS2019)}, year = 2019, month = aug, numpages = {4}, location = {Seoul, Korea} }