arXiv:1805.06260

Image Classification Based on Quantum KNN Algorithm

Yijie Dang, Nan Jiang, Hao Hu, Zhuoxiao Ji, Wenyin Zhang

Published May 16, 2018• 6 citations

Abstract

Image classification is an important task in the field of machine learning and image processing. However, the usually used classification method --- the K Nearest-Neighbor algorithm has high complexity, because its two main processes: similarity computing and searching are time-consuming. Especially in the era of big data, the problem is prominent when the amount of images to be classified is large. In this paper, we try to use the powerful parallel computing ability of quantum computers to optimize the efficiency of image classification. The scheme is based on quantum K Nearest-Neighbor algorithm. Firstly, the feature vectors of images are extracted on classical computers. Then the feature vectors are inputted into a quantum superposition state, which is used to achieve parallel computing of similarity. Next, the quantum minimum search algorithm is used to speed up searching process for similarity. Finally, the image is classified by quantum measurement. The complexity of the quantum algorithm is only O((kM)^(1/2)), which is superior to the classical algorithms. Moreover, the measurement step is executed only once to ensure the validity of the scheme. The experimental results show that, the classification accuracy is 83.1% on Graz-01 dataset and 78% on Caltech-101 dataset, which is close to existing classical algorithms. Hence, our quantum scheme has a good classification performance while greatly improving the efficiency.

DOI: 10.48550/arxiv.1805.06260

Related papers

Quantum Image processing algorithms comparison using datasets of machine learning based applications

Barkha Singh, S. Indu, Sudipta Majumdar

Abstract This article analyzes and compares various Quantum learning algorithms on big data. The main contribution of this article is to provide a new machine-learning approach using Quantum computing for big data analysis with features of robust, novel, and effective Quantum machine images and transit mode. Currently, there is no efficient method for doing Quantum image recognition or classification due to the lack of an effective Quantum feature extraction technique. This work proposes a global Quantum feature extraction technique based on Schmidt decomposition for the first time. Additionally, a new version of the Quantum learning algorithm is shown, which uses the features' Hamming distance to classify images. With the help of algorithm analysis and experimental findings from the benchmark database Caltech 101, a successful method for large-scale image classification is developed and put forth in the context of big data. The proposed model yields an with an average accuracy of 98\% with the proposed enhanced Quantum classifier, QeSVM classifier, swarm particle optimizer with Twin wave SVM, QPSO-TWSVM, and other Q-CNN models on different Big Data sets.

Feb 12, 20241 citation

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 TechnologiesMar 12, 202465 citations

A text classification algorithm based on quantum information

Songtao Shang, Minyong Shi, Wenqian Shang +1 more

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.

International Conference on Natural Computation (ICNC)Aug 1, 20152 citations

Quantum Convolutional Neural Network for Color Image Classification

Muhammad Hamid, Bashir Alam, Om Pal

Abstract Current era is witnessing rapid growth in data and fast data processing methods. In the past few decades, artificial intelligence has matured exponentially and has been applied in many areas such as medicine, transport, finance, and many more. Classical machine learning methods are resource intensive and usually training models takes time. Quantum machine learning can be a alternate solution to this problem and can be used to solve complex data problems. Quantum machine learning utilizes parallel computing capabilities of quantum computers. Quantum machine learning methods can be used for image classification, which is an important task in data science. Here, we have proposed a quantum convolutional neural network for color image classification, where we have applied a quantum convolutional and pooling layers to reduce the number of features without losing crucial information. We have used the proposed method to classify color image of the CIFAR-10 dataset. We have compared the validation accuracies and loss during training for both classical and quantum convolutional neural network. Our results show that we have achieved similar accuracy with less number of trainable parameters. We believe that this study will open new avenue for high dimensional data classification using quantum convolutional neural network in current and beyond NISQ era.

Aug 12, 20251 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 PhysicsOct 21, 202233 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.06441May 9, 20251 citation