{"id":"arxiv/2604.12131","url":"https://arxiv.org/abs/2604.12131","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Dequantizing Short-Path Quantum Algorithms","domain":"quant-ph","source":"arxiv","authors":["François Le Gall","Suguru Tamaki"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-13","reactions":{}}