Time-to-solution

Time-to-solution (TTS) is the framework in which quantum annealers (and Ising-machine heuristics generally) are benchmarked against classical optimization. Defined by Rønnow and colleagues in 2014 while testing the D-Wave Two, it measures how long until the problem is actually solved and, by tracking how that time scales with problem size, gives “quantum speedup” a testable meaning. System-level in spirit, it is filed as platform-specific: it is native to analog optimizers, not gate-model devices.

How it works

Run the solver repeatedly on an instance and estimate the per-run probability p of reaching the ground state (or a chosen target energy). TTS is the time per run multiplied by the repetitions needed for at least one success with 99% probability: R99 = ln(1 − 0.99) / ln(1 − p). Two rules make the number meaningful. First, evaluate at the optimal anneal time: the 2014 paper shows that hardware whose minimum anneal time exceeds the optimum produces scaling curves that can fake or mask speedup. Second, aggregate over quantiles of a random-instance ensemble (median and 99th percentile can diverge sharply) and compare TTS scaling against optimized classical solvers, classifying any speedup as provable, strong, potential, or limited.

Strengths and limitations

TTS charges for actual solving time rather than proxies, so the annealing speedup debate is conducted almost entirely in it. But TTS has no canonical instance set: every study fixes its own problem class, quantile, and classical reference solver and hardware, so TTS numbers, and speedup claims, are relative to those choices. Where ground states are rarely reached, deliberate relaxations take over: time-to-target (2015) and time-to-epsilon (2024). Planted-instance generators such as frustrated cluster loops and Chook supply verifiable problem ensembles.

Notable results

The 2014 study itself found no evidence of quantum speedup on the D-Wave Two. Later headline claims (Google’s ~10^8 speedup on finite-range-tunneling instances; Albash and Lidar’s scaling advantage over simulated annealing; Munoz Bauza and Lidar’s time-to-epsilon result, PRL, 2025) have each been contested or matched by improved classical baselines, most recently a 2026 simulated-bifurcation rebuttal argued under the same TTS-style run-time accounting.