Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA

• URL: http://arxiv.org/abs/2503.12789v1
• Date: Mon, 17 Mar 2025 03:58:43 GMT
• Title: Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA
• Authors: Edward Farhi, Sam Gutmann, Daniel Ranard, Benjamin Villalonga,
• Abstract summary: We study MaxCut on 3-regular graphs of minimum girth $g$ for various $g$'s.<n>For $g geq 16$, at depth $p geq 7$, the QAOA improves on previously known lower bounds.
• Score: 0.027042267806481293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study MaxCut on 3-regular graphs of minimum girth $g$ for various $g$'s. We obtain new lower bounds on the maximum cut achievable in such graphs by analyzing the Quantum Approximate Optimization Algorithm (QAOA). For $g \geq 16$, at depth $p \geq 7$, the QAOA improves on previously known lower bounds. Our bounds are established through classical numerical analysis of the QAOA's expected performance. This analysis does not produce the actual cuts but establishes their existence. When implemented on a quantum computer, the QAOA provides an efficient algorithm for finding such cuts, using a constant-depth quantum circuit. To our knowledge, this gives an exponential speedup over the best known classical algorithm guaranteed to achieve cuts of this size on graphs of this girth. We also apply the QAOA to the Maximum Independent Set problem on the same class of graphs.

Related papers

• Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
  We present a new QAOA ansatz that introduces only one additional parameter to the standard ansatz. We derive a general formula for our new ansatz at $p=1$ and analytically show an improvement in the approximation ratio for cycle graphs.
  arXiv  Detail & Related papers  (2024-11-07T22:20:01Z)
• Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs [26.8902894372334]
  In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem.<n>We apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs.<n>We conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth.
  arXiv  Detail & Related papers  (2024-10-06T08:57:30Z)
• Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
  Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm proposed with the goal of approximately solving optimization problems such as the MAX-CUT problem. We first analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. Second, we demonstrate that Recursive QAOA (RQAOA), which reduces graph size using QAOA as a subroutine, outperforms the level-1 QAOA. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations.
  arXiv  Detail & Related papers  (2024-08-23T16:35:47Z)
• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  We make novel use of sparsification techniques from the non-private streaming and static graph algorithms to achieve new results in the sublinear space, continual release setting.<n>We conclude with additive error lower bounds for edge-privacy in the fully dynamic setting.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
  We consider the maximum cut and maximum independent set problems on random regular graphs. We calculate the energy densities achieved by QAOA for high regularities up to $d=100$. We combine the QAOA analysis with state-of-the-art upper bounds on optimality for both problems.
  arXiv  Detail & Related papers  (2024-06-20T18:00:02Z)
• 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)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to optimization problems. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. We make an optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value.
  arXiv  Detail & Related papers  (2021-10-27T06:35:59Z)
• 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)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$. No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
  arXiv  Detail & Related papers  (2020-02-06T20:40:53Z)

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.