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
PDF (CC BY)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

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

Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering

Alonso Viladomat Jasso, Ark Modi, Roberto Ferrara +4 more

Nearest-neighbour clustering is a simple yet powerful machine learning algorithm that finds natural application in the decoding of signals in classical optical-fibre communication systems. Quantum k-means clustering promises a speed-up over the classical k-means algorithm; however, it has been shown to not currently provide this speed-up for decoding optical-fibre signals due to the embedding of classical data, which introduces inaccuracies and slowdowns. Although still not achieving an exponential speed-up for NISQ implementations, this work proposes the generalised inverse stereographic projection as an improved embedding into the Bloch sphere for quantum distance estimation in k-nearest-neighbour clustering, which allows us to get closer to the classical performance. We also use the generalised inverse stereographic projection to develop an analogous classical clustering algorithm and benchmark its accuracy, runtime and convergence for decoding real-world experimental optical-fibre communication data. This proposed ‘quantum-inspired’ algorithm provides an improvement in both the accuracy and convergence rate with respect to the k-means algorithm. Hence, this work presents two main contributions. Firstly, we propose the general inverse stereographic projection into the Bloch sphere as a better embedding for quantum machine learning algorithms; here, we use the problem of clustering quadrature amplitude modulated optical-fibre signals as an example. Secondly, as a purely classical contribution inspired by the first contribution, we propose and benchmark the use of the general inverse stereographic projection and spherical centroid for clustering optical-fibre signals, showing that optimizing the radius yields a consistent improvement in accuracy and convergence rate.

arXiv:2308.03949•Entropy•Sep 20, 2023•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•3 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•51 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.
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.
Nearest-neighbour clustering is a simple yet powerful machine learning algorithm that finds natural application in the decoding of signals in classical optical-fibre communication systems. Quantum k-means clustering promises a speed-up over the classical k-means algorithm; however, it has been shown to not currently provide this speed-up for decoding optical-fibre signals due to the embedding of classical data, which introduces inaccuracies and slowdowns. Although still not achieving an exponential speed-up for NISQ implementations, this work proposes the generalised inverse stereographic projection as an improved embedding into the Bloch sphere for quantum distance estimation in k-nearest-neighbour clustering, which allows us to get closer to the classical performance. We also use the generalised inverse stereographic projection to develop an analogous classical clustering algorithm and benchmark its accuracy, runtime and convergence for decoding real-world experimental optical-fibre communication data. This proposed ‘quantum-inspired’ algorithm provides an improvement in both the accuracy and convergence rate with respect to the k-means algorithm. Hence, this work presents two main contributions. Firstly, we propose the general inverse stereographic projection into the Bloch sphere as a better embedding for quantum machine learning algorithms; here, we use the problem of clustering quadrature amplitude modulated optical-fibre signals as an example. Secondly, as a purely classical contribution inspired by the first contribution, we propose and benchmark the use of the general inverse stereographic projection and spherical centroid for clustering optical-fibre signals, showing that optimizing the radius yields a consistent improvement in accuracy and convergence rate.
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.