Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Quantum KNN Classification With K Value Selection and Neighbor Selection

Jiaye Li, Jian Zhang, Jilian Zhang, Shichao Zhang

Published Dec 20, 2023• 67 citations
Publisher

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.

DOI
10.1109/tcad.2023.3345251

Related papers

Robust Quantum Feature Selection Algorithm

Shichao Zhang, Jiaye Li, Hang Xu +2 more

High dimensional data has been a notoriously challenging issue. Existing quantum dimension reduction technology mainly focuses on quantum principal component analysis. There are only a few works on the direction of quantum feature selection algorithm which they are not robust. Also, there are few quantum circuits designed for feature selection, in which some steps are not quantized yet. For example, existing quantum circuits cannot solve the objective function based on sparse learning. To deal with these issues, this paper proposes a robust quantum feature selection by designing a new quantum circuit. Specifically, the sparse regularization term and least squares loss are first applied to construct the proposed objective function. And then, six kinds of quantum registers and their initial states are prepared. In addition, quantum techniques, such as quantum phase estimation and controlled rotation, are employed to construct an alternating iterative quantum circuit to obtain the final quantum state of the feature selection variable. Finally, a series of experiments are conducted to verify that the proposed algorithm can accurately select important features and has good robustness.

•Nov 16, 2022•0 citations

Robust Quantum Feature Selection Algorithm

Jiaye Li, Shichao Zhang, Hang Xu +2 more

High dimensional data has been a notoriously challenging issue. Existing quantum dimension reduction technology mainly focuses on quantum principal component analysis. There are only a few works on the direction of quantum feature selection algorithm which they are not robust. Also, there are few quantum circuits designed for feature selection, in which some steps are not quantized yet. For example, existing quantum circuits cannot solve the objective function based on sparse learning. To deal with these issues, this paper proposes a robust quantum feature selection by designing a new quantum circuit. Specifically, the sparse regularization term and least squares loss are first applied to construct the proposed objective function. And then, six kinds of quantum registers and their initial states are prepared. In addition, quantum techniques, such as quantum phase estimation and controlled rotation, are employed to construct an alternating iterative quantum circuit to obtain the final quantum state of the feature selection variable. Finally, a series of experiments are conducted to verify that the proposed algorithm can accurately select important features and has good robustness.

•Nov 15, 2022•1 citation

Quantum K-nearest neighbors classification algorithm based on Mahalanobis distance

Lizhen Gao, Chun-Yue Lu, Gongde Guo +2 more

Mahalanobis distance is a distance measure that takes into account the relationship between features. In this paper, we proposed a quantum KNN classification algorithm based on the Mahalanobis distance, which combines the classical KNN algorithm with quantum computing to solve supervised classification problem in machine learning. Firstly, a quantum sub-algorithm for searching the minimum of disordered data set is utilized to find out K nearest neighbors of the testing sample. Finally, its category can be obtained by counting the categories of K nearest neighbors. Moreover, it is shown that the proposed quantum algorithm has the effect of squared acceleration compared with the classical counterpart.

Frontiers in Physics•Oct 21, 2022•33 citations

Robust Quantum Feature Selection With Sparse Optimization Circuit

Jiaye Li, Jiagang Song, Jinjing Shi +4 more

High-dimensional data has long been a notoriously challenging issue. Existing quantum dimension reduction technology primarily focuses on quantum principal component analysis. However, there are only a few studies on quantum feature selection (QFS) algorithms, and these algorithms are often not robust. Additionally, there are limited quantum circuits specifically designed for feature selection, and they still cannot address the objective function based on sparse learning. To address these issues, this paper proposes a robust QFS algorithm by designing a novel sparse optimization circuit. Specifically, we first apply sparse regularization and least squares loss to construct the proposed objective function. Then, six types of quantum registers and their initial states are prepared. Furthermore, quantum techniques such as quantum phase estimation and controlled rotation are employed to construct a sparse optimization circuit, which is used to obtain the final quantum state of the feature selection variable.Finally, a series of experiments are conducted to verify the accuracy of the feature selection and the robustness of the proposed algorithm.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Jan 6, 2025•20 citations

Quantum multi-label k-nearest neighbor

Yilin Shen, Qin Liao

Although multi-label k-nearest neighbor (ML-kNN) is able to effectively solve multi-label learning (MLL) problem with local neighborhood similarity, its time complexity is nearly unacceptable with large-scale datasets. To solve this issue, we propose a novel ML-kNN algorithm with quantum computing techniques, which called quantum multi-label k-nearest neighbor (QML-kNN). In particular, we first accelerate the calculation of the prior probability by taking advantage of quantum phase estimation and Grover's amplitude amplification. Then, a controlled-SWAP test and a quantum k-maximal similarity search are used for efficiently identifying the neighbors. Subsequently, a quantum parallel counting circuit (QPCC) is designed to rapidly calculate the posterior probabilities. Experimental results demonstrate that QML-kNN is able to significantly reduce the time complexity of solving multi-label problems with performance improvement, achieving a substantial speedup over the classical MLL algorithm.

quant-pharXiv:2607.21919•Jul 27, 2026•0 citations

New approach of KNN Algorithm in quantum computing based on new design of quantum circuits

Vu Tuan Hai, Phan Hoang Chuong, Pham The Bao

Quantum computing has risen as the new type of computer that theoretically reduces the time complexity of classical methods exponentially because of the nature of superposition. It is promising to reduce runtimes on large data sets in machine learning (ML). Meanwhile, k-nearest neighbor (kNN) is a simple ML algorithm that can be translated to a quantum version (QkNN) to perform classification tasks efficiently. Here, we show a new version of QkNN which has a speed up in time complexity by using a new design of quantum circuits called integrated swap test. This quantum circuit can load two N-dimensional states and calculate the fidelity between them. Results show that QkNN allows us to take a different approach to the ML field.

Informatica•Apr 19, 2022•11 citations
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.
High dimensional data has been a notoriously challenging issue. Existing quantum dimension reduction technology mainly focuses on quantum principal component analysis. There are only a few works on the direction of quantum feature selection algorithm which they are not robust. Also, there are few quantum circuits designed for feature selection, in which some steps are not quantized yet. For example, existing quantum circuits cannot solve the objective function based on sparse learning. To deal with these issues, this paper proposes a robust quantum feature selection by designing a new quantum circuit. Specifically, the sparse regularization term and least squares loss are first applied to construct the proposed objective function. And then, six kinds of quantum registers and their initial states are prepared. In addition, quantum techniques, such as quantum phase estimation and controlled rotation, are employed to construct an alternating iterative quantum circuit to obtain the final quantum state of the feature selection variable. Finally, a series of experiments are conducted to verify that the proposed algorithm can accurately select important features and has good robustness.
High dimensional data has been a notoriously challenging issue. Existing quantum dimension reduction technology mainly focuses on quantum principal component analysis. There are only a few works on the direction of quantum feature selection algorithm which they are not robust. Also, there are few quantum circuits designed for feature selection, in which some steps are not quantized yet. For example, existing quantum circuits cannot solve the objective function based on sparse learning. To deal with these issues, this paper proposes a robust quantum feature selection by designing a new quantum circuit. Specifically, the sparse regularization term and least squares loss are first applied to construct the proposed objective function. And then, six kinds of quantum registers and their initial states are prepared. In addition, quantum techniques, such as quantum phase estimation and controlled rotation, are employed to construct an alternating iterative quantum circuit to obtain the final quantum state of the feature selection variable. Finally, a series of experiments are conducted to verify that the proposed algorithm can accurately select important features and has good robustness.
Mahalanobis distance is a distance measure that takes into account the relationship between features. In this paper, we proposed a quantum KNN classification algorithm based on the Mahalanobis distance, which combines the classical KNN algorithm with quantum computing to solve supervised classification problem in machine learning. Firstly, a quantum sub-algorithm for searching the minimum of disordered data set is utilized to find out K nearest neighbors of the testing sample. Finally, its category can be obtained by counting the categories of K nearest neighbors. Moreover, it is shown that the proposed quantum algorithm has the effect of squared acceleration compared with the classical counterpart.
High-dimensional data has long been a notoriously challenging issue. Existing quantum dimension reduction technology primarily focuses on quantum principal component analysis. However, there are only a few studies on quantum feature selection (QFS) algorithms, and these algorithms are often not robust. Additionally, there are limited quantum circuits specifically designed for feature selection, and they still cannot address the objective function based on sparse learning. To address these issues, this paper proposes a robust QFS algorithm by designing a novel sparse optimization circuit. Specifically, we first apply sparse regularization and least squares loss to construct the proposed objective function. Then, six types of quantum registers and their initial states are prepared. Furthermore, quantum techniques such as quantum phase estimation and controlled rotation are employed to construct a sparse optimization circuit, which is used to obtain the final quantum state of the feature selection variable.Finally, a series of experiments are conducted to verify the accuracy of the feature selection and the robustness of the proposed algorithm.
Although multi-label k-nearest neighbor (ML-kNN) is able to effectively solve multi-label learning (MLL) problem with local neighborhood similarity, its time complexity is nearly unacceptable with large-scale datasets. To solve this issue, we propose a novel ML-kNN algorithm with quantum computing techniques, which called quantum multi-label k-nearest neighbor (QML-kNN). In particular, we first accelerate the calculation of the prior probability by taking advantage of quantum phase estimation and Grover's amplitude amplification. Then, a controlled-SWAP test and a quantum k-maximal similarity search are used for efficiently identifying the neighbors. Subsequently, a quantum parallel counting circuit (QPCC) is designed to rapidly calculate the posterior probabilities. Experimental results demonstrate that QML-kNN is able to significantly reduce the time complexity of solving multi-label problems with performance improvement, achieving a substantial speedup over the classical MLL algorithm.
Quantum computing has risen as the new type of computer that theoretically reduces the time complexity of classical methods exponentially because of the nature of superposition. It is promising to reduce runtimes on large data sets in machine learning (ML). Meanwhile, k-nearest neighbor (kNN) is a simple ML algorithm that can be translated to a quantum version (QkNN) to perform classification tasks efficiently. Here, we show a new version of QkNN which has a speed up in time complexity by using a new design of quantum circuits called integrated swap test. This quantum circuit can load two N-dimensional states and calculate the fidelity between them. Results show that QkNN allows us to take a different approach to the ML field.