Internship or Master thesis / Short Doctoral research stay 6 to 9 months / 3 months Starting date (flexible) : Fall 2023

Location : ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France

Contact : Andrea Simonetto, andrea.simonetto@ensta-paris.fr

Operations Research benefits from decades of research on the classical side. On the Quantum Computing side, QAOA may offer perspectives in terms of searching performances execution speed and problem size. The performances of QAOA still have to be fully understood but recent paper show that classical QAOA theoretically outperforms state-of-the-art algorithms [1] on graphs problems.

In top of that the performances of QAOA may be improved in various directions. The big picture of QAOA is the following:

1. Problem encoding in a quantum circuit

2. Defining the ansatz (parametric circuit) to probe the solution space

3. Iterate to optimize: quantum/ classical

-  Vanilla encoding is consuming in terms of qubits: for smart charging problems, we need for example one qubit per vehicle [2]. The search for different and less qubit-consuming encoding may accelerate the quantum exploitation time and recent papers [3] and [4] proposes efficient encoding for sub-graph isomorphism problems.
The first internship we are searching for focuses on the extension of Sub-graph isomorphism to TSP (which is a permutation problem) and to QAOA
-  In vanilla QAOA, constraints are added via a penalty in the cost Hamiltonian. This is not always satisfactory as the weight of the penalty is not easy to calibrate and multiple constraints complicate even more the situation. Two area of researches may be explored

• Addition of the constraints into the mixing Hamiltonian in QAOA to avoid searching in unfeasible region of space. This is the second internship offer.
• Introduce constraints with other techniques including alternating methods (inequality constraints), addition of the “interior point method feature” to variational algorithms and transforming log barriers into polynomials. This is the third internship offer.

[1] Basso, J., Farhi, E., Marwaha, K., Villalonga, B., & Zhou, L. (2021). The quantum approximate optimization algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington- Kirkpatrick model. arXiv preprint arXiv:2110.14206.

[2] Dalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., & Veshchezerova, M. (2021). Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology, 8(1), 12.

[3] M. Rancic (Total Saclay), An exponentially more efficient optimization algorithm for noisy quantum computers, 2021 [arXiv: 2110.10788]

[4] N. Mariella, A.S., A Quantum Algorithm for the Sub-Graph Isomorphism Problem, 2021 [arXiv: 2111.09732]