HUBO Formulation For Task Allocation Optimization in Hybrid Optical-Electrical Networks

Abstract

In supercomputing, large problems are divided into
multiple computational tasks, which are then executed across the
supercomputer’s network. The process of mapping these computational
tasks onto the network constitutes an embedding, which
is essentially equivalent to a combinatorial optimization problem
of graph embedding. For such graph embedding, attaching an
optical switch to host graph ensures that, even if the embedding of
one edge among those connected to each node of guest graph fails,
a successful embedding can still be achieved for optical switch.
Therefore, introducing optical switch is expected to provide new
opportunities for distributed allocation of computational tasks
over the supercomputer’s network. Although solving large-scale
combinatorial optimization problems on class computers remains
highly challenging, a variety of approaches have been actively
explored in recent years. Among these approaches, Quadratic
Unconstrained Binary Optimization (QUBO) is especially suitable
for being solved by quantum computers based on quantum
annealing. When dealing with higher-order polynomial terms,
the QUBO formulation necessitates the introduction of a large
number of auxiliary variables, thereby incurring a significant
computational cost. This study addresses graph embedding using
optical switch by High-order Unconstrained Binary Optimization
(HUBO), which allows for the direct treatment of higher-order
polynomial terms. In this study, we formulate the graph embedding
problem without optical switch as a QUBO, where the
objective function is expressed as the sum of linear, quadratic
terms and formulate the graph embedding problem with optical
switch as a HUBO, where the objective function is expressed
as the sum of linear, quadratic, cubic, and quartic terms. In
our experiments, we embedded the hypercube graph and the
torus graph into random regular graphs with optical switch
and without optical switch. It was observed that the QUBO and
HUBO models we proposed can solve graph embedding problem
and attaching optical switch to host graph appears to be more
effective.