Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915788733022208 |
|---|---|
| author | Mermoud, Dylan Laplace Simonetto, Andrea Elloumi, Sourour |
| author_facet | Mermoud, Dylan Laplace Simonetto, Andrea Elloumi, Sourour |
| contents | 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. The construction of the circuits follows from group-theoretical results, most importantly the Bruhat decomposition of the group generated by the \(\mathtt{cx}\) gates. These circuits require a number of qubits that scale logarithmically with the permutation dimension, and are therefore employable in near-term applications. We further augment the circuits with ancilla qubits to enlarge their span, and with these we build ansatze to tackle permutation-based optimization problems such as quadratic assignment problems, and graph isomorphisms. The resulting quantum algorithm, \textsc{QuPer}, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with $256$ variables, requiring $20$ qubits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05981 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond Mermoud, Dylan Laplace Simonetto, Andrea Elloumi, Sourour Quantum Physics Optimization and Control 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. The construction of the circuits follows from group-theoretical results, most importantly the Bruhat decomposition of the group generated by the \(\mathtt{cx}\) gates. These circuits require a number of qubits that scale logarithmically with the permutation dimension, and are therefore employable in near-term applications. We further augment the circuits with ancilla qubits to enlarge their span, and with these we build ansatze to tackle permutation-based optimization problems such as quadratic assignment problems, and graph isomorphisms. The resulting quantum algorithm, \textsc{QuPer}, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with $256$ variables, requiring $20$ qubits. |
| title | Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond |
| topic | Quantum Physics Optimization and Control |
| url | https://arxiv.org/abs/2505.05981 |