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

International Conference on Natural Computation (ICNC)

A text classification algorithm based on quantum information

Songtao Shang, Minyong Shi, Wenqian Shang, Zhiguo Hong

Published Aug 1, 2015• 2 citations
Publisher

Abstract

Text classification is one of key problems in pattern recognition. The KNN algorithm is a widely used text classification algorithm, because it is simple, valid and non-parameters. The main idea of KNN algorithm is to calculate the similarity between the new sample with unknown class label and the training samples, and choosing the class label of the highest k nearest neighbors as the new sample's class label. However, the text contains hundreds and thousands of features. The similarity computing in large numbers of vector will cost many time. In fact that, many machine learning algorithms are unable to manipulate and compute large number of vectors in high-dimensional space. Quantum computing algorithms are good at computing high-dimensional vectors in large tensor product spaces. It can provide exponential speed-up over its classical counterparts. The N-dimensional quantum vectors represent 2N quantum superposition states. The similarity computing on the N-dimensional vectors is also on the 2N quantum superposition states simultaneously. Therefore, this paper introduces a KNN algorithms based on quantum computing, which uses fidelity to compute the similarity between two quantum states. The Control-Swap Test gate is very convenient as a fidelity estimator.

DOI
10.1109/icnc.2015.7378020

Related papers

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•13 citations

Quantum K‐Nearest Neighbor Classification Algorithm via a Divide‐and‐Conquer Strategy

Li‐Hua Gong, Wei Ding, Zi Li +2 more

Abstract The K‐nearest neighbor algorithm is one of the most frequently applied supervised machine learning algorithms. Similarity computing is considered to be the most crucial and time‐consuming step among the classical K‐nearest neighbor algorithm. A quantum K‐nearest neighbor algorithm is proposed based on the divide‐and‐conquer strategy. A quantum circuit is designed to calculate the fidelity between the test sample and each feature vector of the training dataset. The quantum K‐nearest neighbor algorithm has higher classification efficiency in high‐dimensional data processing. The classification accuracy of the proposed algorithm is equivalent to that of the classical K‐nearest neighbor algorithm under the IRIS dataset. In addition, compared with the typical quantum K‐nearest neighbor algorithms, the proposed classification method possesses higher classification accuracy with less calculation time, which has wide applications in the industrial field.

Advanced Quantum Technologies•Mar 12, 2024•71 citations

Quantum kkk-nearest neighbors algorithm

Afrad Basheer, A. Afham, Sandeep K. Goyal

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.

arXiv:2003.09187•Mar 20, 2020•58 citations

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•37 citations

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•6 citations

Quantum‐Enhanced K‐Nearest Neighbors for Text Classification: A Hybrid Approach with Unified Circuit and Reduced Quantum Gates

Amine Zeguendry, Zahi Jarir, Mohamed Quafafou

Abstract Text classification, a key process in natural language processing (NLP), relies on the k‐nearest neighbors (KNN) algorithm for its simplicity and effectiveness. Traditional methods often grapple with the high‐dimensional nature of textual data, leading to substantial computational demands. This study introduces a novel classical quantum k‐nearest neighbors (CQKNN) algorithm, which integrates quantum circuits into a conventional machine‐learning framework to enhance computational efficiency and reduce storage requirements. This hybrid approach uses a unified quantum circuit that simplifies multiple similarity calculations through mid‐circuit measurements and qubit reset operations, significantly improving upon traditional multi‐circuit quantum k‐nearest neighbors (QKNN) models. The CQKNN algorithm, tested on datasets such as SMS Spam Collection, Twitter US Airline Sentiment, and IMDB Movie Reviews, not only outperforms classical KNN but also addresses challenges posed by noisy intermediate‐scale quantum (NISQ) devices through advanced error mitigation techniques. This work highlights resource efficiency and reduced gate complexity and demonstrates the practical application of fidelity in quantum similarity calculations, setting new standards for quantum‐enhanced machine learning and advancing current quantum technology capabilities in complex data classification tasks.

Advanced Quantum Technologies•Aug 1, 2024•11 citations
Text classification is one of key problems in pattern recognition. The KNN algorithm is a widely used text classification algorithm, because it is simple, valid and non-parameters. The main idea of KNN algorithm is to calculate the similarity between the new sample with unknown class label and the training samples, and choosing the class label of the highest k nearest neighbors as the new sample's class label. However, the text contains hundreds and thousands of features. The similarity computing in large numbers of vector will cost many time. In fact that, many machine learning algorithms are unable to manipulate and compute large number of vectors in high-dimensional space. Quantum computing algorithms are good at computing high-dimensional vectors in large tensor product spaces. It can provide exponential speed-up over its classical counterparts. The N-dimensional quantum vectors represent 2N quantum superposition states. The similarity computing on the N-dimensional vectors is also on the 2N quantum superposition states simultaneously. Therefore, this paper introduces a KNN algorithms based on quantum computing, which uses fidelity to compute the similarity between two quantum states. The Control-Swap Test gate is very convenient as a fidelity estimator.
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.
Abstract The K‐nearest neighbor algorithm is one of the most frequently applied supervised machine learning algorithms. Similarity computing is considered to be the most crucial and time‐consuming step among the classical K‐nearest neighbor algorithm. A quantum K‐nearest neighbor algorithm is proposed based on the divide‐and‐conquer strategy. A quantum circuit is designed to calculate the fidelity between the test sample and each feature vector of the training dataset. The quantum K‐nearest neighbor algorithm has higher classification efficiency in high‐dimensional data processing. The classification accuracy of the proposed algorithm is equivalent to that of the classical K‐nearest neighbor algorithm under the IRIS dataset. In addition, compared with the typical quantum K‐nearest neighbor algorithms, the proposed classification method possesses higher classification accuracy with less calculation time, which has wide applications in the industrial field.
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.
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.
Abstract Text classification, a key process in natural language processing (NLP), relies on the k‐nearest neighbors (KNN) algorithm for its simplicity and effectiveness. Traditional methods often grapple with the high‐dimensional nature of textual data, leading to substantial computational demands. This study introduces a novel classical quantum k‐nearest neighbors (CQKNN) algorithm, which integrates quantum circuits into a conventional machine‐learning framework to enhance computational efficiency and reduce storage requirements. This hybrid approach uses a unified quantum circuit that simplifies multiple similarity calculations through mid‐circuit measurements and qubit reset operations, significantly improving upon traditional multi‐circuit quantum k‐nearest neighbors (QKNN) models. The CQKNN algorithm, tested on datasets such as SMS Spam Collection, Twitter US Airline Sentiment, and IMDB Movie Reviews, not only outperforms classical KNN but also addresses challenges posed by noisy intermediate‐scale quantum (NISQ) devices through advanced error mitigation techniques. This work highlights resource efficiency and reduced gate complexity and demonstrates the practical application of fidelity in quantum similarity calculations, setting new standards for quantum‐enhanced machine learning and advancing current quantum technology capabilities in complex data classification tasks.