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.
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.
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.
The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.
With the applications of quantum computing becoming more and more widespread, finding ways that allow end users without experience in the field to apply quantum computers to solve their individual problems is becoming a crucial task. However, current optimization algorithms require problem instances to be posed in complex formats that are challenging to formulate, even for experts. In particular, the Quadratic Unconstrained Binary Optimization (QUBO) formalism employed by many quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), involves the mathematical rewriting of constraints under strict conditions. To facilitate this process, we propose a framework to automatically generate QUBO formulations for pathfinding problems. This framework allows users to translate their specific problem instances into formulations that can be passed directly to quantum algorithms for optimization without requiring any expertise in the field of quantum computing. It supports three different encoding schemes that can easily be compared without requiring manual reformulation efforts. The resulting QUBO formulations are robust and efficient, reducing the previously tedious and error-prone reformulation process to a task that can be completed in a matter of seconds. In addition to an open-source Python package available on https://github.com/munich-quantum-toolkit/problemsolver, we also provide a graphical user interface accessible through the web (https://munich-quantum-toolkit.github.io/problemsolver/), which can be used to operate the framework without requiring the end user to write any code.
This article explores the use of QUBO as a practical and educational framework for solving complex optimization problems. QUBO models are widely applicable across fields such as scheduling, routing, and resource allocation, and are compatible with classical, hybrid, and quantum solvers. We discuss the core principles behind QUBO, its connection to physical systems like the Ising model, and its growing relevance in research and education. To demonstrate the practical side, we apply QUBO to a real-world-inspired Multi-agent Route Planning problem, where the goal is to maximize the network coverage while minimizing the total overlap of vehicle-routes. This use-case helps illustrate how QUBO formulations can model trade-offs, encode constraints, and scale to larger problem sizes. In addition, we evaluate midsized instances of the problem on D-Wave Systems’ Advantage2 quantum annealer. The study aims to bridge theoretical optimization with hands-on experimentation, making it suitable for both teaching and applied research.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO). To this end, a QUBO instance with 729 variables is constructed, encoding a Sudoku grid with all constraints in place, which is then partially assigned to account for clues. The resulting instance can be solved with a Quantum Annealer, or any other strategy, to obtain the fully filled-out Sudoku grid. Moreover, as all valid solutions have the same energy, the QUBO instance can be used to sample uniformly from the space of valid Sudoku grids. We demonstrate the described method using both a heuristic solver and a Quantum Annealer.