NEASQC webinar: Quantum Computing for Optimization Problems

Partners involved

Date: 9 July 2024
Time: 11:00-12:00 CEST

NEASQC is organising a series of interactive webinars to share our findings with the quantum computing community. Each month NEASQC experts present an Open Source library available in the NEASQC GitHub or a technique they investigated, and answer your questions.

In July, we will present some outcomes of the NEASQC use case on HPC mesh segmentation.

Abstract: Variational quantum algorithms such as the Quantum Approximate Optimization Algorithm(QAOA) and its extensions like Quantum Alternating Operator Ansatz have been heavily studied for NP-hard combinatorial optimization problems. In the Noisy Intermediate Scale Quantum (NISQ) era, as the name suggests, the quantum computers are still relatively small and noisy. The number of qubits required in QAOA and similar algorithms scale linearly with problem size, meaning that a problem of size n requires O(n) qubits. This has limited the application of such algorithms to toy problems. Here we demonstrate an algorithm where the number of qubits required scales logarithmically with problem size, meaning that a problem of size n shall require O(log n) number of qubits. We call this algorithm the LogQ encoding. We benchmark LogQ against classical algorithms for several NP-hard problems. In addition, we generalize the method so that it can be used for any Quadratic Unconstrained Binary Optimization (QUBO) problem. We then present the use-case of mesh segmentation. Mesh segmentation refers to the process of dividing a complex mesh (composed of vertices, edges, and faces) into meaningful and semantically coherent parts or regions. We convert the problem into a QUBO problem and treat it using LogQ.

Speaker: Yagnik Chatterjee, TotalEnergies

Yagnik is a final-year Ph.D. candidate at TotalEnergies and the Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM). He specializes in the exciting intersection of operations research and quantum computing. His research focuses on designing and implementing quantum variational algorithms for solving combinatorial optimization problems. Prior to his Ph.D., he obtained BSc and MSc degrees in Physics.

Related publications

Location :
Our website uses cookies to give you the most optimal experience online by: measuring our audience, understanding how our webpages are viewed and improving consequently the way our website works, providing you with relevant and personalized marketing content. You have full control over what you want to activate. You can accept the cookies by clicking on the “Accept all cookies” button or customize your choices by selecting the cookies you want to activate. You can also decline all cookies by clicking on the “Decline all cookies” button. Please find more information on our use of cookies and how to withdraw at any time your consent on our privacy policy.
Accept all cookies
Decline all cookies
Privacy Policy