Quantum-Accelerated Flight Selection: Probing Grover's Algorithm and Quantum Device Efficiency


Authors : Jayesh Hire; Vaidehi Gawande; Sagar Dhande

Volume/Issue : Volume 9 - 2024, Issue 8 - August

Google Scholar : https://tinyurl.com/4vvabvbw

Scribd : https://tinyurl.com/33xhwken

DOI : https://doi.org/10.38124/ijisrt/IJISRT24AUG998

Abstract : Current flight search platforms primarily consider four essential factors when planning a trip: departure/arrival dates, as well as the origin and destination locations. However, when additional parameters are added to this search, the problem shifts from a simple to a complex search, as the engine must sift through a massive dataset of flights, including information on airlines, flight routes, fees, and more. To address this challenge and improve flight search efficiency amidst data-intensive and resource-demanding environments, this paper proposes the use of Grover's search algorithm. This algorithm is demonstrated as the optimal solution for searches with increased constraints. The paper highlights the practical application of Grover's search algorithm across three datasets of assorted sizes, as well as various quantum hardware and simulators available in the NISQ era. Furthermore, this paper provides an in-depth understanding of the complexity of quantum circuit design, including the key phases of state encoding and amplitude amplification. The effectiveness of these approaches is evaluated through analysis of execution times and quantum measurement results. The aim is to showcase the potential of quantum computing in revolutionizing real-world search tasks, particularly in the realm of flight selection.

Keywords : Quantum Computing, Quantum Search, Quantum Algorithm, Grovers Algorithm, Quantum Application.

References :

  1. Ladd, T. D., Jelezko, F., Laflamme, R., Nakamura, Y., Monroe, C., & O’Brien, J. L. (2010). Quantum computers. Nature 2010 464:7285, 464(7285), 45–53. https://doi.org/10.1038/nature08812
  2. Szalay, A. S., Gray, J., & Vandenberg, J. (n.d.). Petabyte Scale Data Mining: Dream or Reality?
  3. de Wolf, R. (2017). The Potential Impact of Quantum Computers on Society.
  4. Harrow, A. W., Hassidim, A., & Lloyd, S. (2009). Quantum Algorithm for Linear Systems of Equations. Physical Review Letters, 103(15), 150502. https://doi.org/10.1103/PhysRevLett.103.150502
  5. Shor, P. W. (2006). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. 41(2), 303–332. https://doi.org/10.1137/S0036144598347011
  6. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. https://doi.org/10.1145/359340.359342
  7. Grover, L. K. (1996). A fast quantum mechanical algorithm for database search.
  8. Yanofsky, N. S. (2007). AN INTRODUCTION TO QUANTUM COMPUTING.
  9. Nielsen, M. A. ., & Chuang, I. L. . (2023). Quantum computation and quantum information. Cambridge University Press.
  10. Adedoyin, A., Ambrosiano, J., Anisimov, P., et al. (2022). Quantum Algorithm Implementations for Beginners. ACM Trans. Quantum Comput., 3(4), Article 18. https://doi.org/10.1145/3517340
  11. Szabłowski, P. J., Paweł, B., Szabłowski, J., & Szabłowski, P. J. (2021). Understanding mathematics of Grover’s algorithm. Quantum Information Processing, 20, 191. https://doi.org/10.1007/s11128-021-03125-w
  12. IBM, Ibm quantum experience, 2023. Available: https: //quantum-computing.ibm.com/
  13. Google, Cirq, 2023. Available: https://quantumai. google/cirq.
  14. Bergholm, V., Izaac, J., Schuld, M., et al. (2022). PennyLane: Automatic differentiation of hybrid quantum-classical computations. PennyLaneAI. https://github.com/PennyLaneAI/pennylane/
  15. Steiger, D. S., Häner, T., & Troyer, M. (2018). ProjectQ: An Open Source Software Framework for Quantum Computing. https://doi.org/10.22331/q-2018-01-31-49
  16. Mandviwalla, A., Ohshiro, K., & Ji, B. (2018). Implementing Grover’s Algorithm on the IBM Quantum Computers.
  17. Johnstun, S., & van Huele, J.-F. (2021). Understanding and compensating for noise on IBM quantum computers. American Journal of Physics, 89(10), 935–942. https://doi.org/10.1119/10.0006204

Current flight search platforms primarily consider four essential factors when planning a trip: departure/arrival dates, as well as the origin and destination locations. However, when additional parameters are added to this search, the problem shifts from a simple to a complex search, as the engine must sift through a massive dataset of flights, including information on airlines, flight routes, fees, and more. To address this challenge and improve flight search efficiency amidst data-intensive and resource-demanding environments, this paper proposes the use of Grover's search algorithm. This algorithm is demonstrated as the optimal solution for searches with increased constraints. The paper highlights the practical application of Grover's search algorithm across three datasets of assorted sizes, as well as various quantum hardware and simulators available in the NISQ era. Furthermore, this paper provides an in-depth understanding of the complexity of quantum circuit design, including the key phases of state encoding and amplitude amplification. The effectiveness of these approaches is evaluated through analysis of execution times and quantum measurement results. The aim is to showcase the potential of quantum computing in revolutionizing real-world search tasks, particularly in the realm of flight selection.

Keywords : Quantum Computing, Quantum Search, Quantum Algorithm, Grovers Algorithm, Quantum Application.

Video Explanation for Published paper

Never miss an update from Papermashup

Get notified about the latest tutorials and downloads.

Subscribe by Email

Get alerts directly into your inbox after each post and stay updated.
Subscribe
OR

Subscribe by RSS

Add our RSS to your feedreader to get regular updates from us.
Subscribe