Succinct QUBO formulations for permutation problems by sorting networks

Katalin Friedl, Levente Gegő, László Kabódi, Viktória Nemkin

arXivarxiv/2603.07579Mar 8, 2026quant-phscore 0

Quadratic Unconstrained Binary Optimization (QUBO) is a standard NP-hard optimization problem. Recently, it has gained renewed interest through quantum computing, as QUBOs directly reduce to the Ising model, on which quantum annealing devices are based. We introduce a QUBO formulation for permutations using compare-exchange networks, with only $O(n \log^2 n)$ binary variables. This is a substantial improvement over the standard permutation matrix encoding, which requires $n^2$ variables and has a much denser interaction graph. A central feature of our approach is uniformity: each permutation…

SourceJSON

Comments and reviews

No comments yet.

API

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