Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

Tristan Zaborniak, Prashanti Priya Angara, Vikram Khipple Mulligan, Hausi Müller, Ulrike Stege

arXivarxiv/2604.21123Apr 22, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.21123
curl -X POST /api/v1/records/arxiv/2604.21123/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.21123/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'