Agenda

Benchmarking quantum annealing machines
for solving combinatorial problems

Daniel Vert (CEA list)

Mardi 22 Juin à 14h

Zoom link : https://univ-grenoble-alpes-fr.zoom.us/j/91808901596?pwd=UWZ2cml2N1VBOEZBenk0d3RJek9rdz09

Abstract: Quantum computing is receiving renewed interest with recent announcements from several players. The most obvious reason is that some quantum algorithms can solve in polynomial time the same tasks that are currently considered non-polynomial on classical computers. In recent years, analog quantum machines have appeared, of which the computers currently marketed by the Canadian company D-Wave are the first representatives, operating on a quantum accelerated annealing principle. From an abstract point of view, such a machine can be considered as an oracle specialized in solving an NP-hard optimization problem with an algorithm functionally analogous to simulated annealing but with quantum acceleration. In addition to the formal analogies between simulated annealing and quantum annealing, there is an analogy between the current state of the art and that of simulated annealing when it was introduced. The work carried out in the framework consists in understanding the functioning of such a machine and in determining to what extent it contributes to the solution of combinatorial problems. The challenge is to know whether or not there is an acceleration of a quantum nature in these machines compared to other computers. The idea is to provide a first study on the behavior of quantum annealing when confronted with a problem known to trap classical annealing. The bipartite matching problem was specifically chosen to be difficult to solve using simulated annealing. Comparing the performances between these two annealers gives a first benchmark and allows to better characterize their potentials.