Quadratic Quantum Speedup for Finding Independent Set of a Graph

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²\) scaling, where n is the number of vertexes, our quantum algorithm achieves a time complexity of O\(n²\) 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²\) quantum algorithm outperforming the classical greedy algorithm, that also runs in O\(n²\). 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.