Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

This paper introduces and reviews QUDO, T-QUDO, and HOBO formulations for combinatorial optimization, demonstrating their explicit encodings and applications to problems like the knapsack and traveling salesman problems, as well as various logic games, to facilitate their use in quantum and quantum-inspired algorithms.

The Gist

Imagine you are trying to solve a massive, complicated puzzle. In the world of computers, this is called combinatorial optimization. It's like trying to find the single best way to arrange a set of items to get the highest score, while following strict rules.

For a long time, computers have been taught to solve these puzzles using a specific language called QUBO (Quadratic Unconstrained Binary Optimization). Think of QUBO as a strict language where every piece of the puzzle can only be in one of two states: ON or OFF (like a light switch). While this works for many things, it's often like trying to describe a complex painting using only black and white pixels. You have to use thousands of tiny switches to represent just one color, which makes the puzzle huge and hard to solve.

This paper introduces three new, more flexible "languages" that allow computers to speak in richer colors, making it easier to solve these puzzles. The author, Alejandro Mata Ali, shows how these new languages work using famous math problems and logic games.

Here is a breakdown of the three new languages and the games used to test them:

1. QUDO: The "Dial" Instead of the "Switch"

The Concept:
In the old QUBO language, variables are binary switches (0 or 1). QUDO (Quadratic Unconstrained D-ary Optimization) upgrades these switches to dials. Instead of just being ON or OFF, a dial can be set to any number from 0 up to a specific limit (like a volume knob that goes from 0 to 10).

The Analogy:
Imagine you are packing a suitcase.

• QUBO approach: You have to decide for every single sock, shirt, and pair of shoes whether to pack it (1) or not (0). If you want to pack 5 shirts, you need 5 separate switches.
• QUDO approach: You have a single dial for "Shirts." You just turn the dial to "5," and the computer knows you are packing five shirts.

The Paper's Examples:

• The Knapsack Problem: This is the classic "what fits in the bag" puzzle. The paper shows that using QUDO dials is much more efficient than using hundreds of binary switches to count how many items of each type you take.
• Hashiwokakero (Bridges): A puzzle where you connect islands with bridges. Since you can build 0, 1, or 2 bridges between islands, a dial (0, 1, or 2) fits the problem perfectly, whereas binary switches would require extra tricks to count up to 2.

2. T-QUDO: The "Smart Relationship" Map

The Concept:
Sometimes, the rules of a puzzle aren't just about the value of one dial, but about the relationship between two dials. T-QUDO (Tensor QUDO) is a language that understands these complex relationships directly.

The Analogy:
Imagine a party where you have to seat guests.

• QUDO: You can tell the computer, "Guest A is happy if they sit in Chair 1."
• T-QUDO: You can tell the computer, "Guest A is happy if they sit in Chair 1 AND Guest B sits in Chair 3. But if Guest B sits in Chair 4, Guest A gets angry."
  T-QUDO allows the computer to understand these specific "if-then" pairings without needing to break them down into tiny, clumsy binary steps.

The Paper's Examples:

• Traveling Salesman Problem: A salesman must visit every city exactly once. T-QUDO makes it easy to say, "If you are in City A at step 1, you cannot be in City A at step 2."
• N-Queens: The goal is to place queens on a chessboard so none attack each other. T-QUDO handles the rule "If Queen A is in Row 1, Column 3, then Queen B cannot be in Row 2, Column 4" very naturally.
• Kakuro & Inshi no Heya: These are number puzzles (like Sudoku but with sums and products). T-QUDO allows the computer to check sums and products of groups of numbers directly, rather than forcing them into binary math.

3. HOBO: The "Group Hug"

The Concept:
Sometimes, a rule involves three or more variables acting together at once. HOBO (Higher-Order Binary Optimization) is a language that allows variables to interact in groups, not just pairs.

The Analogy:
Imagine a game of musical chairs.

• Binary/Pairwise: You can only check if Person A is sitting next to Person B.
• HOBO: You can check if Person A, Person B, and Person C are all sitting in a specific triangle formation at the same time. It captures the "group dynamic" in one go.

The Paper's Example:

• Peg Solitaire: This is the game where you jump pegs over each other to remove them. A move involves three specific spots: the starting peg, the jumped peg, and the landing spot. HOBO is perfect for describing this three-way interaction in a single step, making the solution much cleaner.

Why Does This Matter?

The paper argues that while these new languages (QUDO, T-QUDO, HOBO) are more complex to learn than the old binary language, they are often much more efficient for specific types of problems.

• Less Clutter: They use fewer variables (fewer "switches" or "dials") to describe the same problem.
• Better Hardware: The paper notes that future quantum computers (which use "qudits" instead of just "qubits") are being built to speak these languages natively. By formulating problems this way now, we are preparing for that future hardware.
• The Trade-off: You can translate these new languages back into the old binary language (QUBO), but it often makes the problem bigger and messier. It's like translating a poem from English to a language with only 26 letters, then trying to force it back into English—it loses its elegance.

Summary

The paper is a guidebook for mathematicians and computer scientists. It says: "Stop trying to force every complex problem into a simple ON/OFF box. Sometimes, you need a dial (QUDO), a relationship map (T-QUDO), or a group hug (HOBO) to solve the puzzle efficiently."

The author proves this by taking difficult logic games (like Hashiwokakero, N-Queens, and Peg Solitaire) and showing how these new formulations solve them with fewer resources and clearer rules than the traditional methods.

Technical Summary

1. Problem Statement

Combinatorial optimization problems (e.g., Knapsack, Traveling Salesman, N-Queens) are often NP-Hard and lack efficient classical solutions. While the Quadratic Unconstrained Binary Optimization (QUBO) formulation is the standard for mapping these problems to quantum hardware (specifically via the Ising Hamiltonian and QAOA), it has limitations:

• Variable Inefficiency: Problems with natural multi-valued states (e.g., selecting $k$ items from $n$) require binary encoding, which increases the number of variables and introduces invalid states that require penalty terms.
• Constraint Limitations: Certain logical constraints (e.g., specific value implications or non-coincidence of specific values) are difficult or impossible to implement efficiently in standard QUBO due to the binary nature of the variables ($x_i^2 = x_i$).
• Hardware Mismatch: Emerging quantum technologies, such as qudits (d-level quantum systems), offer a natural way to represent non-binary variables but require optimization formulations beyond QUBO.

The paper addresses the need for more general formulations that leverage qudits and higher-order interactions to reduce resource overhead and simplify constraint implementation.

2. Methodology

The author introduces and analyzes three generalized optimization frameworks, providing explicit mathematical formulations and demonstrating their application to classic problems and combinatorial games.

A. Quadratic Unconstrained D-ary Optimization (QUDO)

• Definition: A generalization of QUBO where variables $x_i$ are bounded non-negative integers ($x_i \in \{0, 1, \dots, d_i-1\}$) rather than binary.
• Cost Function: $C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$.
• Key Features:
  • Requires qudits for direct implementation.
  • Allows for linear terms (unlike pure QUBO where $x_i^2=x_i$).
  • Limitations: Certain constraints (e.g., "if $x_i=a$ then $x_j \neq b$") are hard to implement because the sign of interaction terms depends on the specific values of non-binary variables.
  • Implementation: Can be mapped to QAOA using qudit phase gates $P(\theta)$ and controlled phase gates.

B. Tensor Quadratic Unconstrained D-ary Optimization (T-QUDO)

• Definition: A pairwise categorical generalization of QUDO. It treats variables as categorical labels rather than numerical values.
• Cost Function: $C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$.
• Key Features:
  • Uses a cost tensor $Q_{i,j, a, b}$ to define the cost of assigning value $a$ to variable $i$ and value $b$ to variable $j$.
  • Advantage: Overcomes QUDO's limitations by easily implementing complex logical constraints (e.g., specific value implications, non-coincidence of specific values) without relying on arithmetic properties.
  • Encoding: Can be encoded into HOBO or QUBO (via one-hot or binary encoding), though this may increase variable count.

C. Higher-Order Binary Optimization (HOBO)

• Definition: A formulation using multilinear pseudo-Boolean functions of order $m$ (where $m > 2$).
• Cost Function: $C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$, where $y_i \in \{0, 1\}$.
• Key Features:
  • Allows interactions between more than two variables.
  • Relation to T-QUDO: T-QUDO interactions can be encoded into HOBO by binarizing qudit labels.
  • Implementation: Directly applicable to qubit-based quantum devices that support higher-order interactions or via reduction techniques.

3. Key Contributions and Case Studies

The paper validates these formulations by applying them to the Knapsack Problem, Traveling Salesman Problem (TSP), and five combinatorial games.

Problem	Formulation Used	Key Insight/Result
Knapsack	QUDO	Demonstrates significant resource reduction. Instead of binary variables for item counts, a single qudit per item class represents the count directly. Reduces the number of variables and slack variables needed compared to QUBO.
Hashiwokakero	QUDO	Models bridge connections (0, 1, or 2) naturally. Uses auxiliary flow variables (encoded as qudits) to enforce global connectivity, proving that QUDO can handle complex topological constraints exactly.
Traveling Salesman (TSP)	T-QUDO	Uses variables $x_t$ representing the node at timestep $t$. The "no-repeat" constraint is naturally handled via a pairwise penalty term $\delta_{x_t, x_{t'}}$, avoiding the need for complex prime-number encodings or massive binary matrices.
N-Queens	T-QUDO	Reduces variables from $N^2$ (binary grid) to $N$ (column index per row). The T-QUDO tensor naturally encodes row, column, and diagonal constraints as specific tensor entries, simplifying the cost function structure.
Kakuro	T-QUDO	Combines QUDO (for sum constraints) and T-QUDO (for non-repetition constraints). The categorical nature of T-QUDO perfectly handles the "unique number in a row/column" rule.
Inshi no Heya	T-QUDO	Handles multiplicative region constraints by converting products to sums of prime exponents (unary functions), which fit naturally into the T-QUDO framework.
Peg Solitaire	HOBO	Models the game as a sequence of states. The movement logic (jumping over a peg) requires 4-variable interactions (source, middle, dest, time), which is naturally expressed in HOBO without needing to reduce to quadratic terms.

4. Results

• Resource Efficiency: QUDO and T-QUDO formulations often require fewer variables than their QUBO counterparts. For example, N-Queens drops from $N^2$ binary variables to $N$ qudits.
• Constraint Flexibility: T-QUDO allows for the direct implementation of logical constraints (implication, non-coincidence) that are cumbersome or impossible in QUDO/QUBO without auxiliary variables.
• Feasibility: The paper provides explicit cost functions and penalty terms for all examples, demonstrating that these formulations are mathematically sound and "exact" (i.e., valid solutions have zero cost).
• Quantum Implementation: The author outlines how to implement these cost functions in QAOA:
  • QUDO: Uses single-qudit phase gates and two-qudit gates.
  • T-QUDO: Uses controlled focus phase gates.
  • HOBO: Uses multi-controlled phase gates (or ancilla-based reductions).

5. Significance

• Bridging Theory and Hardware: The paper serves as a practical guide for utilizing emerging qudit-based quantum hardware, moving beyond the binary limitation of current qubit-centric research.
• Algorithmic Optimization: It demonstrates that choosing the correct formulation (QUDO/T-QUDO/HOBO) based on the problem's natural structure can drastically reduce the complexity of the optimization landscape, potentially improving the performance of quantum algorithms like QAOA.
• Educational Framework: By using well-known games and puzzles, the paper lowers the barrier to entry for understanding complex higher-order and multi-valued optimization formalisms.
• Future Directions: The work suggests that future quantum hardware architectures should support higher-order interactions and qudits natively to solve combinatorial problems more efficiently than current binary-reduction methods allow.

In conclusion, the paper argues that while QUBO is a powerful tool, QUDO, T-QUDO, and HOBO offer superior efficiency and expressiveness for specific classes of combinatorial problems, particularly those involving multi-valued variables or complex logical constraints, and are directly implementable on next-generation quantum devices.