Solving MaxCut with Quantum Imaginary Time Evolution

• URL: http://arxiv.org/abs/2201.12221v1
• Date: Fri, 28 Jan 2022 16:24:30 GMT
• Title: Solving MaxCut with Quantum Imaginary Time Evolution
• Authors: Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski, Phillip Lotshaw, Travis Humble
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state that involve no entanglement. We apply the method to graphs with number of vertices |V| = 4,6,8,10, and show that after ten QITE steps, the average solution is 100%, 99%, 98%, 97%, respectively, of the maximum MaxCut solution. By employing an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised, we show that the modified algorithm has a 100% performance converging to the maximum solution of the MaxCut problem for all graphs up to eight vertices as well as about 100 random samples of ten-vertex graphs. This improved method has an overhead which is polynomial in the number of vertices.

Related papers

• 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)
• Combinatorial optimization with quantum imaginary time evolution [2.048226951354646]
  We show that a linear Ansatz yields good results for a wide range of PUBO problems. We obtain numerical results for the Low Autocorrelation Binary Sequences (LABS) and weighted MaxCut optimization problems.
  arXiv  Detail & Related papers  (2023-12-27T18:18:12Z)
• Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms [1.2622634782102324]
  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.
  arXiv  Detail & Related papers  (2023-06-01T09:44:17Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Online Correlation Clustering for Dynamic Complete Signed Graphs [9.13755431537592]
  We consider the problem of correlation clustering for dynamic complete signed graphs. Online approximation algorithm in [CALM+21] for correlation clustering is used. This is the first online algorithm for dynamic graphs which allows a full set of graph editing operations.
  arXiv  Detail & Related papers  (2022-11-13T19:36:38Z)
• 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)
• Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
  We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
  arXiv  Detail & Related papers  (2022-03-27T20:22:17Z)
• Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
  We study a linear convex-concave saddle-point problem $min_xmax_y f(x) ytopmathbfA x - g(y)
  arXiv  Detail & Related papers  (2021-12-30T20:31:46Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• 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)

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.