Quantum spatial best-arm identification via quantum walks

• URL: http://arxiv.org/abs/2509.05890v1
• Date: Sun, 07 Sep 2025 01:53:09 GMT
• Title: Quantum spatial best-arm identification via quantum walks
• Authors: Tomoki Yamagami, Etsuo Segawa, Takatomo Mihana, André Röhm, Atsushi Uchida, Ryoichi Horisaki,
• Abstract summary: We propose a quantum algorithm for best-arm identification in graph bandits.<n>We employ quantum walks to encode superpositions over graph-constrained actions.<n>Our results highlight the potential of quantum walks to accelerate exploration in constrained environments.
• Score: 0.5541644538483946
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum reinforcement learning has emerged as a framework combining quantum computation with sequential decision-making, and applications to the multi-armed bandit (MAB) problem have been reported. The graph bandit problem extends the MAB setting by introducing spatial constraints, yet quantum approaches remain limited. We propose a quantum algorithm for best-arm identification in graph bandits, termed Quantum Spatial Best-Arm Identification (QSBAI). The method employs quantum walks to encode superpositions over graph-constrained actions, extending amplitude amplification and generalizing the Quantum BAI algorithm via Szegedy's walk framework. This establishes a link between Grover-type search and reinforcement learning tasks with structural restrictions. We analyze complete and bipartite graphs, deriving the maximal success probability of identifying the best arm and the time step at which it is achieved. Our results highlight the potential of quantum walks to accelerate exploration in constrained environments and extend the applicability of quantum algorithms for decision-making.

Related papers

• Quantum Circuit-Based Adaptation for Credit Risk Analysis [27.308408027453012]
  Noisy and Intermediate-Scale Quantum, or NISQ, processors are sensitive to noise, prone to quantum decoherence, and are not yet capable of continuous quantum error correction for fault-tolerant quantum computation.<n>We experimentally study how hardware-aware variational quantum circuits on a superconducting quantum processing unit can model distributions relevant to specific use-case applications for Credit Risk Analysis.
  arXiv  Detail & Related papers  (2026-01-11T11:17:37Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Quantum walks through generalized graph composition [0.30458514384586405]
  We generalize the recently-introduced graph composition framework to the non-boolean setting.<n>For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs.<n>We provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator.
  arXiv  Detail & Related papers  (2025-10-06T16:07:20Z)
• Quantum quench dynamics as a shortcut to adiabaticity [31.114245664719455]
  We develop and test a quantum algorithm in which the incorporation of a quench step serves as a remedy to the diverging adiabatic timescale. Our experiments show that this approach significantly outperforms the adiabatic algorithm.
  arXiv  Detail & Related papers  (2024-05-31T17:07:43Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
  We introduce an innovative quantum framework for the agent's engagement with an unknown MDP.<n>We show that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning.
  arXiv  Detail & Related papers  (2023-10-18T03:17:51Z)
• Quantivine: A Visualization Approach for Large-scale Quantum Circuit Representation and Analysis [31.203764035373677]
  We develop Quantivine, an interactive system for exploring and understanding quantum circuits. A series of novel circuit visualizations are designed to uncover contextual details such as qubit provenance, parallelism, and entanglement. The effectiveness of Quantivine is demonstrated through two usage scenarios of quantum circuits with up to 100 qubits.
  arXiv  Detail & Related papers  (2023-07-18T04:51:28Z)
• Improved maximum-likelihood quantum amplitude estimation [0.0]
  Quantum estimation is a key subroutine in a number of powerful quantum algorithms, including quantum-enhanced Monte Carlo simulation and quantum machine learning. In this article, we deepen the analysis of Maximum-likelihood quantum amplitude estimation (MLQAE) to put the algorithm in a more prescriptive form, including scenarios where quantum circuit depth is limited. We then propose and numerically validate a modification to the algorithm to overcome this problem, bringing the algorithm even closer to being useful as a practical subroutine on near- and mid-term quantum hardware.
  arXiv  Detail & Related papers  (2022-09-07T17:30:37Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware. We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
  arXiv  Detail & Related papers  (2022-06-13T16:21:04Z)
• Squeezing and quantum approximate optimization [0.6562256987706128]
  Variational quantum algorithms offer fascinating prospects for the solution of optimization problems using digital quantum computers. However, the achievable performance in such algorithms and the role of quantum correlations therein remain unclear. We show numerically as well as on an IBM quantum chip how highly squeezed states are generated in a systematic procedure.
  arXiv  Detail & Related papers  (2022-05-20T18:00:06Z)
• Quantum Bandits [10.151012770913622]
  We consider the quantum version of the bandit problem known as em best arm identification (BAI) We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum. We then propose an algorithm based on quantum amplitude amplification to solve BAI.
  arXiv  Detail & Related papers  (2020-02-15T15:17:11Z)

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.