A quantum switch is one of the most fundamental network elements for connecting different quantum devices. In this paper, we explore the “optimal entanglement policy” of a quantum switch under a scenario where the stored and entangled qubits in the quantum switch may undergo a decoherence process. Finding an optimal entanglement policy is important as it enables a quantum switch to make a judicious basis measurement based on the number of existing link-level entanglements to maximize the “weighted throughput”. We use a Markov decision process framework to model the dynamics of the quantum switch, and theoretically reveal a threshold-based relationship between bipartite and tripartite policies under a very general class of weight functions with a weight parameter β. We further extend our analysis to uncover athreshold-based structure of optimal policies. In particular, the optimal policy for the quantum switch is a bipartite or tripartite policy when β is below a threshold β∗Bor above a threshold β∗T, respectively. When β∗B∗T, the optimal policy becomes a “threshold-based and state-dependent entanglement policy”. We also extend the work to allow a mixture of bipartite and tripartite policies by introducing a state-dependent mixed action. We theoretically show threshold-related relationships between mixed and bipartite/tripartite policies. Moreover, we extend this analysis to study optimal policies and characterize the threshold-based structure when the mixed action is considered. We carry out extensive numerical experiments to confirm that the optimal entanglement policy has such structural property when the mixed action is considered or not.

In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment’s dynamics (i.e., transition probabilities), we prove that our Quantum Value Iteration (QVI) algorithm QVI-1 achieves a quadratic speedup in the size of the action space $(A)$ compared with the classical value iteration algorithm for computing the optimal policy ($\pi^{\ast}$) and the optimal V-value function ($V_{0}^{\ast}$). Furthermore, our algorithm QVI-2 provides an additional speedup in the size of the state space $(S)$ when obtaining near-optimal policies and V-value functions. Both QVI-1 and QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on $S$ and $A$. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms QVI-3 and QVI-4 achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of $A$, estimation error $(\epsilon)$, and time horizon $(H)$. More importantly, we prove quantum lower bounds to show that QVI-3 and QVI-4 are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.