{"id":"arxiv/2607.22818","url":"https://arxiv.org/abs/2607.22818","tags":["quant-ph","cond-mat.dis-nn","cs.LG"],"score":0,"title":"Practical advantage beyond the quadratic speedup limit with fully-quantum walks","domain":"quant-ph","source":"arxiv","authors":["Massimiliano Incudini","Guglielmo Mazzola"],"reviews":0,"subject":"quant-ph","summary":"We introduce a new class of fully-quantum Metropolis walks in which both the proposal and acceptance steps are intrinsically quantum. Unlike standard quantum walks obtained by quantizing classically efficient Markov chains, our algorithm employs Hamiltonian simulation as a quantum-native proposal mechanism, enlarging the class of quantum walks beyond classical counterparts. We target the problem of sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed error in total variation distance. This approach achieves about a cubic polynomial asymptotic…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-24","reactions":{}}