Resource-efficient quantum optimization via higher-order encoding

Journal article

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.

Authors: Koch, F; Panahiyan, S; Mukherjee, R; Doetsch, J; Jaksch, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: SpringerOpen
• Journal: EPJ Quantum Technology
• Volume: 13
• Issue: 1
• Article number: 59
• Publication date: 2026-05-25
• Acceptance date: 2026-05-18
• DOI: 10.1140/epjqt/s40507-026-00526-7
• EISSN: 2196-0763
• ISSN: 2662-4400
• Language: English
• Keywords: Quantum Optimization (QO); Higher-Order Unconstrained Binary Optimization (HUBO); Quantum Circuit (QC); Quadratic Unconstrained Binary Optimization (QUBO); Graph Coloring; Combinatorial Optimization Problems (COPs); Polynomial Unconstrained Binary Optimization (PUBO); Integer Programming (IP); Gate Assignment Problem (GAP); Quantum Approximate Optimization Algorithm (QAOA)