QUBO formulations of the longest path problem

Cristian S. Calude, Michael J. Dinneen, Richard Hua

Richard Hua, Michael J. Dinneen

Mayowa Ayodele

Renáta Rusnáková, Martin Chovanec, Maroš Harahus +1 more

This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.

Fumiyo Takano, Motoi Suzuki, Y. Kobayashi +1 more

Federico Fuidio, Laura Gatti, Rafael Sotelo

This paper presents a QUBO formulation for the Grid Pathfinding Problem or Maze Solving Problem. The environment is represented as a grid where some vertices are walkable (free) and others are blocked (walls or obstacles). The objective is to find a path from a start to a goal point. This problem has many applications in the consumer technology industry and other sectors. The formulation presented here reduces the complexity of well-known algorithms for the worst-case scenarios. The QUBO formulation is suitable to be solved by quantum annealers. The formulation proposed here has been tested on the D-Wave quantum annealer simulator.