Applications of quantum algorithms to partially observable Markov decision processes

摘要

Due to the enormous processing gains that are theoretically achievable by using quantum algorithms instead of classical algorithms to solve rather generic classes of numerical problems, it makes sense that one should evaluate their potential applicability, appropriateness, and efficiency for solving virtually any computationally intensive task. Since many types of control and optimization problems may be couched in terms of partially observable Markov decision processes (POMDPs), and since solutions to these types of problems are invariably extremely difficult to obtain, the use of quantum algorithms to help solve POMDP problems is investigated here. Quantum algorithms are indeed found likely to provide significant efficiency improvements in several computationally intensive tasks associated with solving POMDPs, particularly in the areas of searching, optimization, and parameter optimization and estimation.