Quantum k-Nearest Neighbours Algorithm

Abstract

Quantum computing (QC) and machine learning (ML) are two disciplines experiencing tremendous growth these days. Machine learning works through picking up patterns in huge amounts of data to build a model, which it uses upon unseen data to make predictions. Various ML algorithms are nothing but different ways through which the machine can find interesting patterns in data. Quantum computers promises a different paradigm of computing - one where certain problems, such as prime factorisation, could be solved faster than any classical computer. We propose a quantum analog of the classical k-nearest neighbour (kNN) machine learning algorithm. Our algorithm uses Fredkin gates and wavefunction collapse upon measurement to estimate the fidelity simultaneously between the test state and all the train states, which is advantageous over its classical counterpart in certain situations. The quantum kNN algorithm presented here is capable of dealing with completely unknown test states encoded in quantum systems. We discuss the cost and analysis of our algorithm and compare it with other similar methods. As an example, we test this algorithm on the problem of classifying n-qubit pure entangled states.