Quantum Algorithms for Finite-horizon Markov Decision Processes

• URL: http://arxiv.org/abs/2508.05712v1
• Date: Thu, 07 Aug 2025 09:00:23 GMT
• Title: Quantum Algorithms for Finite-horizon Markov Decision Processes
• Authors: Bin Luo, Yuwen Huang, Jonathan Allcock, Xiaojun Lin, Shengyu Zhang, John C. S. Lui,
• Abstract summary: We design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs)<n>In the exact dynamics setting, we prove that our $textbfQVI-1$ algorithm achieves a quadratic speedup in the size of the action space $(A)$.<n>In the generative model setting, we prove that our algorithms $textbfQVI-3$ and $textbfQVI-4$ achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm.
• Score: 40.812944518646006
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\textbf{Quantum Value Iteration (QVI)}$ algorithm $\textbf{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^{*}$) and the optimal V-value function ($V_{0}^{*}$). Furthermore, our algorithm $\textbf{QVI-2}$ provides an additional speedup in the size of the state space $(S)$ when obtaining near-optimal policies and V-value functions. Both $\textbf{QVI-1}$ and $\textbf{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 $\textbf{QVI-3}$ and $\textbf{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 $\textbf{QVI-3}$ and $\textbf{QVI-4}$ are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.

Related papers

• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  Quantum algorithms for linear systems produce the solution state $A-1|brangle$ by querying two oracles. We present a quantum linear system algorithm making $mathbfThetaleft (1/sqrtpright)$ queries to $O_b$, which is optimal in the success probability. In various applications such as solving differential equations, we can further improve the dependence on $p$ using a block preconditioning scheme.
  arXiv  Detail & Related papers  (2024-10-23T18:00:01Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
  arXiv  Detail & Related papers  (2024-07-04T11:03:48Z)
• Computational Supremacy of Quantum Eigensolver by Extension of Optimized Binary Configurations [0.0]
  We develop a quantum eigensolver based on a D-Wave Quantum Annealer (D-Wave QA) This approach performs iterative QA measurements to optimize the eigenstates $vert psi rangle$ without the derivation of a classical computer. We confirm that the proposed QE algorithm provides exact solutions within the errors of $5 times 10-3$.
  arXiv  Detail & Related papers  (2024-06-05T15:19:53Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study [0.0]
  optimizing a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs) We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, $eta$.
  arXiv  Detail & Related papers  (2022-02-14T15:00:28Z)
• Quantum Algorithms for Reinforcement Learning with a Generative Model [16.168901236223117]
  Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. We design quantum algorithms that approximate an optimal policy ($pi*$), the optimal value function ($v*$), and the optimal $Q$-function ($q*$) We show that our quantum algorithm for computing $q*$ is optimal by proving a matching quantum lower bound.
  arXiv  Detail & Related papers  (2021-12-15T19:51:49Z)
• Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
  This work presents the first projection-free algorithm to solve bi-level optimization problems, where the objective function depends on another optimization problem. The proposed $textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$) is shown to achieve a sample complexity of $mathcalO(epsilon-2)$ for convex objectives.
  arXiv  Detail & Related papers  (2021-10-22T11:49:15Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits [0.755972004983746]
  Variational quantum algorithms (VQAs) optimize the parameters $vectheta$ of a parametrized quantum circuit. We prove two results, assuming $V(vectheta)$ is an alternating layered ansatz composed of blocks forming local 2-designs. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.
  arXiv  Detail & Related papers  (2020-01-02T18:18:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.