Quantum Speedup for the Maximum Cut Problem

• URL: http://arxiv.org/abs/2305.16644v2
• Date: Tue, 13 Jun 2023 04:10:53 GMT
• Title: Quantum Speedup for the Maximum Cut Problem
• Authors: Weng-Long Chang, Renata Wong, Wen-Yu Chung, Yu-Hao Chen, Ju-Chin Chen, Athanasios V. Vasilakos
• Abstract summary: We propose a quantum algorithm to solve the maximum cut problem for any graph $G$ with a quadratic speedup over its classical counterparts. With respect to oracle-related quantum algorithms for NP-complete problems, we identify our algorithm as optimal.
• Score: 6.588073742048931
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Given an undirected, unweighted graph with $n$ vertices and $m$ edges, the maximum cut problem is to find a partition of the $n$ vertices into disjoint subsets $V_1$ and $V_2$ such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which has potential applications ranging from circuit layout design, statistical physics, computer vision, machine learning and network science to clustering. In this paper, we propose a quantum algorithm to solve the maximum cut problem for any graph $G$ with a quadratic speedup over its classical counterparts, where the temporal and spatial complexities are reduced to, respectively, $O(\sqrt{2^n/r})$ and $O(m^2)$. With respect to oracle-related quantum algorithms for NP-complete problems, we identify our algorithm as optimal. Furthermore, to justify the feasibility of the proposed algorithm, we successfully solve a typical maximum cut problem for a graph with three vertices and two edges by carrying out experiments on IBM's quantum computer.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle problem [0.0]
  Hamiltonian cycle problem (HCP) consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once. In this paper we compare some algorithms to solve aHCP, using different models of computations and especially the probabilistic and quantum ones.
  arXiv  Detail & Related papers  (2023-11-18T02:36:10Z)
• Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
  We consider an inverse problem for a finite graph $(X,E)$ where we are given a subset of vertices. We show that this problem has unique solution under certain conditions and develop quantum computing methods to solve it.
  arXiv  Detail & Related papers  (2023-06-08T14:48:48Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• 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)
• 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)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  We show that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of $> 5$ a maximum cut of at most $1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$. We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$, where
  arXiv  Detail & Related papers  (2021-06-10T16:28:23Z)
• Classical algorithms for Forrelation [2.624902795082451]
  We study the forrelation problem: given a pair of $n$-bit Boolean functions $f$ and $g$, estimate the correlation between $f$ and the Fourier transform of $g$. This problem is known to provide the largest possible quantum speedup in terms of its query complexity. We show that the graph-based forrelation problem can be solved on a classical computer in time $O(n)$ for any bipartite graph.
  arXiv  Detail & Related papers  (2021-02-13T17:25:41Z)
• Decomposition algorithms for solving NP-hard problems on a quantum annealer [0.0]
  NP-hard problems have applications in computational chemistry, biochemistry and computer network security. Adaabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems.
  arXiv  Detail & Related papers  (2020-09-10T15:59:06Z)

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.