On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA

• URL: http://arxiv.org/abs/2408.15413v2
• Date: Fri, 30 Aug 2024 19:52:35 GMT
• Title: On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Authors: Leonardo Lavagna, Simone Piperno, Andrea Ceschini, Massimo Panella,
• Abstract summary: We investigate the Maximum Cut (MaxCut) problem on different graph classes with the Quantum Approximate Optimization Algorithm (QAOA) In particular, perturbations on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. Through an analysis of the spectrum of the graphs and their perturbations, we aim to extract valuable insights into how symmetry impacts the performance of QAOA.
• Score: 0.5999777817331315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the Maximum Cut (MaxCut) problem on different graph classes with the Quantum Approximate Optimization Algorithm (QAOA) using symmetries. In particular, heuristics on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. To do so, we first solve the MaxCut problem on well-known graphs, then we consider a simple and controllable perturbation of the graph and find again the approximate MaxCut with the QAOA. Through an analysis of the spectrum of the graphs and their perturbations, as well as a careful study of the associated automorphism groups, we aim to extract valuable insights into how symmetry impacts the performance of QAOA. These insights can then be leveraged to heuristically reduce the quantum circuit complexity, the number of training steps, or the number of parameters involved, thus enhancing the efficiency and effectiveness of QAOA-based solutions.

Related papers

• Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
  We use the Nauty package to identify graph automorphisms, focusing on determining edge equivalence classes. By exploiting these symmetries, we achieve a significant reduction in the complexity of the Hamiltonian. Our results show that using automorphism-based symmetries to reduce the Pauli terms in the Hamiltonian can significantly decrease computational overhead without compromising the quality of the solutions obtained.
  arXiv  Detail & Related papers  (2024-10-29T17:10:25Z)
• MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
  Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges. The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
  arXiv  Detail & Related papers  (2024-09-27T12:28:18Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  Quantifying performance bounds provides insight into when QAOA may be viable for solving real-world applications. We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs. The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance.
  arXiv  Detail & Related papers  (2021-02-12T23:12:09Z)
• Impact of Graph Structures for QAOA on MaxCut [0.2609784101826761]
  The quantum approximate optimization algorithm (QAOA) is a promising method of solving optimization problems using quantum computing. We evaluate the performance of QAOA at depths at most three on the MaxCut problem for all connected non-isomorphic graphs. Knowing the relationship between structure and performance can allow us to identify classes of problems that are likely to exhibit a quantum advantage.
  arXiv  Detail & Related papers  (2021-02-11T13:32:00Z)
• Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
  We propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems.
  arXiv  Detail & Related papers  (2021-01-25T18:25:44Z)
• Classical symmetries and QAOA [3.2880869992413246]
  We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function.
  arXiv  Detail & Related papers  (2020-12-08T20:02:09Z)

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.