⚛️ quantum physics

Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization

This paper demonstrates that using Quadratic Unconstrained D-ary Optimization (QUDO) to encode decision variables in higher-dimensional Hilbert spaces provides more efficient, scalable, and accurate solutions for various combinatorial optimization problems compared to traditional binary QUBO formulations.

Original authors: Shashank Sanjay Bhat, Peiyong Wang, Joseph West, Udaya Parampalli

Published 2026-02-10

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Shashank Sanjay Bhat, Peiyong Wang, Joseph West, Udaya Parampalli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a massive, complex wedding for 500 guests. You have to decide who sits at which table, who gets the vegetarian meal, and how to coordinate the flower deliveries.

This paper is about finding a much smarter way to "encode" these complex instructions so that a futuristic computer—a Quantum Computer—can solve the puzzle faster and with much less "brain power."

Here is the breakdown of the paper using everyday analogies.

1. The Old Way: The "Light Switch" Method (QUBO)

Currently, most people try to talk to quantum computers using a language called QUBO.

Imagine that instead of just saying, "Put Alice at Table 5," you have to use thousands of tiny light switches. To represent one single decision, you have to flip a whole row of switches:

Switch 1: Is Alice at Table 1? (Off)
Switch 2: Is Alice at Table 2? (Off)
Switch 3: Is Alice at Table 3? (On!)

This works, but it’s incredibly bulky. If you have a lot of guests, you end up with millions of switches. Even worse, you have to add "penalty rules" to make sure you don't accidentally turn on two switches for the same person (which would mean Alice is sitting at two tables at once). The computer spends most of its energy just trying to follow these "don't do this" rules rather than actually solving the wedding plan.

2. The New Way: The "Dimmer Switch" Method (QUDO)

The researchers propose a new language called QUDO.

Instead of using a massive row of On/Off light switches, they use a single Dimmer Switch for each person. This switch doesn't just have two settings; it has many levels.

Level 1: Table 1
Level 2: Table 2
Level 3: Table 3... and so on.

By using these "multi-level" switches (which scientists call Qudits), the instructions become incredibly compact. You don't need a million switches; you just need one switch per guest. Because the switch inherently can only be set to one level at a time, you don't need those annoying "penalty rules" to stop people from being in two places at once. The rules are "baked into" the hardware.

3. The Test: The "Obstacle Course"

To prove this works, the researchers put both methods through a series of "mental obstacle courses" (mathematical problems):

The Traveling Salesman: Finding the shortest route to visit several cities.
The Delivery Driver (VRP): Coordinating multiple trucks to deliver packages.
The Coloring Book: Assigning colors to a map so no two touching areas are the same.
The Busy Factory (Job Scheduling): Deciding the order of tasks on a machine.

4. The Results: Why it Matters

The results were a landslide victory for the "Dimmer Switch" (QUDO) method:

It’s Leaner: It uses far fewer "quantum parts" to describe the same problem.
It’s Smarter: The "Old Way" (QUBO) often got confused by the penalty rules and would suggest impossible solutions (like a driver being in two cities at once). The "New Way" (QUDO) almost always found valid, high-quality solutions.
It’s Faster: Because the instructions are simpler, the computer doesn't have to "think" as hard to find the best answer.

The Bottom Line

As we build more powerful quantum computers, we shouldn't just try to build bigger "light switch" boards. This paper shows that if we change the language we use—moving from simple On/Off switches to multi-level Dimmer switches—we can solve the world's most complex puzzles much more efficiently.

Technical Summary: Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization

1. Problem Statement

Combinatorial optimization problems (e.g., TSP, VRP, Graph Coloring) are NP-hard and typically formulated for quantum computers using Quadratic Unconstrained Binary Optimization (QUBO). In the QUBO framework, decision variables are restricted to binary states ($0$ or $1$). To enforce structural constraints (like ensuring a city is visited only once), QUBO relies on one-hot encoding and extensive penalty terms.

This approach leads to two major bottlenecks for Near-term Intermediate-Scale Quantum (NISQ) devices:

Resource Explosion: The number of qubits required scales quadratically with problem size (e.g., $N^2$ qubits for $N$ cities).
Complexity/Infeasibility: High-dimensional penalty terms create dense, complex Hamiltonians and "rugged" optimization landscapes, making it difficult for variational algorithms like QAOA to find valid (feasible) solutions.

2. Methodology

The authors propose and benchmark Quadratic Unconstrained D-ary Optimization (QUDO) as a superior alternative.

Core Concept: Instead of decomposing a multi-state variable into multiple qubits, QUDO encodes decision variables directly into higher-dimensional Hilbert spaces using qudits (d-level systems). For example, a variable representing $N$ possible cities is represented by a single $N$ -level qudit.
Algorithmic Framework: The study utilizes a generalized version of the Quantum Approximate Optimization Algorithm (qudit QAOA). While the variational structure remains similar to standard QAOA, the cost and mixer Hamiltonians are implemented using higher-dimensional operators (e.g., cyclic shift Hamiltonians and generalized Pauli operators).
Comparative Benchmarking: The authors perform a systematic, head-to-head comparison between QUBO (using qubits) and QUDO (using qudits) across six problem classes:
1. Traveling Salesman Problem (TSP)
2. Single-Depot Vehicle Routing Problem (VRP)
3. Multi-Depot Vehicle Routing Problem (MDVRP)
4. Unweighted Max-K-Cut
5. Graph Coloring
6. Job Scheduling
Metrics: Performance is measured via Approximation Ratio (AR), Reach Percentage (success rate), Feasibility Probability ( $P_{valid}$ ), optimization efficiency (steps/evaluations), and total wall-clock runtime.

3. Key Contributions

Unified Modeling Framework: The paper provides a formal mathematical bridge between binary, D-ary, and higher-order encodings, demonstrating how constraints can be "embedded" into the variable domain rather than added as external penalties.
Resource Compression Analysis: The work quantifies the exponential reduction in the number of quantum registers required when moving from one-hot binary encodings to native D-ary encodings.
Systematic Algorithmic Evaluation: Unlike previous works that focused only on formulation or isolated instances, this paper provides a comprehensive study of how encoding choice affects the optimization landscape and the success of variational solvers.

4. Key Results

Across all tested problem classes, QUDO consistently outperformed QUBO:

Superior Scalability & Resource Efficiency: QUDO requires significantly fewer quantum variables. For TSP, the Hilbert space size is reduced from $2^{N^2}$ (QUBO) to $N^N$ (QUDO). For Graph Coloring, it reduces from $2^{NK}$ to $K^N$ .
Higher Feasibility ( $P_{valid}$ ): QUBO formulations suffered from "vanishing feasibility"—as problem size increased, the probability of the algorithm sampling a valid solution dropped toward zero. QUDO, by design, uses variables that inherently represent valid states, maintaining high feasibility.
Improved Optimization Landscape: QUDO produced smoother landscapes, requiring fewer optimization iterations and function evaluations to reach target solutions.
Higher Approximation Ratios: QUDO achieved near-optimal or exact solutions (AR $\approx 1.0$ ) even at shallow circuit depths ( $p=1, 2, 3$ ), whereas QUBO often failed to converge or produced highly infeasible results.

5. Significance

This research identifies encoding strategy as a critical factor in the success of quantum combinatorial optimization. It demonstrates that the limitations of current quantum optimization are not just due to hardware noise, but also due to the mathematical inefficiency of binary encodings.

By proving that qudit-native formulations (QUDO) provide a more compact, feasible, and easier-to-optimize representation, the paper paves the way for utilizing next-generation quantum hardware (such as trapped ions or Rydberg atoms) that can naturally support higher-dimensional qudit states. This shift could significantly extend the reach of NISQ-era devices to solve larger, more complex real-world industrial problems.