Benchmarking quantum versions of the kNN algorithm with a metric based on amplitude-encoded features

Area of Science:

• Quantum Computing
• Machine Learning
• Pattern Recognition

Background:

• The k-Nearest Neighbors (kNN) algorithm is a fundamental machine learning technique.
• Quantum computing offers potential speedups for complex computational tasks.
• Existing quantum kNN (QkNN) algorithms face challenges with qubit efficiency and memory requirements.

Purpose of the Study:

• To introduce a novel, memory-efficient quantum subroutine for pattern distance computation.
• To integrate this subroutine into two prominent QkNN algorithms (Schuld et al. and Quezada et al.).
• To compare the performance and resource utilization of QkNN algorithms with and without the proposed subroutine.

Main Methods:

• Development of a quantum subroutine for calculating pattern distances using amplitude-encoded features.
• Integration of the subroutine into Schuld's and Quezada's QkNN frameworks.
• Empirical evaluation across thirteen diverse datasets, comparing qubit usage and classification metrics (accuracy, F1 score).

Main Results:

• The proposed subroutine consistently reduced the number of required qubits by at least 50% for both QkNN algorithms.
• Overall performance was largely maintained, with some datasets showing improvements and others slight decreases in accuracy or F1 score.
• Specific improvements were noted in datasets like Cryotherapy and Balance Scale for Schuld's algorithm, and Caesarian, Haberman, and Immunotherapy for Quezada's algorithm.

Conclusions:

• The developed quantum subroutine offers a significant improvement in qubit efficiency for QkNN algorithms.
• This memory-saving approach is a valuable contribution to practical quantum machine learning implementations.
• Further research can explore broader applications and optimizations of this quantum distance computation method.