# Dequantizing Short-Path Quantum Algorithms

arXiv: https://arxiv.org/abs/2604.12131 · HTML: https://mlsanity.com/paper/2604.12131/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2026.

## Built on by (most cited first, 1 of 1)

- [QANTIS: Hardware-Calibrated Sequential POMDP Belief Updates on IBM Heron](https://mlsanity.com/paper/2607.06760/) (2026)

## Abstract (arXiv)

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~ao (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.