Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.05981 · Quantum

Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond

Dylan Laplace Mermoud, Andrea Simonetto, Sourour Elloumi

Published Feb 9, 2026• 0 citations
arXivHTMLPDF

Abstract

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 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, QuPer, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with 256 variables, requiring 20 qubits.

DOI
10.22331/q-2026-02-09-1998

Related papers

A Quantum Algorithm for the Sub-graph Isomorphism Problem

Nicola Mariella, Andrea Simonetto

We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.

arXiv:2111.09732•ACM Transactions on Quantum Computing•Oct 26, 2022•7 citations

Variational Approach for Uniform Quantum Permutation Generators

Farzam Nosrati, Nicolás Borrajo, Antonio Fernández Anta +1 more

Uniform permutation generation is a fundamental task in both classical and quantum computation, with applications ranging from cryptography to quantum optimization and quantum error correction. Existing exact quantum constructions typically require all-to-all qubit connectivity and quadratic circuit depth. We develop a variational quantum circuit framework for uniform permutation generation under connectivity constraints, in which the circuit architecture is determined by the underlying interaction graph and the variational parameters are optimized to enforce the target permutation statistics. In particular, 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. Our approach, therefore, removes the need for all-to-all connectivity while improving the depth of previous exact constructions by a factor. We further prove that a quantum Beneš-like architecture is intrinsically non-uniform. Despite its logarithmic depth and ability to realize any permutation it cannot generate a uniform distribution over permutations for any choice of variational parameters. These results clarify the role of circuit topology in exact permutation generation and identify variational quantum circuits as a natural framework for hardware-constrained uniform sampling. More broadly, this work suggests that exact uniform permutation generation is a strictly stronger requirement than mere permutation realizability, and lays the groundwork for a formal complexity separation between the two.

quant-pharXiv:2606.10230•Jun 10, 2026•0 citations

Efficient Variational Quantum Algorithms for the Generalized Assignment Problem

Carlo Mastroianni, Francesco Plastina, Jacopo Settino +1 more

Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.

quant-pharXiv:2511.02739•Nov 5, 2025•0 citations

Quantum circuits for permutation matrices

Jason Hanson

Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on $2^n$ letters. All circuits involve $n$ qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved.

quant-pharXiv:2512.11938•Dec 15, 2025•0 citations

Non-Variational Quantum Combinatorial Optimisation

Tavis Bennett, Lyle Noakes, Jingbo B. Wang

This paper introduces a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems, including constrained and non-binary problems. The algorithm leverages an engineered interference process achieved through repeated application of two unitaries; one inducing phase-shifts dependent on objective function values, and the other mixing phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific graph. The algorithm's versatility is demonstrated through its application to various problems, namely those for which solutions are characterised by either a vector of binary variables, a vector of non-binary integer variables, or permutations (a vector of integer variables without repetition). An efficient quantum circuit implementation of the CTQW for each of these problem types is also discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. The algorithm's performance is demonstrated through numerical simulation for randomly generated instances of the following problems (and problem sizes): weighted maxcut (18 vertices), maximum independent set (18 vertices), k-means clustering (12 datapoints, 3 clusters), capacitated facility location (12 customers, 3 facility locations), and the quadratic assignment problem (9 locations). For each problem instance, the algorithm finds a globally optimal solution with a small number of iterations.

arXiv:2404.03167•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•2 citations

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti +4 more

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $$m={{\mathcal{O}}}({n}^{k})$$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.

arXiv:2401.09421•Nature Communications•Jan 8, 2025•47 citations
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 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, QuPer, is competitive with respect to classical heuristics and we could simulate its behavior up to a problem with 256 variables, requiring 20 qubits.
We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.
Uniform permutation generation is a fundamental task in both classical and quantum computation, with applications ranging from cryptography to quantum optimization and quantum error correction. Existing exact quantum constructions typically require all-to-all qubit connectivity and quadratic circuit depth. We develop a variational quantum circuit framework for uniform permutation generation under connectivity constraints, in which the circuit architecture is determined by the underlying interaction graph and the variational parameters are optimized to enforce the target permutation statistics. In particular, we present explicit controlled-SWAP-based unitary constructions that achieve exact uniformity with quadratic circuit size and linear depth O(n)O(n)O(n) on linear nearest-neighbor topologies. Our approach, therefore, removes the need for all-to-all connectivity while improving the depth of previous exact constructions by a factor. We further prove that a quantum Beneš-like architecture is intrinsically non-uniform. Despite its logarithmic depth and ability to realize any permutation it cannot generate a uniform distribution over permutations for any choice of variational parameters. These results clarify the role of circuit topology in exact permutation generation and identify variational quantum circuits as a natural framework for hardware-constrained uniform sampling. More broadly, this work suggests that exact uniform permutation generation is a strictly stronger requirement than mere permutation realizability, and lays the groundwork for a formal complexity separation between the two.
Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.
Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on 2n2^n2n letters. All circuits involve nnn qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved.
This paper introduces a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems, including constrained and non-binary problems. The algorithm leverages an engineered interference process achieved through repeated application of two unitaries; one inducing phase-shifts dependent on objective function values, and the other mixing phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific graph. The algorithm's versatility is demonstrated through its application to various problems, namely those for which solutions are characterised by either a vector of binary variables, a vector of non-binary integer variables, or permutations (a vector of integer variables without repetition). An efficient quantum circuit implementation of the CTQW for each of these problem types is also discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. The algorithm's performance is demonstrated through numerical simulation for randomly generated instances of the following problems (and problem sizes): weighted maxcut (18 vertices), maximum independent set (18 vertices), k-means clustering (12 datapoints, 3 clusters), capacitated facility location (12 customers, 3 facility locations), and the quadratic assignment problem (9 locations). For each problem instance, the algorithm finds a globally optimal solution with a small number of iterations.
Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over m=O(nk)m={{\mathcal{O}}}({n}^{k})m=O(nk) binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.