REVIEW 4 major objections 5 minor 19 references
Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing
T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A quantum-assisted kNN algorithm claims to cut nearest-neighbor search from O(log N) to O(log M) by first compressing the data set into M granular balls and searching a layered small-world graph built over them.
desk verdict The central complexity claims collapse when you read the pseudocode: the swap test is miscosted, and Algorithm 3 does not build an HNSW graph. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central objects are granular balls and the layered quantum graph built on them. A granular ball is a cluster of sample points represented by its center and average radius; the classical generation step splits balls until their label purity reaches a threshold T, yielding M balls with M much smaller than N. The quantum HNSW layer structure assigns each ball to a top layer L = min(floor(-log2 r), log M) for a uniform random r, then at each layer uses QRAM to load stored data, angle encoding to convert each dimension to a rotation on the Bloch sphere, swap tests to estimate the squared inner product between the insertion point and candidate nodes, and a quantum comparator to select the closest candidate and record the connection in an adjacency matrix. The search uses the same encoding plus a priority queue of size k maintained across log M layers. These components are what the complexity analysis counts as O(log M) for QRAM, O(1) for encoding and swap test, and O(m) for the iterative comparison loop, yielding the stated bounds.
What would settle it
Run the paper's Algorithm 3 on a benchmark data set, vary the number of granular balls M by changing the purity threshold, and count the number of swap-test shots needed to make the quantum comparator select the true nearest neighbor in each layer; if the shot count grows with M or with the inverse square of the smallest similarity gap, the per-layer cost is not O(1) and the O(log M) total does not hold.
Extended reading notes
Core claim
On the paper's own terms, the discovery is a three-stage pipeline whose cost is dominated by the compressed granular-ball size M rather than the original N. Classical granular-ball generation turns the raw data into M balls with centers and radii; a quantum implementation of HNSW then builds a layered graph on these balls, using QRAM to load ball data, angle encoding to map each ball to qubit rotations, swap tests to measure inner-product similarity between an insertion point and candidate neighbors, and a quantum comparator to select the nearest neighbor, connecting the insertion point to one nearest neighbor in each layer. Search goes from the top layer down to layer zero, computing similarities between the test point and the neighbors reached so far and updating a priority queue of size k, and the majority label in the queue decides the test label. The paper's stated results are that construction costs O(M log M) (stated in the abstract) or O(cdN) once the classical granular-ball pre-processing is included (stated in Section 5.1), and that search costs O(log M), giving the lowest complexity among the algorithms compared in Tables 2 and 3.
Load-bearing premise
The O(log M) search time rests on treating each quantum similarity check (a swap test) as one constant-time operation; in reality the overlap probability must be estimated by many repeated measurements to rank neighbors reliably, and if that repetition cost scales with the data size or precision, the logarithmic bound fails.
Editorial extensions
If this is right
- If the complexity analysis is correct, kNN classification on large data sets reduces to a query whose cost grows logarithmically with the number of granular balls, not with the number of raw points.
- The algorithm would beat classical HNSW's O(log N) search bound whenever M is much smaller than N, and would beat quantum kNN baselines with O(sqrt(kN)) or O(N) complexity.
- The quantum graph is built once and can be reused for many test points, since the encoded layer data and adjacency matrices are stored for repeated queries.
- Construction cost is dominated by the classical granular-ball generation step O(cdN), so the claimed quantum advantage is in search time rather than in building the index.
Reading between the lines
- Editorial extension: the O(log M) search bound should be tested empirically by varying M through the purity threshold T and measuring query time; if the scaling departs from logarithmic, the weak point is likely the sparse one-neighbor-per-layer construction rather than the quantum components.
- Editorial extension: the swap test is treated as cost O(1) even though separating the closest from the second-closest candidate requires a number of measurement shots that grows with the inverse square of the similarity gap; adding this precision cost could turn the per-layer cost into a data- or precision-dependent factor.
- Editorial extension: a hybrid ablation that replaces the swap test with classical inner products between granular-ball centers would isolate how much of the claimed speedup comes from granular-ball compression alone, independent of quantum similarity estimation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes GB-QkNN, a quantum approximate k-nearest-neighbor classifier that combines granular-ball data condensation, a hierarchical navigable small world (HNSW)-style graph, and quantum subroutines (QRAM, angle encoding, swap test, quantum comparator). The abstract and introduction claim a graph construction complexity of O(M log M) and a search complexity of O(log M), where M is the number of granular balls and M is much smaller than the original data size N. Section 5 provides a time-complexity analysis and a comparison with existing classical and quantum kNN algorithms, concluding that GB-QkNN has superior theoretical efficiency. No experimental evaluation is reported.
Significance. If the claimed complexity bounds were correctly derived, the algorithm would be an interesting contribution: it would offer an approximate kNN classifier with logarithmic search cost in the number of representative clusters, potentially relevant for large-scale classification. The paper also addresses a real bottleneck in kNN algorithms. However, the central complexity claims are not established by the manuscript, and several load-bearing steps are either contradictory or rely on unstated assumptions. The work is therefore not yet at the level required for publication; the potential significance is real but the current support is insufficient.
major comments (4)
- [Abstract and Section 5.1] The central construction-complexity claim is internally inconsistent. The abstract and introduction state that GB-QkNN achieves a graph construction complexity of O(M log M), but Section 5.1 computes the construction cost as O(M) O(log M) + O(log M) + O(cdN) and then simplifies it to O(cdN). Table 3 also lists O(cdN) as the construction complexity. Since N is stated to be much larger than M, O(cdN) and O(M log M) cannot both describe the full pipeline; the abstract's claim is not supported by the paper's own analysis.
- [Algorithm 3] Algorithm 3 does not construct an HNSW graph, so the cited O(log N) search bound of Malkov and Yashunin (2016) does not transfer. In each layer, the algorithm inspects at most m elements from the similarity set H and sets exactly one adjacency-matrix entry J[layer][countp][index] = 1. Thus every inserted node has out-degree one per layer, and the chosen index is the nearest among the first m popped elements, not necessarily the layer's true nearest neighbor. The resulting structure is a layered forest, not the multi-link small-world graph on which HNSW's logarithmic navigability depends. The O(log M) search complexity claimed in Section 5.2 and Table 3 is asserted rather than derived.
- [Section 5.1, Step 2] The swap test is counted as O(1), but estimating the similarity |⟨φ|ψ⟩|² from the measurement probability p(0) = 1/2 + 1/2|⟨φ|ψ⟩|² requires repeated measurements to reach the precision needed for neighbor ranking. In a nearest-neighbor search, the required precision depends on the gap between the similarities of candidate points, which can scale with M; this is ignored in both the construction and search complexity analyses. Accounting for the measurement overhead would add a multiplicative factor that is generally not O(1).
- [Section 5] The headline complexity figures are largely taken from prior work rather than derived in this manuscript. The O(cdN) granular-ball generation cost is cited from Xia et al. (2022), and the O(log M) search bound is the HNSW bound applied to M granular balls. The paper does not derive a new bound for its specific construction, and the quantum subroutines (angle encoding, swap test, comparator) are assigned constant or near-constant costs without a detailed fault-tolerant or sampling analysis. The claim of 'superior efficiency and accuracy' is therefore not substantiated.
minor comments (5)
- [Algorithm 2] The variable assignments in Algorithm 2 appear inconsistent: it sets M ← |b| and N ← 2^⌈log2 |a|⌉, but the subsequent encoding and comparator description in Section 3.2 uses |a⟩ and |b⟩ as the two numbers to compare; the roles of M and N are unclear and should be reconciled with the notation table.
- [Algorithm 4] The name 'neighborpos' is misleading: it is updated to the index of the current best match and then used to select nodes in the next layer via J[layer][index][neighborpos] == 1, which does not correspond to the multi-neighbor traversal described in the text. The pseudocode should be aligned with the prose.
- [Section 4.2] The granular-ball splitting rule is under-specified. In particular, it is not clear what happens when a granular-ball contains only points of one class, how the purity threshold T is chosen, or how the 'second center' is selected when no point of a different class exists; these details affect the reproducibility of the algorithm.
- [Section 5.3, Table 2] The comparison in Table 2 is not uniform: some entries are classification-time complexities while others appear to be index-construction or query complexities, and the cited works use different conventions. The table should be accompanied by a clear statement of what each complexity measure counts.
- [Throughout] There are several typographical and formatting issues, including 'ma3ximum neighbor count m' in Algorithm 4's input list, a duplicated paragraph in Section 4.1, and the use of undisplayed Unicode characters such as 'V anana' in Table 3. These should be corrected in revision.
Circularity Check
No load-bearing circularity: the O(M log M) and O(log M) claims are derived from the algorithm's layer-loop counts, and the O(cdN) term is an externally checkable preprocessing cost from prior work; remaining issues are correctness and internal consistency, not circularity.
full rationale
The paper's central complexity claims are not circular in the required sense. The construction complexity O(M log M) and search complexity O(log M) are derived in Sections 4.3 and 5.2 by counting the loop structure of Algorithms 3 and 4: for each of M points, the construction visits at most logM layers, and each search visits logM layers with per-layer work treated as O(1) or O(m). These are direct counting arguments, not self-referential definitions. The O(cdN) term for granular-ball generation is imported from [Xia et al., 2022], a paper co-authored by the first author, but for this analysis it is a parameter-free, externally checkable complexity result used as a preprocessing cost; it is not the prediction of a quantity fitted to the present algorithm. The paper does contain an internal inconsistency: the abstract claims O(M log M) construction, while Section 5.1 and Table 3 simplify the full construction cost to O(cdN). That is a correctness or reporting issue, not a circular reduction. Similarly, the O(1) swap-test cost and the mismatch between Algorithm 3 and the HNSW construction are substantive correctness concerns but do not make the derivation circular. The only reason the score is not 0 is the repeated reliance on the first author's earlier granular-ball complexity result within the central complexity derivation; this is a minor self-citation point but not a load-bearing circular step.
Assumptions & free parameters
free parameters (2)
- granular-ball purity threshold T
- maximum neighbor count m
assumptions (4)
- ad hoc to paper Swap test estimates state similarity in O(1) time
- domain assumption QRAM can be built and queried in O(log M) time
- ad hoc to paper A graph with one edge per node per layer behaves like HNSW
- domain assumption Quantum comparator has unit cost
Cite this review
Pith. "Pith review of Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing." pith.science (2026). https://pith.science/paper/HQEUCO44
@misc{pith2026250523066,
author = {Pith},
title = {Pith review of: Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing},
year = {2026},
howpublished = {\url{https://pith.science/paper/HQEUCO44}},
note = {Machine review of arXiv:2505.23066}
}
abstract
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.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
[Altaisky, 2001] M. V . Altaisky. Quantum neural network. arXiv preprint, quant-ph/0107012,
arXiv 2001
-
[12]
[Li W . and others., 2019] Sun Y . Li W ., Zhang Y . and oth- ers. Approximate nearest neighbor search on high dimen- sional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering , 32(8):1475–1488,
work page 2019
-
[13]
[Malkov and Y ashunin, 2016] Y . A. Malkov and D. A. Y ashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence, PP(99),
work page 2016
-
[15]
[Quezada et al., 2022] L. F. Quezada, G. H. Sun, and S. H. Dong. Quantum version of the k-nn classifier based on a quantum sorting algorithm. Annalen der Physik , 534(5):2100449,
work page 2022
-
[16]
[Rebentrost et al., 2014] P . Rebentrost, M. Mohseni, and S. Lloyd. Quantum support vector machine for big data classification. Physical Review Letters , 113(13):130503,
work page 2014
- [18]
-
[19]
[Zardini et al., 2024] E. Zardini, E. Blanzieri, and D. Pas- torello. A quantum k-nearest neighbors algorithm based on the euclidean distance estimation. Quantum Machine Intelligence, 6(1):1–22,
work page 2024
- [1993]
Show all 19 references
-
[2001]
Basheer, S
[Basheer et al., 2020] A. Basheer, S. K. Goyal, and A. Afham. Quantum k-nearest neighbors algorithm. arXiv preprint, arXiv:2003.09187,
2020 arXiv
-
[2003]
[Jayaram Subramanya S., 2019 ] Simhadri H. V . Jayaram Subramanya S., Devvrit F. Diskann: Fast accurate billion- point nearest neighbor search on a single node. In Ad- vances in Neural Information Processing Systems , vol- ume 32,
2019
-
[2008]
[Guo et al., 2003] G. Guo, D. Bell, and H. Wang. Knn model-based approach in classification. In OTM Confeder- ated International Conferences ”On the Move to Meaning- ful Internet Systems” . Springer, Berlin, Heidelberg,
2003
-
[2014]
[Xia et al., 2022] S. Xia, X. Dai, and G. Wang. An efficient and adaptive granular-ball generation method in classifica - tion problem. IEEE Transactions on Neural Networks and Learning Systems, 35(4):5319–5331,
2022
-
[2016]
V ., 2019] Dias Z
[Munoz J. V ., 2019] Dias Z. Munoz J. V ., Gonc ¸alves M. A. Hierarchical clustering-based graphs for large scale ap- proximate nearest neighbor search. Pattern Recognition, 96:106970,
2019
-
[2017]
[Feng et al., 2023] C. Feng, B. Zhao, and X. Zhou. An enhanced quantum k-nearest neighbor classification algo- rithm based on polar distance. Entropy, 25(1):127,
2023
-
[2019]
[Li et al., 2022] J. Li, S. Lin, and K. Y u. Quantum k-nearest neighbor classification algorithm based on hamming dis- tance. Quantum Information Processing, 21(1):18,
2022
-
[2020]
[Bennett et al., 1993] C. H. Bennett, G. Brassard, and C. Cr´ epeau. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Phys- ical Review Letters, 70(13):1895,
1993
-
[2021]
[Gao et al., 2022] L. Z. Gao, C. Y . Lu, and G. D. Guo. Quan- tum k-nearest neighbors classification algorithm based on mahalanobis distance. Frontiers in Physics , 10:1047466,
2022
-
[2022]
Giovannetti, S
[Giovannetti et al., 2008] V . Giovannetti, S. Lloyd, and L. Maccone. Quantum random access memory. Physical Review Letters, 100(16):160501,
2008
-
[2023]
[Fu et al., 2021] C. Fu, C. Wang, and D. Cai. High dimen- sional similarity search with satellite system graph: Ef- ficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine In- telligence, 44(8):4139–4150,
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.