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

Multi-class quantum k-nearest-neighbour classification in a single quantum circuit

Razieh Abdolahi, M. Reza Soleymani, Walaa Hamouda

Published Oct 8, 2026• 0 citations
Publisher

Abstract

Abstract In this paper we present a novel quantum k-nearest-neighbour circuit. The k-nearest-neighbour problem asks for the K closest stored points to a query among all data; quantum interference allows every stored point of every class to be compared in a single execution, a substantial computational gain. Quantum k-nearest-neighbour designs to date have rested on assumed primitives—quantum random-access memory, oracle access, amplitude-amplified search—which remain hypothetical and serve mainly to set limits on what the algorithms could achieve, or they restrict the distance metric or the number of classes. Our design uses none of these: no quantum random-access memory, no oracle, no metric restriction, no binary-class limit, and every operation is a practically implementable gate. Training members of each class are loaded into a dedicated register in superposition, a butterfly network of controlled-SWAP stages routes all classes to a common comparison position, and the class and member identity of every neighbour is read directly from the measurement statistics. The architecture rests on closed-form expressions for the post-selected probabilities and a geometric analysis showing that inverse stereographic projection carries the Euclidean nearest-neighbour ranking onto state fidelity with a sharp distortion bound. In simulation the circuit reproduces its intended decision rule exactly, and its accuracy matches classical k-nearest neighbours across a controlled benchmark at a realistic measurement budget. Every loading and sampling cost is stated in full—costs that most prior work hides by assuming quantum random-access memory.

DOI
10.21203/rs.3.rs-10705827/v1

Related papers

Quantum algorithm for neural network enhanced multi-class parallel classification

Anqi Zhang, Xiaoyun He, Shengmei Zhao

Using the properties of quantum superposition, we propose a quantum classification algorithm to efficiently perform multi-class classification tasks, where the training data are loaded into parameterized operators which are applied to the basis of the quantum state in quantum circuit composed by \emph{sample register} and \emph{label register}, and the parameters of quantum gates are optimized by a hybrid quantum-classical method, which is composed of a trainable quantum circuit and a gradient-based classical optimizer. After several quantum-to-class repetitions, the quantum state is optimal that the state in \emph{sample register} is the same as that in \emph{label register}. %A structure of loading data many times is performed as a quantum version of neural network to improve the expression ability of quantum circuit. For a classification task of $L$-class, the analysis shows that the space and time complexity of the quantum circuit are $O(L*logL)$ and $O(logL)$, respectively. The numerical simulation results of 2-class task and 5-class task show that the proposed algorithm has a higher classification accuracy, faster convergence and higher expression ability. The classification accuracy and the speed of converging can also be improved by increasing the number times of applying multi-qubit controlled operators on the quantum circuit, especially for multiple classes classification.

arXiv:2203.04097•Mar 8, 2022•0 citations

Comparison of Two Quantum Nearest Neighbor Classifiers on IBM’s Quantum Simulator

Wei Hu

Today computers are used to store data in memory and then process them. In our big data era, we are facing the challenge of storing and processing the data simply due to their fast ever growing size. Quantum computation offers solutions to these two prominent issues quantum mechanically and beautifully. Through careful design to employ superposition, entanglement, and interference of quantum states, a quantum algorithm can allow a quantum computer to store datasets of exponentially large size as linear size and then process them in parallel. Quantum computing has found its way in the world of machine learning where new ideas and approaches are in great need as the classical computers have reached their capacity and the demand for processing big data grows much faster than the computing power the classical computers can provide today. Nearest neighbor algorithms are simple, robust, and versatile supervised machine learning algorithms, which store all training data points as their learned “model” and make the prediction of a new test data point by computing the distances between the query point and all the training data points. Quantum counterparts of these classical algorithms provide efficient and elegant ways to deal with the two major issues of storing data in memory and computing the distances. The purpose of our study is to select two similar quantum nearest neighbor algorithms and use a simple dataset to give insight into how they work, highlight their quantum nature, and compare their performances on IBM’s quantum simulator.

Natural Science•Jan 1, 2018•10 citations

Quantum K-Nearest Neighbors: Utilizing QRAM and SWAP-Test Techniques for Enhanced Performance

Alberto Maldonado-Romo, Jesús Yaljá Montiel-Pérez, Victor Onofre +2 more

This work introduces a quantum K-Nearest Neighbor (K-NN) classifier algorithm. The algorithm utilizes angle encoding through a Quantum Random Access Memory (QRAM) using n number of qubit addresses with O(log(n)) space complexity. It incorporates Grover’s algorithm and the quantum SWAP-Test to identify similar states and determine the nearest neighbors with high probability, achieving Om search complexity, where m is the qubit address. We implement a simulation of the algorithm using IBM’s Qiskit with GPU support, applying it to the Iris and MNIST datasets with two different angle encodings. The experiments employ multiple QRAM cell sizes (8, 16, 32, 64, 128) and perform ten trials per size. According to the performance, accuracy values in the Iris dataset range from 89.3 ± 5.78% to 94.0 ± 1.56%. The MNIST dataset’s mean binary accuracy values range from 79.45 ± 18.84% to 94.00 ± 2.11% for classes 0 and 1. Additionally, a comparison of the results of this proposed approach with different state-of-the-art versions of QK-NN and the classical K-NN using Scikit-learn. This method achieves a 96.4 ± 2.22% accuracy in the Iris dataset. Finally, this proposal contributes an experimental result to the state of the art for the MNIST dataset, achieving an accuracy of 96.55 ± 2.00%. This work presents a new implementation proposal for QK-NN and conducts multiple experiments that yield more robust results than previous implementations. Although our average performance approaches still need to surpass the classic results, an experimental increase in the size of QRAM or the amount of data to encode is not achieved due to limitations. However, our results show promising improvement when considering working with more feature numbers and accommodating more data in the QRAM.

Mathematics•Jun 16, 2024•12 citations

Improving the Designs of Nearest Neighbour Quantum Circuits for 1D and 2D Architectures

Chandan Bandyopadhyay, Anirban Bhattacharjee, Robert Wille +2 more

In recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.

IETE Journal of Research•Sep 27, 2020•6 citations

A Proposed Quantum Classification Algorithm for Symbol Detection with Noisy Observation

Srinath Koya, Mostafizur Rahaman Laskar, Amit Kumar Dutta

Quantum machine learning (QML) and quantum communication (QC) are emerging areas of research for complexity-efficient data processing, information retrieval, system, and simulations. Towards next-generation vehicular technology, quantum circuits and algorithms are critical in providing faster and more reliable solutions. Here, we show a modified quantum K-nearest neighbour (QKNN) algorithm for symbol detection in the communication system. In the proposed algorithm, we embed a quantum swap-test circuit for the distance computation between unknown symbols with known training symbols with a memory-efficient strategy, which eliminated quantum search operations for the small-search space such as 16-QAM symbols. The proposed quantum circuit is simulated on an IBM quantum machine and the numerical results are shown to demonstrate the efficacy of the proposed framework. The classification accuracy as a performance metric is shown and the improvement of quantum resources in terms of gate complexity is discussed.

IEEE Vehicular Technology Conference•Jun 1, 2023•2 citations

A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation

Enrico Zardini, Enrico Blanzieri, Davide Pastorello

Abstract The k-nearest neighbors (k-NN) is a basic machine learning (ML) algorithm, and several quantum versions of it, employing different distance metrics, have been presented in the last few years. Although the Euclidean distance is one of the most widely used distance metrics in ML, it has not received much consideration in the development of these quantum variants. In this article, a novel quantum k-NN algorithm based on the Euclidean distance is introduced. Specifically, the algorithm is characterized by a quantum encoding requiring a low number of qubits and a simple quantum circuit not involving oracles, aspects that favor its realization. In addition to the mathematical formulation and some complexity observations, a detailed empirical evaluation with simulations is presented. In particular, the results have shown the correctness of the formulation, a drop in the performance of the algorithm when the number of measurements is limited, the competitiveness with respect to some classical baseline methods in the ideal case, and the possibility of improving the performance by increasing the number of measurements.

arXiv:2305.04287•Quantum Machine Intelligence•Apr 23, 2024•41 citations
Abstract In this paper we present a novel quantum k-nearest-neighbour circuit. The k-nearest-neighbour problem asks for the K closest stored points to a query among all data; quantum interference allows every stored point of every class to be compared in a single execution, a substantial computational gain. Quantum k-nearest-neighbour designs to date have rested on assumed primitives—quantum random-access memory, oracle access, amplitude-amplified search—which remain hypothetical and serve mainly to set limits on what the algorithms could achieve, or they restrict the distance metric or the number of classes. Our design uses none of these: no quantum random-access memory, no oracle, no metric restriction, no binary-class limit, and every operation is a practically implementable gate. Training members of each class are loaded into a dedicated register in superposition, a butterfly network of controlled-SWAP stages routes all classes to a common comparison position, and the class and member identity of every neighbour is read directly from the measurement statistics. The architecture rests on closed-form expressions for the post-selected probabilities and a geometric analysis showing that inverse stereographic projection carries the Euclidean nearest-neighbour ranking onto state fidelity with a sharp distortion bound. In simulation the circuit reproduces its intended decision rule exactly, and its accuracy matches classical k-nearest neighbours across a controlled benchmark at a realistic measurement budget. Every loading and sampling cost is stated in full—costs that most prior work hides by assuming quantum random-access memory.
Using the properties of quantum superposition, we propose a quantum classification algorithm to efficiently perform multi-class classification tasks, where the training data are loaded into parameterized operators which are applied to the basis of the quantum state in quantum circuit composed by \emph{sample register} and \emph{label register}, and the parameters of quantum gates are optimized by a hybrid quantum-classical method, which is composed of a trainable quantum circuit and a gradient-based classical optimizer. After several quantum-to-class repetitions, the quantum state is optimal that the state in \emph{sample register} is the same as that in \emph{label register}. %A structure of loading data many times is performed as a quantum version of neural network to improve the expression ability of quantum circuit. For a classification task of LLL-class, the analysis shows that the space and time complexity of the quantum circuit are O(L∗logL)O(L*logL)O(L∗logL) and O(logL)O(logL)O(logL), respectively. The numerical simulation results of 2-class task and 5-class task show that the proposed algorithm has a higher classification accuracy, faster convergence and higher expression ability. The classification accuracy and the speed of converging can also be improved by increasing the number times of applying multi-qubit controlled operators on the quantum circuit, especially for multiple classes classification.
Today computers are used to store data in memory and then process them. In our big data era, we are facing the challenge of storing and processing the data simply due to their fast ever growing size. Quantum computation offers solutions to these two prominent issues quantum mechanically and beautifully. Through careful design to employ superposition, entanglement, and interference of quantum states, a quantum algorithm can allow a quantum computer to store datasets of exponentially large size as linear size and then process them in parallel. Quantum computing has found its way in the world of machine learning where new ideas and approaches are in great need as the classical computers have reached their capacity and the demand for processing big data grows much faster than the computing power the classical computers can provide today. Nearest neighbor algorithms are simple, robust, and versatile supervised machine learning algorithms, which store all training data points as their learned “model” and make the prediction of a new test data point by computing the distances between the query point and all the training data points. Quantum counterparts of these classical algorithms provide efficient and elegant ways to deal with the two major issues of storing data in memory and computing the distances. The purpose of our study is to select two similar quantum nearest neighbor algorithms and use a simple dataset to give insight into how they work, highlight their quantum nature, and compare their performances on IBM’s quantum simulator.
This work introduces a quantum K-Nearest Neighbor (K-NN) classifier algorithm. The algorithm utilizes angle encoding through a Quantum Random Access Memory (QRAM) using n number of qubit addresses with O(log(n)) space complexity. It incorporates Grover’s algorithm and the quantum SWAP-Test to identify similar states and determine the nearest neighbors with high probability, achieving Om search complexity, where m is the qubit address. We implement a simulation of the algorithm using IBM’s Qiskit with GPU support, applying it to the Iris and MNIST datasets with two different angle encodings. The experiments employ multiple QRAM cell sizes (8, 16, 32, 64, 128) and perform ten trials per size. According to the performance, accuracy values in the Iris dataset range from 89.3 ± 5.78% to 94.0 ± 1.56%. The MNIST dataset’s mean binary accuracy values range from 79.45 ± 18.84% to 94.00 ± 2.11% for classes 0 and 1. Additionally, a comparison of the results of this proposed approach with different state-of-the-art versions of QK-NN and the classical K-NN using Scikit-learn. This method achieves a 96.4 ± 2.22% accuracy in the Iris dataset. Finally, this proposal contributes an experimental result to the state of the art for the MNIST dataset, achieving an accuracy of 96.55 ± 2.00%. This work presents a new implementation proposal for QK-NN and conducts multiple experiments that yield more robust results than previous implementations. Although our average performance approaches still need to surpass the classic results, an experimental increase in the size of QRAM or the amount of data to encode is not achieved due to limitations. However, our results show promising improvement when considering working with more feature numbers and accommodating more data in the QRAM.
In recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.
Quantum machine learning (QML) and quantum communication (QC) are emerging areas of research for complexity-efficient data processing, information retrieval, system, and simulations. Towards next-generation vehicular technology, quantum circuits and algorithms are critical in providing faster and more reliable solutions. Here, we show a modified quantum K-nearest neighbour (QKNN) algorithm for symbol detection in the communication system. In the proposed algorithm, we embed a quantum swap-test circuit for the distance computation between unknown symbols with known training symbols with a memory-efficient strategy, which eliminated quantum search operations for the small-search space such as 16-QAM symbols. The proposed quantum circuit is simulated on an IBM quantum machine and the numerical results are shown to demonstrate the efficacy of the proposed framework. The classification accuracy as a performance metric is shown and the improvement of quantum resources in terms of gate complexity is discussed.
Abstract The k-nearest neighbors (k-NN) is a basic machine learning (ML) algorithm, and several quantum versions of it, employing different distance metrics, have been presented in the last few years. Although the Euclidean distance is one of the most widely used distance metrics in ML, it has not received much consideration in the development of these quantum variants. In this article, a novel quantum k-NN algorithm based on the Euclidean distance is introduced. Specifically, the algorithm is characterized by a quantum encoding requiring a low number of qubits and a simple quantum circuit not involving oracles, aspects that favor its realization. In addition to the mathematical formulation and some complexity observations, a detailed empirical evaluation with simulations is presented. In particular, the results have shown the correctness of the formulation, a drop in the performance of the algorithm when the number of measurements is limited, the competitiveness with respect to some classical baseline methods in the ideal case, and the possibility of improving the performance by increasing the number of measurements.