In 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 memoryaccesses, in the presence of preemptions. Our contribution consists in porting that algorithm to the quantum framework, improving the complexity of the algorithm from O(N³) to O(N²+N).