A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916219957805056 |
|---|---|
| author | Zardini, Enrico Blanzieri, Enrico Pastorello, Davide |
| author_facet | Zardini, Enrico Blanzieri, Enrico Pastorello, Davide |
| contents | 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 characterised 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_04287 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation Zardini, Enrico Blanzieri, Enrico Pastorello, Davide Emerging Technologies Quantum Physics 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 characterised 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. |
| title | A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation |
| topic | Emerging Technologies Quantum Physics |
| url | https://arxiv.org/abs/2305.04287 |