Quantum tilted walks speed up solving hard optimization problems
Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
Data Structures and Algorithms
Summary
Solving some hard optimization puzzles by checking possibilities one by one takes a very long time. The authors show a new quantum approach called tilted walks that can find better solutions much faster than old methods, even faster than some recent classical algorithms. Unlike previous quantum methods, this one doesn’t need special preparation steps, making it more practical. They tested this on an example problem and got much better speedups than older quantum approaches.
What this means in practice
- •For quantum algorithm developers: Design quantum algorithms that solve hard combinatorial optimization problems faster than classical or previous quantum methods.
- •For operations research teams: Potentially improve solving weighted constraint satisfaction problems by adopting quantum-inspired optimization techniques when quantum hardware advances.
Authors
Guneykan Ozgul, Shouvanik Chakrabarti
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.