Succinct QUBO formulations for permutation problems by sorting networks

• URL: http://arxiv.org/abs/2603.07579v2
• Date: Fri, 13 Mar 2026 16:59:38 GMT
• Title: Succinct QUBO formulations for permutation problems by sorting networks
• Abstract summary: We introduce a QUBO formulation for permutations using compare-exchange networks, with only $O(n log2 n)$ binary variables.<n>A central feature of our approach is each permutation corresponds to a unique variable assignment, enabling unbiased sampling.<n>We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important.
• Score: 0.1590850178837849
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Variational Approach for Uniform Quantum Permutation Generators [2.4283267413173877]
  We develop a variational quantum circuit framework for uniform permutation generation under connectivity constraints.<n>We present explicit controlled-SWAP-based unitary constructions that achieve exact uniformity with quadratic circuit size and linear depth (O(n)) on linear nearest-neighbor topologies.
  arXiv  Detail & Related papers  (2026-06-08T22:41:09Z)
• Learnable Permutation for Structured Sparsity on Transformer Models [17.777454274409912]
  Structured sparsity has emerged as a popular model pruning technique.<n>Weight permutation is a promising direction to further improve post-pruning performance.<n>We propose a novel end-to-end learnable permutation framework.
  arXiv  Detail & Related papers  (2026-01-30T13:44:00Z)
• Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond [1.17431678544333]
  We present a quantum variational algorithm based on a novel circuit that generates all permutations that can be spanned by one- and two-qubits permutation gates.
  arXiv  Detail & Related papers  (2025-05-09T12:12:26Z)
• Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations [0.0]
  Uniform superpositions over permutations play a central role in quantum error correction, cryptography, and optimisation.<n>We introduce a simple yet powerful quantisation of the classical Fisher-Yates shuffle, yielding a suite of efficient quantum algorithms.<n>Our implementation in Qiskit is available as open-source code, supporting and future exploration of quantum permutation-based algorithms.
  arXiv  Detail & Related papers  (2025-04-24T22:24:39Z)
• Random sampling of permutations through quantum circuits [0.0]
  We introduce a classical algorithm for random sampling of permutations, drawing inspiration from the Steinhaus-Johnson-Trotter algorithm.<n>We develop a quantum analogue of the classical algorithm using a quantum circuit model for random sampling of permutations.
  arXiv  Detail & Related papers  (2024-09-04T18:19:30Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  sparse transformer can reduce the computational complexity of the self-attention layers to $O(n)$, whilst still being a universal approximator of continuous sequence-to-sequence functions. We propose an $O(n)$ complexity sampled transformer that can process point set elements directly without any additional inductive bias.
  arXiv  Detail & Related papers  (2023-02-28T06:38:05Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  We introduce LAW, a new efficient batch acquisition method based on the determinantal point process. We provide a regret analysis for our method to gain insight in its theoretical properties. We evaluate the method on several standard problems involving permutations such as quadratic assignment.
  arXiv  Detail & Related papers  (2021-02-26T10:15:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.