Séminaire du Groupe de Travail "Quantum Information and Quantum Computing": Samuel Deleplanque (IEMN)

La "Maison de la Simulation" et le groupe de travail "Quantum Information and Quantum Computing" vous invite au séminaire de Samuel Deleplanque (IEMN)

Lien Zoom: https://univ-lille-fr.zoom.us/j/95675415665?pwd=Tmh4T09SWUFaZ2dXK2p5dkd3S2NOQT09

11:00-12:00: Samuel Deleplanque (Maître de Conférences à l'Université de Lille et au laboratoire IEMN)

Titre: Quantum-Assisted Combinatorial Optimization: Emphasizing Analog Quantum Machines

Abstract:

This study examines the use of analog quantum computing devices provided by organizations such as D-Wave in Canada, Pasqal in France, and QuEra in the United States. These machines excel in solving problems related to binary, quadratic, and unconstrained optimization (QUBO), sparking an increased interest in this field of study. The paper begins by explaining how these devices operate from a computer science perspective before moving on to discuss universal gate quantum computers, like those created by IBM. It then addresses a range of optimization and operations research issues using quantum analog technologies. Covered topics include the Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), Job Shop Scheduling Problem (JSSP), Resource-Constrained Project Scheduling Problem (RCPSP), Max Cut, and the 3-Satisfiability Problem (3-Sat). In particular, for the 3-Sat problem, this work illustrates the advantages of using polynomial-time reduction to the Maximum Independent Set (MIS) to facilitate problem solving, resulting in a new sparser graph with an increased number of variables. The analysis emphasizes the importance of considering the unique configurations of these quantum devices, such as their incomplete qubit graph, throughout the study.