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:1807.03758

Weaker Assumptions for the Short Path Optimization Algorithm

M. B. Hastings

Published Jul 10, 2018• 0 citations
arXivHTMLPDF

Abstract

The short path algorithm gives a super-Grover speedup for various optimization problems under the assumption of a unique ground state and under an assumption on the density of low-energy states. Here, we remove the assumption of a unique ground state; this uses the same algorithm but a slightly different analysis and holds for arbitrary MAX-$D$-LIN-$2$ problems. Then, specializing to the case $D=2$, we show that for certain values of the objective function we can always achieve a super-Grover speedup (albeit a very slight one) without any assumptions on the density of states. Finally, for random instances, we give a heuristic treatment suggesting a more significant improvement.

DOI
10.48550/arxiv.1807.03758

Related papers

The Short Path Algorithm Applied to a Toy Model

M. B. Hastings

We numerically investigate the performance of the short path optimization algorithm on a toy problem, with the potential chosen to depend only on the total Hamming weight to allow simulation of larger systems. We consider classes of potentials with multiple minima which cause the adiabatic algorithm to experience difficulties with small gaps. The numerical investigation allows us to consider a broader range of parameters than was studied in previous rigorous work on the short path algorithm, and to show that the algorithm can continue to lead to speedups for more general objective functions than those considered before. We find in many cases a polynomial speedup over Grover search. We present a heuristic analytic treatment of choices of these parameters and of scaling of phase transitions in this model.

arXiv:1901.03884•Quantum•May 20, 2019•3 citations

Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

Guneykan Ozgul, Shouvanik Chakrabarti

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.

quant-pharXiv:2609.40088•Oct 1, 2026•0 citations

New Optimized Grover's Algorithm Optimization of Grover's algorithm: with quantum simulating

Idhant Sood, Ahaan Sirohia, Arjun Dev Juneja

The paper below shows an optimized algorithm to perform Grover’s Algorithm on classical computers for high no. of states in reasonable times.

•May 30, 2025•0 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•17 citations

New Optimized Grover's Algorithm Optimization of Grover's algorithm: with quantum simulating

Idhant Sood, Ahaan Sirohia, Arjun Dev Juneja

The paper below shows an optimized algorithm to perform Grover’s Algorithm on classical computers for high no. of states in reasonable times.

•May 23, 2025•0 citations

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•0 citations
The short path algorithm gives a super-Grover speedup for various optimization problems under the assumption of a unique ground state and under an assumption on the density of low-energy states. Here, we remove the assumption of a unique ground state; this uses the same algorithm but a slightly different analysis and holds for arbitrary MAX-DDD-LIN-222 problems. Then, specializing to the case D=2D=2D=2, we show that for certain values of the objective function we can always achieve a super-Grover speedup (albeit a very slight one) without any assumptions on the density of states. Finally, for random instances, we give a heuristic treatment suggesting a more significant improvement.
We numerically investigate the performance of the short path optimization algorithm on a toy problem, with the potential chosen to depend only on the total Hamming weight to allow simulation of larger systems. We consider classes of potentials with multiple minima which cause the adiabatic algorithm to experience difficulties with small gaps. The numerical investigation allows us to consider a broader range of parameters than was studied in previous rigorous work on the short path algorithm, and to show that the algorithm can continue to lead to speedups for more general objective functions than those considered before. We find in many cases a polynomial speedup over Grover search. We present a heuristic analytic treatment of choices of these parameters and of scaling of phase transitions in this model.
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.
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.
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.