Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games
For researchers in quantum optimization, this paper provides a tutorial-like introduction to alternative formulations (QUDO, T-QUDO, HOBO) that may enable solving problems more efficiently than standard QUBO, but the contribution is primarily pedagogical and incremental.
This paper introduces Quadratic Unconstrained D-ary Optimization (QUDO), Tensor QUDO, and Higher-Order Unconstrained Binary Optimization (HOBO) formulations for combinatorial optimization, providing explicit encodings between them and demonstrating their application to problems like knapsack, traveling salesman, and combinatorial games. The work aims to facilitate the use of these formulations in quantum and quantum-inspired optimization algorithms.
In this paper, we present a brief review and introduction to Quadratic Unconstrained D-ary Optimization (QUDO), Tensor Quadratic Unconstrained D-ary Optimization (T-QUDO) and Higher-Order Unconstrained Binary Optimization (HOBO) formulations for combinatorial optimization problems. We also show explicit encodings between these formulations and discuss their limitations. To help their understanding, we make some examples for the knapsack problem, traveling salesman problem and different combinatorial games. The games chosen to exemplify are: Hashiwokakero, N-Queens, Kakuro, Inshi no Heya, and Peg Solitaire. Although some of these games have already been formulated in a QUBO formulation, we are going to approach them with more general formulations, allowing their execution in new quantum or quantum-inspired optimization algorithms. This can be an easier way to introduce these more complicated formulations for harder problems.