Abstract
The KNN (K-nearest neighbors) algorithm is one of Top-10 data mining algorithms and is widely used in various fields of artificial intelligence. This leads to that quantum KNN algorithms have developed and achieved certain speed improvements, denoted as Q-KNN. However, these Q-KNN methods must face two key problems as follows. The first one is that they are mainly focused on neighbor selection without paying attention to the influence of K value on the algorithm. The second is that only the neighbor selection process is quantized, and the selection of K value is not quantized. To solve these problems, this paper designs a novel quantum circuit for KNN classification, so as to simultaneously quantumize the neighbor selection and K value selection process. Specifically, the least squares loss and sparse regularization term are first used to construct the objective function of the proposed quantum KNN, so that it can simultaneously obtain the optimal K value and K nearest neighbors of the testing data. And then, a new quantum circuit is proposed to quantumize the process through quantum phase estimation, controlled rotation, and inverse phase estimation techniques. Finally, experiments are conducted with qiskit and matlab to output the quantum and classical results of the algorithm, verifying that the proposed algorithm can output the optimal K value and K nearest neighbors for each testing data.
Introduction
The K-Nearest Neighbors (KNN) algorithm is a fundamental tool in data mining and artificial intelligence. Despite its popularity, classical KNN faces significant computational challenges, particularly in neighbor selection (calculating distances across large datasets) and $K$-value selection (determining the optimal number of neighbors). While existing Quantum KNN (Q-KNN) variants offer speedups for distance calculations, they often neglect the $K$-value selection process, leaving it to classical trial-and-error. This paper introduces a novel approach that quantizes the entire selection process, finding both the optimal $K$ and the nearest neighbors simultaneously.
Methodology
The proposed algorithm transforms KNN from a simple search into a formal optimization problem. By employing a least-squares loss function combined with dual sparse regularization terms ($l_1$-norm and $l_{2,p}$-norm), the relationship matrix ($W$) is forced to be sparse. In this framework, non-zero entries in $W$ represent the chosen neighbors, and the number of these entries effectively determines the optimal $K$ for a given test point.
The core of the methodology is a hybrid quantum-classical iteration. The quantum circuit, based on the HHL framework, utilizes Quantum Phase Estimation (QPE) to extract eigenvalues of the training data matrix, followed by controlled rotations based on regularization parameters to select neighbors. An inverse QPE then prepares the state for measurement. Classical components update bias terms and the relationship matrix, ensuring convergence to an optimal solution.
Results and Discussion
The algorithm was evaluated using synthetic datasets and the Banknote Authentication Dataset from the UCI Machine Learning Repository. A key finding is the algorithm's ability to achieve exponential speedup under specific conditions, reducing complexity from $O(mn^2)$ to $O(poly \log(n) m)$.
Experimental results on the Banknote dataset showed a classification accuracy of 87.50%, significantly higher than the 70.83% achieved by existing QKNN methods. Simulation results from IBM’s Qiskit confirm that the circuit correctly identifies the most informative neighbors through the sparsity-inducing regularization, as evidenced by the clear probability peaks in the measurement phase.
Conclusion
This research demonstrates that $K$-value selection can be effectively integrated into the quantum neighbor selection process through sparse regularization. While current Noisy Intermediate-Scale Quantum (NISQ) hardware introduces some errors, the theoretical and simulated results prove the viability of this simultaneous quantization. Future work will focus on developing anti-noise Q-KNN variants and quantum denoising techniques to enhance robustness against hardware decoherence.
Summary updated