Quantum POMDPs

Abstract

We present quantum observable Markov decision processes (QOMDPs), the quantum analogues of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent's state is represented as a quantum state and the agent can choose a superoperator to apply. This is similar to the POMDP belief state, which is a probability distribution over world states and evolves via a stochastic matrix. We show that the existence of a policy of at least a certain value has the same complexity for QOMDPs and POMDPs in the polynomial and infinite horizon cases. However, we also prove that the existence of a policy that can reach a goal state is decidable for goal POMDPs and undecidable for goal QOMDPs.

13 pages, 3 figures, revised version (fixes several errors, discusses related work)

References in corpus (3)

• Perseus: Randomized Point-based Value Iteration for POMDPs
• Quantum measurement occurrence is undecidable
• Reachability Analysis of Quantum Markov Decision Processes

Cited by in corpus (27)

• An introduction to quantum machine learning
• Model-Free Quantum Control with Reinforcement Learning
• Quantum games: a review of the history, current state, and interpretation
• Tools for quantum network design
• Machine learning \& artificial intelligence in the quantum domain
• Reinforcement learning for optimal error correction of toric codes
• Policies for elementary links in a quantum network
• Quantum Jump Metrology
• Non-Markovian feedback for optimized quantum error correction
• Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states
• Machine Learning for Estimation and Control of Quantum Systems
• Model Checking Quantum Systems --- A Survey
• Improving robustness of quantum feedback control with reinforcement learning
• Exponential improvements for quantum-accessible reinforcement learning
• Quantum contextual bandits and recommender systems for quantum data
• Exact model reduction for discrete-time conditional quantum dynamics
• Unitary Evolutions Sourced By Interacting Quantum Memories: Closed Quantum Systems Directing Themselves Using Their State Histories
• Quantum Tensor Networks, Stochastic Processes, and Weighted Automata
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Improving quantum state detection with adaptive sequential observations
• Reinforcement learning to learn quantum states for Heisenberg scaling accuracy
• The Learnability of Unknown Quantum Measurements
• Quantum Büchi Automata
• Estimation of mutual information via quantum kernel method
• Decomposition of Quantum Markov Chains and Its Applications
• A Note on Quantum Markov Models
• Molecular Quantum Control Algorithm Design by Reinforcement Learning