用颗粒球与量化加速量子kNN，大幅降低计算时间。
Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing
- 先用颗粒球压缩数据，再用分层小世界图加速搜索。
- 通过量化距离计算，使构建与查询时间复杂度显著下降。
- 适合处理海量数据的高效近邻搜索场景。
高时间复杂度是k近邻（kNN）算法面临的主要挑战之一。尽管当前经典与量子kNN算法已有所改进，但在面对大规模数据时仍存在速度瓶颈。为此，我们提出一种创新算法——基于颗粒球的量子kNN（GB-QkNN）。该方法首先利用颗粒球技术减少需处理的数据量，进而采用分层可导航小世界（HNSW）方法加速搜索过程。此外，通过量化优化了HNSW中耗时的距离计算等步骤，进一步降低了构建与搜索的时间复杂度。综合复杂度分析表明，结合颗粒球与HNSW的量化策略，显著提升了kNN类算法的效率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。