Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The first quantum algorithms for bandits with knapsacks improve the classical problem-independent regret by a factor of $(1+\sqrt{B/\mathrm{OPT}_{\mathrm{LP}}})$ and the problem-dependent log-$T$ term quadratically.

desk verdict First quantum BwK paper, with a genuinely useful problem-dependent result, but the problem-independent headline bound rests on an unstated assumption that fails in common budget regimes. read the letter →

arxiv 2507.04438 v1 pith:5MQ7QAQK submitted 2025-07-06 quant-ph cs.DScs.LGmath.OCstat.ML

Yuexin Su , Ziyi Yang , Peiyuan Huang , Tongyang Li , Yinyu Ye This is my paper
classification quant-phcs.DScs.LGmath.OCstat.ML MSC 68Q1290C0568W27 PACS 03.67.Lx
keywords banditswithknapsacksquantumalgorithmsMonteCarloamplitudeestimationlinearprogrammingregretboundsprimal-dualonlinelearningresourceconstraints
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether quantum oracles can speed up bandits with knapsacks (BwK), the online decision problem in which an agent pulls arms for reward while spending a limited budget across several resources. It claims the first quantum algorithms for this model and proves two kinds of gains. In the problem-independent setting, replacing classical sample-averaging with quantum Monte Carlo estimation shrinks confidence intervals from $1/\sqrt{N}$ to roughly $1/N$ in the number $N$ of oracle queries, and the resulting regret bound improves on the classical one by a factor of $(1+\sqrt{B/\mathrm{OPT}_{\mathrm{LP}}})$. In the problem-dependent setting, a two-phase primal-dual algorithm that uses an approximate quantum linear-programming solver achieves a quadratic improvement in the leading $\log T$ regret term and a polynomial speedup in problem dimensions; the paper proves that the solver's approximation error does not inflate the regret. If these results hold, resource-constrained online learning joins the list of decision problems where quantum access yields provable gains in both regret and running time.

What carries the argument

Two mechanisms carry the argument. The first is quantum Monte Carlo (QMC) mean estimation built on quantum amplitude estimation: with $N$ oracle queries it returns an estimate whose confidence interval has length $\tilde{O}(1/N)$, versus $O(1/\sqrt{N})$ classically, and because measurement collapses the quantum state the algorithms re-run QMC only at geometrically spaced intervals. The second is the inexact quantum linear-programming solver, a zero-sum-game solver accelerated by fast quantum Gibbs sampling that returns an $\epsilon_{\mathrm{LP}}$-optimal, $\epsilon_{\mathrm{LP}}$-feasible solution in time $\tilde{O}(\sqrt{m+d}/\epsilon_{\mathrm{LP}}^{2.5})$ (Lemma 4); the paper's robustness analysis proves that for $\epsilon_{\mathrm{LP}}$ below explicit thresholds the approximation error does not enlarge the regret. Around these sit the inherited classical structure: the bang-per-buck selection rule $r^U_i(s)/(C^L_{\cdot,i}(s)\cdot v(s))$ with a multiplicative-weights price vector $v(s)$ in Algorithm 1, and in Algorithm 2 the two-phase decomposition that separates identification of $I^*$ and $J'$ from exhausting the binding resources, governed by the gap parameter $\delta$, the minimal singular value $\sigma$, and the smallest nonzero primal component $\chi$.

What would settle it

Run Algorithm 1, or just follow its proof's final chain, on an instance with $m > B/\log(dT)$, for example $m = 10$ arms, a single resource with budget $B = 1$, and horizon $T = 10^6$: the dropped term $\mathrm{OPT}_{\mathrm{LP}}\cdot m\log T/B$ is no longer dominated by $\sqrt{\log(dT)}\,\mathrm{OPT}_{\mathrm{LP}}\sqrt{m/B}$, so one must verify whether the claimed bound $O(\sqrt{\log(dT)}\,\mathrm{OPT}_{\mathrm{LP}}\sqrt{m/B} + m\log(dT)\log T)$ still emerges; if it does not, Theorem 1 needs the condition $m \le B/\log(dT)$ added to its statement or the bound revised.

Watch

Extended reading notes

Core claim

The central claim is that the regret bounds classical algorithms achieve with $O(1/\sqrt{N})$ confidence intervals are not optimal when the learner has quantum oracle access to rewards and resource consumption. Algorithm 1, a quantum version of the primal-dual 'bang-per-buck' algorithm, has expected regret $O(\sqrt{\log(dT)}\,\mathrm{OPT}_{\mathrm{LP}}\sqrt{m/B} + m\log(dT)\log T)$ (Theorem 1), compared with the classical bound $O(\sqrt{\log(dT)}\,\mathrm{OPT}_{\mathrm{LP}}\sqrt{m/B}\,(1+\sqrt{B/\mathrm{OPT}_{\mathrm{LP}}}) + m\log(dT)\log T)$; the improvement is exactly the factor $(1+\sqrt{B/\mathrm{OPT}_{\mathrm{LP}}})$. Algorithm 2, which targets problem-dependent bounds, first identifies the optimal arms $I^*$ and the non-binding constraints $J'$ using quantum-estimated upper and lower confidence bounds, then exhausts the binding resources by re-solving an adaptive LP each round. Its regret is $\tilde{O}\big((2+\tfrac{1}{b})\tfrac{m\sqrt{d}\log T}{b\delta} + \tfrac{d^4}{b^2\min\{\chi^2,\delta^2\}\min\{1,\sigma^2\}}\big)$ (Theorem 3), quadratically better than the classical bound in the parameters $\delta$ and $(2+\tfrac{1}{b})$, and its use of an inexact quantum LP solver yields a polynomial speedup in the number of arms $m$ and resources $d$. The load-bearing reassurance, given that quantum LP solvers return only $\epsilon_{\mathrm{LP}}$-approximate solutions, is the robustness analysis of Propositions 4 and 5: below explicit error thresholds the approximation does not break the identification of $I^*$ and $J'$ and does not increase the Phase II regret.

Load-bearing premise

The proof of the problem-independent regret bound (Theorem 1) invokes, in its final step in Appendix B, the condition $m \le B/\log(dT)$ to discard a term, but neither the theorem statement nor the model assumptions in Section 2 list this condition; if the budget $B$ is small relative to the number of arms $m$, the advertised improvement over the classical bound may not follow from the proof as written.

Editorial extensions

If this is right

  • The problem-independent regret $O(\sqrt{\log(dT)}\,\mathrm{OPT}_{\mathrm{LP}}\sqrt{m/B})$ beats the classical bound whenever the budget $B$ exceeds the LP optimum $\mathrm{OPT}_{\mathrm{LP}}$, and the gap between the two bounds grows like $\sqrt{B/\mathrm{OPT}_{\mathrm{LP}}}$.
  • The problem-dependent leading term improves from $O((2+\tfrac{1}{b})^2 md\log T/(b\delta^2))$ to $\tilde{O}((2+\tfrac{1}{b}) m\sqrt{d}\log T/(b\delta))$, a quadratic gain in the parameters $\delta$ and $(2+\tfrac{1}{b})$ at the price of a $\sqrt{d}$ factor.
  • Per-round LP solving in the problem-dependent algorithm drops from roughly $\max\{m,d\}^{2.372}$ time to about $\sqrt{m+d}/\epsilon_{\mathrm{LP}}^{2.5}$, a polynomial speedup in both the number of arms and the number of resources.
  • Approximate LP solving is safe: the regret bounds hold even when every LP is solved only to $\epsilon_{\mathrm{LP}}$-optimality and $\epsilon_{\mathrm{LP}}$-feasibility, provided $\epsilon_{\mathrm{LP}}$ stays below the thresholds stated in Propositions 4 and 5.
  • The problem-independent algorithm uses at most $\tilde{O}(T)$ oracle queries in total, so the regret improvement does not come from extra sampling.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same substitution of quantum Monte Carlo for classical averaging should transfer to other online decision settings whose choice rules depend on estimated expectations, such as online linear programming, dynamic pricing, and ad allocation, because the regret gain is a direct function of the confidence-width exponent; the main barrier is the geometric refresh schedule that Q
  • Editorial inference: the robustness thresholds for $\epsilon_{\mathrm{LP}}$ give classical implementations a concrete licence to replace high-precision interior-point LP solvers with cheap approximate solvers: whenever the error stays below the stated thresholds, the regret guarantee is unchanged and the time saving is effectively free.
  • Editorial inference: the quadratic problem-dependent gain is conditional on amplitude-estimation access to both reward and cost oracles, so a hardware realization that offers only classical sampling would fall back to the classical bounds; the oracle definition is the experimentally testable precondition.
  • Editorial inference: the improvement factor $(1+\sqrt{B/\mathrm{OPT}_{\mathrm{LP}}})$ frames the paper's open lower-bound question concretely: a matching quantum lower bound of $\Omega(\mathrm{OPT}_{\mathrm{LP}}\sqrt{m/B})$ (up to log factors) would show that the problem-independent gain is tight, in direct analogy with the classical lower bound for BwK.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper initiates the study of bandits with knapsacks (BwK) in the quantum-oracle setting. It presents two primal-dual algorithms: Algorithm 1 for the problem-independent regime, claiming regret O(sqrt(log(dT)) * OPTLP * sqrt(m/B) + m log(dT) log T), and Algorithm 2 for the problem-dependent regime, claiming regret O~((2+1/b) m sqrt(d)/(b delta) log T + d^4/(b^2 min{chi^2,delta^2} min{1,sigma^2})) with a quantum LP solver. The problem-dependent analysis is detailed: Propositions 3-5 and Appendix C give a careful error-propagation and robustness framework for approximate LP solutions, and the claimed quadratic improvement in delta and (2+1/b) appears to follow from the stated arguments. The problem-independent proof, however, contains a load-bearing gap: the final simplification in Eq. (50) of Appendix B invokes an unstated assumption m <= B/log(dT) and, even under that assumption, does not dominate the dropped term. The paper also has an implementability issue in Phase II of Algorithm 2 and a scaling issue in the quantum LP time-complexity derivation. Overall, the problem-dependent contribution is promising, but the problem-independent headline result needs a corrected proof or a clearly stated additional assumption.

Significance. If both main theorems are established, the paper would be the first quantum treatment of BwK and would give a genuine quadratic improvement in problem-dependent regret parameters, together with polynomial dimension speedups in time complexity. The careful robustness analysis for approximate LP solvers in Section 4.3 and Appendix C is a substantive strength and may be of independent interest. The problem-dependent section is largely self-contained and does not rely on the flawed step in Theorem 1. However, the problem-independent improvement is the paper's headline claim, and the current proof does not justify it over the stated parameter range. The contribution is therefore conditionally significant: it should be accepted as a major revision only if the gap in the problem-independent proof is repaired, the assumptions are stated precisely, and the Phase II and LP-scaling issues are resolved.

major comments (3)
  1. [Appendix B, Eq. (50); Section 2.1; Theorem 1] The proof of Theorem 1 drops the term OPTLP * (2mC1 log T)/B from Eq. (48) by invoking 'the fact m <= B/log(dT)'. This assumption is nowhere stated in Section 2.1 or in Theorem 1, and it is not implied by the stated assumptions B_j <= T. Moreover, even if m <= B/log(dT) held, the dropped term is only O(OPTLP * log T/log(dT)), while the advertised first term is O(OPTLP) when m/B <= 1/log(dT), so the dropped term is not dominated. The simplification in Eq. (50) is therefore unjustified. A concrete instance satisfying all stated Section 2.1 assumptions is d=1, T=10^6, B=1, m=2, with both arms having deterministic reward 1 and zero resource cost; there the dropped term is about 2T log T while the claimed bound is O(T sqrt(log T)) + O(log^2 T). The problem-independent quantum improvement is the headline claim of the paper, so this gap is load-bearing.
  2. [Algorithm 2, line 27; Section C.4] The Phase II condition in line 27 of Algorithm 2 is written as ||C^L_{·,i}(t) - C_{·,i}||_infty > theta, where C_{·,i} is the unknown true expectation. The algorithm has no access to C_{·,i}; it can only maintain confidence intervals [C^L, C^U]. The analysis in Section C.4 also uses this condition directly, for example in the stage decomposition. The condition should be replaced by a test on the observable confidence-interval width, with the analysis carried out on the high-probability event that C lies in the interval. As written, the pseudocode is not executable, which affects the validity of Algorithm 2 as an algorithm rather than merely its analysis.
  3. [Appendix C.1, Eq. (54); Theorem 2] The time-complexity derivation for the quantum LP solver contains an unjustified simplification. For the LP scaled by T in Eq. (51), the dual variables satisfy 1^T eta' <= 1/b = T/B, not 1/B as stated in the text. Substituting r = 1/b into Lemma 4 introduces an extra factor (1/b)^{2.5} in the per-LP running time, so Eq. (54), and consequently Theorem 2, omit a factor that can be as large as T^{2.5} when B is small. Since Section 2.1 assumes only B in R_+ with B <= T, this factor is not hidden inside the O~ notation, and the claimed polynomial speedup in m and d is not established for small-budget instances.
minor comments (4)
  1. [Section 2.1, Assumptions] The scaling to uniform budgets says factor B_j/B with B = min_j B_j, but the correct factor is B/B_j, since otherwise resource consumptions are scaled up and may exceed the [0,1] range.
  2. [Algorithm 2, line 4] The while-loop condition '|I*| + |J'| <= d' appears to be off by one; it should be '< d' to avoid an unnecessary extra iteration when the sets already cover all d constraints.
  3. [Table 1 and Section 3] The statement that the quantum bound improves the classical bound by a factor of (1 + sqrt(B/OPTLP)) is only accurate if the second O(m log(dT) log T) term is negligible; since both bounds share this term, the factor is not a literal ratio of the full regret bounds.
  4. [Appendix A] There is a typo, 'clssical' for 'classical', and several O~ statements in Appendix C.1 should clarify which parameters are absorbed by the tilde notation.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the quantum regret improvements come from the independently established QMC confidence-interval scaling, and the self-citations are to prior published baselines rather than restatements of the paper's own conclusions.

full rationale

The main quantum improvement is not forced by definition. Theorem 1's problem-independent bound is derived by replacing classical mean estimators with quantum Monte Carlo (Lemmas 2 and 3), which independently give O~(1/N) confidence-interval width instead of O(1/sqrt(N)); the regret calculation then follows the classical [12] analysis. No parameter is fitted to make the advertised bound hold. The problem-dependent Theorem 3 similarly obtains its improvement in delta and (2+1/b) directly from QMC query complexity, while the Phase II regret bound is a robustness analysis of approximate LP solutions. The LP runtime speedup relies on the quantum LP solver of [16,31]; the latter includes an author of this paper, but it is a published external result with stated assumptions about zero-sum games, not a restatement of the BwK results, so it is real evidence rather than circularity. Similarly, [48] is a published classical BwK algorithm used as the template and cited for supporting lemmas; author overlap is not itself circular. The one genuine concern is in Appendix B, Eq. (50): after bounding the regret the paper writes 'where we apply the fact m ≤ B/log(dT) in Eq. (50).' That inequality is not stated among the Section 2.1 assumptions or in Theorem 1, and without it the OPTLP·m·log(T)/B term need not be absorbed into the advertised O(sqrt(log(dT))·OPTLP·sqrt(m/B)) term. This is a correctness/assumption gap in the problem-independent proof, not a circular reduction: the bound is not equivalent to an input by construction, and the problem-dependent theorem does not depend on this step. For these reasons the circularity score is low.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No parameters are fitted to data. Constants C1 and C2 come from the quantum mean-estimation lemmas; problem-dependent quantities delta, sigma, and chi reflect the instance, and algorithm parameters theta and epsilon are explicit choices from these quantities. The main new assumptions are the quantum oracle model, the inherited non-degeneracy assumptions, and the unstated inequality m <= B/log(dT) used in the problem-independent proof.

assumptions (5)
  • domain assumption Access to quantum oracles that prepare superpositions over the unknown reward and cost distributions (Definition 2).
    The quantum speedup is defined relative to this query model; if such oracles cannot be constructed for unknown distributions, the regret bounds do not apply to a physical setting.
  • domain assumption Assumption 1: the LP relaxation has a unique, non-degenerate optimal solution with |I*| = |J*|.
    Used throughout Section 4 to inherit Proposition 1 from [48]; the paper notes it can be enforced by an arbitrarily small perturbation.
  • domain assumption Assumption 2 in Appendix C.4: UCB/LCB contain true values and all arms are optimal, all constraints binding.
    Used in the Phase II robustness analysis; the authors say the relaxation follows from [48], and the concentration part holds with high probability.
  • ad hoc to paper m <= B/log(dT) in the proof of Theorem 1.
    This inequality is invoked after Eq. (50) to drop the term OPTLP * m log T / B, but it is not stated in the theorem or in Section 2.1.
  • domain assumption Quantum LP solver returns epsilon-LP-optimal, epsilon-LP-feasible solutions as in Definition 3, with QRAM access to coefficients.
    Used in Lemma 4 and Proposition 2; QRAM is an additional computational resource beyond the basic oracle model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities." pith.science (2026). https://pith.science/paper/5MQ7QAQK

@misc{pith2026250704438,
  author       = {Pith},
  title        = {Pith review of: Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5MQ7QAQK}},
  note         = {Machine review of arXiv:2507.04438}
}
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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

    cs.LG 2025-07 conditional novelty 6.0 of 10

    Improved classical and quantum regret bounds for reinforcement learning with a generative model, including a new expected-regret measure under which quantum algorithms achieve polylogarithmic regret for infinite-horiz...

Reference graph

Works this paper leans on

76 extracted references · 56 canonical work pages · cited by 1 Pith paper

  1. [48]

    The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks

    Xiaocheng Li, Chunlin Sun, and Yinyu Ye, The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks , International Conference on Machine Learning, pp. 6483–6492, PMLR, 2021, arXiv: 2102.06385

    work page Pith review arXiv 2021

  2. [38]

    Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang, Faster dynamic matrix inverse for faster LPs , arXiv preprint arXiv:2004.07470 (2020), arXiv: 2004.07470

    arXiv 2020

  3. [1]

    Egger, Bruce G

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas B¨ artschi, Harry Buhrman, Carleton Cof- frin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, and Christa Zoufal, Challenges and oppor- tunities in quantum optimization , Nature Reviews Physics 6...

    work page 2024

  4. [2]

    4, 876–890, arXiv: 0911.2974

    Shipra Agrawal, Zizhuo Wang, and Yinyu Ye, A dynamic near-optimal algorithm for online linear programming, Operations Research 62 (2014), no. 4, 876–890, arXiv: 0911.2974

    arXiv 2014

  5. [3]

    2005–2039, SIAM, 2025, arXiv: 2404.16349

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou, More asymmetry yields faster matrix multiplication , Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2005–2039, SIAM, 2025, arXiv: 2404.16349

    arXiv 2025

  6. [4]

    Joran van Apeldoorn and Andr´ as Gily´ en,Improvements in quantum SDP-solving with applications , Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 99:1–99:15, Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik, 2019, arXiv: 1804.05058

    work page Pith review arXiv 2019

  7. [5]

    Joran van Apeldoorn and Andr´ as Gily´ en, Quantum algorithms for zero-sum games , arXiv preprint arXiv:1904.03180 (2019), arXiv: 1904.03180

    arXiv 2019

  8. [6]

    403–414, IEEE, 2017, arXiv: 1705.01843

    Joran van Apeldoorn, Andr´ as Gily´ en, Sander Gribling, and Ronald de Wolf, Quantum SDP-solvers: Better upper and lower bounds , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 403–414, IEEE, 2017, arXiv: 1705.01843

    arXiv 2017

Show all 76 references
  1. [7]

    Joran van Apeldoorn, Andr´ as Gily´ en, Sander Gribling, and Ronald de Wolf,Convex optimization using quantum oracles, Quantum 4 (2020), 220, arXiv: 1809.00643

    2020 arXiv

  2. [8]

    Schapire, The nonstochastic multiarmed bandit problem, SIAM Journal on Computing 32 (2002), no

    Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The nonstochastic multiarmed bandit problem, SIAM Journal on Computing 32 (2002), no. 1, 48–77

    2002

  3. [9]

    Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shou- vanik Chakrabarti, and Marco Pistoia, Fast convex optimization with quantum gradient methods , arXiv preprint arXiv:2503.17356 (2025), arXiv: 2503.17356

    2025 arXiv

  4. [10]

    Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tam´ as Terlaky, and Xiaodi Wu,A quantum central path algorithm for linear optimization , arXiv preprint arXiv:2311.03977 (2023), arXiv: 2311.03977

    2023 arXiv

  5. [11]

    Zuluaga,Quantum interior point methods for semidefinite optimization , Quantum 7 (2023), 1110, arXiv: 2112.06025

    Brandon Augustino, Giacomo Nannicini, Tam´ as Terlaky, and Luis F. Zuluaga,Quantum interior point methods for semidefinite optimization , Quantum 7 (2023), 1110, arXiv: 2112.06025

    2023 arXiv

  6. [12]

    3, 1–55, arXiv: 1305.2545 15

    Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins, Bandits with knapsacks , Jour- nal of the ACM (JACM) 65 (2018), no. 3, 1–55, arXiv: 1305.2545 15

    2018 arXiv

  7. [13]

    1, 80–90

    Dimitris Bertsimas and Jos´ e Ni˜ no-Mora,Restless bandits, linear programming relaxations, and a primal- dual index heuristic , Operations Research 48 (2000), no. 1, 80–90

    2000

  8. [14]

    6, 1537–1550

    Omar Besbes and Assaf Zeevi, Blind network revenue management , Operations Research 60 (2012), no. 6, 1537–1550

    2012

  9. [15]

    Borkar and Sean P

    Vivek S. Borkar and Sean P. Meyn, Risk-sensitive optimal control for Markov decision processes with monotone cost, Mathematics of Operations Research 27 (2002), no. 1, 192–209

    2002

  10. [16]

    Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian, Quantum speedups for zero-sum games via improved dynamic Gibbs sampling , International Conference on Machine Learning, pp

    Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian, Quantum speedups for zero-sum games via improved dynamic Gibbs sampling , International Conference on Machine Learning, pp. 2932–2952, PMLR, 2023, arXiv: 2301.03763

    2023 arXiv

  11. [17]

    Boyd and Lieven Vandenberghe, Convex optimization , Cambridge University Press, 2004

    Stephen P. Boyd and Lieven Vandenberghe, Convex optimization , Cambridge University Press, 2004

    2004

  12. [18]

    Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang, Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 85...

    2021 arXiv

  13. [19]

    Fernando G. S. L. Brand˜ ao, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xi- aodi Wu, Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning , 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019...

    2019 arXiv

  14. [20]

    Brand˜ ao and Krysta Svore, Quantum speed-ups for semidefinite programming , Pro- ceedings of the 58th Annual Symposium on Foundations of Computer Science, pp

    Fernando G.S.L. Brand˜ ao and Krysta Svore, Quantum speed-ups for semidefinite programming , Pro- ceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415–426, 2017, arXiv:1609.05537

    2017 arXiv

  15. [21]

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305 (2002), 53–74, arXiv: quant-ph/0005055

    2002 arXiv

  16. [22]

    Childs, Tongyang Li, and Xiaodi Wu, Quantum algorithms and lower bounds for convex optimization , Quantum 4 (2020), 221, arXiv: 1809.01731

    Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, Quantum algorithms and lower bounds for convex optimization , Quantum 4 (2020), 221, arXiv: 1809.01731

    2020 arXiv

  17. [23]

    3, 52, arXiv: 2311.15587

    Zherui Chen, Yuchen Lu, Hao Wang, Yizhou Liu, and Tongyang Li, Quantum Langevin dynamics for optimization, Communications in Mathematical Physics 406 (2025), no. 3, 52, arXiv: 2311.15587

    2025 arXiv

  18. [24]

    Cohen, Yin Tat Lee, and Zhao Song, Solving linear programs in the current matrix multi- plication time, Journal of the ACM (JACM) 68 (2021), no

    Michael B. Cohen, Yin Tat Lee, and Zhao Song, Solving linear programs in the current matrix multi- plication time, Journal of the ACM (JACM) 68 (2021), no. 1, 1–39, arXiv: 1810.07896

    2021 arXiv

  19. [25]

    33–43, 2022, arXiv: 2111.09787

    Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi, Near-optimal quantum algorithms for multi- variate mean estimation , Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 33–43, 2022, arXiv: 2111.09787

    2022 arXiv

  20. [26]

    Zhongxiang Dai, Gregory Kang Ruey Lau, Arun Verma, Yao Shu, Bryan Kian Hsiang Low, and Patrick Jaillet, Quantum Bayesian optimization, Advances in Neural Information Processing Systems 36 (2023), 20179–20207, arXiv:2310.05373

    2023 arXiv

  21. [27]

    Dantzig and Mukund N

    George B. Dantzig and Mukund N. Thapa, The simplex method , Springer, 1997

    1997

  22. [28]

    Briegel, Machine learning & artificial intelligence in the quantum domain: a review of recent progress, Reports on Progress in Physics 81 (2018), no

    Vedran Dunjko and Hans J. Briegel, Machine learning & artificial intelligence in the quantum domain: a review of recent progress, Reports on Progress in Physics 81 (2018), no. 7, 074001

    2018

  23. [29]

    6, 1586–1602

    Kris Johnson Ferreira, David Simchi-Levi, and He Wang, Online network revenue management using thompson sampling , Operations Research 66 (2018), no. 6, 1586–1602. 16

    2018

  24. [30]

    Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55 (1997), no

    Yoav Freund and Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55 (1997), no. 1, 119–139

    1997

  25. [31]

    Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang, Logarithmic-regret quantum learn- ing algorithms for zero-sum games , Advances in Neural Information Processing Systems 36 (2024), arXiv:2304.14197

    2024 arXiv

  26. [32]

    16, 160501, arXiv: 0708.1879

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, Quantum random access memory , Physical Review Letters 100 (2008), no. 16, 160501, arXiv: 0708.1879

    2008 arXiv

  27. [33]

    John Gittins, Kevin Glazebrook, and Richard Weber, Multi-armed bandit allocation indices, John Wiley & Sons, 2011

    2011

  28. [34]

    Weiyuan Gong, Chenyi Zhang, and Tongyang Li, Robustness of quantum algorithms for non- convex optimization , The Thirteenth International Conference on Learning Representations, 2025, arXiv:2212.02548

    2025 arXiv

  29. [35]

    Grigoriadis and Leonid G

    Michael D. Grigoriadis and Leonid G. Khachiyan, A sublinear-time randomized approximation algorithm for matrix games , Operations Research Letters 18 (1995), no. 2, 53–58

    1995

  30. [36]

    Lov Grover and Terry Rudolph, Creating superpositions that correspond to efficiently integrable proba- bility distributions , arXiv preprint quant-ph/0208112 (2002), arXiv: quant-ph/0208112

    2002 arXiv

  31. [37]

    Sofiene Jerbi, Arjan Cornelissen, M¯ aris Ozols, and Vedran Dunjko,Quantum policy gradient algorithms, arXiv preprint arXiv:2212.09328 (2022), arXiv: 2212.09328

    2022 arXiv

  32. [39]

    302–311, 1984

    Narendra Karmarkar, A new polynomial-time algorithm for linear programming , Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 302–311, 1984

    1984

  33. [40]

    49–1, Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2017, arXiv: 1603.08675

    Iordanis Kerenidis and Anupam Prakash, Quantum recommendation systems , 8th Innovations in The- oretical Computer Science Conference (ITCS 2017), pp. 49–1, Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2017, arXiv: 1603.08675

    2017 arXiv

  34. [41]

    Leonid Genrikhovich Khachiyan, A polynomial algorithm in linear programming , Doklady Akademii Nauk, vol. 244, pp. 1093–1096, Russian Academy of Sciences, 1979

    1979

  35. [42]

    1186–1215, SIAM, 2023, arXiv: 2208.07544

    Robin Kothari and Ryan O’Donnell, Mean estimation when you have the source code; or, quantum Monte Carlo methods, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1186–1215, SIAM, 2023, arXiv: 2208.07544

    2023 arXiv

  36. [43]

    1029–1046, SIAM, 2018

    Francois Le Gall and Florent Urrutia, Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1029–1046, SIAM, 2018

    2018

  37. [44]

    230–249, IEEE, 2015, arXiv:1503.01752

    Yin Tat Lee and Aaron Sidford, Efficient inverse maintenance and faster algorithms for linear program- ming, 2015 IEEE 56th annual symposium on foundations of computer science, pp. 230–249, IEEE, 2015, arXiv:1503.01752

    2015 arXiv

  38. [45]

    1049–1065, IEEE, 2015, arXiv: 1508.04874

    Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong, A faster cutting plane method and its implications for combinatorial and convex optimization , 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049–1065, IEEE, 2015, arXiv: 1508.04874

    2015 arXiv

  39. [46]

    Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu, Quantum Hamiltonian descent , arXiv preprint arXiv:2303.01471 (2023), arXiv: 2303.01471

    2023 arXiv

  40. [47]

    Jiaqi Leng, Kewen Wu, Xiaodi Wu, and Yufan Zheng, (sub) exponential quantum speedup for optimiza- tion, arXiv preprint arXiv:2504.14841 (2025), arXiv: 2504.14841 17

    2025 arXiv

  41. [49]

    Su, and Tongyang Li, On quantum speedups for nonconvex optimization via quantum tunneling walks , Quantum 7 (2023), 1030, arXiv: 2209.14501

    Yizhou Liu, Weijie J. Su, and Tongyang Li, On quantum speedups for nonconvex optimization via quantum tunneling walks , Quantum 7 (2023), 1030, arXiv: 2209.14501

    2023 arXiv

  42. [50]

    6, 305–308

    Nimrod Megiddo and Ramaswamy Chandrasekaran, On the ε-perturbation method for avoiding degen- eracy, Operations Research Letters 8 (1989), no. 6, 305–308

    1989

  43. [51]

    5, 22–es

    Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani, Adwords and generalized online matching, Journal of the ACM (JACM) 54 (2007), no. 5, 22–es

    2007

  44. [52]

    Scherer, Axel Plinge, and Christo- pher Mutschler, A survey on quantum reinforcement learning , arXiv preprint arXiv:2211.03464 (2022), arXiv:2211.03464

    Nico Meyer, Christian Ufrecht, Maniraman Periyasamy, Daniel D. Scherer, Axel Plinge, and Christo- pher Mutschler, A survey on quantum reinforcement learning , arXiv preprint arXiv:2211.03464 (2022), arXiv:2211.03464

    2022 arXiv

  45. [53]

    2181, 20150301, arXiv: 1504.06987

    Ashley Montanaro, Quantum speedup of Monte Carlo methods , Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 471 (2015), no. 2181, 20150301, arXiv: 1504.06987

    2015 arXiv

  46. [54]

    2, 763–780, arXiv: 1910.10649

    Giacomo Nannicini, Fast quantum subroutines for the simplex method , Operations Research 72 (2024), no. 2, 763–780, arXiv: 1910.10649

    2024 arXiv

  47. [55]

    5, 527–535

    Herbert Robbins, Some aspects of the sequential design of experiments , Bulletin of the American Math- ematical Society 58 (1952), no. 5, 527–535

    1952

  48. [56]

    Andrzej Ruszczy´ nski,Risk-averse dynamic programming for Markov decision processes , Mathematical programming 125 (2010), 235–261

    2010

  49. [57]

    1-2, 1–286, arXiv: 1904.07272

    Aleksandrs Slivkins, Introduction to multi-armed bandits, Foundations and Trends® in Machine Learn- ing 12 (2019), no. 1-2, 1–286, arXiv: 1904.07272

    2019 arXiv

  50. [58]

    Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, and Xiaoming Sun,Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, pp. 10087–10094, 2023, arXiv: 2205.14988

    2023 arXiv

  51. [59]

    Childs, Quantum exploration algorithms for multi-armed bandits, Proceedings of the AAAI Conference on Artificial Intelligence, vol

    Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs, Quantum exploration algorithms for multi-armed bandits, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 10102– 10110, 2021, arXiv: 2007.07049

    2021 arXiv

  52. [60]

    2, 517–546

    Mengdi Wang, Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time , Mathematics of Operations Research 45 (2020), no. 2, 517–546

    2020

  53. [61]

    Richard Weber, On the Gittins index for multiarmed bandits , The Annals of Applied Probability (1992), 1024–1033

    1992

  54. [62]

    3, 737–757

    Jia Yuan Yu, Shie Mannor, and Nahum Shimkin, Markov decision processes with arbitrary reward processes, Mathematics of Operations Research 34 (2009), no. 3, 737–757

    2009

  55. [63]

    41268–41299, PMLR, 2023, arXiv:2212.03906

    Chenyi Zhang and Tongyang Li, Quantum lower bounds for finding stationary points of nonconvex func- tions, International Conference on Machine Learning, pp. 41268–41299, PMLR, 2023, arXiv:2212.03906

    2023 arXiv

  56. [64]

    Han Zhong, Jiachen Hu, Yecheng Xue, Tongyang Li, and Liwei Wang, Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret , arXiv preprint arXiv:2302.10796 (2023), arXiv:2302.10796 18 A Quantum and classical algorithms for linear prog...

    2023 arXiv

  57. [65]

    Intuitively, the duration of this stage is of order O(log T )

    In initial stage, the optimal arms have not yet been played for a sufficient number of rounds, so that the condition ∥C L ·,i(t) − C·,i∥∞ > θholds. Intuitively, the duration of this stage is of order O(log T )

  58. [66]

    This improved estimation ensures that the condition ∥C L ·,i(t) − C·,i∥∞ ≤ θ continues to hold, thereby guaranteeing the stability of the smallest singular value of C L(t)

    After initial stage, each optimal arm has been sampled sufficiently often, which facilitates an accurate estimation of the resource consumption matrix C. This improved estimation ensures that the condition ∥C L ·,i(t) − C·,i∥∞ ≤ θ continues to hold, thereby guaranteeing the st...

  59. [67]

    This stage occurs with a small probability and is expected to last only O(1) rounds

    The final stage occurs when the average remaining resource deviates from the target interval, i.e., when B(t) I∗ T −t ̸∈ [b−ϵ, b+ϵ]. This stage occurs with a small probability and is expected to last only O(1) rounds. Since all optimal arms have been identified in Phase I, the...

  60. [68]

    rU (t) ≥ r, C L(t) ≤ C hold element-wise for all t ∈ [T ]

  61. [69]

    Based on Lemma 1, the first part of Assumption 2 is satisfied with high probability

    all arms are optimal and all the constraints are binding, i.e., I ∗ = [m], J ∗ = [d]. Based on Lemma 1, the first part of Assumption 2 is satisfied with high probability. Note that in this phase, our Algorithm 2 employs the quantum oracle as a classical oracle, and uses the cl...

  62. [70]

    In this case, we upper bound the gap between the expected resource consumption and the average remaining resource as shown in (98)

    t ≥ αT 19 . In this case, we upper bound the gap between the expected resource consumption and the average remaining resource as shown in (98). From the definition of ϵt, we have ∥E C·,it+1 (b(t))|Ht − b(t)∥∞ ≤ ϵt, which implies that the event Et is contained in the complement...

  63. [71]

    Since the resource consumption matrix is element-wise bounded in [0 , 1], we have 0 ≤ E C·,it+1 (b(t))|Ht ≤ 1

    t < αT 19 . Since the resource consumption matrix is element-wise bounded in [0 , 1], we have 0 ≤ E C·,it+1 (b(t))|Ht ≤ 1. In addition, 0 ≤ b(t) ≤ 6 5 . As a result, ∥E C·,it+1 (b(t))|Ht − b(t)∥∞ ≤ 6 5 = ϵt. Since the event Et requires ∥E C·,it+1 (b(t))|Ht − b(t)∥∞ to be great...

  64. [72]

    ˜b(s) j ∈ [b − ϵ, b+ ϵ], for s < τ′ j,

  65. [73]

    ˜b(s) j ≡ ˜b (τ ′ j ) j ̸∈ [b − ϵ, b+ ϵ], for τ ′ j ≤ s ≤ t,

  66. [74]

    ˜b(s) k ∈ [b − ϵ, b+ ϵ] for s ≤ τ ′ j and k ∈ [d], k̸= j. Then from the definition of ˜b(s) j and b(s) j , the increment ∆ s = ˜b(s) j − ˜b(s−1) j is given by ∆s = ˜b(s) j − ˜b(s−1) j = ( 0, s > τ ′ j, − 1 T −s (Cj,s − ˜b(s−1) j ), s ≤ τ ′ j. (107) With ˜b(0) j = b, we obtain ...

  67. [75]

    Since {˜b(s) j ∈ [b − ϵ, b+ ϵ], for s < τ′ j} and τ ′ k ≥ τ ′ j for k ∈ [j] and k ̸= j , we have E[∆s|Hs−1] ≤ ϵs T −s , for s ≤ τ ′ j

  68. [76]

    For the first summation in (108), it is bound by sX k=1 E[∆k|Hk−1] ≤ TX k=1 |E[∆k|Hk−1]| = αTX k=1 ¯ϵ T − k + T −1X k=αT +1 ϵk T − k ≤ α¯ϵ 1 − α + T −1X k=αT +1 ϵk T − k

    Since {˜b(s) j ≡ ˜b(s−1) j , for s > τ′ j}, it follows that E[∆s|Hs−1] ≡ 0 for s > τ′ j. For the first summation in (108), it is bound by sX k=1 E[∆k|Hk−1] ≤ TX k=1 |E[∆k|Hk−1]| = αTX k=1 ¯ϵ T − k + T −1X k=αT +1 ϵk T − k ≤ α¯ϵ 1 − α + T −1X k=αT +1 ϵk T − k . (109) Consequent...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.