Partitioning Dense Graphs with Hardware Accelerators

Abstract

Graph partitioning is a fundamental combinatorial optimization problem that attracts a lot of attention from theoreticians and practitioners due to its broad applications. From multilevel graph partitioning to more general-purpose optimization solvers such as Gurobi and CPLEX, a wide range of approaches have been developed. Limitations of these approaches are important to study in order to break the computational optimization barriers of this problem. As we approach the limits of Moore's law, there is now a need to explore ways of solving such problems with special-purpose hardware such as quantum computers or quantum-inspired accelerators. In this work, we experiment with solving the graph partitioning on the Fujitsu Digital Annealer (a special-purpose hardware designed for solving combinatorial optimization problems) and compare it with the existing top solvers. We demonstrate limitations of existing solvers on many dense graphs as well as those of the Digital Annealer on sparse graphs which opens an avenue to hybridize these approaches.

References in corpus (12)

• Topological response in Weyl semimetals and the chiral anomaly
• Consequences of a condensed matter realization of Lorentz violating QED in Weyl semi-metals
• Axion Electrodynamics in Topological Materials
• Gauge Invariance and the Pauli-Villars Regulator in Lorentz- and CPT-Violating Electrodynamics
• Failure of Gauge Invariance in the Nonperturbative Formulation of Massless Lorentz-Violating QED
• Lorentz-CPT violation, radiative corrections and finite temperature
• Induced Chern-Simons-like action in Lorentz-violating massless QED
• There is No Ambiguity in the Radiatively Induced Gravitational Chern-Simons Term
• Chiral Anomaly Beyond Lorentz Invariance
• Multiscale Network Generation
• Free energy-based reinforcement learning using a quantum processor
• Relaxing Lorentz invariance in general perturbative anomalies