Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

• URL: http://arxiv.org/abs/2306.00494v1
• Date: Thu, 1 Jun 2023 09:44:17 GMT
• Title: Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms
• Authors: Moises Ponce, Rebekah Herrman, Phillip C. Lotshaw, Sarah Powers, George Siopsis, Travis Humble, James Ostrowski
• Abstract summary: We develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. We are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1.
• Score: 1.2622634782102324
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum--in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly $k$-regular graphs, as $k$-regular graphs on $n$ vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. While this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

Related papers

• Improved Recursive QAOA for Solving MAX-CUT on Bipartite Graphs [4.364124102844566]
  We analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. We show through numerical results that solving the same problem using level-1 Recursive QAOA (RQAOA) We propose a modified RQAOA that reduces the parameter regime optimized in the QAOA.
  arXiv  Detail & Related papers  (2024-08-23T16:35:47Z)
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
  We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round $i$HVA. Our ansatz solves MaxCut exactly for graphs with up to 24 nodes and $D leq 5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2024-08-17T03:34:17Z)
• 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)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  Normalized-Cut (N-Cut) is a famous model of spectral clustering. Traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$-means or spectral rotation. We propose a novel N-Cut solver based on the famous coordinate descent method.
  arXiv  Detail & Related papers  (2023-11-26T07:11:58Z)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Solving MaxCut with Quantum Imaginary Time Evolution [0.0]
  We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE) We show that after ten Q steps, the average solution is 100%, 99%, 98%, 97%, respectively, of the maximum MaxCut solution.
  arXiv  Detail & Related papers  (2022-01-28T16:24: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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
  arXiv  Detail & Related papers  (2020-05-18T14:23: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.