Quantum Hypergraph Partitioning
This work provides a theoretical foundation and preliminary validation for applying quantum optimization to hypergraph partitioning, a problem relevant to data management and higher-order relation analysis.
The paper formalizes balanced k-way hypergraph partitioning for quantum optimization, deriving QUBO and higher-order formulations. On small 3-uniform hypergraphs, simulated QAOA and SA achieve exact solutions, with balance-penalty weight critically affecting cut quality vs. balance trade-off.
Hypergraph partitioning is a fundamental optimization problem with applications in data management and other domains involving higher-order relations. In this paper, we study balanced hypergraph partitioning from the perspective of quantum optimization. We formalize balanced $k$-way hypergraph partitioning with general hyperedge cut functions, and derive corresponding binary optimization formulations targeted at quantum optimization methods in both the two-way and multi-way settings. Our discussion highlights which cut functions admit Quadratic Unconstrained Binary Optimization (QUBO) encodings and which instead lead to higher-order binary objectives or rational forms. As a preliminary empirical validation, we focus on balanced two-way partitioning with the all-or-nothing cut on 3-uniform hypergraphs, where a direct QUBO is available, and evaluate simulated Quantum Approximate Optimization Algorithm (QAOA) and Simulated Annealing (SA) on small instances against exact solutions. The results show that the formulation is effective on small hypergraphs and that the balance-penalty weight plays a critical role in trading off cut quality and balance.