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...
Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed that DQI achieves a nontrivial satisfaction fraction guarantee only on linear-girth graphs, for which MaxCut is classically easy. However, thes...
Anuj Apte, Shouvanik Chakrabarti, An-Di Gu et al.· 0 citations
SF-NorMuon, a schedule-free spectral optimizer that closes the performance gap with tuned AdamW baselines, makes horizon-free optimization more practical, taking a step towards truly open-ended, continual learning.
We establish a near-linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every...
Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana et al.· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
