Evolving a Multi-Population Evolutionary-QAOA on Distributed QPUs

• URL: http://arxiv.org/abs/2409.10739v2
• Date: Thu, 19 Sep 2024 14:50:03 GMT
• Title: Evolving a Multi-Population Evolutionary-QAOA on Distributed QPUs
• Authors: Francesca Schiavello, Edoardo Altamura, Ivano Tavernelli, Stefano Mensa, Benjamin Symons,
• Abstract summary: We demonstrate that our Evolutionary-QAOA (E-QAOA) pairing performs on par or better than a COBYLA-based QAOA. We also present a novel approach by presenting a multi-population EA distributed on two QPUs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Our research combines an Evolutionary Algorithm (EA) with a Quantum Approximate Optimization Algorithm (QAOA) to update the ansatz parameters, in place of traditional gradient-based methods, and benchmark on the Max-Cut problem. We demonstrate that our Evolutionary-QAOA (E-QAOA) pairing performs on par or better than a COBYLA-based QAOA in terms of solution accuracy and variance, for $d$-3 regular graphs between 4 and 26 nodes, using both $max\_count$ and Conditional Value at Risk (CVaR) for fitness function evaluations. Furthermore, we take our algorithm one step further and present a novel approach by presenting a multi-population EA distributed on two QPUs, which evolves independent and isolated populations in parallel, classically communicating elite individuals. Experiments were conducted on both simulators and IBM quantum hardware, and we investigated the relative performance accuracy and variance.

Related papers

• Fast Genetic Algorithm for feature selection -- A qualitative approximation approach [5.279268784803583]
  We propose a two-stage surrogate-assisted evolutionary approach to address the computational issues arising from using Genetic Algorithm (GA) for feature selection. We show that CHCQX converges faster to feature subset solutions of significantly higher accuracy, particularly for large datasets with over 100K instances.
  arXiv  Detail & Related papers  (2024-04-05T10:15:24Z)
• Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
  We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets) Our empirical results demonstrate the efficacy of this approach, also testing the model in unstable environments.
  arXiv  Detail & Related papers  (2023-11-05T12:03:58Z)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulate is an evolutionary optimization algorithm and software package for global optimization. We provide an MPI-based implementation of our algorithm, which features variants of selection, mutation, crossover, and migration. We find that Propulate is up to three orders of magnitude faster without sacrificing solution accuracy.
  arXiv  Detail & Related papers  (2023-01-20T18:17:34Z)
• Analysis of Quality Diversity Algorithms for the Knapsack Problem [14.12876643502492]
  We apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem. We show that they are able to compute an optimal solution within expected pseudo-polynomial time.
  arXiv  Detail & Related papers  (2022-07-28T12:15:33Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  In this paper, we demonstrate the power of a widely used estimator based on moving average (SEMA) problems. For all these-the-art results, we also present the results for all these-the-art problems.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• 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)
• The Cone epsilon-Dominance: An Approach for Evolutionary Multiobjective Optimization [1.0323063834827413]
  cone epsilon-dominance approach to improve convergence and diversity in evolutionary algorithms. Sixteen well-known benchmark problems are considered in the experimental section. Results suggest that the cone-eps-MOEA is capable of presenting an efficient and balanced performance over all the performance metrics considered.
  arXiv  Detail & Related papers  (2020-07-14T14:13:13Z)
• 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)
• The Hessian Estimation Evolution Strategy [3.756550107432323]
  We present a novel black box optimization algorithm called Hessian Estimation Evolution Strategy. The algorithm updates the covariance matrix of its sampling distribution by directly estimating the curvature of the objective function.
  arXiv  Detail & Related papers  (2020-03-30T08:01: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.