Authors:Hadi Salloum (1,2,3), Kirill Novoselov (1), Aleksandr Pochtarev (1), Yaroslav Kholodov (1,2) ((1) Research Center of the Artificial Intelligence Institute, Innopolis, University, Innopolis, Russia, (2) Moscow Institute of Physics and Technology, Moscow, Russia, (3) Q Deep, Innopolis, Russia)
Abstract:This article explores the comparative strengths of Higher-Order Unconstrained Binary Optimization (HUBO) and Quadratic Unconstrained Binary Optimization (QUBO) models in the context of probability optimization using tensor sampling techniques. HUBO can represent interactions beyond pairwise terms without introducing auxiliary variables, while QUBO benefits from a simpler algebraic structure and a wide range of established solvers. We combine a theoretical analysis of formulation expressiveness and reduction overhead with empirical experiments on synthetic polynomial objectives, RSA factorization, and Max-Cut instances. The results show that native HUBO formulations are often preferable when the original problem contains high-order interactions, because reducing such problems to QUBO increases the effective dimension seen by tensor samplers. At the same time, QUBO remains competitive for naturally quadratic problems. These findings provide practical guidance for selecting an optimization framework that balances model fidelity, dimension growth, and solver performance.
From: Yaroslav Kholodov [view email]
[v1]
Wed, 24 Jun 2026 16:55:55 UTC (206 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。