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

Christopher Rector; Jiangwen Sun

cs.LGOct 24, 2026

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

Authors: Christopher Rector, Jiangwen Sun

Organizations: Computer Science, Old Dominion University, 1 Old Dominion University, Norfolk, 23529, VA, United States of America.

Abstract

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.

Figures & tables

Panel of Figure 2 — Figure 2: A quantum circuit which encodes an 8-element, real-valued vector

Figure 3: Points $p_{\alpha 1}$ and $p_{\alpha 2}$ normalized as $p_{n1}$ and $p_{n2}$ to fit the encoding constraints of GBQCs.

Figure 4: To be encoded into a GBQC, the points $p_{\alpha}$ and $p_{\beta}$ must be normalized to $p_{\alpha n}$ and $p_{\beta n}$ , respectively.

Figure 5: Artificially modifying a point $p_{\alpha}$ to map it to the surface of a higher dimensional sphere of radius $\beta$ .

Panel of Figure 6 — Figure 6: The quantum circuit to compute Euclidean distance, with the ancillary qubit $|a\rangle$ in the zeroth quantum register, the address register $|j\rangle$ in the first, and the data $|\alpha\rangle$ in the second.

Author	Metric	Circuit Depth	Circuit Width	Circuits
Fastovets Fastovets et al. (2019)	Fidelity	$O(\log_{2}(N))$	$\lceil\log_{2}(N)\rceil$	$QR$
Hai Hai et al. (2022)	Fidelity	$O(\log^{2}_{2}(N))$	$O(N)$	$QR$
Afham Afham et al. (2020)	Fidelity	$O(\log_{2}(N))$	$O(\log_{2}(QN))$	$R$
Ruan Ruan et al. (2017)	Hamming	$O(N^{3})$	$N(Q+1)+1$	$R$
Zardini Zardini et al. (2023)	Euclidean	$O(\log_{2}(QF)+N)$	$\lceil\log_{2}(Q)\rceil+\lceil\log_{2}(F)\rceil+2$	$R$
This paper	Euclidean	$O(\log_{2}(Q)\log_{2}(N))$	$\lceil\log_{2}(Q)\rceil+\lceil\log_{2}(N+1)\rceil+1$	$R$

Table 1: A comparison of circuit depth and width between quantum KNN algorithms

Dataset	Classes	Size	Features
Iris - setosa & versicolor	2	100	4
Iris - setosa & virginica	2	100	4
Iris - versicolor & virginica	2	100	4
Transfusion	2	748	4
Vertebral column	2	310	6
Ecoli - cp & im	2	220	7

Table 2: Datasets provided by UCI

Experiment	k=3			k=5			k=7			k=9
Experiment	$\Delta$ Acc	JI	AJI	$\Delta$ Acc	JI	AJI	$\Delta$ Acc	JI	AJI	$\Delta$ Acc	JI	AJI
Setosa-Versicolor	0.000	0.993	0.993	0.000	0.988	0.989	0.000	0.987	0.990	0.000	0.986	0.989
Setosa-Versicolor	$\pm$ 0.000	$\pm$ 0.013	$\pm$ 0.014	$\pm$ 0.000	$\pm$ 0.010	$\pm$ 0.012	$\pm$ 0.000	$\pm$ 0.014	$\pm$ 0.013	$\pm$ 0.000	$\pm$ 0.016	$\pm$ 0.013
Setosa-Virginica	0.000	0.997	0.994	0.001	0.988	0.992	0.000	0.989	0.992	0.001	0.984	0.990
Setosa-Virginica	$\pm$ 0.000	$\pm$ 0.007	$\pm$ 0.012	$\pm$ 0.000	$\pm$ 0.015	$\pm$ 0.012	$\pm$ 0.000	$\pm$ 0.023	$\pm$ 0.015	$\pm$ 0.000	$\pm$ 0.020	$\pm$ 0.016
Versicolor-Virginica	0.000	0.973	0.974	0.000	0.972	0.973	0.000	0.969	0.973	0.001	0.969	0.972

Table 3: The mean difference in accuracy (

\Delta\ Acc

) between the classical KNN computation and the ideal statevector QKNN simulation with its standard deviation, and the mean Jaccard Index (JI) and Average JI (AJI) with standard deviation using the KNN results computed via binary arithmetic as truth.

Panel of Figure 7 — Figure 7: The mean accuracy ( 7a ), $JI$ ( 7b ), and $AJI$ ( 7c ) of the map encoding QKNN algorithm executed on Qiskit’s ideal StatevectorSimulator backend vs the same algorithm executed on Qiskit’s AerSimulator backend with realistic noise.

Panel of Figure 8 — Figure 8: The mean accuracy ( 8a ), $JI$ ( 8b ), and $AJI$ ( 8c ) of simulated QKNN using the map encoding technique compared to the extension encoding technique Zardini et al. (2023) .

Figure 9: The effect of increasing the number of circuit executions and measurements (shots) on the Average Jaccard Index

k-Nearest Neighbors

k-Nearest Neighbors (k-NN) predicts or retrieves from nearby data points using local similarity for classification, regression, clustering, and uncertainty.

See all 34 papers

Quantum Evolution Kernel for Node-Attributed Graphs
Oct 27, 2026Manuel Padovani, Alessandra Di Pierro, Claudia DaffaraQuantum Kernel Methods Graph Representation Learning
Department of Computer Science, University of Verona, Verona, Italy
Distance Prediction for Quantum Codes
Oct 13, 2026Nadav Schneider, Eliya NachmaniQuantum LDPC Codes Quantum Error Correction
School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Israel
Optimal algorithmic complexity of inference in quantum kernel methods
Apr 16, 2026Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2Query Complexity Quantum Kernel Methods
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany · Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany · Department of Quantum Information Science and Engineering, Sejong University, 209 Neungdong-ro, Gwangjin-gu, 05006, Seoul, Republic of Korea +1

Oct 27, 2026J/K move · Enter open · S save

Quantum Evolution Kernel for Node-Attributed Graphs

Manuel Padovani, Alessandra Di Pierro, Claudia Daffara

Department of Computer Science, University of Verona, Verona, Italy

Quantum Kernel Methods Graph Representation Learning Quantum Data Encoding

Open paper AskPDF arXiv

We present a novel approach to embed node-attributed graphs onto neutral-atom quantum computers, and propose an application to digit recognition. Our approach extends PASQAL's quantum evolution kernel (QEK) by introducing a node-level feature encoding based on three-level quantum states. To this purpose, we present a prototype showing how the resulting embedding can be leveraged to extract correlation-based information for classification tasks. The entire quantum process is simulated using Pasqal's Pulser library, which inevitably imposes constraints on the size of the experimental datasets. We compare our method with classical baselines to evaluate its potential. We show that, for the digit recognition task, our method achieves a higher mean accuracy than the more commonly used Jensen-Shannon distance-based methods by utilizing the Wasserstein distance.

Abstract

k-Nearest Neighbors

Explore similar work

Quantum Evolution Kernel for Node-Attributed Graphs

Distance Prediction for Quantum Codes

Optimal algorithmic complexity of inference in quantum kernel methods