research-article

Towards Quantum Computing for Location Tracking and Spatial Systems

Authors:

Moustafa YoussefAuthors Info & Claims

SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information Systems

Pages 278 - 281

https://doi.org/10.1145/3474717.3483958

Published: 04 November 2021 Publication History

Abstract

Quantum computing provides a new way for approaching problem solving, enabling efficient solutions for problems that are hard on classical computers. With researchers around the world showing quantum supremacy and the availability of cloud-based quantum computers, quantum computing is becoming a reality. In this paper, we explore the different directions of the use of quantum computing for location tracking and spatial systems. Specifically, we show an example for the expected gain of using quantum computing for localization by providing an efficient quantum algorithm for RF fingerprinting localization. The proposed quantum algorithm has a complexity that is exponentially better than its classical algorithm version, both in space and running time. We further discuss both software and hardware research challenges and opportunities that researchers can build on to explore this exciting new domain.

References

[1]

Heba Abdelnasser, Reham Mohamed, Ahmed Elgohary, Moustafa Farid Alzantot, He Wang, Souvik Sen, Romit Roy Choudhury, and Moustafa Youssef. 2015. SemanticSLAM: Using environment landmarks for unsupervised indoor localization. IEEE Transactions on Mobile Computing 15, 7 (2015), 1770--1782.

[2]

Heba Aly, Anas Basalamah, and Moustafa Youssef. 2015. LaneQuest: An accurate and energy-efficient lane detection system. In 2015 IEEE International Conference on Pervasive Computing and Communications (PerCom). IEEE.

[3]

Heba Aly and Moustafa Youssef. 2013. Dejavu: An Accurate Energy-Efficient Outdoor Localization System (SIGSPATIAL'13). Association for Computing Machinery, New York, NY, USA, 154--163. https://doi.org/10.1145/2525314.2525338

Digital Library

[4]

Heba Aly and Moustafa Youssef. 2013. New insights into wifi-based device-free localization. In Proceedings of the 2013 ACM conference on Pervasive and ubiquitous computing adjunct publication. 541--548.

Digital Library

[5]

Heba Aly and Moustafa Youssef. 2015. semMatch: Road semantics-based accurate map matching for challenging positioning data. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. 1--10.

Digital Library

[6]

Paramvir Bahl and Venkata N Padmanabhan. 2000. RADAR: An in-building RF-based user Location and Tracking System. In Proceedings IEEE INFOCOM 2000., Vol. 2. 775--784.

[7]

Ionut Constandache, Romit Roy Choudhury, and Injong Rhee. 2010. Towards Mobile Phone Localization without War-Driving. In Proceedings of the 29th Conference on Information Communications (INFOCOM'10). IEEE Press, 2321--2329.

Digital Library

[8]

Arute Frank et al. 2019. Quantum Supremacy using a Programmable Superconducting Processor. Nature 574, 7779 (01 Oct 2019), 505--510.

[9]

Andrew Mark Edmonds et al. 2021. Characterisation of CVD Diamond with High Concentrations of Nitrogen for Magnetic-field Sensing Applications. Materials for Quantum Technology (2021).

[10]

IBM Quantum Experience. 2021. IBM Quantum Systems Overview. (2021). https://quantum-computing.ibm.com/docs/manage/backends/

[11]

Elizabeth Gibney. 2020. Quantum Computer Race Intensifies as alternative Technology Gains Steam. (2020), 342--343.

[12]

Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing. ACM, 212--219.

Digital Library

[13]

Chen Gu, Ahmed Shokry, and Moustafa Youssef. 2021. The Effect of Ground Truth Accuracy on the Evaluation of Localization Systems. (2021).

[14]

Jay Hendricks. 2018. Quantum for Pressure. 14(2018).

[15]

Petar Jurcevic and et al. 2020. Demonstration of Quantum volume 64 on a Superconducting Quantum Computing System. (2020). arXiv:quantph/2008.08571

[16]

Dong Ma, Guohao Lan, Mahbub Hassan, Wen Hu, Mushfika Baishakhi Upama Ashraf Uddin, and Moustafa Youssef. 2018. Gesture Recognition with Transparent Solar Cells: A Feasibility Study (WiNTECH'18). 10.

[17]

Dong Ma, Guohao Lan, Mahbub Hassan, Wen Hu, Mushfika B. Upama, Ashraf Uddin, and Moustafa Youssef. 2019. SolarGest: Ubiquitous and Battery-Free Gesture Recognition Using Solar Cells. In The 25th Annual International Conference on Mobile Computing and Networking (MobiCom '19). https://doi.org/10.1145/3300061.3300129

Digital Library

[18]

Nesma Mohssen, Rana Momtaz, Heba Aly, and Moustafa Youssef. 2014. It's the human that matters: Accurate user orientation estimation for mobile computing applications. (2014).

[19]

Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information (10th ed.). Cambridge University Press, USA.

Digital Library

[20]

C. C. et al. Nshii. 2013. A Surface-Patterned Chip as a Strong Source of Ultracold Atoms for Quantum Technologies. Nature Nanotechnology 8, 5 (01 May 2013).

[21]

Andrew Ofstad, Emmett Nicholas, Rick Szcodronski, and Romit Roy Choudhury. 2008. AAMPL: Accelerometer Augmented Mobile Phone Localization (MELT '08). Association for Computing Machinery, New York, NY, USA, 13--18. https://doi.org/10.1145/1410012.1410016

Digital Library

[22]

Hamada Rizk, Marwan Torki, and Moustafa Youssef. 2018. CellinDeep: Robust and accurate cellular-based indoor localization via deep learning. IEEE Sensors Journal 19, 6 (2018), 2305--2312.

[23]

Maria Schuld and Francesco Petruccione. 2018. Supervised learning with quantum computers. Vol. 17. Springer.

[24]

Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. 2015. An introduction to quantum machine learning. Contemporary Physics 56, 2 (2015), 172--185.

[25]

Ahmed Shokry, Moustafa Elhamshary, and Moustafa Youssef. 2017. The tale of two localization technologies: Enabling accurate low-overhead WiFi-based localization for low-end phones. In Proceedings of the 25th ACM SIGSPATIAL.

Digital Library

[26]

Ahmed Shokry, Mostafa Mahmoud Elhamshary, and Moustafa Youssef. 2020. DynamicSLAM: Leveraging human anchors for ubiquitous low-overhead indoor localization. IEEE Transactions on Mobile Computing (2020).

[27]

Ahmed Shokry, Marwan Torki, and Moustafa Youssef. 2018. DeepLoc: a Ubiquitous Accurate and Low-overhead Outdoor Cellular Localization System. In Proceedings of the 26th ACM SIGSPATIAL.

Digital Library

[28]

Ahmed Shokry and Moustafa Youssef. 2021. Challenge: Quantum Computing for Location Determination. arXiv preprint arXiv:2106.11751 (2021).

[29]

Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (Oct. 1997), 1484--1509. https://doi.org/10.1137/S0097539795293172

Digital Library

[30]

Jimmy Stammers. 2019. An Atom Interferometer for Measuring Horizontal Accelerations. (2019).

[31]

Umesh V. Vazirani. 2002. "A Survey of Quantum Complexity theory. Proceedings of Symposia in Applied Mathematics (2002).

[32]

He Wang and et al. 2012. No Need to War-Drive: Unsupervised Indoor Localization. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services (MobiSys '12).

[33]

Yi Xia, Wei Li, William Clark, Darlene Hart, Quntao Zhuang, and Zheshen Zhang. 2020. Demonstration of a Reconfigurable Entangled Radio-Frequency Photonic Sensor Network. Phys. Rev. Lett. 124 (Apr 2020), 150502. Issue 15.

[34]

Moustafa Youssef and Ashok Agrawala. 2005. The Horus WLAN Location Determination System. In Proceedings of the 3rd international conference on Mobile systems, applications, and services. 205--218.

Digital Library

[35]

Moustafa Youssef and Mahbub Hassan. 2019. Next Generation IoT: Toward Ubiquitous Autonomous Cost-Efficient IoT Devices. IEEE Pervasive Computing 18, 4 (2019), 8--11. https://doi.org/10.1109/MPRV.2019.2947974

Digital Library

[36]

Moustafa Youssef, Matthew Mah, and Ashok Agrawala. 2007. Challenges: Device-Free Passive Localization for Wireless Environments. In Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking (MobiCom '07). 222--229.

Digital Library

Cited By

Pettorru GPilloni VMartalò M(2024)Trustworthy Localization in IoT Networks: A Survey of Localization Techniques, Threats, and MitigationSensors10.3390/s2407221424:7(2214)Online publication date: 29-Mar-2024
https://doi.org/10.3390/s24072214
Shokry AYoussef M(2024)A Quantum Access Points Selection Algorithm for Large-Scale Localization2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639748(1-7)Online publication date: 8-Oct-2024
https://doi.org/10.1109/LCN60385.2024.10639748
Rizk HYamaguchi HYoussef MHigashino T(2023)Laser Range Scanners for Enabling Zero-overhead WiFi-based Indoor Localization SystemACM Transactions on Spatial Algorithms and Systems10.1145/35396599:1(1-25)Online publication date: 12-Jan-2023
https://dl.acm.org/doi/10.1145/3539659
Show More Cited By

Index Terms

Towards Quantum Computing for Location Tracking and Spatial Systems
1. Hardware
  1. Emerging technologies
    1. Quantum technologies
2. Human-centered computing
  1. Ubiquitous and mobile computing

Recommendations

Quantum computing via the Bethe ansatz

We recognize quantum circuit model of computation as factorisable scattering model and propose that a quantum computer is associated with a quantum many-body system solved by the Bethe ansatz. As an typical example to support our perspectives on quantum ...
Quantum computing and quantum simulation with group-II atoms

Recent experimental progress in controlling neutral group-II atoms for optical clocks, and in the production of degenerate gases with group-II atoms has given rise to novel opportunities to address challenges in quantum computing and quantum simulation. ...
Integrable quantum computation

Integrable quantum computation is defined as quantum computing via the integrable condition, in which two-qubit gates are either nontrivial unitary solutions of the Yang---Baxter equation or the Swap gate (permutation). To make the definition clear, in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information Systems

November 2021

700 pages

ISBN:9781450386647

DOI:10.1145/3474717

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SIGSPATIAL '21

Sponsor:

SIGSPATIAL

SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems

November 2 - 5, 2021

Beijing, China

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)10

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pettorru GPilloni VMartalò M(2024)Trustworthy Localization in IoT Networks: A Survey of Localization Techniques, Threats, and MitigationSensors10.3390/s2407221424:7(2214)Online publication date: 29-Mar-2024
https://doi.org/10.3390/s24072214
Shokry AYoussef M(2024)A Quantum Access Points Selection Algorithm for Large-Scale Localization2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639748(1-7)Online publication date: 8-Oct-2024
https://doi.org/10.1109/LCN60385.2024.10639748
Rizk HYamaguchi HYoussef MHigashino T(2023)Laser Range Scanners for Enabling Zero-overhead WiFi-based Indoor Localization SystemACM Transactions on Spatial Algorithms and Systems10.1145/35396599:1(1-25)Online publication date: 12-Jan-2023
https://dl.acm.org/doi/10.1145/3539659
Shokry AYoussef M(2023)QRadar: A Deployable Quantum Euclidean Similarity Large-scale Localization System2023 IEEE 48th Conference on Local Computer Networks (LCN)10.1109/LCN58197.2023.10223339(1-8)Online publication date: 2-Oct-2023
https://doi.org/10.1109/LCN58197.2023.10223339
Zook YShokry AYoussef M(2023)A Quantum Fingerprinting Algorithm for Next Generation Cellular PositioningIEEE Journal on Selected Areas in Communications10.1109/JSAC.2023.332276342:1(93-102)Online publication date: 9-Oct-2023
https://dl.acm.org/doi/10.1109/JSAC.2023.3322763
Shokry AYoussef M(2022)QLoc: A Realistic Quantum Fingerprint-based Algorithm for Large Scale Localization2022 IEEE International Conference on Quantum Computing and Engineering (QCE)10.1109/QCE53715.2022.00043(238-246)Online publication date: Sep-2022
https://doi.org/10.1109/QCE53715.2022.00043
Shokry AYoussef M(2022)A Quantum Algorithm for RF-based Fingerprinting Localization Systems2022 IEEE 47th Conference on Local Computer Networks (LCN)10.1109/LCN53696.2022.9843246(18-25)Online publication date: 26-Sep-2022
https://doi.org/10.1109/LCN53696.2022.9843246
Rizk HAmano TYamaguchi HYoussef M(2022)Cross-Subject Activity Detection for COVID-19 Infection Avoidance Based on Automatically Annotated IMU DataIEEE Sensors Journal10.1109/JSEN.2022.317629122:13(13125-13135)Online publication date: 1-Jul-2022
https://doi.org/10.1109/JSEN.2022.3176291

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents