2024/10/30 by Shouvanik Chakrabarti, Chakrabarti, Shouvanik, Dylan Herman +15 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2410.23270
openalex publication_date 2024/10/30 · openalex created_date 2024/11/14 · openalex updated_date 2026/07/28
We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[Quantum 2, 78 (2018)], which has been extended and shown by Dalzell~et~al.~[STOC~'23] to achieve super-Grover speedups for certain binary optimization problems. We demonstrate that, under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups not only over unstructured search but also over a classical optimization algorithm that searches for the optimum by drawing samples from the stationary distribution of a Markov chain. We employ this framework to obtain algorithms for problems including variants of Max Bisection, Max Independent Set, and finding the ground states of the Antiferromagnetic Ising Model and the Sherrington-Kirkpatrick Model, whose runtimes are asymptotically faster than those obtainable with previous short path techniques. In certain cases, our algorithms achieve super-quadratic speedups compared to the best known classical algorithms with rigorously established runtimes.