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.
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.
The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.
We introduce a qubit- and gate-efficient higher-order unconstrained binary optimization (HUBO) encoding for graph partitioning problems requiring label-count minimization. This widely applicable class of problems includes minimum graph coloring, minimum \textit{k}-cut, and community detection. To the best of our knowledge, this is the first work to address the optimization versions of these problems in a quantum setting, rather than only their decision counterparts. Our construction encodes each vertex variable in a number of bits logarithmic in the number of available labels---the information-theoretic minimum---and employs a novel lexicographic penalty system that implicitly minimizes partition count without requiring dedicated indicator variables. We derive provably sufficient conditions on all penalty coefficients, including those arising from Rosenberg quadratization, guaranteeing feasibility and optimality of the lowest-energy solution. Analogous conditions are derived for a one-hot encoding to enable controlled comparison. We also show that our encoding reduces two-qubit gate count per layer of the quantum approximate optimization algorithm (QAOA). Benchmarking on a quantum annealer demonstrates that our logarithmic encoding greatly improves solution quality and time-to-solution for minimum graph coloring relative to one-hot encoding, with greater advantage as problem size increases.
In this paper, we propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO), where the Grover adaptive search (GAS) is used to provide a quadratic speedup for solving the problem. The conventional method relies on a one-hot encoding of the channel indices, resulting in a quadratic formulation. By contrast, we conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by GAS. Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation. This advantage is achieved at the cost of an increased number of quantum gates, which we demonstrate can be reduced by our proposed descending binary encoding.
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.
Portfolio optimization is one of the most studied optimization problems at the intersection of quantum computing and finance. In this work, we develop the first quantum formulation for a portfolio optimization problem with higherorder moments, skewness and kurtosis. Including higher-order moments leads to more detailed modeling of portfolio return distributions. Portfolio optimization with higher-order moments has been studied in classical portfolio optimization approaches but with limited exploration within quantum formulations. In the context of quantum optimization, higher-order moments generate higher-order terms in the cost Hamiltonian. Thus, instead of obtaining a quadratic unconstrained binary optimization problem, we obtain a higher-order unconstrained binary optimization (HUBO) problem, which has a natural formulation as a parametrized circuit. Additionally, we employ realistic integer variable encoding and a capital-based budget constraint. We consider the classical continuous variable solution with integer programming-based discretization to be the computationally efficient classical baseline for the problem. Our extensive experimental evaluation of100portfolio optimization problems shows that the solutions to the HUBO formulation often correspond to better portfolio allocations than the classical baseline. This is a promising result for those who want to perform computationally challenging portfolio optimization on quantum hardware, as portfolio optimization with higher moments is classically complex. Moreover, the experimental evaluation studies QAOA's performance with higher-order terms in this practically relevant problem.
We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.