{"id":"arxiv/2601.17686","url":"https://arxiv.org/abs/2601.17686","tags":["quant-ph"],"score":0,"title":"Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set","domain":"quant-ph","source":"arxiv","authors":["Vicky Choi"],"reviews":0,"subject":"quant-ph","summary":"Establishing quantum speedup for computationally hard problems of practical relevance, particularly combinatorial optimization problems, remains a central challenge in quantum computation. In this work, we identify a structurally defined family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm that exploits this structure. The algorithm runs in polynomial time and achieves an exponential speedup over both transverse-field quantum annealing and state-of-the-art classical solvers on these instances,…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-25","reactions":{}}