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

arXiv:2003.09187

Quantum kkk-nearest neighbors algorithm

Afrad Basheer, A. Afham, Sandeep K. Goyal

Published Mar 20, 2020• 24 citations
arXivHTMLPDF

Abstract

One of the simplest and most effective classical machine learning algorithms is the $k$-nearest neighbors algorithm ($k$NN) which classifies an unknown test state by finding the $k$ nearest neighbors from a set of $M$ train states. Here we present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. We show that Q$k$NN algorithm can be reduced to an instance of the quantum $k$-maxima algorithm, hence the query complexity of Q$k$NN is $O(\sqrt{kM})$. The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.

DOI
10.48550/arxiv.2003.09187

Related papers

A Fidelity-Based Quantum K-Nearest Neighbors (FQKNN) for Enhanced Classification

Amine Zeguendry, Zahi Jarir, Mohamed Quafafou

Dealing with high-dimensional data is a well-known limitation for the classic K-Nearest Neighbors (KNN) algorithm, creating substantial computational and memory overhead. While Quantum Machine Learning (QML) presents a compelling alternative, many existing Quantum KNN (QKNN) frameworks are largely theoretical, remaining impractical for current hardware due to their significant qubit demands. This paper introduces the Fidelity-Based Quantum K-Nearest Neighbors (FQKNN) algorithm, a method specifically designed for feasibility on near-term devices. Our primary contribution is the use of quantum fidelity as a similarity function, which offers a more nuanced metric than conventional distance calculations. This is combined with an efficient amplitude encoding strategy that logarithmically scales the qubit requirement to just log2(N) for an N-dimensional feature vector. This combination makes FQKNN a resource-efficient and practical algorithm. We validated its performance on the benchmark Iris and Breast Cancer datasets, achieving classification accuracies of 96.7% and 93.3% respectively, surpassing the performance of the classical KNN baseline. These findings not only confirm the viability of our fidelity-based similarity measure but also underscore the demonstrable potential of QML to enhance classification tasks.

International Conference on Optimization and Applications (ICOA)•Oct 16, 2025•1 citation

Quantum k-nearest neighbor machine learning algorithm

Afham, Afrad Basheer, Sandeep K. Goyal

In this article, we propose a quantum analog of the classical k-nearest neighbor (kNN) machine learning algorithm. Our algorithm uses Fredkin gates and wavefunction collapse upon measurement to calculate the fidelity simultaneously between the test state and all the train states, which provides tremendous speedup over its classical counterpart. The quantum kNN algorithm presented here is capable of dealing with completely unknown test states encoded in quantum systems.

•Mar 20, 2020•4 citations

Performance Analysis and Noise Impact of a Novel Quantum KNN Algorithm for Machine Learning

Asif Akhtab Ronggon, Md. Saifur Rahman

This paper presents a novel quantum K-nearest neighbors (QKNN) algorithm, which offers improved performance over the classical k-NN technique by incorporating quantum computing (QC) techniques to enhance classification accuracy, scalability, and robustness. The proposed modifications focus on optimizing quantum data encoding using Hadamard and rotation gates, ensuring more effective rendering of classical data in quantum states. In addition, the quantum feature extraction process is significantly enhanced by the use of entangled gates such as IsingXY and CNOT, which enables better feature interactions and class separability. A novel quantum distance metric, based on the swap test, is introduced to calculate similarity measures between various quantum states, offering superior accuracy and computational efficiency compared to traditional Euclidean distance metrics. We assess the achievement of the proposed QKNN algorithm on three benchmark datasets: Wisconsin Breast Cancer, Iris, and Bank Note Authentication, and have noted its superior performance relative to both classical k-NN (CKNN) and Quantum Neural Network (QNN). The proposed QKNN algorithm is found to achieve prediction accuracies of 98.25%, 100%, and 99.27% ,respectively, for the three datasets, while the customized QNN shows prediction accuracies of only 97.17%, 83.33%, and 86.18%, respectively. Furthermore, we address the challenges of quantum noise by incorporating a repetition encoding-based error mitigation strategy, which ensures the stability and resilience of the algorithm in noisy quantum environments. The results highlight the potential of the proposed QKNN as a scalable, efficient and robust quantum-enhanced machine learning algorithm, especially in high-dimensional and complex datasets, when traditional approaches frequently fail.

arXiv:2505.06441•May 9, 2025•1 citation

A quantum k-nearest neighbors implementation using magnitude-aware comparisons

Christopher Rector, Jiangwen Sun

Much attention has recently been devoted to the k-nearest neighbors (KNN) algorithm as a case study for quantum computing algorithms. Several algorithms have devised methods to compute a similarity metric to solve Quantum KNN (QKNN). This paper presents a practical quantum encoding technique that enables Euclidean distance calculation between vectors with different L2 norms by appending a single component to each vector, then uses it in the QKNN problem. It is arguably simpler to understand and implement than comparable methods and uses fewer qubits. Further, an implementation of this algorithm is provided and is used to benchmark it against a recent Euclidean-distance QKNN method on standard labeled datasets. In addition to demonstrating proper formulation, the results show marked improvement over similar implementations during simulation with realistic noise due to the use of fewer qubits and thus more coherent circuits.

arXiv:2610.33739•Oct 24, 2026•0 citations

Quantum Nearest-Neighbor Algorithms for Machine Learning

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

We present several quantum algorithms for performing nearest-neighbor learning. At the core of our algorithms are fast and coherent quantum methods for computing distance metrics such as the inner product and Euclidean distance. We prove upper bounds on the number of queries to the input data required to compute these metrics. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to the corresponding classical algorithm. In certain cases, we show exponential or even super-exponential reductions over the classical analog. We study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.

Quantum Information and Computation•Jan 9, 2014•68 citations

Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

We present quantum algorithms for performing nearest-neighbor learning and $k$--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.

Quantum Information and Computation•Mar 1, 2015•243 citations
One of the simplest and most effective classical machine learning algorithms is the kkk-nearest neighbors algorithm (kkkNN) which classifies an unknown test state by finding the kkk nearest neighbors from a set of MMM train states. Here we present a quantum analog of classical kkkNN −-− quantum kkkNN (QkkkNN) −-− based on fidelity as the similarity measure. We show that QkkkNN algorithm can be reduced to an instance of the quantum kkk-maxima algorithm, hence the query complexity of QkkkNN is O(kM)O(\sqrt{kM})O(kM​). The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical kkkNN and existing quantum kkkNN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.
Dealing with high-dimensional data is a well-known limitation for the classic K-Nearest Neighbors (KNN) algorithm, creating substantial computational and memory overhead. While Quantum Machine Learning (QML) presents a compelling alternative, many existing Quantum KNN (QKNN) frameworks are largely theoretical, remaining impractical for current hardware due to their significant qubit demands. This paper introduces the Fidelity-Based Quantum K-Nearest Neighbors (FQKNN) algorithm, a method specifically designed for feasibility on near-term devices. Our primary contribution is the use of quantum fidelity as a similarity function, which offers a more nuanced metric than conventional distance calculations. This is combined with an efficient amplitude encoding strategy that logarithmically scales the qubit requirement to just log2(N) for an N-dimensional feature vector. This combination makes FQKNN a resource-efficient and practical algorithm. We validated its performance on the benchmark Iris and Breast Cancer datasets, achieving classification accuracies of 96.7% and 93.3% respectively, surpassing the performance of the classical KNN baseline. These findings not only confirm the viability of our fidelity-based similarity measure but also underscore the demonstrable potential of QML to enhance classification tasks.
This paper presents a novel quantum K-nearest neighbors (QKNN) algorithm, which offers improved performance over the classical k-NN technique by incorporating quantum computing (QC) techniques to enhance classification accuracy, scalability, and robustness. The proposed modifications focus on optimizing quantum data encoding using Hadamard and rotation gates, ensuring more effective rendering of classical data in quantum states. In addition, the quantum feature extraction process is significantly enhanced by the use of entangled gates such as IsingXY and CNOT, which enables better feature interactions and class separability. A novel quantum distance metric, based on the swap test, is introduced to calculate similarity measures between various quantum states, offering superior accuracy and computational efficiency compared to traditional Euclidean distance metrics. We assess the achievement of the proposed QKNN algorithm on three benchmark datasets: Wisconsin Breast Cancer, Iris, and Bank Note Authentication, and have noted its superior performance relative to both classical k-NN (CKNN) and Quantum Neural Network (QNN). The proposed QKNN algorithm is found to achieve prediction accuracies of 98.25%, 100%, and 99.27% ,respectively, for the three datasets, while the customized QNN shows prediction accuracies of only 97.17%, 83.33%, and 86.18%, respectively. Furthermore, we address the challenges of quantum noise by incorporating a repetition encoding-based error mitigation strategy, which ensures the stability and resilience of the algorithm in noisy quantum environments. The results highlight the potential of the proposed QKNN as a scalable, efficient and robust quantum-enhanced machine learning algorithm, especially in high-dimensional and complex datasets, when traditional approaches frequently fail.
Much attention has recently been devoted to the k-nearest neighbors (KNN) algorithm as a case study for quantum computing algorithms. Several algorithms have devised methods to compute a similarity metric to solve Quantum KNN (QKNN). This paper presents a practical quantum encoding technique that enables Euclidean distance calculation between vectors with different L2 norms by appending a single component to each vector, then uses it in the QKNN problem. It is arguably simpler to understand and implement than comparable methods and uses fewer qubits. Further, an implementation of this algorithm is provided and is used to benchmark it against a recent Euclidean-distance QKNN method on standard labeled datasets. In addition to demonstrating proper formulation, the results show marked improvement over similar implementations during simulation with realistic noise due to the use of fewer qubits and thus more coherent circuits.
We present several quantum algorithms for performing nearest-neighbor learning. At the core of our algorithms are fast and coherent quantum methods for computing distance metrics such as the inner product and Euclidean distance. We prove upper bounds on the number of queries to the input data required to compute these metrics. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to the corresponding classical algorithm. In certain cases, we show exponential or even super-exponential reductions over the classical analog. We study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.
We present quantum algorithms for performing nearest-neighbor learning and kkk--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.