Systematic improvement of the quantum approximate optimisation ansatz for combinatorial optimisation using quantum subspace expansion

• URL: http://arxiv.org/abs/2506.18594v1
• Date: Mon, 23 Jun 2025 12:54:06 GMT
• Title: Systematic improvement of the quantum approximate optimisation ansatz for combinatorial optimisation using quantum subspace expansion
• Authors: Yann Beaujeault-Taudière,
• Abstract summary: I study the enhancement of the quantum approximate optimisation ansatz (QAOA) with a generator coordinate method (GCM)<n>I achieve systematic performances improvements in the approximation ratio and fidelity for the maximal independent set on Erd"os-R'enyi graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The quantum approximate optimisation ansatz (QAOA) is one of the flagship algorithms used to tackle combinatorial optimisation on graphs problems using a quantum computer, and is considered a strong candidate for early fault-tolerant advantage. In this work, I study the enhancement of the QAOA with a generator coordinate method (GCM), and achieve systematic performances improvements in the approximation ratio and fidelity for the maximal independent set on Erd\"os-R\'enyi graphs. The cost-to-solution of the present method and the QAOA are compared by analysing the number of logical CNOT and $T$ gates required for either algorithm. Extrapolating on the numerical results obtained, it is estimated that for this specific problem and setup, the approach surpasses QAOA for graphs of size greater than 75 using as little as eight trial states. The potential of the method for other combinatorial optimisation problems is briefly discussed.

Related papers

• A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
  We consider a novel optimization design for multi-waveguide pinching-antenna systems.<n>The proposed GML-JO algorithm is robust to different choices and better performance compared with the existing optimization methods.
  arXiv  Detail & Related papers  (2025-06-14T17:35:27Z)
• Adam assisted Fully informed Particle Swarm Optimzation ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA) [1.024113475677323]
  The Quantum Approximate Optimization Algorithm (QAOA) is a prominent variational algorithm used for solving optimization problems such as the Max-Cut problem.<n>A key challenge in QAOA lies in efficiently identifying suitable parameters that lead to high-quality solutions.
  arXiv  Detail & Related papers  (2025-06-07T13:14:41Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Similarity-Based Parameter Transferability in the Quantum Approximate Optimization Algorithm [2.985148456817082]
  We show clustering of optimal QAOA parameters around specific values. successful transferability of parameters between different QAOA instances can be explained. We show that one can use optimal donor graph QAOA parameters as near-optimal parameters for larger acceptor graphs with comparable approximation ratios.
  arXiv  Detail & Related papers  (2023-07-11T16:35:49Z)
• 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)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• Transferability of optimal QAOA parameters between random graphs [3.321726991033431]
  We show that convergence of the optimal QAOA parameters around specific values can be explained and predicted based on the local properties of the graphs. We demonstrate how optimized parameters calculated for a 6-node random graph can be successfully used without modification as nearly optimal parameters for a 64-node random graph.
  arXiv  Detail & Related papers  (2021-06-14T15:57:47Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage.
  arXiv  Detail & Related papers  (2020-06-08T18:00:18Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.