Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40088

Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

Guneykan Ozgul, Shouvanik Chakrabarti

quant-phcs.DSmath.OCSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.

AI Summary

Quantum short-path algorithms give super-quadratic speedups over exhaustive search for some optimization families, but a recent classical conditioning-and-search algorithm weakens that comparison. This paper asks whether quantum algorithms can beat the quadratic acceleration of this stronger baseline. It introduces quantum tilted walks: for a reversible-chain discriminant $D$ and normalized objective $G$, apply $C_{b,M}=(M+1)^{-1}\sum_{m=0}^M[(D+bG)/E_b]^m$, where $E_b=\lambda_{\max}(D+bG)$. Unlike short-path ground-state preparation, this transformation permits nonstationary initial states and requires no lower bound on the tilted Hamiltonian’s spectral gap. For coherent conditioned stationary states on a candidate set $T$ and a higher-scoring successful set $S$, the main bound is $|\langle S|C_{b,M}|T\rangle|\geq\operatorname{poly}(n)^{-1}\sqrt{\pi(S)/\pi(T)}\,2^{\kappa n/2}$. Positive path expansions establish amplitude growth; log-Sobolev concentration bounds the normalization cost. For weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP under stated regularity assumptions, this yields exact-optimization runtimes $2^{(1-c^{\mathrm{cl}}-\kappa)n/2+o(n)}$, with constant $\kappa>0$, versus conditioning-and-search’s $2^{(1-c^{\mathrm{cl}})n+o(n)}$. The CSP comparison additionally requires a successful-set size condition, satisfied for exact-$k$ instances with $k\geq6$. Oracle implementation, precision costs, and unknown optimum and normalization parameters are addressed. The comparison is not against every classical algorithm; conditioning-and-search is not the best known baseline for MAX-$k$-CSP. Practical exponent sizes are not evaluated. A synthetic example demonstrates amplitude gain with exponentially small spectral gaps, but its target is directly constructible, so it establishes no hard-problem speedup.

Little sign of AI-generated textAI use disclosedStrong assumptions
Large Language Models have been used to help with writing and grammar, and to audit the technical material for rigor and completeness.

Central claim may not hold: The weighted MAX-k-CSP algorithm optimizes clause weights Gamma_j w_j instead of the stated weights w_j, and an exact-6 instance satisfying the theorem's regularity assumptions reverses the optimum. The abstract's same-assumptions CSP comparison omits the additional condition sigma_B >= gamma_B, which can fail for instances satisfying the other stated assumptions. The abstract describes the synthetic example as a computational speedup over short-path algorithms, whereas the body proves only a separation of analytical guarantees on an easily solved problem.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization

Shouvanik Chakrabarti, Dylan Herman, Guneykan Ozgul +6 more

We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{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.

arXiv:2410.23270•Oct 30, 2024•14 citations

Quantum speedup for combinatorial optimization with flat energy landscapes

Madelyn Cain, Sambuddha Chattopadhyay, Jin-Guo Liu +3 more

Designing quantum algorithms with a speedup over their classical analogs is a central challenge in quantum information science. Motivated by recent experimental observations of a superlinear quantum speedup in solving the Maximum Independent Set problem on certain unit-disk graph instances [Ebadi et al., Science 376, 6598 (2022)], we develop a theoretical framework to analyze the relative performance of the optimized quantum adiabatic algorithm and a broad class of classical Markov chain Monte Carlo algorithms. We outline conditions for the quantum adiabatic algorithm to achieve a quadratic speedup on hard problem instances featuring flat low-energy landscapes and provide example instances with either a quantum speedup or slowdown. We then introduce an additional local Hamiltonian with no sign problem to the optimized adiabatic algorithm to achieve a quadratic speedup over a wide class of classical simulated annealing, parallel tempering, and quantum Monte Carlo algorithms in solving these hard problem instances. Finally, we use this framework to analyze the experimental observations.

arXiv:2306.13123•Jun 22, 2023•38 citations

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.

quant-pharXiv:2604.12131•Apr 15, 2026•4 citations

A Short Path Quantum Algorithm for Exact Optimization

M. B. Hastings

We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree D ; this problem is called weighted MAX-E D -LIN2. We require that the optimal solution be unique for odd D and doubly degenerate for even D ; however, we expect that the algorithm still works without this condition and we show how to reduce to the case without this assumption at the cost of an additional overhead. While the time required is still exponential, the algorithm provably outperforms Grover's algorithm assuming a mild condition on the number of low energy states of the target Hamiltonian. The detailed analysis of the runtime dependence on a tradeoff between the number of such states and algorithm speed: fewer such states allows a greater speedup. This leads to a natural hybrid algorithm that finds either an exact or approximate solution.

arXiv:1802.10124•Quantum•Jul 26, 2018•24 citations

Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk

Simon Apers, Shantanav Chakraborty, Leonardo Novo +1 more

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

arXiv:2112.12746•Physical Review Letters•Oct 14, 2022•75 citations

Combinatorial optimization

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers applications of quantum computing in the area of combinatorial optimization. This area is related to operations research, and it encompasses many tasks that appear in science and industry, such as scheduling, routing, and supply chain management. We cover specific problems where a quadratic quantum speedup may be available via Grover’s quantum algorithm for unstructured search. We also cover several more recent proposals for achieving superquadratic speedups, including the quantum adiabatic algorithm, the quantum approximate optimization algorithm (QAOA), and the short-path algorithm.

Cambridge University Press eBooks•Apr 24, 2025•1 citation
We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-Ekkk-LIN2 and weighted MAX-kkk-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.
Quantum short-path algorithms give super-quadratic speedups over exhaustive search for some optimization families, but a recent classical conditioning-and-search algorithm weakens that comparison. This paper asks whether quantum algorithms can beat the quadratic acceleration of this stronger baseline.
It introduces quantum tilted walks: for a reversible-chain discriminant DDD and normalized objective GGG, apply Cb,M=(M+1)−1∑m=0M[(D+bG)/Eb]mC_{b,M}=(M+1)^{-1}\sum_{m=0}^M[(D+bG)/E_b]^mCb,M​=(M+1)−1∑m=0M​[(D+bG)/Eb​]m, where Eb=λmax⁡(D+bG)E_b=\lambda_{\max}(D+bG)Eb​=λmax​(D+bG). Unlike short-path ground-state preparation, this transformation permits nonstationary initial states and requires no lower bound on the tilted Hamiltonian’s spectral gap. For coherent conditioned stationary states on a candidate set TTT and a higher-scoring successful set SSS, the main bound is ∣⟨S∣Cb,M∣T⟩∣≥poly⁡(n)−1π(S)/π(T) 2κn/2|\langle S|C_{b,M}|T\rangle|\geq\operatorname{poly}(n)^{-1}\sqrt{\pi(S)/\pi(T)}\,2^{\kappa n/2}∣⟨S∣Cb,M​∣T⟩∣≥poly(n)−1π(S)/π(T)​2κn/2. Positive path expansions establish amplitude growth; log-Sobolev concentration bounds the normalization cost.
For weighted MAX-Ekkk-LIN2 and weighted MAX-kkk-CSP under stated regularity assumptions, this yields exact-optimization runtimes 2(1−ccl−κ)n/2+o(n)2^{(1-c^{\mathrm{cl}}-\kappa)n/2+o(n)}2(1−ccl−κ)n/2+o(n), with constant κ>0\kappa>0κ>0, versus conditioning-and-search’s 2(1−ccl)n+o(n)2^{(1-c^{\mathrm{cl}})n+o(n)}2(1−ccl)n+o(n). The CSP comparison additionally requires a successful-set size condition, satisfied for exact-kkk instances with k≥6k\geq6k≥6. Oracle implementation, precision costs, and unknown optimum and normalization parameters are addressed.
The comparison is not against every classical algorithm; conditioning-and-search is not the best known baseline for MAX-kkk-CSP. Practical exponent sizes are not evaluated. A synthetic example demonstrates amplitude gain with exponentially small spectral gaps, but its target is directly constructible, so it establishes no hard-problem speedup.
We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{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.
Designing quantum algorithms with a speedup over their classical analogs is a central challenge in quantum information science. Motivated by recent experimental observations of a superlinear quantum speedup in solving the Maximum Independent Set problem on certain unit-disk graph instances [Ebadi et al., Science 376, 6598 (2022)], we develop a theoretical framework to analyze the relative performance of the optimized quantum adiabatic algorithm and a broad class of classical Markov chain Monte Carlo algorithms. We outline conditions for the quantum adiabatic algorithm to achieve a quadratic speedup on hard problem instances featuring flat low-energy landscapes and provide example instances with either a quantum speedup or slowdown. We then introduce an additional local Hamiltonian with no sign problem to the optimized adiabatic algorithm to achieve a quadratic speedup over a wide class of classical simulated annealing, parallel tempering, and quantum Monte Carlo algorithms in solving these hard problem instances. Finally, we use this framework to analyze the experimental observations.
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-kkk-CSPs), leading to quantum algorithms with complexity 2(1−c)n/22^{(1-c)n/2}2(1−c)n/2 for some constant c>0c>0c>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′)n2^{(1-c')n}2(1−c′)n, for some constant c′>cc'>cc′>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.
We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree D ; this problem is called weighted MAX-E D -LIN2. We require that the optimal solution be unique for odd D and doubly degenerate for even D ; however, we expect that the algorithm still works without this condition and we show how to reduce to the case without this assumption at the cost of an additional overhead. While the time required is still exponential, the algorithm provably outperforms Grover's algorithm assuming a mild condition on the number of low energy states of the target Hamiltonian. The detailed analysis of the runtime dependence on a tradeoff between the number of such states and algorithm speed: fewer such states allows a greater speedup. This leads to a natural hybrid algorithm that finds either an exact or approximate solution.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
This chapter covers applications of quantum computing in the area of combinatorial optimization. This area is related to operations research, and it encompasses many tasks that appear in science and industry, such as scheduling, routing, and supply chain management. We cover specific problems where a quadratic quantum speedup may be available via Grover’s quantum algorithm for unstructured search. We also cover several more recent proposals for achieving superquadratic speedups, including the quantum adiabatic algorithm, the quantum approximate optimization algorithm (QAOA), and the short-path algorithm.