Quantum $k$-nearest neighbors algorithm

Abstract

One of the simplest and most effective classical machine learning algorithms is the $k$-nearest neighbors algorithm ($k$NN) which classifies an unknown test state by finding the $k$ nearest neighbors from a set of $M$ train states. Here we present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. We show that Q$k$NN algorithm can be reduced to an instance of the quantum $k$-maxima algorithm, hence the query complexity of Q$k$NN is $O(\sqrt{kM})$. The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.

arXiv comment21 pages, 11 figures. Final preprint version

References in corpus (10)

• Three qubits can be entangled in two inequivalent ways
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Machine learning phases of matter
• Quantum Algorithms Revisited
• Quantum Data Fitting
• Quantum state discrimination and its applications
• Quantum Analog-Digital Conversion
• A Quantum Algorithm for Finding $k$-Minima
• Learning to Detect Entanglement

Cited by in corpus (1)

• Riemannian-geometric generalizations of quantum fidelities and Bures-Wasserstein distance