Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.
Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.
The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly.
Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.
This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
The Quantum Approximate Optimization Algorithm (QAOA) requires considered optimization problems to be translated into a compatible format. A popular transformation step in this pipeline involves the quadratization of higher-order binary optimization problems, translating them into Quadratic Unconstrained Binary Optimization (QUBO) formulations through the introduction of auxiliary variables. Conventional algorithms for the selection of auxiliary variables often aim to minimize the total number of required variables without taking the constraints of the underlying quantum computer-in particular, the connectivity of its qubits-into consideration. This quickly results in interaction graphs that are incompatible with the target device, resulting in a substantial compilation overhead even with highly optimized compilers. To address this issue, this work presents a novel approach for the selection of auxiliary variables tailored for architectures with limited connectivity. By specifically constructing an interaction graph with a regular structure and a limited maximal degree of vertices, we find a way to construct QAOA circuits that can be mapped efficiently to a variety of architectures. We show that, compared to circuits constructed from a QUBO formulation using conventional auxiliary selection methods, the proposed approach reduces the circuit depth by almost 40%. An implementation of all proposed methods is publicly available at https://github.com/munich-quantum-toolkit/problemsolver.
This thesis explores quantum computing for combinatorial optimization through the Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via the Gurobi solver. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with degree and subtour constraints embedded using quadratic penalties. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound solvers outperform it in both solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap grows with problem size, reflecting sensitivity to variational parameter tuning, penalty scaling, and hardware noise. Among classical optimizers for QAOA, COBYLA offers the most effective tradeoff between efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most prominent hybrid quantum–classical algorithms for combinatorial optimization on noisy intermediate-scale quantum (NISQ) hardware. QAOA maps real-world problems into Ising or quadratic unconstrained binary optimization (QUBO) forms and alternates cost and mixer operators in a shallow parameterized circuit whose angles are tuned by a classical optimizer. This article introduces QAOA from fundamentals to practice, emphasizing why it aligns with industrial optimization through binary decision modeling and the presence of severe scaling challenges in classical optimization. We review research trends that improve expressivity and trainability, including ansatz engineering, parameter initialization, and hybrid training strategies, drawing parallels to developments in artificial intelligence. After that, we survey representative applications in emerging domains such as drug discovery, materials design, semiconductor design, logistics, and finance highlighting practical encodings and constraint-preserving formulations that keep quantum evolution within feasible subspaces beyond penalty-based methods. Finally, we present QAOA as a rapidly maturing framework with credible pathways toward near-term utility in real industrial workflows.