NEASQC webinar: Quantum Computing for Optimization Problems

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

• Deliverable: D5.9: Benchmarking of QAOA-based algorithms for mesh segmentation, against K-Means, normalized and randomized cuts, and core extraction methods
• Publication: Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer (Physical Review A)