# Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing

arXiv: https://arxiv.org/abs/2505.23066 · HTML: https://mlsanity.com/paper/2505.23066/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 20 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 2 of 2)

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Quantum version of the k-NN classifier based on a quantum sorting algorithm](https://mlsanity.com/paper/2204.03761/) (2022)

## Abstract (arXiv)

High time complexity is one of the biggest challenges faced by k-Nearest Neighbors (kNN). Although current classical and quantum kNN algorithms have made some improvements, they still have a speed bottleneck when facing large amounts of data. To address this issue, we propose an innovative algorithm called Granular-Ball based Quantum kNN(GB-QkNN). This approach achieves higher efficiency by first employing granular-balls, which reduces the data size needed to processed. The search process is then accelerated by adopting a Hierarchical Navigable Small World (HNSW) method. Moreover, we optimize the time-consuming steps, such as distance calculation, of the HNSW via quantization, further reducing the time complexity of the construct and search process. By combining the use of granular-balls and quantization of the HNSW method, our approach manages to take advantage of these treatments and significantly reduces the time complexity of the kNN-like algorithms, as revealed by a comprehensive complexity analysis.