Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911637224554496 |
|---|---|
| author | Ali, Alejandro Mata |
| author_facet | Ali, Alejandro Mata |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_01958 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games Ali, Alejandro Mata Emerging Technologies Quantum Physics 90C27, 90C20, 81Q99 G.1.6; G.2.1 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. |
| title | Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games |
| topic | Emerging Technologies Quantum Physics 90C27, 90C20, 81Q99 G.1.6; G.2.1 |
| url | https://arxiv.org/abs/2508.01958 |