Andrea is Professor at l’ENSTA. Below the details of his talk, that will be held in room 405, building TPR2, Luminy.
Title : Efficient Quantum Encodings for Combinatorial Optimization Problems:
The Sub-Graph Isomorphism Case
Abstract : With the steady advances in quantum technology to develop reliable quantum computers and software interfaces, quantum computing is well on track to disrupt traditional workflows in solving hard problems. A natural question is then whether quantum-based approaches can help the resolution of combinatorial optimization problems, which are both widespread in real life and very hard to solve classically. Here, the answer is more nuanced.
A class of promising candidates to solve combinatorial optimization problems on near-term quantum computers is the class of variational algorithms, which alternate quantum evaluations and classical steps. Here, one big open question towards quantum advantage is how we encode the problem into the quantum hardware to be able to scale better (e.g., solve larger problems, solve the same problems faster) than on classical computers.
In this talk, I will present some work in tackling this open question by looking at a specific combinatorial problem. In particular, I will propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new Ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.The talk is based on https://arxiv.org/abs/2111.09732.