Quadratic Quantum Speedup for Finding Independent Set of a Graph

• URL: http://arxiv.org/abs/2510.26395v1
• Date: Thu, 30 Oct 2025 11:35:47 GMT
• Title: Quadratic Quantum Speedup for Finding Independent Set of a Graph
• Authors: Xianjue Zhao, Peiyun Ge, Li You, Biao Wu,
• Abstract summary: A quadratic speedup of the quantum adiabatic algorithm (QAA) for finding independent sets in a graph is proven analytically.<n>In comparison to the best classical algorithm with $O(n2)$ scaling, our quantum algorithm achieves a time complexity of $O(n2)$ for finding a large IS, which reduces to $O(n)$ for identifying a size-2 IS.
• Score: 5.668733678326325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A quadratic speedup of the quantum adiabatic algorithm (QAA) for finding independent sets (ISs) in a graph is proven analytically. In comparison to the best classical algorithm with $O(n^2)$ scaling, where $n$ is the number of vertexes, our quantum algorithm achieves a time complexity of $O(n^2)$ for finding a large IS, which reduces to $O(n)$ for identifying a size-2 IS. The complexity bounds we obtain are confirmed numerically for a specific case with the $O(n^2)$ quantum algorithm outperforming the classical greedy algorithm, that also runs in $O(n^2)$. The definitive analytical and numerical evidence for the quadratic quantum speedup benefited from an analytical framework based on the Magnus expansion in the interaction picture (MEIP), which overcomes the dependence on the ground state degeneracy encountered in conventional energy gap analysis. In addition, our analysis links the performance of QAA to the spectral structure of the median graph, bridging algorithmic complexity, graph theory, and experimentally realizable Rydberg Hamiltonians. The understanding gained provides practical guidance for optimizing near-term Rydberg atom experiments by revealing the significant impact of detuning on blockade violations.

Related papers

• Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
  We study the quantum query complexity of approximate graph isomorphism testing.<n>We present a quantum algorithm based on MNRS quantum walk search over the product graph $(G,H)$ of the two input graphs.
  arXiv  Detail & Related papers  (2026-03-03T06:43:41Z)
• 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)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• 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)
• On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
  A feature of constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_mathrmunsat-N_mathrmsat$, spectrally filtered quantum optimization will return states with $E leq q_m.
  arXiv  Detail & Related papers  (2023-12-11T04:15:55Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• The complexity of quantum support vector machines [1.7887848708497243]
  Quantum support vector machines employ quantum circuits to define the kernel function. We show that the dual problem can be solved in $O(M4.67/varepsilon2)$ quantum circuit evaluations.
  arXiv  Detail & Related papers  (2022-02-28T19:01:17Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• 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)
• Quantum Algorithm for Approximating Maximum Independent Sets [0.0]
  We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing. For sparse and dense graphs, our quantum algorithm on average can find an independent set of size very close to $alpha(G)$.
  arXiv  Detail & Related papers  (2020-05-26T23:55:49Z)

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.