K-spin Hamiltonian for quantum-resolvable Markov decision processes
This work addresses the challenge of solving MDPs more efficiently using quantum computing, which could benefit reinforcement learning applications, though it appears incremental as it builds on existing quantum methods applied to a known problem.
The authors tackled the problem of solving Markov decision processes (MDPs) by deriving a K-spin Hamiltonian representation, enabling the use of quantum algorithms like adiabatic annealing and QAOA for optimal policy search. They validated their approach with proof-of-concept calculations comparing simulated and quantum annealing to classical Q-Learning, and analyzed the scaling of quantum hardware resources.
The Markov decision process is the mathematical formalization underlying the modern field of reinforcement learning when transition and reward functions are unknown. We derive a pseudo-Boolean cost function that is equivalent to a K-spin Hamiltonian representation of the discrete, finite, discounted Markov decision process with infinite horizon. This K-spin Hamiltonian furnishes a starting point from which to solve for an optimal policy using heuristic quantum algorithms such as adiabatic quantum annealing and the quantum approximate optimization algorithm on near-term quantum hardware. In proving that the variational minimization of our Hamiltonian is equivalent to the Bellman optimality condition we establish an interesting analogy with classical field theory. Along with proof-of-concept calculations to corroborate our formulation by simulated and quantum annealing against classical Q-Learning, we analyze the scaling of physical resources required to solve our Hamiltonian on quantum hardware.