Towards a quantum algorithm for evaluating WCETs

International audienceIn this paper we propose a quantum-based solution to the problem of counting the cache hits, an important issue when analyzing real-time embedded applications. This field has already seen the development of "quantum-inspired" classical algorithms which are competitive with the state of the art. We designed a polynomial-time dynamic programming algorithm for computing the lowest number of cache hits realized by a deterministic sequence of memory accesses, in the presence of preemptions. Our contribution consists in porting that algorithm to the quantum framework, improving the complexity of the algorithm from (3) to (2 +)