%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Locality in Quantum Annealing to approximate combinatorials problems}
%

% Pour le sommaire
\addcontentsline{toc}{section}{Locality in Quantum Annealing to approximate combinatorials problems}
%

% Pour la liste des auteurs
\index{Braida, A.}\index{Martiel, S.}\index{Todinca, A.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Arthur Braida}, Atos Quantum Lab \& LIFO, {\tt arthur.braida@atos.net}\\ %souligner l'orateur
\indent
Simon Martiel, Atos Quantum Lab, {\tt simon.martiel@atos.net}\\ 
\indent
Ioan Todinca, LIFO, {\tt ioan.todinca@univ-orleans.fr}\\ 
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

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.

We believe that quantum annealing is a promising, general framework for designing approximation algorithms, but the main obstacle is the current lack of mathematical tools for analyzing the solutions obtained in limited time. The purpose of this work is to make a step forward toward such tools, and show that QA produces reasonable solutions for specific optimization problems, on specific graph classes. More precisely, we will focus on short-constant-time evolution, and we are interested in getting an approximate solution. Indeed, we would like to understand what guarantee on the results quantum computers can expect to reach while they are stable only for a very short time.

In this work 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, hence 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. Hence 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.






%\begin{thebibliography}{99}

%\bibitem{qaoa}
%E.~Fahri, J.~Goldstone and S.~Gutmann, \emph{A quantum approximate optimization algorithm}, (2014).

%\end{thebibliography}


\vfill
\end{document}