{"id":"arxiv/2603.07579","url":"https://arxiv.org/abs/2603.07579","tags":["quant-ph","cs.DS"],"score":0,"title":"Succinct QUBO formulations for permutation problems by sorting networks","domain":"quant-ph","source":"arxiv","authors":["Katalin Friedl","Levente Gegő","László Kabódi","Viktória Nemkin"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-08","reactions":{}}