Adaptive Shot Allocation for Recursive QAOA via Reinforcement Learning

• URL: http://arxiv.org/abs/2605.26544v1
• Date: Tue, 26 May 2026 04:48:29 GMT
• Title: Adaptive Shot Allocation for Recursive QAOA via Reinforcement Learning
• Abstract summary: Recursive QAOA (RQAOA) solves optimization problems by using shallow quantum circuits to estimate pairwise correlations.<n>Each elimination step requires measurement shots, and the total shot cost grows with the number of repeated stages.<n>On near-term quantum devices, increasing shot counts can translate directly into greater exposure to hardware-level noise sources.
• Score: 1.5469452301122175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recursive QAOA (RQAOA) solves combinatorial optimization problems by using shallow quantum circuits to estimate pairwise correlations and recursively eliminate variables until a classical solver can handle the residual instance. Each elimination step requires measurement shots, and the total shot cost grows with the number of recursive stages. On near-term quantum devices, increasing shot counts can translate directly into greater exposure to hardware-level noise sources such as readout errors and decoherence, making shot-efficient execution not merely a cost-reduction measure but a factor with direct implications for solution reliability. While shot reduction has been studied broadly across NISQ algorithms, step-wise measurement control inside the recursive loop of RQAOA has received little attention. We formulate this step-wise allocation as a sequential decision problem and propose two strategies for depth-1 RQAOA on weighted Max-Cut instances. A hand-crafted heuristic assigns shots based on local indicators of step difficulty, and a tabular Double Q-learning agent learns a residual policy that adjusts this baseline under a Lagrangian-constrained objective. Both methods are evaluated under a fixed-cap fairness protocol that equalizes the per-step budget across all strategies, and the elimination rule itself is kept unchanged so that the contribution of adaptive measurement control can be isolated. On a diverse set of weighted graph instances spanning a range of sizes and structures, the heuristic reduces total shots by approximately 23% relative to uniform allocation, and the RL policy achieves a 36% reduction with a lower effective shots per success ratio than both baselines. The improvement persists on problem sizes not seen during training, suggesting that reinforcement learning can discover efficient, instance-adaptive measurement strategies in recursive quantum optimization.

Related papers

• Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives [2.153824429735596]
  We develop a model-based optimistic learning algorithm that maintains confidence sets for the transition kernel and plans using a lower-buffered quantile criterion.<n>We prove that the exact point-quantile evaluation and exact lower-buffered quantile evaluation are PP-hard under Turing-time reductions.
  arXiv  Detail & Related papers  (2026-08-23T05:41:32Z)
• DISA: Offline Importance Sampling for Distribution-Matching LLM-RL [56.9445657766829]
  We introduce DISA, which moves this calibration problem outside the RL loop.<n> DISA draws proposal trajectories offline, estimates the partition function via importance sampling, and freezes the resulting partition-function estimate.<n>On two open-weight backbones across six math and three code benchmarks, DISA matches or exceeds the online-coupled distribution-matching baseline Flow.
  arXiv  Detail & Related papers  (2026-05-17T07:14:44Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• QTALE: Quantization-Robust Token-Adaptive Layer Execution for LLMs [0.0]
  Large language models (LLMs) demand substantial computational and memory resources.<n>We propose QTALE, a novel framework that enables seamless integration of token-adaptive execution with quantization.
  arXiv  Detail & Related papers  (2026-02-11T02:19:11Z)
• Recursive QAOA for Interference-Aware Resource Allocation in Wireless Networks [4.9873153106566575]
  Discrete radio resource management problems in dense wireless networks are difficult to solve at scale.<n>We investigate a quantum-classical approach based on the Recursive Quantum Approximate Optimization Algorithm (RQAOA), which interleaves shallow QAOA layers with variable elimination guided by measured single- and two-qubit correlators.<n>For interference-aware channel assignment, we give a compact QUBO/Ising formulation in which pairwise interference induces same-channel couplings and one-hot constraints are enforced via quadratic penalties.
  arXiv  Detail & Related papers  (2026-02-07T10:28:38Z)
• Q-learning with Adjoint Matching [58.78551025170267]
  We propose Q-learning with Adjoint Matching (QAM), a novel TD-based reinforcement learning (RL) algorithm.<n>QAM sidesteps two challenges by leveraging adjoint matching, a recently proposed technique in generative modeling.<n>It consistently outperforms prior approaches on hard, sparse reward tasks in both offline and offline-to-online RL.
  arXiv  Detail & Related papers  (2026-01-20T18:45:34Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem [5.7878635559750515]
  We propose the Iterative Partition Search Algorithm (IPSA) for solving the Shortest Vector Problem (SVP)<n>Our algorithm inherits the core idea of partitioning to circumvent the zero vector" from PSA and the iterative lattice basis reduction" framework from IQOAP.<n>A key feature of IPSA is the 1-tailed search spaces", which can be viewed as a highly constrained variant of PSA's partitioning strategy.
  arXiv  Detail & Related papers  (2025-08-26T12:53:02Z)
• Shot-Efficient ADAPT-VQE via Reused Pauli Measurements and Variance-Based Shot Allocation [0.0]
  We propose two integrated strategies to reduce the shot requirements in ADAPT-VQE.<n>First, we reuse Pauli measurement outcomes obtained during VQE parameter optimization in the subsequent operator selection step of the next ADAPT-VQE iteration.<n>Second, we apply variance-based shot allocation to both Hamiltonian and operator gradient measurements.
  arXiv  Detail & Related papers  (2025-07-22T12:34:49Z)
• R-Sparse: Rank-Aware Activation Sparsity for Efficient LLM Inference [77.47238561728459]
  R-Sparse is a training-free activation sparsity approach capable of achieving high sparsity levels in advanced LLMs.<n> Experiments on Llama-2/3 and Mistral models across ten diverse tasks demonstrate that R-Sparse achieves comparable performance at 50% model-level sparsity.
  arXiv  Detail & Related papers  (2025-04-28T03:30:32Z)
• CBQ: Cross-Block Quantization for Large Language Models [66.82132832702895]
  Post-training quantization (PTQ) has played a key role in compressing large language models (LLMs) with ultra-low costs.<n>We propose CBQ, a cross-block reconstruction-based PTQ method for LLMs.<n> CBQ employs a cross-block dependency using a reconstruction scheme, establishing long-range dependencies across multiple blocks to minimize error accumulation.
  arXiv  Detail & Related papers  (2023-12-13T07:56:27Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)

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.