https://doi.org/10.1140/epjqt/s40507-026-00526-7
Research
Resource-efficient quantum optimization via higher-order encoding
1
Institute for Quantum Physics, University of Hamburg, Luruper Chaussee 149, 22761, Hamburg, Germany
2
Max Planck Institute for the Structure and Dynamics of Matter, Luruper Chaussee 149, 22761, Hamburg, Germany
3
Zentrum für Optische Quantentechnologien, University of Hamburg, Luruper Chaussee 149, 22761, Hamburg, Germany
4
Department of Physics & Astronomy, University of Tennessee, 37403, Chattanooga, TN, USA
5
UTC Quantum Center, University of Tennessee, 37403, Chattanooga, TN, USA
6
Lufthansa Industry Solutions, Südportal 7, Norderstedt, 22848, Schleswig-Holstein, Germany
7
The Hamburg Centre for Ultrafast Imaging, University of Hamburg, Luruper Chaussee 149, 22761, Hamburg, Germany
8
Clarendon Laboratory, University of Oxford, Parks Road, OX1 3PU, Oxford, UK
a
This email address is being protected from spambots. You need JavaScript enabled to view it.
Received:
23
January
2026
Accepted:
18
May
2026
Published online:
25
May
2026
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 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.
Key words: Quadratic Unconstrained Binary Optimization (QUBO) / Higher-Order Unconstrained Binary Optimization (HUBO) / Polynomial Unconstrained Binary Optimization (PUBO) / Quantum Approximate Optimization Algorithm (QAOA) / Combinatorial Optimization Problems (COPs) / Graph Coloring / Gate Assignment Problem (GAP) / Integer Programming (IP) / Quantum Optimization (QO) / Quantum Circuit (QC)
© The Author(s) 2026
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
