Seminar of the Quantum Information Working Group: Samuel Deleplanque (IEMN)

The "Maison de la Simulation" and the "Quantum Information and Quantum Computing" working group invite you to a seminar given by Samuel Deleplanque, assistant Professor at the University of Lille and IEMN institute

Zoom link for virtual broadcasting: https://univ-lille-fr.zoom.us/j/95675415665?pwd=Tmh4T09SWUFaZ2dXK2p5dkd3S2NOQT09

11:00-12:00: Samuel Deleplanque (assistant Professor at the University of Lille and IEMN institute)

Title: 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.