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.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.

quant-pharXiv:2604.12131Apr 15, 20260 citations

Performance of the quantum adiabatic algorithm on constraint satisfaction and spin glass problems

Itay Hen, A. P. Young

The European Physical Journal Special TopicsFeb 1, 20152 citations

Quantum-Enhanced Constraint Satisfaction Problems (QCSP)

Jincheng Zhang

Quantum-Enhanced Constraint Satisfaction Problems (QCSP) addresses the computational bottleneck in solving constraint satisfaction problems (CSPs) by introducing quantum superposition to enhance search strategies. This paper presents a novel quantum algorithm designed to significantly reduce the computational complexity of solving CSPs, particularly those exhibiting high branching factors. We detail the algorithm's core mechanism, leveraging quantum superposition to efficiently explore the solution space and improve search performance. The proposed approach offers a fundamentally new method for tackling CSPs, promising substantial improvements in scalability and efficiency compared to classical approaches. This work is motivated by the inherent advantages of quantum computation in exploring complex solution spaces.Quantum-Enhanced Constraint Satisfaction Problems (QCSP) addresses the computational bottleneck in solving constraint satisfaction problems (CSPs) by introducing quantum superposition to enhance search strategies. This paper presents a novel quantum algorithm designed to significantly reduce the computational complexity of solving CSPs, particularly those exhibiting high branching factors. We detail the algorithm's core mechanism, leveraging quantum superposition to efficiently explore the solution space and improve search performance. The proposed approach offers a fundamentally new method for tackling CSPs, promising substantial improvements in scalability and efficiency compared to classical approaches. This work is motivated by the inherent advantages of quantum computation in exploring complex solution spaces.

Sep 3, 20260 citations

The complexity of the Quantum Adiabatic Algorithm

A. P. Young, Sergey Knysh, Vadim Smelyanskiy

Computer Physics CommunicationsJun 9, 20106 citations

Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems

Itay Hen, A. P. Young

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.

arXiv:1109.6872Physical Review EDec 29, 201189 citations

Adiabatic Quantum Computation and the Theory of Quantum Phase Transitions

William M. Kaminsky, Seth Lloyd

Bulletin of the American Physical SocietyMar 8, 20070 citations

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.