Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing

1 Introduction

Machine learning, a fundamental technology of artificial intelligence, facilitates prediction and decision-making by extracting patterns from large data sets. Within the supervised learning domain, the kNN algorithm [Guo et al., 2003] has been widely adopted for classification and regression due to its conceptual simplicity and practical effectiveness. However, the rapid expansion of the data scale in the current era of information has exposed significant challenges associated with the time complexity of the classical kNN algorithm, particularly when applied to large-scale data sets. This challenge has emerged as a critical bottleneck that limits the algorithm's scalability and broader applicability.

This paper seeks to address these limitations by improving algorithmic efficiency while maintaining the accuracy of nearest neighbor search, utilizing two pivotal approaches: granular-ball theory [Xia et al., 2022] and the quantization of HNSW [Malkov and Yashunin, 2016]. As an advanced data modeling technique, granular-ball theory effectively reduces data volume and alleviates the computational burden of large-scale data sets through granularity division and aggregation processes. In addition, this paper employs quantum computing by encoding information in qubits and harnessing their unique properties of superposition and entanglement.

Specifically, for the GB-QkNN algorithm proposed in our paper, the granular-ball theory is applied to reduce the data scale and represent the original data set using the granularball, thus significantly decreasing the graph construction scale. Subsequently, a quantum algorithm is employed to optimize the HNSWmethod. Once the graph is constructed, the quantum computation performs layer-by-layer kNN searches on the test data set, completing the classification tasks efficiently. This approach achieves a graph construction complexity of O(M logM), where N is the size of the data set, and M(M ≪ N) is the number of granular-ball. In addition, it can reduce the search complexity to O(logM). Compared to existing classical and quantum kNN algorithms, the proposed approach demonstrates superior efficiency and accuracy, making it a compelling solution for large-scale data sets. Our contributions are as follows.

• This work integrates the granular-ball theory with the HNSWmethod, effectively reducing the data size and significantly accelerating the search process for kNN.
• We extend the HNSW method by introducing a quantum-enhanced approach, taking advantage of the inherent parallelism of quantum computing to accelerate distance computations and significantly improve graph construction efficiency.
• A comprehensive time complexity analysis reveals that the proposed algorithm achieves a lower time complexity than existing classical and quantum kNN algorithms.

2 RelatedWork

The classical kNN algorithm, first introduced by Thomas Cover in 1967, has experienced substantial development due to its intuitive design and high accuracy. However, exponential growth in data size has rendered its time complexity a critical bottleneck, limiting its practical applicability. To solve this problem, various approximate kNN algorithms have been proposed. The HNSWmethod, introduced in 2016, employs a graph-based hierarchical structure with small-world properties. With a construction time complexity of O(N logN), HNSW achieves a significant reduction in the search time complexity to O(logN). In 2021, Fu advanced this line of research by proposing the NSSG [Fu et al., 2021] (Navigable Satellite System Graphs), which builds on the SSG (Satellite System Graphs) through an optimized pruning strategy. This approach achieves a construction time complexity of O(N + N 1.14 ) while maintaining a search time complexity of O(logN). Currently, quantum machine learning is rapidly advancing, holds significant promise, and has driven the development of advanced algorithms such as quantum support vector machines [Rebentrost et al., 2014], quantum kNN [Basheer et al., 2020], and quantum neural networks [Altaisky, 2001]. In particular, for quantum kNN, Manuela C. G. Laing proposed a preliminary quantum kNN framework leveraging Grover's algorithm in 2017, attaining a time complexity of O(√N). Building on this, in 2022, a quantum k NN algorithm based on the Hamming distance [Li et al., 2022] was introduced, achieving a time complexity of O(√N log2 N) and marking a notable improvement. In 2023, a quantum kNN algorithm employing polar distance [Feng et al., 2023] further reduced the time complexity to O(√kN ).

The structure of this paper is organized as follows. Section 3 introduces the foundational concepts of granular-ball, quantum computing, and the HNSWmethod. Section 4 provides a detailed description of the proposed algorithm and its implementation process. Section 5 presents a comprehensive analysis of the algorithm's time complexity and a performance comparison with existing classical approximate kNN and quantum kNN algorithms. Finally, Section 6 concludes the paper by summarizing key contributions and highlighting potential directions for future research in related areas.

3 Background

This section provides an overview of the fundamentals for the proposed algorithm, including the concept of granular-balls, quantum computing basics, and the HNSW method.

3.1 Granular-Balls

Granular-ball computation is an efficient and robust granular computing method proposed in [Xia et al., 2022] based on granular cognitive computing, which can also reduce attributes. The core idea is to use granular-balls to cover and represent the sample space. For a granular-ball G = {xi, i = 1, · · · , n}, where xi represents a sample point within the granular-ball, and n represents the number of sample points in the granular-ball, the center C and radius R of the granularball can be described as:

3.2 QuantumAlgorithms

Now we introduce some quantum computing circuits used in our algorithm.

QRAM

QRAM (QuantumRandomAccessMachine) [Giovannetti et al., 2008] leverages the properties of quantum superposition and entanglement to implement a quantum memory capable of random access. It stores addresses and data in the form of quantum entanglement. The specific data encoding process is as follows:

where |j⟩a represents the j-th memory unit. After being stored in QRAM, the data are encoded in the data register. |Dj⟩a represents the value of the j-th data D, and ψj denotes the probability amplitude of each state.

Angle encoding

Angle encoding [Farhi et al., 2017] utilizes RX(θ), RY (θ), and RZ(θ) to rotate the angles in the Bloch sphere to encode classical information. For quantum algorithms that do not require arithmetic operations, the three above-mentioned rotation gates transform the data into the relative phase angles of the quantum bits, effectively mapping the data to a point on the Bloch sphere. The specific implementation of the controlled RY (CRY) gate CRY(·) is given by

where |a⟩ is the control bit of the CRY gate and θ is the rotation angle.

Swap test

Swap test [Bennett et al., 1993] calculates the similarity between quantum states |ϕ⟩ and |φ⟩ by determining the similarity, that is, the squared modulus of the inner product between these states. The quantum circuit of the Swap test is shown in Fig. 1. The output of this quantum circuit is:

When we measure the last qubit of the output, the following probability can be obtained:

Algorithm 1 Similarity Calculation

We can obtain the similarity of two quantum states through the above three quantum modules. Algorithm 1 gives the pseudocode for convenience in the following use.

Quantum Comparison Circuit

A quantum comparator can be used to compare two values.

The unitary evolution of this quantum state after passing through the quantum comparison circuit is shown in Eq. 8:

In the above equation |a⟩ |b⟩ are two numbers involved in the comparison, the |0⟩ represent the the auxiliary bit with input state 0, |c⟩ stores information about the comparison results, when c = 0, a ≥ b; and when c = 1, a < b. Figure 2 shows the quantum circuit of the two-bit quantum comparator.

Finally, the comparison result is obtained by the value of c at the end of the output, the details are given in Algorithm 2:

3.3 HNSW

HNSW is an approximate kNN search algorithm inspired by small-world networks, which utilizes a hierarchical graph structure to accelerate the search process. HNSW achieves

Algorithm 2 Quantum Compare

Input: Data values a and b

Output: Result of min(a, b)

M ← |b|, N ← 2⌈log2 |a|⌉

Through QRAM, angle encoding map a, b onto angles:

N∑

i=0

M∑

j=0

N∑

i=0

M∑

j=0

QuantumCompare: UCMP |a⟩ |b⟩ |0⟩ |0⟩ = |a⟩ |b⟩ |0⟩ |c⟩;

Return c == 0 ? b : a;

|i⟩|j⟩|0⟩|0⟩ →

|i⟩|j⟩|ϕ⟩|φ⟩

high query efficiency and scalability by combining local connections with long-range shortcuts, outperforming traditional planar or linear graph representations.

The two main processes of HNSW are construction and search. During construction, nodes are assigned to layers based on a probability distribution and connect to nearest neighbors using a greedy strategy. During the search, the algorithm starts at the top layer, iteratively selects the nearest neighbors, and refines the results at the lower layers to identify the k nearest neighbors. Priority queues optimize neighbor selection, ensuring efficient traversal. These points establish connections or conduct search operations with their neighbors, progressing from the top layer to the bottom.

4 Methodology

Before introducing our proposed algorithm, we list the notations used in presenting the algorithm in Table 1.

4.1 AlgorithmFlow

The overall algorithm flow of the proposed GB-QkNN algorithm is depicted by the flow chart as shown in Fig. 3.

The process is divided into three main stages. The first stage involves the classical algorithm: the original data set D is used to generate the granular ball, and the granular ball data set G is obtained. The second stage is based on the quantum algorithm, which comprises two key steps: constructing the quantum HNSW and searching within the quantum HNSW. These steps use quantum algorithms such as QRAM, angle encoding, Swap test, and quantum comparators to facilitate parallel distance calculations and magnitude comparisons during the construction of the HNSW for the granularball data set G. Subsequently, these quantum algorithms are employed to compute the distance between the test point and the original points in the graph and identify the neighboring points of the test point, thereby completing the quantum HNSW search process. The third stage involves classical computation to determine the type distribution within the priority queue Q. The test point is classified according to the type with the highest proportion in the priority queue. The following sections provide a detailed explanation of each stage. The process is divided into three main stages. The first stage involves the classical algorithm: the original data set D is used to generate the granular ball, and the granular ball data set G is obtained. The second stage is based on the quantum algorithm, which comprises two key steps: constructing the quantum HNSW and searching within the quantum HNSW. These steps use quantum algorithms such as QRAM, angle encoding, Swap test, and quantum comparators to facilitate parallel distance calculations and magnitude comparisons during the construction of the HNSW for the granular-ball data set G. Subsequently, these quantum algorithms are employed to compute the distance between the test point and the original points in the graph and identify the neighboring points of the test point, thereby completing the quantum HNSW search process. The third stage involves classical computation to determine the type distribution within the priority queue Q. The test point is classified according to the type with the highest proportion in the priority queue. The following sections provide a detailed explanation of each stage.

4.2 Granular-ball Generation

The original data set D is initially considered to be the first granular-ball. A random point is selected from the granularball to serve as the center, and another point, which is the most distant and belongs to a different class, is chosen as the second center. The purity of each granular-ball is then assessed to determine whether it meets the threshold value T. If the purity is insufficient, the granular-ball is split according to the following rule: the remaining data points within the current granular-ball are assigned to the granular-ball corresponding to the center that is closest to them. For the newly created granular-ball resulting from the split, the original center is retained as the new center, and another point, the farthest from the current center and belonging to a different class, is selected as the second center. This splitting process continues iteratively until all granular-ball exhibit a purity greater than or equal to the threshold T. The final data set of granularballs G is obtained, with its size denoted as M.

4.3 QuantumHNSWConstruction

Quantum HNSW construction is the basis of quantum HNSW search. We need to obtain the data sets Si(i ∈ [0, logM] [Malkov and Yashunin, 2016] of each layer, which represents the ith layer), and the adjacency matrix Ji(i ∈ [0, logM]) of each layer from the quantum HNSW construction.

Figure 4 shows the process of one data point participating in the construction of quantum HNSW, where the blue point is the newly inserted data point. The specific construction process of one data point is described as follows.

Step 1: Determine the top layer to insert. The top layer of insertion L is first determined by a random function as in Eq. 9.

where r ∈ (0, 1) is a uniformly distributed random number. To ensure that L does not exceed the total number of layers, the final definition of L is given in Eq. 10.

Step 2: Insert one data point from layer to layer. The data point will construct the graph from the layer L down. In the construction process, only the insertion operation is needed if there is only the newly inserted data point in the layer. If there are other data points in the layer, the similarity calculation will determine the nearest data point to the insertion point. In addition, the connection relationship between the insertion point and the nearest data point is established, and the nearest data point is used as the neighbor node of the insertion point in the next layer. When the insertion point is inserted into the next layer, the nearest data point is determined by the neighboring nodes obtained from the previous layer and the adjacency matrix of the current layer. The insertion point establishes a connection relationship with the nearest data point through the adjacency matrix. Similarly, the nearest point will be the neighbor node of the next layer.

Algorithm 3 Quantum HNSW Construction

Input: The size of Granular-ball data set M, granular-ball data set G, maximum neighbor count m Output: Data point set S[i][j] (i ∈ [0, logM]), adjacency matrix J[i][j][k] (i ∈ [0, logM])(j, k ∈ [0,M]) Initialize S ← ∅, J ← ∅, countp ← 0 while countp < M do Sample r ∼ Uniform(0, 1) Compute L ← min(- log2 (r), log M) Set layer ← 0 while layer < L do Add G[countp] to S[layer] Initialize min ← INT MAX, Lc[layer] ← ∅, Dc[countp] ← ∅ InitializeH ← Algorithm1(S[layer], G[countp]) Set tempm ← m while tempm > 0 do if H.size() ̸= 0 then if min ̸= Algorithm2(min, H.front()) then min ← H.front() index ← H.front().index() end if Remove H.front() from H else Break; end if tempm ← tempm - 1 end while J[layer][countp][index] ← 1 layer ← layer + 1 end while countp ← countp + 1 end while return S, J

This operation continues until the insertion point is inserted into the lowest layer.

When all data points in G are inserted through the two steps above, the data set Si and the adjacency matrix Ji of each layer are obtained.

The pseudocode for the quantum HNSW graph construction is shown in Algorithm 3.

After introducing the whole construction process from the perspective of how each point is inserted, we will introduce the construction process of each layer from the perspective of how it is implemented through quantum algorithms. Firstly, the data are encoded by QRAM, angle encoding. The similarity measurement is performed on the encoded data, and the connection relationship is established on the basis of the similarity. Then, this data point is used as the next layer's neighbor node for the insertion point. The steps are described below.

Step1: Quantum state encoding. Suppose that the dimension of the granular-ball data set G is d, and the range of data point values for each dimension is ⌊0, 2ta -1⌋. Firstly, the granular-ball data set G is stored in the memory qubits by QRAM, and the address qubits are used to control the memory qubits in parallel. Subsequently, the angle encoding is used to map the data on the bus qubits to the angle on the Bloch sphere. The specific quantum circuit is shown in Fig. 5. From top to bottom, the first s qubits store the address information of one dimension, where 2s ≥ M. The address qubits can be reused for d dimensions of the same data. The next 2s route qubits are used as a bridge for the address qubits to find the memory qubits. There are 2s groups of memory qubits and every group of ta memory qubits is used to store specific numerical information. The following ta bus qubits are adopted to store numerical information, which will be used in the subsequent angle encoding. Finally, qubits ang are added to store the angle encoding information.

It can be seen from Fig. 5 that the data set G is first encoded by QRAM, whose specific quantum circuit is shown in [Giovannetti et al., 2008]. This is followed by angle encoding. The data is stored in binary form on the bus qubits of QRAM, which can be encoded into angles by controlled rotation operations. When the control qubit is 1, the controlled rotation operations can encode the data into angles π 2v of the qubit ang. The value of v starts from 2 and increases by 1 each time until ta+1. Finally, we use QRAM † to restore the quantum state to the state before using QRAM.

Step2: Obtaining similarity. The similarity of the two quantum states is their inner product, which can be obtained by performing a Swap test operation.

First, we should obtain the quantum states that will participate in the similarity calculation. They are the node set information in each layer and the newly inserted data point, which are encoded in qubits ang in Fig. 5. Based on the data sets Si, the adjacency matrix Ji and the neighboring nodes of each layer, we can obtain the set of nodes Sci(c ∈ [0,m], i ∈ [0, logM]). The node set of the current layer is the union of the neighbor node and the one-hop nodes of the neighbor node.

Then, as shown in Fig. 6, the angle qubits corresponding to the current insertion point dinsert and the set of points Sci are used as input for the similarity calculation. Each angle qubit in the set Sci performs the Swap test with dinsert. Information about their similarity |⟨dinsert | Sci⟩|2 is stored in the probability of measuring qubits result to get 0 or 1.

The probability expression related to the similarity in Swap test is specific as follows:

where |⟨dinsert | Sci⟩|2 represents the similarity between Sci

m

and dinsert. p(0) and p(1) represent the probability of obtaining the state |0⟩ and |1⟩ after quantum measurement.

The lower the probability that we get result to be 1 when we measure, the more similar the two data points are and the closer they are to each other.

Step 3: Building connections. We must find the data point C closest to the insertion point dinsert in the current layer. C can be obtained by using a quantum comparator [Yuan et al., 2022] on the similarity information obtained in Step 2. Then, the corresponding element is set to 1 in the adjacency matrix Ji to represent the connection relationship between the two points. Finally, the point C is used as the neighbor node inserted in the next layer.

Once all points in the granular-ball data set have been inserted, the construction of the quantum HNSW is complete, resulting in the constructed data sets Si of each layer and the adjacency matrix Ji for each layer.

4.4 QuantumHNSWSearch

The search will begin from the top layer of the constructed quantum HNSW for the test data point dt based on Si and Ji previously determined. The pseudocode of the quantum HNSW search is shown in Algorithm 4.

We divide the quantum HNSW search process into four steps.

Step1: Quantum state encoding. The data in the constructed graph has been encoded into angle qubits during the quantum HNSW construction. We only need to encode the test data point dt in a quantum state using QRAM and angle encoding, in the same way as in Fig. 5.

Step2: Obtain the nearest data point of the current layer.

To determine the nearest data point of dt in the current layer, we need to obtain the node set Sci(c ∈ [0, m] , i ∈ [0, logM]) to perform similarity with dt. Based on data sets Si and the adjacency matrix Ji established during the construction process for each layer, we can obtain the nearest data point of the test point dt in the current layer using the same method as in the construction process. Then, this data point will be added to a predefined priority queue Q. The size of the queue is k, and the priority queue will automatically be sorted by the values of members, and the higher values have a higher priority. The specific structure of the queue is shown in Fig. 7.

Step3: Obtain k nearest data points. We traverse the quantum HNSW graph from the top to the bottom layer to obtain the k nearest neighbors of the test data point dt by repeatedly executing Step 1 and Step 2. The nearest data point is added to the priority queue Q for each layer. When the capacity of Q exceeds k, a quantum comparator is used to evaluate the relationship between the nearest data point dci(i ∈

Algorithm 4 Quantum HNSW Search

Input: Data point set S[i][j] (i ∈ 0 to logM), adjacency matrix J[i][j][k] (i ∈ 0 to logM), test point dt, granular-ball data set size M, granular-ball data set G, ma3ximum neighbor count m Output: Type of test point dt

Initialize H ← ∅ layer ← 0 neighborpos ← 0 Qpriority ← ∅ typetest ← ∅ while layer < logM do Initialize similarityCalcSet ← ∅, min ← INT MAX if layer == 0 then H ← Algorithm1(S[layer], dt) elseindex ← 0 count ← 0 while index < M and count < m do if J[layer][index][neighborpos] == 1 then Add G[index] to similarityCalcSet count ← count + 1 end if index ← index + 1 end while H ← Algorithm1(similarityCalcSet, dt) end if tempm ← m while tempm > 0 do tempm ← tempm - 1 if H.size() ̸= 0 then if min ̸= Algorithm2(min, H.front()) then min ← H.front() index ← H.front().index() end if Remove H.front() from H else Break; end if end while neighborpos ← index if Qpriority.size() > m and min <= Qpriority.front() then Qpriority.popfront() end if Add G[neighborpos] to Qpriority layer ← layer + 1 end while Compute type ← maxtype(Qpriority) return type

(0, logM)) and the highest priority data dbi(i ∈ (0, logM)) in the queue. If dci > dbi, the priority queue remains unchanged; otherwise, dci is added to the queue and dbi is removed.

Step4: Classification of test data. Based on the k nearest neighbors obtained in Step 3, the label of the test data point dt is determined by the majority class label of its nearest k neighbors.

5 Time Complexity Analysis

This section analyzes the time complexity in two aspects: construction and search.

5.1 Construction Part

The algorithm begins by generating a granular-ball data set from the classical data set, and the time complexity to generate the classical granular ball is given by O(cdN) [Xia et al., 2022], which is performed only once as part of the data pre-processing phase. Then, we will analyze the construction complexity of the quantum HNSW based on the granularball. First, the time complexity of QRAM, based on its quantum circuit structure and characteristics, is O(logM). Second, the time complexity of angle encoding, which involves only rotation operations, is O(1). Third, the time complexity of the Swap test is O(1), and the time complexity of the quantum iterative comparison is O(m), where m represents the maximum number of neighbors for each node, which is much smaller thanM.

The loop process consists of two parts. The first part involves all M points participating in the construction. The second part requires that each point begin construction from its corresponding L (L ≤ logM) layer, with operations including angle encoding, Swap test, and iterative comparison. Based on the above analysis, the time complexity of the loop part is O(M)O(logM)(O(m) + O(1) + O(1)), which simplifies to O(M)O(logM). Including QRAM and granular-ball generation, the resulting time complexity is O(M)O(logM) +O(logM) +O(cdN), which can be simplified to O(cdN).

5.2 Search Part

The input test point begins at the top layer and searches a total of logM layers to the bottom. Each layer involves angle encoding, Swap test, and quantum iterative comparators. The time complexity of each quantum algorithm is shown in the construction part. Therefore, the time complexity of the loop search process is O(logM)(O(m) +O(1) +O(1)). Since the maximum number of neighbors m is much smaller than the size of the granular-ball data set M, this simplifies to O(logM). Thus, the final time complexity for the quantum HNSW search is O(logM).

5.3 Time Complexity Comparison

To evaluate the performance of the GB-QkNN algorithm, the comparison between the proposed algorithm and the other quantum kNN algorithms is performed, which is shown in Table 2. M denotes the size of the granular-ball data set, and N represents the size of the original data set, where N ≫ M. It can be seen from Table 2 that the proposed GB-QkNN algorithm exhibits the lowest time complexity.

Table 3 compares the proposed algorithm with the classical graph-based approximate kNN algorithms. It shows that the GB-Qk NN algorithm outperforms the current classical graph-based approximate kNN algorithms in construction and search complexity. This highlights the superior theoretical performance and faster execution speed of the proposed algorithm.

6 Conclusion and FutureWorks

This paper proposes a GB-QkNN algorithm to improve the search efficiency of kNN in large-scale data sets. This approach integrates granular-ball theory, the HNSW method, and quantum computing to reduce the time complexity and improve the search efficiency of kNN. The proposed GBQkNN algorithm has a very low time complexity in the search process. Future work will focus on optimizing the granularball generation and attribute-reduction processes to reduce time complexity. With the ongoing advancement of quantum computing, the GB-Qk NN algorithm has promising application potential.

Acknowledgments

The authors would like to acknowledge the financial support of the National Natural Science Foundation of China (Nos. 62221005, 62450043, 62222601, and 62176033).