{"id":"arxiv/2604.21123","url":"https://arxiv.org/abs/2604.21123","tags":["quant-ph"],"score":0,"title":"Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization","domain":"quant-ph","source":"arxiv","authors":["Tristan Zaborniak","Prashanti Priya Angara","Vikram Khipple Mulligan","Hausi Müller","Ulrike Stege"],"reviews":0,"subject":"quant-ph","summary":"We introduce a qubit- and gate-efficient higher-order unconstrained binary optimization (HUBO) encoding for graph partitioning problems requiring label-count minimization. This widely applicable class of problems includes minimum graph coloring, minimum \\textit{k}-cut, and community detection. To the best of our knowledge, this is the first work to address the optimization versions of these problems in a quantum setting, rather than only their decision counterparts. Our construction encodes each vertex variable in a number of bits logarithmic in the number of available labels---the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-22","reactions":{}}