Quantum Optimisation Leap Bypasses Complexity Limits for Real-World Problems

Scientists are increasingly exploring alternative problem formulations to overcome limitations in scaling quantum combinatorial optimisation algorithms. Shashank Sanjay Bhat, Peiyong Wang, Joseph West, and Udaya Parampalli, from the University of Melbourne and CSIRO Clayton, present a systematic study of Quadratic Unconstrained D-ary Optimisation (QUDO) as a potential solution to the complexities of traditional Quadratic Unconstrained Binary Optimisation (QUBO) methods. Their research demonstrates that QUDO effectively encodes structural constraints across diverse problem classes, including the Traveling Salesman Problem and graph colouring, without relying on penalty terms that inflate computational demands. By benchmarking QUDO against QUBO using the Quantum Approximate Optimisation Algorithm, the team reveals consistently improved approximation ratios and reduced computational overhead, suggesting QUDO offers a more scalable and expressive representation for tackling complex optimisation challenges on near-term quantum hardware.

Researchers are hindered by penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. This combinatorial explosion renders many large-scale instances intractable for classical algorithms, motivating sustained interest in quantum approaches for their solution.
Current quantum hardware operates in the Noisy Intermediate-scale quantum (NISQ) regime which is characterised by limited qubit counts, constrained connectivity and errors. Such variables can be naturally represented using qudits, whose local Hilbert spaces provide direct access to multiple discrete levels.

This representation enables constraints such as ordering, assignment, and route separation to be expressed intrinsically, reducing the need for auxiliary variables and penalty terms that dominate binary formulations. In addition to the approximation ratio relative to the optimal solution, we report the reach percentage which is the fraction of the multi-start runs that achieve the target solution quality, the number of optimisation iterations and objective function evaluations required to reach the target value, and the total wall clock runtime.
Together, these metrics provide a detailed characterisation of optimisation behaviour and scalability across binary and D-ary quantum optimisation frameworks. For this problem, we provide benchmarking Results for both QAOA and qudit QAOA and report the corresponding solution metrics.

We then set out to study additional combinatorial optimisation problems, including the single-depot vehicle routing problem, multi-depot vehicle routing problem, unweighted Max-K-Cut, graph coloring, and job scheduling. For each problem, we present both the QUBO and QUDO formulations and perform a comparative benchmarking analysis using QAOA and qudit QAOA, respectively.
This paper is organized as follows: Section 2 reviews related work and positions the present study within the existing literature. Section 3 describes the methodological framework adopted throughout the paper. They argue that this exponential reduction in Hilbert space size may facilitate both quantum and classical solution Methods.

The authors explicitly construct a qudit Hamiltonian whose ground state corresponds to a valid TSP tour and validate the approach using classical simulations based on variational Monte Carlo with neural quantum states, solving instances with up to ∼100 cities. They describe the extended QAOA framework on a Hilbert space of dimension dN, including cost Hamiltonians constructed using generalised Pauli and angular-momentum operators to represent multi-valued cost functions, and discuss three strategies for incorporating linear constraints into the variational circuit, namely penalty terms, ancilla-assisted conditionals, and dynamical decoupling.

As a proof of concept, the authors present numerical simulations for a simplified electric-vehicle charging optimisation problem, mapped to a max-k graph coloring instance, illustrating the flexibility of qudit formulations for a range of integer optimisation problems. Weggemans et al introduced a qudit-native formulation of correlation clustering and demonstrate how it can be solved with a qudit-based QAOA implemented on a neutral-atom (Rydberg) platform.

They map each clustering decision to a multi-level (qudit) degree of freedom, thereby avoiding the overhead of one-hot or binary encodings, and construct both cost and mixer Hamiltonians that naturally operate within the feasible subspace. The authors develop a full-stack pipeline spanning from high-level problem encoding to low-level gate decomposition tailored to Rydberg qudit hardware, and provide resource counts and circuit depth estimates that illustrate the potential hardware efficiency of qudit implementations.

Through this concrete case study, the work highlights practical advantages of qudit representations, including reduced gate counts and more compact formulations, when tackling non-binary combinatorial problems. The paper empirically compares the resulting QUIO and QUBO re-formulations in terms of variable count, problem density, and performance when solved on both classical solvers and prototype qudit devices such as the Entropy Dirac-3 quantum computer.

Prior work on D-ary encodings and qudit-based optimisation highlights important representational and hardware-level advantages, but remains limited either to formulation level analyses without algorithmic evaluation, to qudit-QAOA demonstrations on isolated problem instances, or to empirical comparisons focused on variable counts and resource metrics rather than solution quality. Existing studies do not provide a systematic, head-to-head assessment of QUDO versus QUBO within a unified variational framework, nor do they quantify how representation choice affects approximation ratio, feasibility, and scalability of QAOA across multiple canonical NP-hard combinatorial problems under comparable circuit depths.

In contrast, the present work bridges these gaps by combining explicit QUDO and QUBO formulations with qudit and qubit based QAOA implementations across a broad problem suite, enabling a controlled evaluation of the algorithmic consequences of d-ary encodings and demonstrating that QUDO formulations exploit the larger d-level Hilbert space. All simulations are performed at circuit depths p = 1, 2, 3, with variational parameters γl, βl for l = 1 to p optimised using the COBYLA classical optimizer. Since the QAOA optimisation landscape is highly nonconvex, certain parameter choices may not yield high quality solutions.

To mitigate sensitivity to parameter initialisation, reduce bias from suboptimal local minima, and limit computational overhead, we perform ten independent multi-start optimisation runs with randomly initialised parameters. Qubit QAOA and qudit QAOA share the same variational structure. The difference lies in how decision variables are encoded.

QUBO formulations typically require a larger number of penalty terms to enforce constraints. QUDO formulations exploit the larger d-level Hilbert space. This allows constraints to be encoded more directly.

As a result, fewer penalty terms are often required. In qubit QAOA, the cost Hamiltonian is implemented using two qubit entangling gates such as CNOT or CZ. These gates are combined with single qubit RZ rotations. This study systematically investigates QUDO, encoding decision variables directly into higher dimensional Hilbert spaces, and avoids the need for extensive penalty constructions commonly found in QUBO formulations.

Benchmarking against binary QUBO counterparts and exact classical solutions reveals consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths. This comparative benchmarking analysis utilised QAOA and qudit QAOA to evaluate performance across all problem instances. While the authors acknowledge the limitations of current quantum hardware in fully realising the potential of these formulations, the results suggest a promising pathway towards more efficient quantum algorithms for complex optimisation tasks. Future research will likely focus on exploring the boundaries of QUDO’s applicability and developing tailored quantum algorithms to fully exploit its advantages, potentially extending to more complex problem instances and larger system sizes.