A Quantum Algorithm for Finding k-Minima
| Language | English |
|---|---|
| Type | Proceedings of International Conferences |
| Authors | Kohei Miyamoto, Masakazu Iwamura, Koichi Kise |
| Title | A Quantum Algorithm for Finding k-Minima |
| Journal | Proc. 19th Asian Quantum Information Science Conference (AQIS2019) |
| Number of pages | 4 |
| Location | Seoul, Korea |
| Reviewed | Reviewed |
| Presentation type | Poster |
| Date | August 2019 |
| Research fields | Quantum Computing, Nearest Neighbor Search |
| Key | Miyamoto2019_AQISb (id=1681) |
Abstract
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.
Note
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}