Quantum computing has revolutionized optimization, offering innovative methods to address computationally challenging problems for classical computers. Among these problems, the shortest path problem holds a significant importance across various domains, such as transportation, logistics, and network design. Classical algorithms like the Dijkstra, Bellman-Ford algorithms and \(A^{*}\) are efficient but as the size and complexity of the graph increase, these methods become less feasible. This paper shows the application of quantum optimization techniques to the shortest path problem by reformulating it as a Quadratic System and further maps it to the Quadratic Unconstrained Binary Optimization model. Further with Variational Quantum Eigensolver, this research translates the shortest path problem into a quantum-ready format, enabling its solution using quantum hardware. An quadratic objective function is designed to minimize the path cost while enforcing graph constraints and flow conservation. Transformed the quadratic binary optimization function into an equivalent Ising Hamiltonian via an mapping binary decision variables \(a_i \in \{0,1\}\) to spin states \( s_i \in \{-1,1\} \) and optimized for energy landscape. It demonstrates the feasibility of solving graph-based optimization problems using quantum algorithms, contributing to advancements in quantum-enhanced optimization. The findings highlight the promise of integrating quantum computing into real-world applications, laying the groundwork for future research in hybrid quantum-classical optimization and its potential to address shortest-path problems efficiently.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantum Computing for Graph Optimization: An Approach to the Shortest Path Problem

  • Aniket Bembale,
  • Nagendra Singh,
  • P. Vinayaka,
  • Jitesh Choudhary

摘要

Quantum computing has revolutionized optimization, offering innovative methods to address computationally challenging problems for classical computers. Among these problems, the shortest path problem holds a significant importance across various domains, such as transportation, logistics, and network design. Classical algorithms like the Dijkstra, Bellman-Ford algorithms and \(A^{*}\) are efficient but as the size and complexity of the graph increase, these methods become less feasible. This paper shows the application of quantum optimization techniques to the shortest path problem by reformulating it as a Quadratic System and further maps it to the Quadratic Unconstrained Binary Optimization model. Further with Variational Quantum Eigensolver, this research translates the shortest path problem into a quantum-ready format, enabling its solution using quantum hardware. An quadratic objective function is designed to minimize the path cost while enforcing graph constraints and flow conservation. Transformed the quadratic binary optimization function into an equivalent Ising Hamiltonian via an mapping binary decision variables \(a_i \in \{0,1\}\) to spin states \( s_i \in \{-1,1\} \) and optimized for energy landscape. It demonstrates the feasibility of solving graph-based optimization problems using quantum algorithms, contributing to advancements in quantum-enhanced optimization. The findings highlight the promise of integrating quantum computing into real-world applications, laying the groundwork for future research in hybrid quantum-classical optimization and its potential to address shortest-path problems efficiently.