Quantum approaches for WCET-related optimization problems

Gabriella Bettonte (1, 2) , Valentin Gilbert (2) , Daniel Vert (2) , Stéphane Louise (2) , Renaud Sirdey (2)

1 Université Paris-Saclay
2 LCYL - Laboratoire pour la Confiance des sYstèmes de calcuL

This paper explores the potential of quantum computing on a WCET(Worst-Case Execution Time (of a program).)-related combinatorial optimization problem applied to a set of several polynomial special cases. We consider the maximization problem of determining the most expensive path in a control flow graph. In these graphs, vertices represent blocks of code whose execution times are fixed and known in advance. We port the considered optimization problem to the quantum framework by expressing it as a QUBO. We then experimentally compare the performances in solving the problem of classic Simulated Annealing (SA), Quantum Annealing (QA), and Quantum Approximate Optimization Algorithm (QAOA). Our experiments suggest that QA represents a fast equivalent of simulated annealing. Indeed, we measured the approximation ratio on the results of QA and SA, showing that their performances are comparable, at least on our set of simplified problems.

Domaines: Recherche opérationnelle [math.OC]

Gabriella Bettonte, Valentin Gilbert, Daniel Vert, Stéphane Louise, Renaud Sirdey. Quantum approaches for WCET-related optimization problems. ICCS, Jun 2022, Londres, United Kingdom. pp.202--217, ⟨10.1007/978-3-031-08760-8_18⟩. ⟨hal-04495534⟩