Succinct QUBO formulations for permutation problems by sorting networks
This work provides a more efficient and sparser QUBO formulation for permutation problems, which is beneficial for researchers and practitioners working with quantum annealing devices and combinatorial optimization, particularly in areas requiring unbiased sampling of constrained permutations.
This paper introduces a Quadratic Unconstrained Binary Optimization (QUBO) formulation for permutation problems using compare-exchange networks. This new formulation requires only O(n log^2 n) binary variables, which is a substantial improvement over the standard n^2 variables required by permutation matrix encoding. The method also enables unbiased sampling and supports additional constraints like fixed points and parity.
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 corresponds to a unique variable assignment, enabling unbiased sampling. Our construction also allows additional constraints, including fixed points and parity. Moreover, it provides a representation of permutations that supports the operations multiplication and inversion, and also makes it possible to check the order of a permutation. This can be used to uniformly generate permutations of a given order or, for example, permutations that commute with a specified permutation. To our knowledge, this is the first result linking oblivious compare-exchange networks with QUBO encodings. While similar functionality can be achieved using permutation matrices, our method yields QUBOs that are both smaller and sparser. We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important, including cryptography and combinatorial design.