Partitioning Dense Graphs with Hardware Accelerators
arXiv:2202.09420 · doi:10.1016/j.physletb.2022.137043
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 (47)
- Ising formulations of many NP problems
- Lorentz-Violating Extension of the Standard Model
- Weyl Semimetal in a Topological Insulator Multilayer
- CPT Violation and the Standard Model
- Data Tables for Lorentz and CPT Violation
- High-Energy Tests of Lorentz Invariance
- Topological response in Weyl semimetals and the chiral anomaly
- Electromagnetic Response of Weyl Semimetals
- Radiatively Induced Lorentz and CPT Violation in Electrodynamics
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Axionic field theory of (3+1)-dimensional Weyl semi-metals
- Consequences of a condensed matter realization of Lorentz violating QED in Weyl semi-metals
- Axion Electrodynamics in Topological Materials
- Exact calculation of the radiatively-induced Lorentz and CPT violation in QED
- When radiative corrections are finite but undetermined
- Physical (ir)relevance of ambiguities to Lorentz and CPT violation in QED
- Gauge Invariance and the Pauli-Villars Regulator in Lorentz- and CPT-Violating Electrodynamics
- Regularisation : many recipes, but a unique principle : Ward identities and Normalisation conditions. The case of CPT violation in QED
- Failure of Gauge Invariance in the Nonperturbative Formulation of Massless Lorentz-Violating QED
- Bare and Induced Lorentz and CPT Invariance Violations in QED
- Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
- Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
- Radiatively-Induced Lorentz and CPT Violating Chern-Simons Term in QED
- Thermal transport, geometry, and anomalies
- Lorentz-CPT violation, radiative corrections and finite temperature
- Lorentz violation in Dirac and Weyl semimetals
- Network Community Detection On Small Quantum Computers
- A Remark on Lorentz Violation at Finite Temperature
- Understanding Radiatively Induced Lorentz-CPT Violation in Differential Regularization
- Radiative Effects in the Standard Model Extension
- Role of Ambiguities and Gauge Invariance in the Calculation of the Radiatively Induced Chern-Simons Shift in Extended Q.E.D.
- Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
- Induced Chern-Simons-like action in Lorentz-violating massless QED
- Radiatively Induced Lorentz and CPT Violation in Schwinger Constant Field Approximation
- Chern-Simons like term generation in an extended model of QED under external conditions
- Community Detection Across Emerging Quantum Architectures
- There is No Ambiguity in the Radiatively Induced Gravitational Chern-Simons Term
- Leveraging Adiabatic Quantum Computation for Election Forecasting
- Chiral Anomaly Beyond Lorentz Invariance
- On induced CPT-odd Chern-Simons terms in 3+1 effective action
- Induced Lorentz-violating terms at finite temperature
- A Novel Graph-based Approach for Determining Molecular Similarity
- Multiscale Network Generation
- Free energy-based reinforcement learning using a quantum processor
- Reinforcement Learning Using Quantum Boltzmann Machines
- Relaxing Lorentz invariance in general perturbative anomalies
- One-loop calculations in Lorentz-breaking theories and proper-time method
Cited by in corpus (8)
- Lorentz violation in Dirac and Weyl semimetals
- Cold plasma waves in the chiral Maxwell-Carroll-Field-Jackiw electrodynamics
- Lorentz invariance violation and the CPT-odd electromagnetic response of a tilted anisotropic Weyl semimetal
- Optical properties and energy propagation in a dielectric medium supporting magnetic current
- Physical interpretation of large Lorentz violation via Weyl semimetals
- Nonperturbative Lorentz Violation and Field Quantization
- Optical reflection signature of an axion dielectric with magnetic current
- Effective electromagnetic Lagrangians in the derivative expansion method