  Quantum Annealing (QA) is a computational framework where a quantum system's
continuous evolution is used to find the global minimum of an objective
function over an unstructured search space. It can be seen as a general
metaheuristic for optimization problems, including NP-hard ones if we allow an
exponentially large running time. While QA is widely studied from a heuristic
point of view, little is known about theoretical guarantees on the quality of
the solutions obtained in polynomial time.
  In this paper we use a technique borrowed from theoretical physics, the
Lieb-Robinson (LR) bound, and develop new tools proving that short, constant
time quantum annealing guarantees constant factor approximations ratios for
some optimization problems when restricted to bounded degree graphs.
Informally, on bounded degree graphs the LR bound allows us to retrieve a
(relaxed) locality argument, through which the approximation ratio can be
deduced by studying subgraphs of bounded radius.
  We illustrate our tools on problems MaxCut and Maximum Independent Set for
cubic graphs, providing explicit approximation ratios and the runtimes needed
to obtain them. Our results are of similar flavor to the well-known ones
obtained in the different but related QAOA (quantum optimization algorithms)
framework.
  Eventually, we discuss theoretical and experimental arguments for further
improvements.
