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

• URL: http://arxiv.org/abs/2505.05981v1
• Date: Fri, 09 May 2025 12:12:26 GMT
• Title: Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond
• Authors: Dylan Laplace Mermoud, Andrea Simonetto, Sourour Elloumi,
• Abstract summary: 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.
• Score: 1.17431678544333
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \(\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.

Related papers

• Data Complexity Measures for Quantum Circuits Architecture Recommendation [55.74527632797241]
  Quantum Parametric Circuits are constructed as an alternative to reduce the size of quantum circuits.<n> determining the optimal circuit for a given problem remains an open question.<n>In this work, a quantum circuit recommendation architecture for classification problems is proposed using database complexity measures.
  arXiv  Detail & Related papers  (2025-02-21T01:17:24Z)
• Grover Adaptive Search with Spin Variables [3.190355298836875]
  We introduce a novel quantum dictionary subroutine that is designed for this spin-based algorithm. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit.
  arXiv  Detail & Related papers  (2024-10-15T14:24:27Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Hamiltonian-based graph-state ansatz for variational quantum algorithms [2.1438108757511958]
  We introduce a new circuit design that combines graph-based diagonalization circuits with arbitrary single-qubit rotation gates.<n>We test the accuracy of the proposed ansatz in estimating ground state energies of various molecules of size up to 12-qubits.
  arXiv  Detail & Related papers  (2023-12-28T17:28:23Z)
• Sub-universal variational circuits for combinatorial optimization problems [0.0]
  This work introduces a novel class of classical probabilistic circuits designed for generating quantum approximate solutions to optimization problems constructed using two-bit matrices. Through a numerical study, we investigate the performance of our proposed variational circuits in solving the Max-Cut problem on various graphs of increasing sizes. Our findings suggest that evaluating the performance of quantum variational circuits against variational circuits with sub-universal gate sets is a valuable benchmark for identifying areas where quantum variational circuits can excel.
  arXiv  Detail & Related papers  (2023-08-29T02:16:48Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Ion native variational ansatz for quantum approximate optimization [0.0]
  We show that symmetry can be broken to solve all problem instances of the Sherrington-Kirkpatrick Hamiltonian. Specifically these findings widen the class problem instances which might be solved by ion based quantum processors.
  arXiv  Detail & Related papers  (2022-06-23T18:00:01Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Combinatorial optimization through variational quantum power method [0.0]
  We present a variational quantum circuit method for the power iteration. It can be used to find the eigenpairs of unitary matrices and so their associated Hamiltonians. The circuit can be simulated on the near term quantum computers with ease.
  arXiv  Detail & Related papers  (2020-07-02T10:34:16Z)

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.