On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915590298402816 |
|---|---|
| author | Lavagna, Leonardo Piperno, Simone Ceschini, Andrea Panella, Massimo |
| author_facet | Lavagna, Leonardo Piperno, Simone Ceschini, Andrea Panella, Massimo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15413 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA Lavagna, Leonardo Piperno, Simone Ceschini, Andrea Panella, Massimo Quantum Physics 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. |
| title | On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.15413 |