Abstract
High time complexity is one of the biggest challenges faced by 𝘬-Nearest Neighbors (𝘬NN). Although current classical and quantum 𝘬NN 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 𝘬NN(GB-Q𝘬NN). 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 𝘬NN-like algorithms, as revealed by a comprehensive complexity analysis.