SIGNAL
The quadratic speedup has long been treated as a ceiling for quantum-walk algorithms — a hard limit on what this class of techniques could ever deliver against their best classical counterparts. A new preprint argues that ceiling is, for one specific class of hard combinatorial sampling, a line on a map rather than a wall in the world.
The authors introduce a "fully-quantum Metropolis walk" in which both the proposal and acceptance steps of the Markov chain are intrinsically quantum, rather than a quantum walk grafted onto a classically efficient chain. Hamiltonian simulation does the proposal work natively, which is what enlarges the class of quantum walks beyond their classical ancestors. The target problem is sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed total-variation error.
The reported magnitude: about a cubic polynomial asymptotic advantage over previous quantum walks, for a total sixth-degree polynomial queries speedup over the best classical walk. The authors also report a fault-tolerant resource estimate and benchmark against CPU, GPU, and FPGA implementations of the best classical Markov chain. Under identical hardware assumptions, the runtime crossover shrinks from roughly 1,000 years to under a day.
The caveats are honest, and they are part of the story. The claim is single-source — a preprint, not yet peer-reviewed. The hardware assumption is matched across quantum and classical baselines, not a prediction about real machines. There is no independent reproduction yet. Read narrowly: for low-temperature Gibbs sampling of dense Ising models, on matched hardware assumptions, the quadratic ceiling is no longer where this algorithm lands. That is a map-redrawing claim about a specific class, not a general "quantum is faster" verdict.