A Quantum Algorithm for RF-based Fingerprinting Localization Systems

Fingerprinting is one of the mainstream technologies for localization. However, it needs significant storage overhead and running time, preventing it from scaling to support worldwide indoor/outdoor localization. Quantum computing has the potential to revolutionize computation by making some classically intractable problems solvable on quantum computers. In this paper, we propose a quantum fingerprint-based localization algorithm for enabling large-scale location tracking systems, envisioning future era of location tracking and spatial systems. Specifically, we propose a quantum algorithm that provides an exponential enhancement of both the space and running time complexity compared to the traditional classical systems. We give the details of how to build the quantum fingerprint, how to encode the received signal strength (RSS) measurements in quantum particles, and finally; present a quantum algorithm for calculating the cosine similarity between the online RSS measurements and the fingerprint ones. Results from deploying our algorithm in three real testbeds on IBM Quantum Experience machines confirm the ability of our quantum system to get the same accuracy as the classical one but with the potential exponential saving in both space and running time.