Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities

• URL: http://arxiv.org/abs/2507.04438v1
• Date: Sun, 06 Jul 2025 15:52:37 GMT
• Title: Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
• Authors: Yuexin Su, Ziyi Yang, Peiyuan Huang, Tongyang Li, Yinyu Ye,
• Abstract summary: Bandits with knapsacks (BwK) constitute a model that combines integer programming with online learning.<n>We study the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles.<n>Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints.
• Score: 23.221938246770712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent regret bound of ${O}(\sqrt{T})$ and a problem-dependent bound of ${O}(\log T)$. In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of $(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})$, where $B$ is budget constraint in BwK and $\mathrm{OPT}_{\mathrm{LP}}$ denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.

Related papers

• A competitive NISQ and qubit-efficient solver for the LABS problem [0.0]
  Pauli Correlation.<n>(PCE) has recently been introduced as a qubit-efficient approach to optimization problems within variational quantum algorithms.<n>We extend the PCE-based framework to solve the Low Autocorrelation Binary Sequences (LABS) problem.
  arXiv  Detail & Related papers  (2025-06-20T18:00:02Z)
• A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
  We propose a new approach to utilize quantum computers for binary linear programming (BLP)<n>Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP.<n>In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework.
  arXiv  Detail & Related papers  (2025-03-27T07:24:33Z)
• A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
  We propose a quantum-classical hybrid algorithm with Ising model (HAWI) to address the Learning-With-Errors (LWE) problem. We identify the low-energy levels of the Hamiltonian to extract the solution, making it suitable for implementation on current noisy intermediate-scale quantum (NISQ) devices. Our algorithm is iterations, and its time complexity depends on the specific quantum algorithm employed to find the Hamiltonian's low-energy levels.
  arXiv  Detail & Related papers  (2024-08-15T05:11:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum Bayesian Optimization [64.58749619145908]
  We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
  arXiv  Detail & Related papers  (2023-10-09T03:10:42Z)
• Alleviating the quantum Big-$M$ problem [0.22615818641180715]
  Classically known as the "Big-$M$" problem, it affects the physical energy scale.<n>We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$.<n>We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
  arXiv  Detail & Related papers  (2023-07-19T18:00:05Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets [20.426493569846855]
  Multi-arm bandit (MAB) and linear bandit (SLB) are important models in reinforcement learning. We propose quantum algorithms for both models with $O(mboxpoly(log T))$ regrets. This is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning.
  arXiv  Detail & Related papers  (2022-05-30T10:54:53Z)

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.