2019/07/07 by Kohei Miyamoto, Miyamoto, Kohei, Masakazu Iwamura +3 · 4 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Computability, Logic, AI Algorithms #Quantum Information and Cryptography
paper · pdf · doi:10.48550/arxiv.1907.03315
We propose a new finding k-minima algorithm and prove that its query complexity is O(√(kN)), where N is the number of data indices. Though the complexity is equivalent to that of an existing method, the proposed is simpler. The main idea of the proposed algorithm is to search a good threshold that is near the k-th smallest data. Then, by using the generalization of amplitude amplification, all k data are found out of order and the query complexity is O(√(kN)). This generalization of amplitude amplification is also not well discussed and we briefly prove the query complexity. Our algorithm can be directly adapted to distance-related problems like k-nearest neighbor search and clustering and classification. There are few quantum algorithms that return multiple answers and they are not well discussed.