Dequantizing Short-Path Quantum Algorithms

Quantum Physics [Submitted on 13 Apr 2026] Dequantizing Short-Path Quantum Algorithms François Le Gall, Suguru Tamaki The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the need to control the spectral gap along a long adiabatic path. Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) recently revisited this framework and obtained a clear analysis of the complexity of the short-path algorithm for several classes of constraint satisfaction problems (MAX-k-CSPs), leading to quantum algorithms with complexity 2^{(1-c)n/2} for some constant c>0. This suggested a super-quadratic quantum advantage over classical algorithms. In this work, we identify an explicit classical mechanism underlying a substantial part of this line of work, and show that it leads to clean dequantizations. As a consequence, we obtain classical algorithms that run in time 2^{(1-c')n}, for some constant c'>c, for the same classes of constraint satisfaction problems. This shows that current short-path quantum algorithms for these problems do not achieve a super-quadratic advantage. On the positive side, our results provide a new ``quantum-inspired'' approach to designing classical algorithms for important classes of constraint satisfaction problems. Comments: 45 pages Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2604.12131 [quant-ph]   (or arXiv:2604.12131v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.12131 Focus to learn more Submission history From: Francois Le Gall [view email] [v1] Mon, 13 Apr 2026 23:31:53 UTC (48 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.CC cs.DS References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)