Orateur
Description
The Influence Maximization Problem (IMP), which seeks to identify influential nodes in a network to maximize expected information spread, is inherently stochastic and NP-hard—making it a natural candidate for quantum optimization methods. Classical approaches typically formulate IMP as a deterministic optimization problem (e.g., via sample average approximation), then encode it as a Quadratic Unconstrained Binary Optimization (QUBO) problem. However, enforcing coverage-type constraints in QUBO formulations often requires auxiliary slack variables, resulting in substantial overhead and limiting scalability. In this work, we introduce a novel High-Order Binary Optimization (HOBO) formulation for IMP that directly captures the constraint logic without slack variables. Specifically, we reformulate common constraints of the form $y \le \sum x_j$ using compact product-based expressions, applicable when the sum includes a small number of terms. This leads to a parametric HOBO model that enables a tunable trade-off between reducing variable count and managing the complexity of higher-order interactions. We establish rigorous theoretical bounds for penalty parameters and validate the approach through extensive experiments on stochastic network instances drawn from Erdös-Renyi and Scale-Free graphs. Compared to standard QUBO formulations, our HOBO model yields faster solution times, lower variance in performance across samples, and high-quality solutions. These results highlight HOBO formulations as an efficient and scalable alternative for solving smaller IMP on current quantum hardware.
