Resource-Efficient Quantum Optimization via Higher-Order Encoding
Frederik Koch, Shahram Panahiyan, Rick Mukherjee, Joseph Doetsch, Dieter Jaksch · 2025
Read Resource-Efficient Quantum Optimization via Higher-Order Encoding by Frederik Koch, Shahram Panahiyan, Rick Mukherjee, Joseph Doetsch, Dieter Jaksch (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17545.txt.
Introduction
Frederik Koch and four co-authors cut the resource cost of quantum optimization by changing how problems are encoded. The standard encoding, quadratic binary optimization, inflates circuits with penalty terms, demanding qubits and gates that near-term devices cannot spare. Higher-order encodings keep the problem's natural multi-variable interactions instead of flattening them. The authors show how to construct the corresponding quantum Hamiltonians systematically.
Benchmarked on gate assignment, maximum colorable subgraph, and integer programming problems, the higher-order formulation needed far fewer qubits. It also cut total entangling gate counts by at least about ninety percent on every tested instance. They release an open-source Python library that automates the construction and reaches beyond their examples. The pitch is practical: many optimization problems fit today's quantum hardware only if the encoding stops wasting its scarcest resources.
Catalog record
| CREATOR | Frederik Koch, Shahram Panahiyan, Rick Mukherjee, Joseph Doetsch, Dieter Jaksch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-17545
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Resource-Efficient Quantum Optimization via Higher-Order Encoding Frederik Koch, Shahram Panahiyan, Rick Mukherjee, Joseph Doetsch, Dieter Jaksch Abstract 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 QUBO in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, exponentially reduces qubit requirements and decreases CNOT gate counts by at least 89.6% after compilation to single- and two-qubit gates for all tested instances. These results highlight HUBO as a practical alternative for current and near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, broadening access to resource-efficient quantum optimization. Figure 1: Number of CNOT gates required to reach solution threshold for three COPs, optimized by QAOA with QUBO (yellow marker) and HUBO (blue marker) encodings as a function of problem size n\times m . The GAP optimizes the assignment of n aircraft to m airport gates. In the MkCS problem, n vertices are colored with m colors, IP optimizes a polynomial over n variables, each taking one of m possible values. Further details and quantum encodings are provided in the main text. Combinatorial optimization problems are prominent in numerous scientific and industrial domains, ranging from logistics and finance [ 45 ] to computational biology [ 49 ] and operations research [ 9 ] . Challenging problems require finding (near)-optimal solutions within vast discrete configuration spaces, where the search complexity often grows exponentially with problem size [ 15 ] . Theoretical insights from statistical physics have illuminated these challenges through their connection to disordered systems, revealing that most industrial optimization problems belong to the NP-hard complexity class [ 23 ] . Classical methods, including metaheuristics such as simulated annealing and tabu search [ 36 , 26 ] , and commercial solvers like CPLEX and Gurobi [ 35 , 30 ] face significant limitations when confronting non-convex energy landscapes. Even relatively small problems (sometimes below 100 variables) remain computationally intractable for them [ 71 , 51 , 48 , 16 , 11 , 22 ] . Quantum algorithms, such as adiabatic quantum optimization [ 1 , 18 ] and the Quantum Approximate Optimization Algorithm (QAOA) [ 20 ] are poised to address these challenges. This is predominantly done by exploiting mappings of COPs to QUBO models [ 43 , 28 , 40 ] which is further facilitated by modeling tools such as Pyqubo [ 74 ] . Previous studies [ 17 , 47 ] have identified several practical limitations of QUBO formulations, including large qubit requirements, costly penalty terms for constraint enforcement, and consequently increased circuit depth with large CNOT gates, which motivate the search for more resource-efficient alternatives. In contrast, HUBO encodings directly incorporate such constraints and, therefore, can reduce resource demands. While demonstrated in specific settings, including protein folding and the traveling salesperson problem [ 54 , 24 , 53 , 72 ] , prior work has lacked a general framework. Moreover, practical concerns remain regarding hardware implementation: higher-order terms formally require multiqubit interactions, whereas present quantum processors primarily support operations involving just one or two qubits at a time [ 69 , 21 ] . In this work, we show how such circuits can be implemented entirely with single- and two-qubit gates. By comparing to QUBO encodings, we demonstrate that HUBO encodings provide substantial and consistent resource advantages for three representative COPs: GAP, MkCS, and IP. These advantages persist after full circuit compilation, with HUBO exponentially lowering qubit counts and reducing CNOT requirements by at least 89.6% for all benchmarked problem classes and sizes (see Figure 1 ). To support broad adoption, we present PyHUBO, an open-source Python library [ 37 ] , and introduce a systematic framework for constructing HUBO Hamiltonians, showing that for the problems considered, our method yields numerical complexity that scales polynomially with problem size. Although we focus on QAOA, the approach applies to other algorithms and problems with one-hot or related constraints. Our results demonstrate that HUBO encodings can directly mitigate resource bottlenecks in quantum combinatorial optimization. 1 Methodology The methodology of this work is structured as follows. In Sec. ( 1.1 ), we establish a formal definition and notation for COPs and illustrate this formulation using three representative examples: the GAP, the MkCS, and IP. In Sec. ( 1.2 ), we show how the COP formulations from Sec. ( 1.1 ) can be systematically mapped to QUBO and HUBO encodings. Finally, Sec. ( 1.3 ) describes the implementation of these encodings within the QAOA algorithm, utilizing only single- and two-qubit gates. 1.1 Combinatorial Optimization Problems A COP consists of a finite set of feasible solutions and an objective function to be optimized [ 56 ] . For the remainder of this work, we use the following definition: Consider an n variable COP, where every variable can assume one of m values. Variables are indexed by 1\leq i\leq n and values by 1\leq v\leq m . In the following, we will use the terms i th variable and variable i interchangeably to refer to the variable indexed by i , and similarly, we will use the v th value and value v interchangeably to refer to the value indexed by v. A solution \mathbf{s}\in\{1,\cdots,m\}^{n} assigns a value to each variable. For every \mathbf{s} there exists an objective function C(\mathbf{s}) that can be computed in polynomial time and a polynomial time oracle that verifies whether \mathbf{s} is a feasible solution. The task is to find a solution such that the objective function is minimal among all feasible solutions, i.e., \mathbf{s}^{*}=\operatorname*{argmin}_{\mathbf{s}}C(\mathbf{s}) . In most applications, the objective function is a polynomial function of the variables [ 9 ] , and for practical purposes, we express it as C(\mathbf{s})=\sum_{1\leq i\leq n}c_{1}(i,s_{i})+\sum_{1\leq i<j\leq n}c_{2}(i,j,s_{i},s_{j})+\cdots, (1) where c_{1}(i,s_{i}) is the cost of assigning the value s_{i} to the i th variable, c_{2}(i,j,s_{i},s_{j}) the cost of assigning the value s_{i} to the i th variable while simultaneously assigning the value s_{j} to the j th variable. In principle, the objective function can be of any order. However, for most industrial applications, it is linear or quadratic [ 14 ] , i.e. Eq. ( 1 ) only contains terms of the form c_{1}(i,s_{i}) or c_{2}(i,j,s_{i},s_{j}) . Therefore, without loss of generality, we only consider linear and quadratic COPs. Often, COPs also involve constraints. For practical purposes, we formulate these constraints as inequalities, which can be converted to equality constraints, e.g., using slack variables [ 13 ] . The equality constraints are added as penalty terms to Eq. ( 1 ) with appropriately chosen Lagrange multipliers [ 25 ] . For example, a COP with a constraint that all variable pairs (i,j)\in P for some set P can not assume the same value can be stated as \begin{split}&\underset{\mathbf{s}\in\{1,\cdots,m\}^{n}}{\text{minimize}}\quad C(\mathbf{s})\\ &\underset{\forall(i,j)\in P}{\text{subject to}}\quad s_{i}\neq s_{j}.\end{split} (2) The penalty term for this constraint has the form \begin{split}c_{2}(i,j,v,v)&=\lambda\\ \forall(i,j)\in P\quad\forall v&\in\{1,\ldots,m\},\end{split} (3) with the Lagrange multiplier \lambda chosen large enough such that the optimal solution respects the constraint. By