Impact of Graph Structures for QAOA on MaxCut
- URL: http://arxiv.org/abs/2102.05997v1
- Date: Thu, 11 Feb 2021 13:32:00 GMT
- Title: Impact of Graph Structures for QAOA on MaxCut
- Authors: Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw,
Travis S. Humble and George Siopsis
- Abstract summary: 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.
- Score: 0.2609784101826761
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a promising method
of solving combinatorial optimization problems using quantum computing. QAOA on
the MaxCut problem has been studied extensively on specific families of graphs,
however, little is known about the algorithm on arbitrary graphs. We evaluate
the performance of QAOA at depths at most three on the MaxCut problem for all
connected non-isomorphic graphs with at most eight vertices and analyze how
graph structure affects QAOA performance. Some of the strongest predictors of
QAOA success are the existence of odd-cycles and the amount of symmetry in the
graph. The data generated from these studies are shared in a
publicly-accessible database to serve as a benchmark for QAOA calculations and
experiments. Knowing the relationship between structure and performance can
allow us to identify classes of combinatorial problems that are likely to
exhibit a quantum advantage.
Related papers
- On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA [0.5999777817331315]
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.
arXiv Detail & Related papers (2024-08-27T21:38:23Z) - 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) - Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing [0.0]
We introduce a new parametrized version of QA enabling a precise 1-local analysis of the algorithm.
We show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms.
arXiv Detail & Related papers (2023-11-21T17:15:21Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks.
In this work, we explore the potential of using this information for probabilistic balanced k-means clustering.
Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost.
This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
arXiv Detail & Related papers (2023-10-18T17:59:45Z) - 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) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - 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)
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.