Along with AI computing shining in scientific discovery, its potential in the combinatorial optimization (CO) domain has also emerged in recent years. Yet, existing unsupervised neural network solvers struggle to solve
k-grouping problems (e.g., coloring, partitioning) on large-scale graphs and hypergraphs, due to limited computational frameworks. In this work, we propose Deep
k-grouping, an unsupervised learning-based CO framework. Specifically, we contribute: Novel one-hot encoded polynomial unconstrained binary optimization (OH-PUBO), a formulation for modeling k-grouping problems on graphs and hypergraphs (e.g., graph/hypergraph coloring and partitioning); GPU-accelerated algorithms for large-scale k-grouping CO problems. Deep
k-grouping employs the relaxation of large-scale OH-PUBO objectives as differentiable loss functions and trains to optimize them in an unsupervised manner. To ensure scalability, it leverages GPU-accelerated algorithms to unify the training pipeline; A Gini coefficient-based continuous relaxation annealing strategy to enforce discreteness of solutions while preventing convergence to local optima. Experimental results demonstrate that Deep
k-grouping outperforms existing neural network solvers and classical heuristics such as SCIP and Tabu.
Abstract The quantum many-body problem (QMBP) has become a hot topic in high-energy physics and condensed-matter physics. With an exponential increase in the dimensions of Hilbert space, it becomes very challenging to solve the QMBP, even with the most powerful computers. With the rapid development of machine learning, artificial neural networks provide a powerful tool that can represent or approximate quantum many-body states. In this paper, we aim to explicitly construct the neural network representations of hypergraph states. We construct the neural network representations for any k -uniform hypergraph state and any hypergraph state, respectively, without stochastic optimization of the network parameters. Our method constructively shows that all hypergraph states can be represented precisely by the appropriate neural networks introduced in [ Science 355 (2017) 602] and formulated in [ Sci. China-Phys. Mech. Astron. 63 (2020) 210312].