Automated planning using quantum computation

Abstract

This paper presents an adaptation of the standard quantum search technique to enable application within Dynamic Programming, in order to optimise a Markov Decision Process. This is applicable to problems arising from typical planning domains that are intractable due to computational complexity when using classical computation. The proposed method is able to balance state-space exploration with greedy selection of the local minima by setting appropriate thresholds via quantum counting. A quantum walk is used to propogate through a graphical representation of the state space.