Quantum approaches for WCET-related optimization problems
| Autor: | Bettonte, Gabriella, Gilbert, Valentin, Vert, Daniel, Louise, Stéphane, Sirdey, Renaud |
|---|---|
| Přispěvatelé: | CEA- Saclay (CEA), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Université Paris-Saclay, Bettonte, Gabriella |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE ICCS 2022 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE ICCS 2022, Jun 2022, London, United Kingdom |
| Popis: | International audience; This paper explores the potential of quantum computing on a WCET 1-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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|