Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.23066 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909626591608832 |
|---|---|
| author | Xia, Shuyin Tian, Xiaojiang Yuan, Suzhen Deng, Jeremiah D. |
| author_facet | Xia, Shuyin Tian, Xiaojiang Yuan, Suzhen Deng, Jeremiah D. |
| contents | High time complexity is one of the biggest challenges faced by $k$-Nearest Neighbors ($k$NN). Although current classical and quantum $k$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 $k$NN(GB-Q$k$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 $k$NN-like algorithms, as revealed by a comprehensive complexity analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_23066 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing Xia, Shuyin Tian, Xiaojiang Yuan, Suzhen Deng, Jeremiah D. Quantum Physics Artificial Intelligence Machine Learning High time complexity is one of the biggest challenges faced by $k$-Nearest Neighbors ($k$NN). Although current classical and quantum $k$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 $k$NN(GB-Q$k$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 $k$NN-like algorithms, as revealed by a comprehensive complexity analysis. |
| title | Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing |
| topic | Quantum Physics Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2505.23066 |