arXiv:2609.40088
Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
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.
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.
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.