Resource-Efficient Quantum Optimization via Higher-Order Encoding

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.

24 pages, 18 figures

References in corpus (32)

• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• $XY$-mixers: analytical and numerical results for QAOA
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• On the CNOT-complexity of CNOT-PHASE circuits
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Low Autocorrelation Binary Sequences
• Making Trotters Sprint: A Variational Imaginary Time Ansatz for Quantum Many-body Systems
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Measurement-Based Long-Range Entangling Gates in Constant Depth
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
• Guided quantum walk
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization