Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms Maoli Liu1 , Zhuohua Li2 , and John C.S. Lui1 1

The Chinese University of Hong Kong 2 Xidian University

arXiv:2608.14319v1 [cs.LG] 14 Aug 2026

Abstract We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB) in the model of Wan et al. [2023], where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon T with regret O(K log T ) for QMAB with K arms and O(d2 polylog T ) for d-dimensional QLB. This leaves open whether the K log T scale is unavoidable and whether the d2 dependence can be improved. We prove the first minimax lower bounds of Ω(K log(T /K)) for QMAB and Ω(d log(T /d)) for finite-action QLB, resolving the question raised by Wan et al. [2023] of whether regret independent of T is achievable. At the heart of our argument is a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives, proved by the polynomial method and a Remez-type inequality for trigonometric polynomials. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. Complementing the lower bounds, we give a designbased elimination algorithm for finite-action QLB. When the action set has size poly(d), its regret is linear in d, improving the prior d2 dependence and matching our lower bound up to polylogarithmic factors. The algorithm couples a low-bias low-variance quantum mean estimator with a small-support G-optimal design through a query allocation matched to the design weights. The design-based elimination reduces the dimension dependence from d2 to d3/2 when using Quantum Monte Carlo estimates. The low-variance estimator then makes reconstruction error √ aggregate through variance rather than worst-case absolute error, removing the remaining d factor.

1

Introduction

In the stochastic multi-armed bandit (MAB) problem [Robbins, 1952, Lattimore and Szepesvári, 2020], a learner is given K arms, each associated with an unknown reward distribution of mean µ(i) ∈ [0, 1]. In each round t ∈ [T ], the learner selects an arm and observes P a reward sampled from its distribution. The goal is to minimize the cumulative regret R(T ) := Tt=1 (µ⋆ − µ(at )), where µ⋆ is the largest mean. In the stochastic linear bandit problem, actions (also called arms) are vectors x ∈ A ⊆ Rd√ , and the mean reward of x is x⊤ θ for an unknown parameter θ ∈ Rd . √ The minimax e regret is Θ( KT ) for MAB [Auer et al., 2002, Audibert and Bubeck, 2009] and Θ(d T ) for linear bandits with general action sets [Dani et al., 2008, Abbasi-Yadkori et al., 2011]. For linear bandits √ e dT log K) [Lattimore and Szepesvári, 2020]. with K actions, classical algorithms admit regret O( Classically, log T -type regret appears only as an instance-dependent guarantee: for a fixed instance with constant gaps, the optimal regret scales as Θ(log T ) [Lai and Robbins, 1985]. 1

Wan et al. [2023] introduced the quantum bandit model we study, in which each arm is equipped with a quantum reward oracle, a unitary that encodes its reward distribution. In each round, the learner selects an arm and applies the corresponding oracle or its inverse at most once, instead of observing a classical sample. With such oracle access, quantum mean estimation methods such as Quantum Monte Carlo (QMC) estimate a mean to accuracy ϵ using O(1/ϵ) oracle queries [Montanaro, 2015], rather than the classical Θ(1/ϵ2 ) samples. Building on this speedup, Wan et al. [2023] obtained regret O(K log T ) for quantum multi-armed bandits under bounded rewards. For quantum linear bandits, their QLinUCB algorithm applies to general action sets and gives an explicit O(d2 polylog T ) regret bound. These upper bounds leave two questions open. The first is whether the logarithmic dependence on T is intrinsic: Wan et al. [2023] explicitly asked whether T -independent regret is achievable or whether a quantum lower bound rules it out. The second concerns the dimension dependence for finite action sets. The O(d2 polylog T ) guarantee applies to finite action sets only through their general-action analysis, and the finite-action regime, a central setting in classical linear bandits, has not been examined in its own right. We answer both questions. For quantum multi-armed bandits, we prove an Ω(K log(T /K)) regret lower bound, nearly matching the O(K log T ) upper bound of Wan et al. [2023] and ruling out T -independent regret. For finite-action quantum linear bandits, we prove an Ω(d log(T /d)) lower bound with only d actions. Complementing it, we give LV-G-Elim, an algorithm whose regret is nearly linear in d under bounded rewards when K = poly(d). The lower bounds rest on a reduction from bandit regret to a point-versus-interval testing problem, which is then lower bounded by the polynomial method together with a Remez-type inequality for trigonometric polynomials. The upper bound couples a small-support G-optimal design with a low-bias low-variance quantum mean estimator through a query allocation matched to the design weights. We state the results next and then give a technical overview.

1.1

Our Results

Our first result resolves the question of Wan et al. [2023] by showing that worst-case regret must grow logarithmically with T . Theorem 1 (QMAB minimax lower bound; informal version of Theorem 8). For every K ⩾ 2 and T ≳ K, any quantum multi-armed bandit policy π over T rounds suffers expected regret Ω(K log(T /K)) on some K-armed bandit instance. The same hard instances, realized as a linear bandit with only d actions, yield our finite-action QLB lower bound. Theorem 2 (Finite-action QLB lower bound; informal version of Theorem 13). For every d ⩾ 2 and T ≳ d, there is an action set A ⊆ Rd with |A| = d such that any quantum linear bandit policy π over T rounds suffers expected regret Ω(d log(T /d)) on some instance with action set A. Our algorithm LV-G-Elim nearly matches the linear bandit lower bound when K = poly(d). Theorem 3 (Regret of LV-G-Elim; informal version of Theorem 18). For finite-action quantum
linear bandits with K actions, LV-G-Elim has expected regret O d log(KT ) · polylog(d, T ) . Table 1 compares our bounds with classical and prior quantum bounds. For MAB, the upper bound is due to Audibert and Bubeck [2009] and the lower bound is from Auer et al. [2002]. For linear bandits with general action sets, the upper bound is due to Abbasi-Yadkori et al. [2011] and 2

Table 1: Regret bounds for multi-armed bandits and linear bandits. Bound Classical

UB LB

Quantum

UB [Wan et al., 2023] UB (This paper) LB (This paper)

MAB √ O(√ KT ) Ω( KT )

Linear, general A √ O(d T√log T ) Ω(d T )

Linear, finite A √ O( dT √ log K) Ω( dT )

O(K log T ) — Ω(K log(T /K))

O(d2 polylog T ) — Ω(d log(T /d))

O(d2 polylog T ) O(d log T log(KT )) ‡ Ω(d log(T /d))

The quantum bounds are for the model with quantum reward oracles (Section 2), under the bounded-reward assumption. Wan et al. [2023] also give bounds under a bounded-variance assumption. UB and LB denote upper and lower bounds. ‡ Up to log(dT ) log log(dT ) factors.

the lower bound is from Dani et al. [2008]. For finite-action linear bandits, the upper bound is from Lattimore and Szepesvári [2020, Chapter 22], while the lower bound follows from the standard embedding of d-armed bandits. Our QLB lower bound is proved with Bernoulli rewards and a finite action set with K = d actions, and hence also applies to general action sets (see Remark 14). For finite action sets with K = poly(d), our upper and lower bounds nearly match, while for general action sets the optimal dimension dependence remains open.

1.2

Technical Overview

Lower bounds. Neither of the two standard classical lower bound mechanisms directly yields our quantum lower bounds. Instead, as we explain below, the hardness comes from testing against an interval of alternatives rather than a fixed point. Classical minimax lower bounds rest on a twopoint change-of-measure argument: two reward distributions whose means differ by ϵ can have KL 2) divergence of order ϵ2 , so distinguishing them even with constant error probability requires Ω(1/ϵ √ samples. Balancing this testing cost with the regret incurred by a gap ϵ yields the familiar Ω( KT ) rate. However, quantum mean estimation distinguishes two such distributions using only O(1/ϵ) queries, weakening this mechanism. The second classical mechanism comes from instance-dependent lower bounds, such as the Lai–Robbins bound [Lai and Robbins, 1985]. These bounds operate in a high-confidence regime: driving the probability of confusing a suboptimal arm with the optimal one down to δ gives the sample cost a log(1/δ) factor. Taking δ of order 1/T produces the classical log T term. In the quantum model, this source of difficulty is absent for two-point comparisons: for a fixed pair of distinct oracle unitaries, the cost of distinguishing them is bounded by a quantity determined by the pair, with no log(1/δ) growth. Our regret lower bounds, however, require exactly this log(1/δ) growth, so it must be recovered from a source other than two-point comparisons. This is what the interval of alternatives provides. The hard instances realize this interval through a needle-in-a-haystack structure: one reference arm has a mean above the common baseline mean shared by the candidate arms. In each alternative instance, one of these candidate arms has its mean elevated to an unknown value in an interval separated from this baseline mean. For this family, low regret under the baseline instance limits how often the policy can select the candidate arms, while low regret on the alternatives requires it to rule out that any of them is elevated. This converts regret minimization into single-arm tests that distinguish, with error probability δ, a baseline mean from an interval of elevated means. The interval is essential because a single fixed alternative would not produce the required log(1/δ) growth. For a q-query quantum test, the probability of declaring the mean to be the baseline value is a trigonometric polynomial of degree O(q) in the amplitude parameter. A Remez-type inequality 3

shows that if such a polynomial is at least a constant at the baseline while remaining uniformly at most δ on an interval separated from it, then its degree is Ω(log(1/δ)). Combined with the degree bound O(q), this forces q = Ω(log(1/δ)). A truncation argument extends this fixed-query lower bound to expected query counts, since a bandit policy spends a random number of queries on each arm. The bandit reduction turns a policy with worst-case regret MT into such tests with error probabilities O(MT /T ). Plugging the testing lower bound into the reduction gives Ω(K log(T /K)) for QMAB, and realizing the same hard family as a d-action linear bandit gives Ω(d log(T /d)) for finite-action QLB. Thus, in the quantum model, logarithmic regret becomes the worst-case scale, and constant-gap instances already yield the lower bound. Upper bound. The prior upper bound for quantum linear bandits is given by the QLinUCB algorithm of Wan et al. [2023], which applies to general action sets and therefore also to the finite action sets considered here. It is a quantum analogue of the OFUL (Optimism in the Face of Uncertainty for Linear bandits) confidence-ellipsoid approach [Abbasi-Yadkori et al., 2011]. Its stage analysis sums confidence-radius terms over O(d log T ) stages and yields an O(d2 polylog T ) regret bound. Our approach instead uses phased elimination with G-optimal exploration [Lattimore and Szepesvári, 2020], a scheme specific to finite action sets. In each phase, a design selects support actions to query, and the resulting estimates are extrapolated to all active actions with error amplification controlled by the design. The quantum setting changes this accounting in two places. First, the support size moves from an additive overhead to a leading term in the regret bound. In the classical analysis, estimating to accuracy ϵ costs ϵ−2 samples in the leading term, so the support size appears only as an additive rounding overhead. By contrast, quantum mean estimation has leading cost ϵ−1 , and each support action requires its own estimator call with a constant minimum number of queries. Since each query in a phase incurs regret proportional to the phase accuracy, the support size enters the leading term of the regret bound. We therefore use a small-support approximate G-optimal design with support size O(r), where r is the dimension of the span of the active set. Second, the choice of estimator determines how errors aggregate when the support estimates are extrapolated. A direct high-probability estimator such as QMC controls worst-case absolute errors √ on the support, and extrapolation through the design can amplify such errors by a factor of r. Thus √ achieving phase accuracy ϵ requires support accuracy ρ ≍ ϵ/ r, and the regret becomes of order d3/2 . Our algorithm instead uses the low-bias low-variance estimator of Cornelissen and Hamoudi [2023]: with a query allocation matched to the design weights, independent fluctuations aggregate through √ variance, and the r loss disappears. Amplifying the resulting constant-probability estimates by medians over the active set costs a log K factor. When K = poly(d), the regret is nearly linear in d, matching the lower bound up to polylogarithmic factors.

1.3

Related Work

Quantum bandits. The quantum bandit model we study was introduced by Wan et al. [2023], who obtained regret O(K log T ) for multi-armed bandits and O(d2 polylog T ) for linear bandits under bounded rewards, with counterparts under a bounded-variance assumption that carry additional logarithmic factors. Dai et al. [2023] extended the model to kernelized rewards, but their analysis relies on a sub-Gaussianity assumption on the QMC error that, as Hikima et al. [2024] point out, is not guaranteed by the QMC method. Hikima et al. [2024] give an algorithm for quantum kernelized bandits whose analysis avoids this assumption. Although they do not state a separate linear bandit result, specializing their confidence bound and determinant-based stage-count argument to the linear kernel yields regret O(d3/2 polylog T ) for general action sets (see Appendix B). In the same oracle 4

model, Wang et al. [2025] study best arm identification, and further consider oracles that address up √ to m arms in superposition, gaining an additional m factor with matching query lower bounds. The model has also been extended to heavy-tailed rewards [Wu et al., 2023], Lipschitz bandits [Yi et al., 2026], and bandits with knapsacks [Su et al., 2025]. These works do not establish minimax regret lower bounds in this model. A parallel line of work studies best arm identification with coherent access to the arms [Casalé et al., 2020, Wang et al., 2021]. In this stronger model, Wang et al. [2021] obtain a quadratic speedup with a matching query lower bound. At the other end, Buchholz et al. [2025] show that when the reward randomness cannot be accessed coherently, the quantum advantage disappears entirely. Both the achievable speedup and the ultimate limits thus depend on the access model, and our lower bounds characterize these limits for the model of Wan et al. [2023]. In a different direction, Lumbreras et al. [2022] √ study bandits whose arms are observables applied to an unknown quantum state and prove Ω( T ) regret lower bounds, which do not transfer to our setting since the model and the source of randomness differ. Relatedly, Lumbreras and Tomamichel [2024] show that classical linear bandits with noise vanishing near the optimal action admit polylog (T ) minimax regret, with applications to learning pure quantum states [Lumbreras et al., 2026]. This gives a route to logarithmic regret different from the query speedups studied in this paper. Classical linear bandits √ and experimental design. For general action sets, confidence-ellipsoid e algorithms achieve O(d T ) regret [Dani et al., 2008, Abbasi-Yadkori et al., 2011]. For finite action √ sets, phased elimination with G-optimal design achieves O( dT log K) regret [Lattimore et al., 2020, Lattimore and Szepesvári, 2020]. Our algorithm follows this finite-action scheme, with the sampling step replaced by quantum estimation, which in turn constrains the design. For the design itself, the Kiefer–Wolfowitz theorem [Kiefer and Wolfowitz, 1960] guarantees a G-optimal design, Lattimore et al. [2020] obtain one with support size O(d log log d), and we use the rounding method of Allen-Zhu et al. [2021] to obtain support O(r) on an action set of rank r. In the classical setting, small support is mainly a computational convenience. By contrast, it is essential in our quantum algorithm, since the query allocation must place a minimum number of queries on every support point. For contextual linear √ bandits with action sets that may change over time, SupLinUCB [Chu e dT log K) regret. In this setting, Li et al. [2019] prove a lower bound of et al., 2011] attains O( p order Ω( dT log(T /d) log K). Their upper bound matches it up to iterated logarithmic factors and the replacement of log(T /d) by log T . Design-based allocation also plays a central role in linear pure exploration [Soare et al., 2014, Fiez et al., 2019]. Quantum query lower bounds. Quantum query lower bounds often proceed by representing acceptance probabilities as low-degree polynomials [Beals et al., 2001]. Closest to our fixed-query testing lemma is Mande and de Wolf [2026], who prove an Ω(log(1/δ))-query lower bound for achieving error probability δ in phase estimation. Their proof likewise represents acceptance probabilities as trigonometric polynomials. In their problem, the alternatives cover all phases outside a small window, so a growth inequality on large sets [Borwein and Erdelyi, 1995, Theorem 5.1.2] suffices. Our alternatives instead form a short interval, and this requires a Remez-type inequality on small sets [Ganzburg, 2012]. Moreover, a bandit policy spends a random number of queries on each arm, so the fixed-query bound must be extended to expected query counts, which we obtain by truncation. Finally, the reduction from bandit regret to point-versus-interval testing has no analogue in phase estimation, and is what turns the testing lower bound into a regret lower bound.

5

2

Preliminaries

Notation. For a positive integer n, let [n] := {1, . . . , n}. We use ∥ · ∥2 for the Euclidean norm, e1 , . . . , ed for the standard basis of Rd , and span(X ) for the linear span of a set X . For a matrix M , Range(M ) denotes its range and M + its Moore–Penrose pseudoinverse. All logarithms are natural unless the base is written explicitly. In informal statements, a ≳ b means a ⩾ Cb for a universal constant C > 0. Quantum reward oracles. Let Ω be a finite sample space equipped with a probability measure P , and let y : Ω → [0, 1] be a random variable representing the reward, with mean µ := Eω∼P [y(ω)]. The quantum reward oracle associated with (P, y) is a unitary O acting as Xp O : |0⟩ 7→ P (ω) |ω⟩|y(ω)⟩, (1) ω∈Ω

where |0⟩ denotes the all-zero state of both registers, an outcome register for ω and a reward register for y(ω). Measuring the reward register of the output state O|0⟩ in the computational basis yields a classical sample of y, so the oracle O generalizes classical reward feedback. Quantum multi-armed bandits. A quantum multi-armed bandit (QMAB) instance ν consists of K arms. Each arm i ∈ [K] is associated with an unknown reward distribution (Pi , yi ), where Pi is a probability measure on a finite sample space Ωi and yi : Ωi → [0, 1] is the reward. The mean reward of arm i is denoted by µ(i). In the quantum bandit model of Wan et al. [2023], access to each arm i is only through a quantum reward oracle Oi of the form (1) that encodes (Pi , yi ). The learner interacts with the instance over a horizon of T rounds, maintaining a quantum circuit throughout. In each round t ∈ [T ], the learner selects an arm at ∈ [K] and applies either Oat or Oa† t at most once. Between consecutive rounds, the learner may place arbitrary unitaries that do not depend on the unknown reward distributions, and it may perform measurements at any round. We call the learner’s strategy a policy, denoted π. Let i⋆ ∈ arg maxi∈[K] µ(i) be an optimal arm, and let ∆i := µ(i⋆ ) − µ(i) be the reward gap of arm i. The learner’s objective is to minimize the cumulative regret, the total gap from always selecting an optimal arm: T X
R(T ) := µ(i⋆ ) − µ(at ) . t=1

For a policy π and an instance ν, we write RTπ (ν) := Eν [R(T )] for the expected regret, and use Prν and Eν for probabilities and expectations when π runs on ν. Quantum linear bandits. A quantum linear bandit (QLB) instance consists of a known action set A ⊆ Rd and an unknown parameter θ ∈ Rd . The mean reward of an action x ∈ A is µ(x) := x⊤ θ. We assume ∥x∥2 ⩽ 1 for all x ∈ A, ∥θ∥2 ⩽ 1, and µ(x) ∈ [0, 1] for all x ∈ A. As in the QMAB model, each action x ∈ A is accessed through a quantum reward oracle Ox of the form (1) whose reward mean is µ(x). In this paper, we focus on finite action sets and write K := |A| for the number of actions. The interaction protocol is the same as in the multi-armed case, with arms replaced by actions. The cumulative regret is defined in the same way, with i⋆ replaced by an optimal action x⋆ ∈ arg maxx∈A µ(x). For a policy π, we write RTπ (θ) for the expected regret on the instance determined by the parameter θ. 6

Quantum mean estimation. Our algorithms estimate the mean rewards of actions with two quantum subroutines. The first is the standard Quantum Monte Carlo (QMC) estimator, which guarantees a small error with high probability and underlies the algorithms of Wan et al. [2023]. The second is the nondestructive unbiased amplitude estimator of Cornelissen and Hamoudi [2023], which controls the bias and the variance. We restate their guarantee below and specialize it to reward oracles of the form (1). Lemma 4 (Quantum Monte Carlo [Montanaro, 2015, Theorem 2.3]). There exists a constant C1 > 1 and a quantum algorithm QMC(O, ϵ, δ) such that, for any ϵ ∈ (0, 1] and δ ∈ (0, 1), the algorithm outputs an estimate µ b of µ satisfying Pr |b µ − µ| > ϵ ⩽ δ. It uses at most Cϵ1 log 1δ queries to O and O† . Lemma 5 (Nondestructive unbiased amplitude estimation [Cornelissen and Hamoudi, 2023, Theorem 2.4]). Let |ψ⟩ be a quantum state and let Π be a projection operator with p = ∥Π|ψ⟩∥2 . Given t ⩾ 4 and ε ∈ (0, 1), the algorithm NdUb-Amplitude(|ψ⟩, Π, t, ε) outputs an estimate pe ∈ [−2π, 2π] such that 91 p E[e p] − p ⩽ ε, Var(e p) ⩽ 2 + ε. t The algorithm needs one copy of |ψ⟩, which is restored at the end of the computation with probability at least 1 − ε, and O(t log log(t) log(t/ε)) applications in expectation of the reflection operators I − 2|ψ⟩⟨ψ| and I − 2Π.1 Specializing this estimator to reward oracles yields the following mean estimator, which is the form we use. Lemma 6 (Low-bias low-variance quantum mean estimation; from Cornelissen and Hamoudi, 2023, Theorem 2.4). There exist constants CQ , CV > 0 and a quantum algorithm LVQME(O, t, ζ) such that, for any t ⩾ 4 and ζ ∈ (0, 1), the algorithm outputs an estimate µ b of µ satisfying E[b µ] − µ ⩽ ζ,

Var(b µ) ⩽

CV + ζ. t2

Its expected number of queries to O and O† is at most CQ t log log(t) log ζt .2 Proof. We obtain the lemma by specializing Lemma 5. Add one ancilla qubit, and let W be the
√ √ unitary that rotates the ancilla according to the reward value, W : |y⟩|0⟩ 7→ |y⟩ 1 − y |0⟩ + y |1⟩ for y ∈ [0, 1], extended arbitrarily to a full unitary. Set V := W (O ⊗ I), and let |ψ⟩ := V |0⟩, where |0⟩ denotes the all-zero initial state including the ancilla. Let Π := I ⊗ |1⟩⟨1| be the projection onto P the ancilla state |1⟩. Then ∥Π|ψ⟩∥2 = ω∈Ω P (ω) y(ω) = µ, so Lemma 5 applied to (|ψ⟩, Π) directly yields an estimate of µ. The algorithm LVQME(O, t, ζ) prepares |ψ⟩, runs NdUb-Amplitude(|ψ⟩, Π, t, ζ), and returns its output as µ b. Since t ⩾ 4 and ζ ∈ (0, 1), Lemma 5 gives |E[b µ] − µ| ⩽ ζ and Var(b µ) ⩽ 91µ/t2 + ζ ⩽ 2 91/t + ζ, using µ ⩽ 1, so the variance bound holds with CV := 91. Note that although the estimate µ b may lie outside [0, 1], the analysis in Section 4 uses only its bias and variance guarantees. 1

In the construction underlying Cornelissen and Hamoudi [2023, Theorem 2.4], the reflection primitives are applied also in controlled form (see their Lemmas A.1, A.5, and B.1), and such applications are included in the reflection count of Theorem 2.4. The amplification and conversion unitaries there are implemented from the same reflection primitives (their Lemmas A.3–A.4). 2 Only the expectation of the query count is bounded. The design estimation procedure in Section 4 therefore enforces a deterministic query threshold.

7

It remains to count oracle queries. Preparing |ψ⟩ uses one query to O. Write Rψ := I − 2|ψ⟩⟨ψ|, RΠ := I − 2Π, and R0 := I − 2|0⟩⟨0|. Since |ψ⟩ = V |0⟩, the identity Rψ = V R0 V † implements Rψ using one query each to O and O† , while RΠ = I ⊗ (I − 2|1⟩⟨1|) is independent of the oracle. The same accounting applies to controlled reflections. For any unitary D that is independent of the oracle and any number j of control qubits, cj -(V DV † ) = (I ⊗ V )(cj -D)(I ⊗ V † ), as can be verified on the control subspaces. Taking D = R0 shows that every controlled application of Rψ uses one ordinary query each to O and O† , whereas controlled applications of RΠ use no oracle queries. Controlled products can be implemented factorwise, and the controlled global phase in the Grover operator −Rψ RΠ does not depend on the oracle. Hence every reflection counted in Lemma 5, controlled or not, uses at most one query each to O and O† , and the stated expected query bound follows after absorbing constants into CQ . Remark 7 (Controlled oracle access is not needed). Controlled versions of O and O† are in general not available from black-box access to an unknown unitary, and our model does not grant them. The proof of Lemma 6 shows that they are not needed, and the same accounting covers the controlled powers of the Grover operator in the QMC estimator of Lemma 4, which explains why QMC-based algorithms, including those of Wan et al. [2023], run in this model. Our lower bounds in Section 3 allow tests with controlled queries, and therefore hold a fortiori for policies in our model.

3

Lower Bounds

We prove the quantum bandit lower bounds in this section. We first establish a minimax lower bound for quantum multi-armed bandits and then adapt the same hard-instance construction to finite-action quantum linear bandits. For the lower bounds, it suffices to work with canonical Bernoulli reward oracles. For p ∈ [0, 1], let Op denote the canonical Bernoulli oracle, whose full unitary action is specified in Section 3.2. In particular, it acts on the all-zero state as p √ Op |0⟩ = 1 − p |0⟩|0⟩ + p |1⟩|1⟩, and is a specialization of (1). Let BK denote the class of K-armed bandit instances with mean function µ : [K] → [0, 1] in which every arm uses a canonical Bernoulli oracle, meaning that Oi = Oµ(i) for every i ∈ [K]. We first prove the following minimax lower bound over BK . Theorem 8 (QMAB minimax lower bound). There exist universal constants c, C > 0 such that for every K ⩾ 2 and T ⩾ CK, for any quantum multi-armed bandit policy π over T rounds, there exists an instance ν ∈ BK such that T RTπ (ν) ⩾ cK log . K

3.1

Hard Instances and Proof Overview

We construct a family of hard instances inside BK . The baseline instance ν 0 has mean 1/2 on arm 1 and mean 5/12 on every arm i ⩾ 2. For each i ∈ {2, . . . , K} and q ∈ [7/12, 2/3], let ν i,q be the instance in which arm i has mean q, arm 1 has mean 1/2, and every arm j ∈ / {1, i} has mean 5/12. The set of alternatives for arm i is Ui = {ν i,q : q ∈ [7/12, 2/3]}. Therefore, arm 1 is uniquely optimal in ν 0 , and every suboptimal arm i ⩾ 2 has gap 1/12 under ν 0 . In every instance of Ui , arm i is uniquely optimal, denote the hard family by S and every suboptimal arm has gap at least 1/12. We π (ν) for its worst-case regret UK = {ν 0 } ∪ K U , and for a policy π, we write M = sup R T ν∈UK T i=2 i over the hard family. 8

Proof overview. The proof turns regret minimization on UK into a collection of single-arm quantum testing problems. Under the baseline instance ν 0 , every round selecting a suboptimal arm i ⩾ 2 incurs constant regret. By contrast, under the alternative instances in Ui , arm i is optimal and every round selecting another arm incurs constant regret. A low-regret policy must therefore determine, for each arm i ⩾ 2, whether its mean is the baseline value 5/12 or lies in the interval [7/12, 2/3]. It is essential that the alternatives form an interval rather than a single point. For quantum queries, two fixed unitary oracles can be distinguished without paying a log(1/δ) query cost to reach error probability δ. Indeed, a constant number of coherent queries suffices to distinguish O5/12 and O7/12 perfectly [Acin, 2001, Duan et al., 2007]. As we show below, the logarithmic dependence on the error probability δ reappears when the same test must succeed for every mean in the alternative interval [7/12, 2/3]. This is why the hard family uses a point-versus-interval testing problem rather than a point-versus-point one. The main technical step is the following single-arm quantum testing lower bound. Consider a canonical Bernoulli oracle Op with unknown mean p. We prove that any quantum test that queries Op or its inverse and distinguishes the case p = 5/12 from the alternatives p ∈ [7/12, 2/3], with both error probabilities at most δ, must make Ω(log(1/δ)) queries in expectation when p = 5/12. We first prove the lower bound for fixed-query tests, which make at most q queries. Parameterizing p = sin2 θ, the acceptance probability of such a test is a trigonometric polynomial in θ of degree O(q). A Remez-type inequality shows that a trigonometric polynomial cannot be bounded away from zero at one angle while being uniformly at most δ on an interval of angles unless its degree is Ω(log(1/δ)). A truncation argument then turns the fixed-query lower bound into the expected-query bound needed for the bandit reduction. The bandit reduction turns a policy with worst-case regret MT into a family of single-arm tests, one for each arm i ⩾ 2. The test for arm i decides according to whether arm i is selected in more than T /2 rounds. Declaring the wrong side means that at least half of the rounds are spent on suboptimal arms, which incurs Ω(T ) regret, while the expected regret is at most MT . Thus each test has both error probabilities O(MT /T ). The testing lower bound, applied with δ = O(MT /T ), shows that the test makes Ω(log(T /MT )) queries in expectation under ν 0 . Since the test queries the unknown oracle only in rounds selecting arm i, and at most once in each such round, this implies Eν 0 [Ni (T )] = Ω(log(T /MT )), where Ni (T ) denotes the number of rounds selecting arm i. Since each such round incurs constant regret under ν 0 , summing over i = 2, . . . , K gives MT ≳ K log(T /MT ), and solving this implicit inequality yields MT = Ω(K log(T /K)). The next subsections make this argument formal. Section 3.2 proves the single-arm quantum testing lower bound. Section 3.3 gives the bandit-to-testing reduction. Section 3.4 combines the two to complete the proof of Theorem 8. Finally, Section 3.5 establishes a lower bound for finite-action quantum linear bandits.

3.2

A Single-Arm Quantum Testing Lower Bound

We now prove the single-arm quantum testing lower bound discussed in the proof overview. Consider a canonical Bernoulli oracle Op with unknown mean p ∈ [0, 1]. A single-arm quantum test starts from a fixed initial state and interleaves queries to Op , Op† , or their controlled versions with other quantum operations that do not depend on p. It may perform intermediate measurements and choose later operations adaptively, but the only p-dependent operations are the oracle queries. The test must decide whether the unknown mean is the baseline value or belongs to the alternative interval. We write this testing problem as   5 7 2 H0 : p = , H1 : p ∈ , . 12 12 3 9

The output baseline corresponds to H0 , and the output alternative corresponds to H1 . We also write Prp and Ep for probabilities and expectations when the oracle is Op . The proof has two steps. First, we prove the lower bound for tests with a fixed query budget. Then a truncation argument converts it to the expected-query lower bound needed for the bandit reduction in Section 3.3. The fixed-query step is a degree argument. The polynomial representation follows the polynomial method of Beals et al. [2001]. In the Boolean oracle setting, query lower bounds come from approximate-degree lower bounds for Boolean functions. By contrast, the oracle in our setting is a unitary depending on a continuous parameter, so the degree lower bound comes from the following Remez-type inequality for trigonometric polynomials. Lemma 9 (Remez-type inequality; Ganzburg, 2012, Theorem 1). Let J ⊆ R be an interval of length λ ∈ (0, 2π). Every real trigonometric polynomial G of degree at most m satisfies sup |G(θ)| ⩽ Cλm sup |G(θ)|, θ∈R

where

Cλ =

θ∈J



2 sin(λ/4)

2

.

Proof. By Ganzburg [2012, Theorem 1], applied with m ⩾ 1, every real trigonometric polynomial Q
2m of degree at most m satisfies ∥Q∥C((−π,π]) ⩽ 21 2/sin(λ/4) ∥Q∥C(E) for every measurable set E ⊆ e (−π, π] of Lebesgue measure at least λ ∈ (0, 2π]. Let t0 be the center of J and set G(θ) := G(θ + t0 ), a real trigonometric polynomial of the same degree. Since λ < 2π, the interval J − t0 = [−λ/2, λ/2] e with E = [−λ/2, λ/2], and using the 2πis contained in (−π, π]. Applying the inequality above to G 1 e periodicity of G together with 2 ⩽ 1, we obtain supθ∈R |G(θ)| = supθ∈(−π,π] |G(θ)| ⩽ Cλm supθ∈J |G(θ)|. The case m = 0 holds trivially since G is then constant. Throughout this subsection, we write p = sin2 θ with θ ∈ [0, π/2] and abbreviate Oθ := Osin2 θ . We take Oθ = Rθ ⊕ I, where   cos θ − sin θ Rθ = sin θ cos θ acts on the two-dimensional subspace spanned by |0⟩|0⟩ and |1⟩|1⟩, and the identity acts on its orthogonal complement. Then Oθ |0⟩|0⟩ = cos θ |0⟩|0⟩ + sin θ |1⟩|1⟩, which matches (1) with p = sin2 θ, and every entry of Oθ and Oθ† is a real trigonometric polynomial in θ of degree at most one. We set h p p p i p p θ0 = arcsin 5/12, J1 = arcsin 7/12, arcsin 2/3 , λ1 = arcsin 2/3 − arcsin 7/12. Then θ0 is the angle corresponding to H0 , while J1 is the interval of angles corresponding to H1 . Both λ1 > 0 and θ0 ∈ / J1 hold. With this notation, we now state the fixed-query lower bound. Lemma 10 (Fixed-query lower bound). There exists a universal constant c0 > 0 such that the following holds for every δ ∈ (0, 1/6]. Let a single-arm quantum test make at most q queries and satisfy and sup Pr(output baseline) ⩽ δ. Pr (output alternative) ⩽ 13 p∈[7/12,2/3] p

5/12

Then q ⩾ c0 log(1/δ). Proof. We first show that the acceptance probability P (θ) = Prsin2 θ (output alternative) is a real trigonometric polynomial in θ of degree at most 2q. By the deferred measurement principle [Nielsen and Chuang, 2010], a test that makes at most q queries is equivalent to a single quantum circuit 10

in which q controlled-query steps alternate with θ-independent unitaries, followed by a single measurement. For t = 1, . . . , q, the t-th controlled-query step applies Wt (θ) = Π0 ⊗ I + Π+ ⊗ Oθ + Π− ⊗ Oθ† , (t)

(t)

(t)

(t)

(t)

(t)

where Π0 , Π+ , Π− are orthogonal projections on the work registers that resolve the identity. They correspond respectively to making no query, querying Oθ , and querying Oθ† at step t. Branches of the computation that have already stopped act through the identity component. Therefore, a test that makes at most q queries can be padded to q controlled-query steps. Since every entry of Oθ and Oθ† has degree at most one, so does every entry of Wt (θ). The final state is Uq Wq (θ)Uq−1 · · · W1 (θ)U0 |ψ0 ⟩, where |ψ0 ⟩ is the fixed initial state of the test and the Ut are θ-independent unitaries. Therefore, each amplitude of the final state is a trigonometric polynomial in θ of degree at most q with complex coefficients. The probability P (θ) is the squared norm of the projection of the final state onto the subspace corresponding to the output alternative. Hence P (θ) is a sum of squared moduli of such amplitudes, and therefore a real trigonometric polynomial of degree at most 2q. We now convert the two error conditions into a degree lower bound via Lemma 9. Define G(θ) = 1−P (θ), the probability of outputting baseline at angle θ. Then G is also a real trigonometric polynomial of degree at most 2q, and 0 ⩽ G ⩽ 1. Since sin2 θ0 = 5/12, the error condition at p = 5/12 gives P (θ0 ) ⩽ 13 , and hence G(θ0 ) ⩾ 23 . Since J1 is the set of angles corresponding to p ∈ [7/12, 2/3], the error condition on the alternative interval gives supθ∈J1 |G(θ)| ⩽ δ, using G ⩾ 0. Applying Lemma 9 with J = J1 , we obtain 2q 2 3 ⩽ G(θ0 ) ⩽ sup|G(θ)| ⩽ Cλ1 δ. θ∈R

Therefore 2q log Cλ1 ⩾ log(2/(3δ)). Since δ ⩽ 1/6, we have log 2/(3δ) ⩾ 12 log(1/δ). Moreover, Cλ1 > 1 is a universal constant determined by the interval J1 . Combining these, we obtain
−1 q ⩾ c0 log(1/δ) for a universal constant c0 = 4 log Cλ1 > 0. Lemma 10 concerns tests with a fixed query budget, while the bandit reduction in Section 3.3 produces tests whose number of queries is random, because a bandit policy chooses which arm to query adaptively. We next derive the corresponding expected-query lower bound by truncation. Here we only require that the number of queries made so far is known during the run, so that the test can be stopped after a prescribed number of queries. This holds for the tests obtained from bandit policies. Lemma 11 (Expected-query lower bound). There exist universal constants c1 , δ0 > 0 such that the following holds for every δ ∈ (0, δ0 ]. Let a single-arm quantum test make a random number N ⩾ 0 of queries, with the number of queries made so far known during the run, and suppose that Pr (output alternative) ⩽ δ

sup

and

Pr(output baseline) ⩽ δ.

p∈[7/12,2/3] p

5/12

Then E5/12 [N ] ⩾ c1 log(1/δ). Proof. Let δ0 := min{1/6, Cλ−8 } and c1 := c0 /12, where c0 is the constant of Lemma 10. Let 1 m := E5/12 [N ]. If m = ∞, there is nothing to prove, so assume m < ∞. Set the budget q := max{1, ⌈6m⌉}. Consider the truncated test that runs the given test, outputs its answer if it 11

stops within q queries, and otherwise interrupts it after the q-th query and outputs alternative. Since the number of queries made so far is known during the run, the truncation is well defined, and the truncated test makes at most q queries. Under p = 5/12, Markov’s inequality gives Pr5/12 (N > q) ⩽ m/q ⩽ 1/6, so the truncated test outputs alternative with probability at most δ + 1/6 ⩽ 1/3. Under any p ∈ [7/12, 2/3], forcing the output alternative on truncation cannot increase the probability of outputting baseline, so this probability remains at most δ. The truncated test is thus a single-arm quantum test making at most q queries and satisfying the two error conditions of Lemma 10. Applying Lemma 10 to the truncated test gives q ⩾ c0 log(1/δ). Since δ ⩽ Cλ−8 and c0 = 1 −1 (4 log Cλ1 ) , this implies q ⩾ 2. Hence q = ⌈6m⌉, so q ⩽ 6m + 1 and m ⩾ (q − 1)/6. Since q ⩾ 2, we also have q − 1 ⩾ q/2. Therefore m⩾

3.3

q−1 q c0 ⩾ ⩾ log(1/δ) = c1 log(1/δ). 6 12 12

From Bandit Regret to Testing

We now carry out the reduction from bandit regret to single-arm testing described in the proof overview. Fix a quantum multi-armed bandit policy π, and recall that MT = supν∈UK RTπ (ν) denotes its worst-case regret over the hard family. For an instance ν ∈ UK and an arm i ∈ [K], let Ni (T ) denote the number of rounds in which π selects arm i when run on ν. Note that Ni (T ) counts selections rather than oracle queries. The two coincide for policies that query the selected arm’s oracle in every round, and in general the number of queries to arm i is at most Ni (T ). Lemma 12 (Bandit-to-testing reduction). Let c1 , δ0 be the constants of Lemma 11, and suppose 0 < MT ⩽ δ0 T /24. Then, for every i ∈ {2, . . . , K},    Eν 0 Ni (T ) ⩾ c1 log

T  . 24 MT

Proof. Fix i ∈ {2, . . . , K}, and let Ai := {Ni (T ) > T /2}. We first bound the two error probabilities that will arise from the testing rule. • Under ν 0 , arm i is suboptimal with gap 1/12, so each round selecting arm i incurs regret 1/12. Using Eν 0 [Ni (T )] ⩾ T2 Prν 0 (Ni (T ) > T /2), we get 1 1 T MT ⩾ RTπ (ν 0 ) ⩾ 12 Eν 0 [Ni (T )] ⩾ 12 · T2 Pr(Ai ) = 24 Pr(Ai ), ν0

ν0

hence Prν 0 (Ai ) ⩽ 24MT /T . and every other arm has gap at least 1/12. Since • Under any instance ν ∈ Ui , arm i is optimal P the policy selects exactly one arm per round, j̸=i Nj (T ) = T − Ni (T ), and on the complement Aci we have T − Ni (T ) ⩾ T /2. Hence   1 1 T MT ⩾ RTπ (ν) ⩾ 12 Eν T − Ni (T ) ⩾ 12 · T2 Pr(Aci ) = 24 Pr(Aci ), ν

hence Prν (Aci ) ⩽ 24MT /T .

12

ν

We now convert the policy into a single-arm quantum test whose unknown oracle represents arm i. The instance ν 0 and the instances in Ui differ only in the mean of arm i, so the oracles of all arms j = ̸ i are fixed and known. The test simulates the policy round by round. Whenever the policy selects an arm j ̸= i and queries its oracle, the test applies the known oracle of arm j or its inverse, without querying the unknown oracle. Whenever the policy selects arm i and queries its oracle, the test queries the unknown oracle or its inverse, matching the operation chosen by the policy. In rounds where the policy makes no query, the test makes none. After T rounds, the test uses Ai as its decision rule, outputting alternative if Ai occurs and baseline otherwise. By construction, running the test with unknown oracle Op reproduces the run of the policy on the instance in which arm i has mean p. If p = 5/12, this is the run on ν 0 . If p ∈ [7/12, 2/3], it is the run on the corresponding instance in Ui . Therefore the error probability under H0 is Prν 0 (Ai ), and the worst-case error probability under H1 is supν∈Ui Prν (Aci ). Both are at most 24MT /T . The number of queries made by the test under H0 is at most the number of rounds in which the simulated policy selects arm i. The latter has the same distribution as Ni (T ) under ν 0 . The number of queries made so far can be tracked during the simulation, because each round contains either no oracle call or one explicitly specified call to the selected arm’s oracle or its inverse. Since 0 < 24MT /T ⩽ δ0 , we may apply Lemma 11 with δ = 24MT /T to the test above. Its T expected number of queries under H0 is therefore at least c1 log 24M , and since this query count is T at most the number of rounds selecting arm i, we conclude that Eν 0 [Ni (T )] ⩾ c1 log

3.4

T . 24MT

Completing the QMAB Lower Bound

We now prove Theorem 8 by applying Lemma 12 across arms and evaluating the regret under the baseline instance. Proof of Theorem 8. Fix a quantum multi-armed bandit policy π, and recall that MT = supν∈UK RTπ (ν) denotes its worst-case regret over the hard family UK . Since UK ⊆ BK , it suffices to find an instance in UK with the claimed regret lower bound. Let c1 , δ0 be the constants of Lemma 11, and assume T ⩾ CK for a universal constant C chosen below. For convenience, set x := T /K. We prove that MT ⩾ c̄K log x, where c̄ := min{δ0 /24, c1 /96}, distinguishing two cases according to the size of MT . Case 1: Suppose MT > δ0 T /24, so that the regret is already of linear order in T . Then MT >

δ0 δ0 Kx ⩾ K log x ⩾ c̄ K log x, 24 24

using log x ⩽ x and c̄ ⩽ δ0 /24. Case 2: Suppose MT ⩽ δ0 T /24, the regime of Lemma 12. We first note that MT > 0, which is needed to apply the lemma. Let a1 be the first arm selected by the policy. Consider the alternative instance ν 2,7/12 ∈ U2 , in which arm 2 has mean 7/12. When a1 is selected, no query has been made yet, so a1 has the same distribution under ν 0 and under ν 2,7/12 . The first round regret is at least (1/12) Pr(a1 ̸= 1) under ν 0 , and at least (1/12) Pr(a1 ̸= 2) under ν 2,7/12 . Since Pr(a1 ̸= 1) + Pr(a1 ̸= 2) ⩾ 1, one of these two instances has positive expected regret, and hence MT > 0.

13

T Since 0 < MT ⩽ δ0 T /24, Lemma 12 gives Eν 0 [Ni (T )] ⩾ c1 log 24M for every i ∈ {2, . . . , K}. T 0 Moreover, under ν , every arm i ⩾ 2 has gap 1/12, so each round selecting an arm i ⩾ 2 incurs regret 1/12. Summing over arms and evaluating the regret under ν 0 , we get

MT ⩾ RTπ (ν 0 ) =

K   c1 (K − 1) 1 X c1 T T ⩾ , Eν 0 Ni (T ) ⩾ log K log 12 12 24MT 24 24MT i=2

using K − 1 ⩾ K/2 for K ⩾ 2. We now show that MT ⩾ (c1 /96)K log x. Suppose for contradiction that MT < (c1 /96)K log x. √ Let C ⩾ e be a universal constant such that x ⩾ (c1 /4) log x for all x ⩾ C. Then, using T = Kx, √ Kx 4x T > = ⩾ x. 24MT 24 · (c1 /96)K log x c1 log x Substituting this bound into the inequality MT ⩾ (c1 /24)K log(T /(24MT )) yields MT ⩾

√ c1 c1 c1 K log x = K log x ⩾ 2 · K log x, 24 48 96

contradicting the assumption. Hence MT ⩾ (c1 /96)K log x, and since c̄ ⩽ c1 /96, we conclude that MT ⩾ c̄K log x in this case as well. It remains to pass from MT to a single instance. Since MT ⩾ c̄K log x > 0 and MT is the supremum of RTπ (ν) over ν ∈ UK , there exists an instance ν ∈ UK with RTπ (ν) ⩾ MT /2 ⩾ (c̄/2)K log x. Since x = T /K, Theorem 8 holds with c := c̄/2.

3.5

A Finite-Action QLB Lower Bound

We now prove a lower bound for finite-action quantum linear bandits by realizing the QMAB hard family with an action set of only d actions. Embedding the arms directly as the standard basis √ vectors would require every coordinate of θ to carry a constant baseline mean, forcing ∥θ∥2 = Θ( d). We instead let the actions xi , i ⩾ 2, share a common reference direction, so that one coordinate of θ provides their common baseline mean while keeping ∥θ∥2 = O(1). The orthogonal component of xi then encodes the alternatives under which xi is optimal. Theorem 13 (Finite-action QLB lower bound). There exist universal constants c, C > 0 such that for every d ⩾ 2 and T ⩾ Cd, there exist an action set A ⊆ Rd , |A| = d, with ∥x∥2 ⩽ 1 for all x ∈ A, and a parameter set Θ ⊆ {θ ∈ Rd : ∥θ∥2 ⩽ 1, x⊤ θ ∈ [0, 1] for all x ∈ A} such that for any quantum linear bandit policy π over T rounds, there exists θ ∈ Θ with RTπ (θ) ⩾ cd log

T . d

Proof. Let c, C be the constants of Theorem 8. Define the action set A := {x1 , . . . , xd } by x1 := e1 ,

xi := 56 e1 +

√

11 6 ei ,

i = 2, . . . , d,

so that ∥x1 ∥2 = 1 and ∥xi ∥22 = 25/36 + 11/36 = 1. Define θ0 := 12 e1 , and for i ∈ {2, . . . , d} and q ∈ [7/12, 2/3],   5 θ(i,q) := 12 e1 + √611 q − 12 ei . Let Θ := {θ0 } ∪ {θ(i,q) : 2 ⩽ i ⩽ d, q ∈ [7/12, 2/3]}. For each θ ∈ Θ, the corresponding instance uses canonical Bernoulli oracles, with Ox = Ox⊤ θ for every x ∈ A. 14

We now verify the parameter and mean constraints. For the parameter norm, ∥θ0 ∥2 = 1/2, and since q −5/12 ⩽ 1/4, we have ∥θ(i,q) ∥22 = 1/4+(36/11)(q −5/12)2 ⩽ 1/4+(36/11)·(1/16) = 5/11 < 1. 0 ⊤ 0 (i,q) , the coefficients For the means, x⊤ 1 θ = 1/2 and x√i θ = (5/6) · (1/2) = 5/12 for i ⩾ 2. Under θ (i,q) = 5/12 + 11 · √6 (q − 5/12) = q, while x⊤ θ (i,q) = 1/2 and x⊤ θ (i,q) = 5/12 cancel to give x⊤ 1 i θ j 6 11 for j ∈ / {1, i}. In particular, all means lie in {5/12, 1/2} ∪ [7/12, 2/3] ⊆ [0, 1]. Consequently, as θ ranges over Θ, the induced action-mean vectors follow exactly the pattern of the hard family Ud ⊆ Bd of Section 3.1, instantiated with K = d arms. The parameter θ0 induces the baseline instance ν 0 , and θ(i,q) induces ν i,q . Since a quantum linear bandit policy on the finite action set A selects one action per round and applies its reward oracle or the inverse at most once, it induces a quantum multi-armed bandit policy on the corresponding d-armed instances, with the same oracle interactions and the same regret. Applying the proof of Theorem 8 to this induced d-armed hard family produces an instance of Ud with regret at least cd log(T /d). The corresponding parameter θ ∈ Θ then gives RTπ (θ) ⩾ cd log(T /d). Remark 14. The hard instances used in the lower bound proofs have Bernoulli rewards, so both lower bounds also hold under the bounded-variance assumption of Wan et al. [2023]. Moreover, the QLB hard family uses a fixed action set of size K = d, so the QLB lower bound also applies to general action sets. On the other hand, the reduction uses that arms are selected classically in each round, so the lower bounds do not directly extend to models permitting superposed arm selection, such as the m-arm oracles of Wang et al. [2025] or the fully coherent access model of Wang et al. [2021].

4

Finite-Action Quantum Linear Bandits

Section 3.5 shows that finite-action quantum linear bandits suffer regret Ω(d log(T /d)). Complementing this lower bound, we give LV-G-Elim, a phased elimination algorithm for finite action sets. When K = poly(d), LV-G-Elim has regret nearly linear in d, matching the lower bound up to polylogarithmic factors. This improves the d2 dependence of the QLinUCB algorithm of Wan et al. [2023]. The algorithm uses a small-support approximate G-optimal design on the current active set in each phase. The G-optimality condition controls the error amplification when the support estimates are extrapolated to all active actions, while the small support keeps the number of queried actions proportional to the dimension. We estimate the support means using the low-bias low-variance quantum mean estimator from Lemma 6, with a query allocation matched to the design weights, so that the reconstruction error aggregates through variance. A direct high-probability estimator such √ as QMC would instead aggregate worst-case absolute errors and lose an extra d factor. We return to this comparison at the end of the section.

4.1

Small-Support Approximate G-Optimal Design

Classical phased elimination algorithms for finite-action linear bandits use G-optimal designs to estimate all active actions from samples drawn on a design support [Lattimore and Szepesvári, 2020]. In the classical analysis, estimating the active actions to accuracy ϵ in a phase costs ϵ−2 samples in the leading term, so the size of the design support only contributes a lower-order rounding overhead. Quantum queries change this accounting. The leading cost of quantum mean estimation is of order ϵ−1 rather than ϵ−2 , but the estimator must be run separately on each support action, with a constant minimum number of queries per call. The size of the support thus enters the query bound directly, rather than only as a rounding overhead. To obtain regret nearly linear in d, the design must therefore have nearly linear support while still controlling the error amplification of 15

extrapolating from the support to all active actions. The following lemma provides such a design with support size O(r) and G-value O(r), where r is the dimension of the span of the active set. Lemma 15 (Small-support approximate G-optimal design). There exist universal constants cs , CG > 0 such that the following holds. Let X ⊆ Rd be finite with r = dim(span(X )) ⩾ 1. One can compute a subset S ⊆ P X and a distribution π supported on S, with |S| ⩽ cs r, such that the design information matrix M = a∈S π(a)aa⊤ satisfies max x⊤ M + x ⩽ CG r.

Range(M ) = span(X ),

x∈X

For each x ∈ X , define its design-induced prediction weights by αa (x) = π(a)a⊤ M + x for a ∈ S. Then we have X X αa (x)2 x= αa (x)a, = x⊤ M + x ⩽ CG r. π(a) a∈S

a∈S

Proof sketch. The proof has two steps: we first compute an approximately optimal continuous design, and then round it to an integer design of total mass m = Θ(r), whose normalization is the desired distribution π. Since rounding preserves the G-value up to a constant factor, and the normalization multiplies back at most the factor m removed by the scaling, the final G-value remains O(r). For the first step, let V = span(X ) and work in coordinates on V , so that the design problem is r-dimensional and full rank. In this space, the Kiefer–Wolfowitz equivalence theorem [Kiefer and Wolfowitz, 1960] shows that the continuous G-optimal value is r, and the continuous relaxation method of Allen-Zhu et al. [2021, Section 3] computes a distribution w whose G-value is O(r). For the second step, we round the scaled design mw, whose information matrix is m times that of w and whose G-value is therefore O(r/m). To match the constraints of the rounding theorem, we replace each design point by m identical copies and assign weight w(x) to each copy. This copied-list representation has the same total mass m and the same information matrix mMw as mw, but all coordinate weights lie in [0, 1]. Applying the rounding theorem of Allen-Zhu et al. [2021, Theorem 2.1] with budget m then yields integer multiplicities of total mass m b ⩽ m whose G-value is at most O(r/m). Merging identical copies and normalizing by m b gives a distribution π supported on a set S with |S| ⩽ m b = O(r), and since M is the rounded information matrix divided by m, b the G-value is multiplied by m b ⩽ m. Thus the resulting matrix M satisfies maxx∈X x⊤ M + x ⩽ m b · O(r/m) = O(r). Finally, the rounded design has finite G-value, so the selected points span V and hence Range(M ) = span(X ). The prediction-weight identities then follow from M M + x = x, valid for x ∈ X ⊆ Range(M ), together with M + M M + = M + . The full proof is given in Appendix A. The design can be computed in polynomial time. The running-time accounting is given in Appendix A. We refer to a triple (S, π, M ) satisfying Lemma 15 as a design. The associated prediction weights express the mean of every active action as a weighted combination of the means on the support, with the resulting error amplification controlled by the G-value. We next show how to estimate the support means with a query allocation matched to the design weights.

4.2

From LVQME to High-Probability Design Estimates

The estimator LVQME controls the bias and the variance of its output, rather than directly providing a high-probability error bound. We therefore proceed in two steps: we first obtain estimates that are accurate with constant probability for each fixed action, and then amplify them to estimates that hold simultaneously over the active set with high probability, as required by the elimination step.

16

The estimation procedure. Fix an active set A ⊆ Rd and a design (S, π, M ) satisfying Lemma 15, and let r = dim(span(A)) ⩾ 1. Given an accuracy parameter ϵ ∈ (0, 1], we set ( & p ') rπ(a) ϵ2 ta := max 4, ct (a ∈ S), ζ := cζ , ϵ r where ct > 0 is a sufficiently large universal constant and cζ > 0 is a sufficiently small universal constant, which are to be chosen in the proof of Lemma 16. The value ta allocates more estimation effort to support actions with larger design weight π(a). Let & ' X ta U := 6 CQ , (2) ta log log(ta ) log ζ a∈S

where CQ is the query constant in Lemma 6. The procedure runs one independent call LVQME(Oa , ta , ζ) for each a ∈ S, sequentially in an arbitrary fixed order, using U as a shared deterministic threshold on the total number of oracle queries. If some call is still running after U oracle queries in total, the procedure stops and sets µ ba := 0 for every a ∈ S. This stopping event is accounted for in Lemma 16. Otherwise, µ ba is the output of the call on a. In both cases, the procedure returns X µ e(x) := αa (x) µ ba for all x ∈ A, a∈S

where {αa (x)}a∈S are the prediction weights from Lemma 15. The following lemma shows that the estimation procedure is accurate with constant probability for each fixed action x ∈ A. Lemma 16 (LVQME design estimates). There exist universal constants ct , cζ > 0 such that the following holds. The estimation procedure has the deterministic query threshold U as in (2). This threshold satisfies r   r r  U =O log 4 + log log 4 + . ϵ ϵ ϵ Moreover, for each fixed x ∈ A, Pr[ |e µ(x) − µ(x)| > ϵ ] ⩽

5 . 12

Proof. We first give the main idea of the proof. The stopping rule converts the random query cost of the LVQME calls into the deterministic threshold U , at the price of a constant failure probability, which is controlled by Markov’s inequality. On the remaining event, the estimate µ e(x) inherits the two guarantees of Lemma 6: its bias is small because each µ ba is nearly unbiased and we choose ζ = cζ ϵ2 /r, while its variance is smallpbecause the fluctuations of independent calls average under the design weights. The allocation ta ∝ rπ(a)/ϵ makes the variance controlled by the design quantity x⊤ M + x. Chebyshev’s inequality then converts this variance bound into the constant probability guarantee. We now turn to the details. By construction, the estimation procedure never makes more than U oracle queries, so for the query bound it suffices to bound the size of U . First, by the definition of ta , each a ∈ S satisfies p ta ⩽ ct rπ(a)/ϵ + 5, where the ceiling contributes at most 1 and the truncation at 4 contributes at p most 4. Summing over a ∈ S and applying the Cauchy–Schwarz inequality to the weights π(a), √ √ s X √ r X ct cs r ct r X p ct r ta ⩽ 5|S| + π(a) ⩽ 5|S| + |S| π(a) ⩽ 5cs r + =O , ϵ ϵ ϵ ϵ a∈S

a∈S

a∈S

17

P using |S| ⩽ cs r, a∈S π(a) = 1, and ϵ ⩽ 1 to absorb the first term. Next, we bound the logarithmic √ 3/2 /ϵ3 ), where factors. Every a ∈ S satisfies 4 ⩽ ta = O( r/ϵ), and hence ta /ζ = ta · r/(cζ ϵ2 ) = O(r


r the constants depend only on ct , cζ . Therefore log log(taP ) log(ta /ζ) = O log 4 + ϵ log log 4 + rϵ for every a ∈ S, and combining this with the bound on a∈S ta gives the stated bound on U . We now fix x ∈ A and bound the error probability. Consider the process that runs all |S| calls to completion, with the stopping rule removed, on the same realization of randomness. The estimation procedure coincides with this uninterrupted process unless the latter makes more than U queries. P By Lemma 6, the expected total number of queries of the uninterrupted process is at most CQ a∈S ta log log(ta ) log(ta /ζ) ⩽ U/6 by (2). Hence, by Markov’s inequality, the uninterrupted process makes more than U queries with probability at most 1/6. Otherwise, the stopping rule is not triggered and the two processes coincide. It remains to bound the deviation of the uninterrupted estimator, which we again denote by µ e(x). For each a ∈ S, decompose µ ba − µ(a) = ba + ξa ,

ba := E[b µa ] − µ(a),

ξa := µ ba − E[b µa ],

so that E[ξa ] = 0 and Lemma 6 gives |ba | ⩽ ζ and Var(ξa ) ⩽ CV /t2a + ζ. Moreover, the ξa are independent across a ∈ S, since the procedure runsP the calls independently. Since Lemma 15 gives P x = a∈S αa (x)a, the linear model implies µ(x) = a∈S αa (x)µ(a). Hence X X µ e(x) − µ(x) = αa (x) ba + αa (x) ξa . a∈S

a∈S

For the bias term, the Cauchy–Schwarz inequality weighted by π gives X

αa (x) ba ⩽ ζ

a∈S

 X α (x)2 1/2  X 1/2 X p p ϵ2 ϵ a |αa (x)| ⩽ ζ π(a) ⩽ ζ CG r = c ζ CG √ ⩽ , π(a) 4 r a∈S

a∈S

a∈S

√
−1 P . using a∈S αa (x)2 /π(a) = x⊤ M + x ⩽ CG r, r ⩾ 1, and ϵ ⩽ 1, provided cζ ⩽ 4 CG For the fluctuation term, since the ξa are independent, Var

X a∈S

 X X αa (x)2 X αa (x) ξa = αa (x)2 Var(ξa ) ⩽ CV + ζ αa (x)2 , t2a a∈S

a∈S

a∈S

where we substituted Var(ξa ) ⩽ CV /t2a + ζ. For the first term, the definition of ta gives t2a ⩾ c2t r π(a)/ϵ2 , and hence CV

X αa (x)2 t2a

a∈S

⩽

ϵ2 CV ϵ2 X αa (x)2 CV ϵ2 CV CG 2 ⩽ · C r = ϵ ⩽ , G π(a) 32 c2t r c2t r c2t a∈S

using a∈S αa (x)2 /π(a) = x⊤ M + x ⩽ CG r, provided c2t ⩾ 32CV CG . For the second term, since π(a) ⩽ 1 for every a ∈ S, P

ζ

X a∈S

αa (x)2 ⩽ ζ

X αa (x)2 a∈S

π(a)

⩽ ζ CG r = cζ CG ϵ2 ⩽

provided cζ ⩽ (32CG )−1 . Combining the two terms, Var

X a∈S

 ϵ2 αa (x) ξa ⩽ . 16 18

ϵ2 , 32

Since E

P

a∈S αa (x) ξa



= 0, by Chebyshev’s inequality, Pr

h X

αa (x) ξa >

a∈S

ϵi 1 ⩽ . 2 4

P Suppose that the stopping rule is not triggered and that a∈S αa (x) ξa ⩽ ϵ/2. In this case, µ e(x) coincides with the uninterrupted estimator, and by the decomposition above, |e µ(x) − µ(x)| ⩽

X

αa (x) ba +

a∈S

X

αa (x) ξa ⩽

a∈S

ϵ ϵ + ⩽ ϵ, 4 2

where the bias bound holds deterministically. Hence the error event {|e µ(x)−µ(x)| > ϵ} is contained in  the union of the two events above, and a union bound gives Pr |e µ(x)−µ(x)| > ϵ ⩽ 1/6+1/4 = 5/12. 
−1 √ √
−1 Finally, choosing ct := 32CV CG and cζ := min 1, 4 CG satisfies all the , 32CG constraints above, and cζ ⩽ 1 ensures ζ ∈ (0, 1) as required by Lemma 6. High-probability estimates. The estimation procedure is accurate for each fixed action only with constant probability. To obtain estimates that are accurate for all actions in A simultaneously with high probability, we run it several times independently and take medians. Lemma 17 (High-probability LVQME design estimates). There exists a universal constant CN > 0   such that the following holds. For a confidence parameter δ ∈ (0, 1), let N := CN log |A| δ . Run the estimation procedure of Lemma 16 independently N times, and for each x ∈ A, let µ b(x) be the (1) (N ) (j) median of µ e (x), . . . , µ e (x), where µ e (x) denotes the estimate µ e(x) returned by the j-th run. Then the total number of oracle queries is deterministically at most     r |A| r r NU = O log log 4 + log log 4 + , ϵ δ ϵ ϵ and with probability at least 1 − δ, |b µ(x) − µ(x)| ⩽ ϵ

for all x ∈ A.

Proof. Fix x ∈ A. By Lemma 16, each run satisfies |e µ(j) (x) − µ(x)| ⩽ ϵ with probability at least 1 − 5/12 = 7/12 > 1/2, independently across j ∈ {1, . . . , N }. By a standard median argument and a Chernoff bound,   δ Pr |b µ(x) − µ(x)| > ϵ ⩽ e−Ω(N ) ⩽ , |A| provided CN is sufficiently large. A union bound over x ∈ A then shows that, with probability at least 1 − δ, |b µ(x) − µ(x)| ⩽ ϵ for all x ∈ A. For the query bound, the medians µ b(x) for x ∈ A, are computed from the same N runs, and each run makes at most U queries by Lemma 16. Hence the total number of queries is deterministically at most N U , and the stated bound follows from the bound on U in Lemma 16 together with the definition of N . For convenience, we refer to this median-amplified estimator as LVQMEDesignEstimate.

19

4.3

Low-Variance G-Optimal Design Elimination

We now combine the design and the estimator into a phased elimination algorithm. LV-G-Elim (Algorithm 1) follows the classical G-optimal exploration scheme [Lattimore and Szepesvári, 2020], with the sampling-and-estimation step replaced by LVQMEDesignEstimate. In phase ℓ, it computes a small-support design for the current active set Aℓ (Line 4), calls the estimator with target accuracy ϵℓ = 2−ℓ (Line 5), and eliminates every action whose estimate falls more than 2ϵℓ below the best estimate (Lines 6 and 7). The algorithm stops once the total number of oracle queries reaches T . If every phase finishes before the budget is exhausted, the algorithm queries an arbitrary action in the current active set for the remaining rounds. If span(Aℓ ) = {0} at the beginning of a phase, the algorithm stops the phased procedure and plays an arbitrary active action for all remaining rounds. Algorithm 1: Low-Variance G-Optimal Design Elimination (LV-G-Elim) Input: Action set A ⊆ Rd , horizon T , confidence parameter δ ∈ (0, 1) 1 LT ← ⌈log2 T ⌉, A0 ← A, δ ′ ← δ/(LT + 1) 2 for ℓ = 0, 1, . . . , LT (terminate once the total number of oracle queries reaches T ) do 3 ϵℓ ← 2−ℓ 4 Compute a small-support design (Sℓ , πℓ , Mℓ ) for Aℓ as in Lemma 15 5 {b µℓ (x)}x∈Aℓ ← LVQMEDesignEstimate(Aℓ , Sℓ , πℓ , Mℓ , ϵℓ , δ ′ ) 6 µ b⋆ℓ ← maxz∈Aℓ µ bℓ (z) 7 Aℓ+1 ← {x ∈ Aℓ : µ bℓ (x) ⩾ µ b⋆ℓ − 2ϵℓ } The following theorem gives the regret guarantee for LV-G-Elim. Theorem 18 (Regret of LV-G-Elim). For any confidence parameter δ ∈ (0, 1), with probability at least 1 − δ, LV-G-Elim satisfies   K log T log(dT ) log log(dT ) . R(T ) = O d log T log δ Moreover, running LV-G-Elim with confidence parameter 1/T gives E[R(T )] = O (d log T log(KT ) log(dT ) log log(dT )) . Proof. We first give the main idea of the proof. With probability at least 1 − δ, all estimates used by the algorithm are accurate for the corresponding active actions. On this good event, the optimal action is never eliminated, and every action that remains active after phase ℓ has suboptimality gap e e O(ϵℓ ). The number of queries in phase ℓ is O(d/ϵ ℓ ) by Lemma 17, where O hides logarithmic factors e in d, T, K and 1/δ, so the regret incurred in phase ℓ is O(d). Summing over the O(log T ) phases gives the stated bound. We now turn to the details. The algorithm runs at most LT + 1 phases. For each phase ℓ = 0, . . . , LT in which T the elimination step is performed, define Eℓ := |b µℓ (x) − µ(x)| ⩽ ϵℓ for all x ∈ Aℓ and E := ℓ Eℓ , where the intersection ranges over all such phases. For each such phase, let Fℓ be the history before phase ℓ. Conditional on Fℓ , the active set Aℓ and the design (Sℓ , πℓ , Mℓ ) are fixed, so Lemma 17 gives Pr(Eℓc | Fℓ ) ⩽ δ ′ almost surely. Taking expectations gives Pr(Eℓc ) ⩽ δ ′ , where δ ′ = δ/(LT + 1). A union bound over the at most LT + 1 phases gives Pr[E] ⩾ 1 − δ. It remains to prove the regret bound on E. Fix x⋆ ∈ arg maxx∈A µ(x), set µ⋆ := µ(x⋆ ), and write ∆(x) := µ⋆ − µ(x). We claim the following on E: for every phase ℓ in which the elimination step is performed, x⋆ ∈ Aℓ+1 , and ∆(x) ⩽ 4ϵℓ for all x ∈ Aℓ+1 . 20

Initially, x⋆ ∈ A0 = A. Assume inductively that x⋆ ∈ Aℓ . For every z ∈ Aℓ , on Eℓ , µ bℓ (x⋆ ) ⩾ µ⋆ − ϵℓ ⩾ µ(z) − ϵℓ ⩾ µ bℓ (z) − 2ϵℓ . Thus µ bℓ (x⋆ ) ⩾ µ b⋆ℓ − 2ϵℓ , so x⋆ is not eliminated. If x ∈ Aℓ+1 , then µ bℓ (x) ⩾ µ b⋆ℓ − 2ϵℓ ⩾ µ bℓ (x⋆ ) − 2ϵℓ , and hence µ(x) ⩾ µ bℓ (x) − ϵℓ ⩾ µ bℓ (x⋆ ) − 3ϵℓ ⩾ µ⋆ − 4ϵℓ . This proves the claim. We now bound the instantaneous regret of the actions queried in each phase. In phase ℓ, the algorithm queries only actions in Sℓ ⊆ Aℓ . For ℓ = 0, all gaps are at most 1 = ϵ0 , since all means lie in [0, 1]. For ℓ ⩾ 1, the claim applied to phase ℓ − 1 gives ∆(x) ⩽ 4ϵℓ−1 = 8ϵℓ for all x ∈ Aℓ . Thus every query performed in phase ℓ incurs regret at most 8ϵℓ , for every ℓ ⩾ 0. Next, we bound the number of queries in each phase. In phase ℓ, writing rℓ := dim(span(Aℓ )) ⩽ d and Kℓ := |Aℓ | ⩽ K, Lemma 17 shows that the estimator makes at most     rℓ  Kℓ rℓ rℓ  log ′ log 4 + Qℓ = O log log 4 + ϵℓ δ ϵℓ ϵℓ oracle queries deterministically. For every ℓ ⩽ LT we have ϵℓ = 2−ℓ ⩾ 1/(2T ), so 4 + rℓ /ϵℓ =

K log T O(dT ), and log(Kℓ /δ ′ ) ⩽ log K(LT + 1)/δ = O log δ . Hence   K log T d log log(dT ) log log(dT ) . Qℓ = O ϵℓ δ We now combine the two bounds. The regret incurred in phase ℓ is at most the number of queries performed in that phase multiplied by 8ϵℓ . This holds whether or not the phase completes, since the gap bound depends only on Aℓ , which is determined before the phase begins, and the number of queries performed in phase ℓ never exceeds Qℓ . Hence, on E, the regret incurred during the planned phases is at most LT X ℓ=0

  K log T 8ϵℓ Qℓ = O (LT + 1) d log log(dT ) log log(dT ) . δ

If all planned phases finish before T queries are made, then the current active set is ALT +1 , and the remaining queries are to actions in this set. By the claim applied to phase LT , every action in ALT +1 has gap at most 4ϵLT ⩽ 4/T . Since there are at most T remaining queries, their total regret is at most 4, which is absorbed in the bound above. Therefore LT + 1 = O(log T ) gives the high-probability bound. Finally, we prove the expected regret bound. Run LV-G-Elim with confidence parameter δ = 1/T . Since every gap is at most 1 and there are at most T queries, the regret is at most T deterministically. Hence, using the high-probability bound with δ = 1/T , E[R(T )] ⩽ O (d log T log(KT log T ) log(dT ) log log(dT )) + Pr[E c ] T. Here Pr[E c ] ⩽ 1/T , so the second term is at most 1. Since log(KT log T ) ⩽ log(KT 2 ) ⩽ 2 log(KT ), we conclude E[R(T )] = O (d log T log(KT ) log(dT ) log log(dT )) , which completes the proof. 21

Remark 19 (Bounded-variance rewards). Our upper-bound analysis uses bounded rewards only through the quantum mean estimation primitive. Under the bounded-variance assumption of Wan et al. [2023], with a known variance bound σ 2 and rewards of finite support size n, the nondestructive median estimator and the unbiased mean estimator of Cornelissen and Hamoudi [2023, Propositions 3.1 and 3.2] can be combined to obtain estimates with bias O(εσ), variance e O(σ 2 /t2 ), and query complexity O(t). This suggests that the same design-based argument can be extended by scaling the confidence radii and query allocations with σ, at the cost of additional polylogarithmic factors, including a logarithmic dependence on n. A complete treatment requires a corresponding deterministic-budget estimator and is left for future work. Comparison with a QMC variant. A natural alternative is to keep the same phased elimination algorithm and the same small-support designs, but estimate the support means using the QMC estimator from Lemma 4. This gives a simpler design estimator with direct high-probability guarantees on the support. The price is that the errors aggregate through worst-case absolute error: if each support estimate √ has error at most ρ, then extrapolation through the prediction weights gives an error of at most CG r ρ for every active action by the Cauchy–Schwarz inequality. Achieving √ accuracy ϵ thus requires ρ ≍ ϵ/ r, which leads to a design-estimation cost of order r3/2 /ϵ up to logarithmic factors. The low-variance estimator from Lemma 6 avoids this loss because independent fluctuations aggregate through variance. With a query allocation matched to the design weights, the variances P √ add up to O(ϵ2 ) under the same weighted sum a∈S αa (x)2 /π(a) ⩽ CG r, without the r inflation in the required support accuracy. Lemma 20 (QMC design estimates). Fix an active set A ⊆ Rd and a design (S, π, M ) satisfying Lemma 15, and let r = dim(span(A)) ⩾ √ 1. Given an accuracy parameter ϵ ∈ (0, 1] and a confidence parameter δ ∈ (0, 1), set ρ := min{1, ϵ/ CG r}. ba be the output of an independent P For each a ∈ S, let µ call QMC(Oa , ρ, δ/|S|), and define µ b(x) := a∈S αa (x) µ ba for all x ∈ A, where {αa (x)}a∈S are the prediction weights from Lemma 15. Then the total number of oracle queries is always bounded by O(r3/2 ϵ−1 log(r/δ)), and with probability at least 1 − δ, |b µ(x) − µ(x)| ⩽ ϵ

for all x ∈ A.

Proof. By Lemma 4 and a union bound over S, with probability at least 1 − δ, the estimates {b µa : a ∈ S} µa − µ(a)| ⩽ ρ for every a ∈ S. On this Psatisfy |b Pevent, fix x ∈ A. Since Lemma 15 α gives x = (x)a, the linear model implies µ(x) = a∈S a a∈S αa (x)µ(a). Therefore, by the Cauchy–Schwarz inequality weighted by π, |b µ(x)−µ(x)| =

X a∈S

αa (x) µ ba −µ(a)

⩽

X αa (x)2 a∈S

π(a)

!1

!1

2

2

X

π(a)(b µa − µ(a))2

⩽

p CG r ρ ⩽ ϵ.

a∈S

It remains to bound the number of queries. Each QMC call uses O(ρ−1 log(|S|/δ)) oracle √ queries −1 ⩽ 1 + by Lemma 4. By the definition of ρ, using r ⩾ 1 and ϵ ⩽ 1, we have ρ CG r/ϵ
⩽ √ √ −1 (1 + CG ) r/ϵ. With |S| ⩽ cs r, the total number of queries over a ∈ S is O |S| ρ log(|S|/δ) =
O r3/2 ϵ−1 log(r/δ) . We denote this estimator by QMCDesignEstimate, and let QMC-G-Elim be the variant of Algorithm 1 obtained by replacing LVQMEDesignEstimate with QMCDesignEstimate in Line 5. 22

Corollary 21 (Regret of QMC-G-Elim). For any  confidence parameter  δ ∈ (0, 1), with probability d log T 3/2 at least 1 − δ, QMC-G-Elim satisfies R(T ) = O d log T log δ . Moreover, running QMC
G-Elim with confidence parameter 1/T gives E[R(T )] = O d3/2 log T log(dT ) . Proof. We follow the proof of Theorem 18, replacing Lemma 17 by Lemma 20. The elimination argument and the instantaneous regret bound are unchanged. The number of queries in phase ℓ is always bounded by ! ! 3/2 rℓ rℓ d3/2 d log T Qℓ = O , log ′ = O log ϵℓ δ ϵℓ δ T
where δ ′ = δ/(LT + 1). Hence the regret incurred in phase ℓ is at most 8ϵℓ Qℓ = O d3/2 log d log , δ and summing over the O(log T ) phases gives the high-probability bound. For the expected regret bound, we run QMC-G-Elim with confidence parameter δ = 1/T . As in the proof of Theorem 18, the failure event contributes at most 1 to the expected regret, and log(dT log T ) = O(log(dT )). This gives the stated bound. The two estimators thus offer a trade-off. The QMC variant avoids the log K factor because√ its high-probability guarantee requires a union bound only over the design support, but it pays the d loss from worst-case error propagation through the prediction weights. By contrast, the single-run design estimate underlying LVQMEDesignEstimate is accurate for each fixed action only with constant probability, and the median amplification needed to cover all active actions is the source of the log K factor in Theorem 18. When K = poly(d), this logarithmic dependence is mild, and the regret of LV-G-Elim is nearly linear in d. For exponentially large action sets with log K = Θ(d), QMC-G-Elim can give a better dimension dependence.

5

Conclusion

We proved the first regret lower bounds for quantum bandits in the reward oracle model of Wan et al. [2023]: Ω(K log(T /K)) for multi-armed bandits and Ω(d log(T /d)) for linear bandits with only d actions. The first bound nearly matches their O(K log T ) upper bound and resolves their question of whether T -independent regret is achievable. Complementing the lower bounds, our algorithm LV-G-Elim attains regret nearly linear in d when K = poly(d), improving the prior d2 dependence and addressing the dimension-dependence question raised by Wan et al. [2023]. Several questions remain open. For multi-armed bandits, it remains to close the logarithmic slack between our Ω(K log(T /K)) lower bound and the O(K log T ) upper bound. For general action sets, the optimal dimension dependence is unresolved. The upper bounds are O(d2 polylog T ) from Wan et al. [2023] and O(d3/2 polylog T ) from a linear-kernel specialization of the analysis of Hikima et al. [2024] (see Appendix B), while our lower bound is Ω(d log(T /d)). For finite action sets with K superpolynomial in d, the nearly linear bound of LV-G-Elim carries an extra log K factor, while the QMC variant removes this dependence at the cost of a d3/2 dimension factor. Whether the two advantages can be combined, for instance by improving the log K dependence toward the classical √ log K, remains open. On the lower bound side, our construction uses only K = d actions and does not rule out a mild K dependence for larger fixed action sets, which would have to remain consistent with the QMC upper bound. Beyond these gaps, our upper bound may extend to the bounded-variance assumption via the estimator replacement sketched in Remark 19, and we leave a full treatment to future work.

23

A

Small-Support Approximate G-Optimal Designs

This appendix gives the details for Lemma 15. The proof uses two standard tools from optimal experimental design: the Kiefer–Wolfowitz equivalence theorem of Kiefer and Wolfowitz [1960] and the rounding theorem and continuous relaxation method of Allen-Zhu et al. [2021]. r be finite with span(Z) = Rr . Then Theorem 22 (Kiefer and Wolfowitz, 1960). Let Z ⊆ RP ⋆ there exists a distribution w ∈ ∆(Z) such that Mw⋆ = z∈Z w⋆ (z)zz ⊤ is positive definite and maxz∈Z z ⊤ Mw−1 ⋆ z ⩽ r.

Theorem 23 (Allen-Zhu et al., 2021, Theorem 2.1). Let z1 , . . . , zN ∈ Rr , and for s ∈ RN ⩾0 write PN P ⊤ 2 N Σs = i=1 si zi zi . Suppose ε ∈ (0, 1/6] and N ⩾ m ⩾ 5r/ε . Let u ∈ [0, 1] satisfy i ui ⩽ m and e r2 ), one can compute sb ∈ {0, 1}N with P sbi ⩽ m such that Σsb ≻ 0 and Σu ≻ 0. Then, in time O(N i ⊤ −1 maxi∈[N ] zi⊤ Σs−1 b zi ⩽ (1 + 6ε) maxi∈[N ] zi Σu zi . In the notation of Allen-Zhu et al. [2021], Theorem 23 is their Theorem 2.1 applied with multiplicity bound b = 1 and the G-optimality criterion fG (Σ) = maxi∈[N ] zi⊤ Σ−1 zi , which satisfies the monotonicity and reciprocal sub-linearity assumptions required there [Allen-Zhu et al., 2021, Fact 1.3]. We also use the continuous relaxation method of Allen-Zhu et al. [2021, Section 3] to compute a constant-factor approximate continuous G-optimal design. Proof of Lemma 15. Let V = span(X ). Choose an orthonormal basis U ∈ Rd×r for V , and write x̃ = U ⊤ x ∈ Rr for each x ∈ X . Since U ⊤ is an isometry on V , the map x 7→ x̃ is a bijection from X onto Xe := {x̃ : x ∈ X }, and Xe spans Rr . We first construct the design in these coordinates. Fix a universal constant ε0 ∈ (0, 1/6] and set m = ⌈5r/ε20 ⌉ ⩽ cs r, where cs := 5/ε20 + 1, using r ⩾ 1. We compute an approximately G-optimal distribution on Xe. Consider the continuous design problem of mass m on Xe, namely minimizing fG (Σu ) = maxx̃∈Xe x̃⊤ Σ−1 u x̃ over fractional designs ⋆ u ⩾ 0 of total mass m. By Theorem 22, there exists a distribution w on Xe with maxx̃ x̃⊤ Mw−1 ⋆ x̃ ⩽ r; −1 ⋆ since fG (tΣ) = t fG (Σ), the scaled design mw is feasible and shows that the optimal value of the mass-m problem is at most r/m. The criterion fG satisfies the convexity and Lipschitz assumptions of Allen-Zhu et al. [2021, Remark 3.4], so the entropic mirror descent method of Allen-Zhu et al. [2021, Corollary 3.9], applied with budget k = m, multiplicity bound b = m, and relative error δ = 1/2, computes a fractional design u0 of total mass m with fG (Σu0 ) ⩽ 32 r/m. Writing u0 = mw fw = P w(x̃)x̃x̃⊤ satisfies max e x̃⊤ M fw−1 x̃ ⩽ C0 r with for a distribution w on Xe, the matrix M x̃ x̃∈X fw is positive definite, since its G-value is finite and Xe spans Rr . C0 := 32 ; in particular, M Following the standard reduction from multiplicity m to the b = 1 case in Allen-Zhu et al. [2021], replace each point x̃ ∈ Xe by m identical copies. The copied list has N = m|Xe| ⩾ m points. On this copied list, let u′ be the fractional design assigning weight w(x̃) to each copy of x̃. Then u′ has all fw ≻ 0, so its G-value is at coordinates in [0, 1], total mass m, and information matrix Σu′ = mM most C0 r/m. Applying Theorem 23 with budget m and ε = ε0 , we obtain an integral design sb on the copied list with total mass m b ⩽ m, positive definite information matrix, and G-value at most C1 r/m, where C1 := (1 + 6ε0 )C0 . Merge identical copies back into the points of Xe. Let sbx̃ be the resulting multiplicity of x̃, e Then |S| e ⩽ m let Se = {x̃ : sbx̃ > 0}, and define π e(x̃) = sbx̃ /m b for x̃ ∈ S. b ⩽ m ⩽ cs r. With P P ⊤ ⊤ e f e Asb = x̃ sbx̃ x̃x̃ ≻ 0, the normalized matrix M = x̃∈Se π e(x̃)x̃x̃ = Asb/m b satisfies f−1 x̃ = m e−1 x̃ ⩽ m max x̃⊤ M b max x̃⊤ A b· sb x̃∈Xe

x̃∈Xe

24

C1 r ⩽ C1 r. m

Now map the design back to the original space. Let S ⊆ X be the preimage of Se under x 7→ x̃, e ⩽ cs r. The original information matrix is and set π(x) = π e(U ⊤ x) for x ∈ S. Then |S| = |S| ⊤ fU . Since M f ≻ 0, we have Range(M ) = V = span(X ) and M + = U M f−1 U ⊤ . Hence M = UM f−1 x̃ ⩽ C1 r. max x⊤ M + x = max x̃⊤ M x∈X

x̃∈Xe

This proves the design bound with CG = C1 . It remains to prove the identities for the prediction weights. For αa (x) = π(a)a⊤ M + x, since x ∈ Range(M ), X X αa (x)a = π(a)aa⊤ M + x = M M + x = x. a∈S

Moreover,

X αa (x)2 a∈S

π(a)

a∈S

=

X

π(a)(a⊤ M + x)2 = x⊤ M + M M + x = x⊤ M + x.

a∈S

The bound x⊤ M + x ⩽ CG r follows from the design bound above. Finally, we account for the running time. The continuous design problem is convex, and a constantfactor approximate solution suffices for the proof above, which can be computed in polynomial time by the ellipsoid method, as noted by Allen-Zhu et al. [2021, Section 3]. The rounding step runs in e r2 ) = O(|X e time O(N | r3 ) by Theorem 23, since the copied list has N = m|X | = O(r|X |) points. The remaining steps, namely the basis computation, copying, merging, and normalization, take time polynomial in |X | and d. Hence the design of Lemma 15 is computable in time polynomial in |X | and d.

B

An O(d3/2 polylog T ) Bound for General Action Sets

In this appendix, we specialize the analysis of Hikima et al. [2024] to the d-dimensional linear kernel. Although they do not state a separate result for quantum linear bandits, their confidence bound, combined with a determinant-based stage-count argument, yields an O(d3/2 polylog T ) regret bound for general, possibly infinite, action sets. Throughout, A ⊆ {x ∈ Rd : ∥x∥2 ⩽ 1} is an arbitrary action set, ∥θ∥2 ⩽ 1, and µ(x) = x⊤ θ ∈ [0, 1], as in Section 2, and we assume T ⩾ 2. The linear kernel k(x, z) = x⊤ z has feature map ϕ(x) = x and reproducing kernel Hilbert space Rd , so the boundedness assumptions of Hikima et al. [2024] hold with supx,z |k(x, z)| ⩽ 1 and ∥θ∥Hk = ∥θ∥2 ⩽ 1. Their eigendecay machinery is needed only to bound the number of stages for infinite-dimensional kernels and is not used here. We run their algorithm QMCKernelUCB with regularization parameter ρ = 1 and tradeoff parameter η = 1, and assume that an action maximizing the UCB index below is attained in each stage (e.g., A compact). Otherwise, a 1/T -approximate maximizer changes the bounds by at most an additive constant. If A = {0}, the regret is identically zero. Otherwise, removing the zero vector does not change the optimal mean, since all mean rewards lie in [0, 1]. Thus we may assume 0 ∈ / A, and hence εs > 0 in every stage below. For the linear kernel, the kernel expressions of Hikima et al. [2024, Proposition 4.1] reduce to weighted ridge regression, and the algorithm takes the same weighted ridge-regression form as QLinUCB of Wan et al. [2023] but uses a smaller confidence radius. Given T , aPfailure probability ⊤ δ ∈ (0, 1), and a stage upper bound M , the algorithm maintains Vs = Id + sk=1 ε−2 k xk xk and P θbs = Vs−1 sk=1 ε−2 ., terminating at round T , it selects xs ∈ k yk xk . In each
stage s = 1, 2, . .√ ⊤ b arg maxx∈A x θs−1 + βs−1 ∥x∥V −1 with βs−1 := 1 + s − 1, sets εs := ∥xs ∥V −1 ⩽ ∥xs ∥2 ⩽ 1, and s−1

s−1

25

plays xs for the next qs := ⌈ Cεs1 log M δ ⌉ rounds, which suffice for the at most qs oracle queries of QMC(Oxs , εs , δ/M ) in Lemma 4, producing an estimate ys of x⊤ s θ when the stage completes. Every stage thus occupies exactly qs consecutive rounds, with xs selected for the entire block even if the QMC call finishes early, unless the horizon is exhausted during the block, in which case the stage remains incomplete and Vs is not updated. The estimator uses only the oracles Oxs and Ox† s , by the accounting of Remark 7. The first ingredient is√the confidence bound of Hikima et al. [2024], specialized to this setting. It √ improves the width 1 + ds in the corresponding step of Wan et al. [2023, Lemma 3] to 1 + s, which is the source of the improvement from d2 to d3/2 . Lemma 24 (Confidence bound; from Hikima et al., 2024, Proposition 4.2 with ρ = η = S = 1). Let m be the total number of stages initiated by the algorithm and suppose M ⩾ m. With probability at least 1 − δ, for every s ∈ {0, 1, . . . , m − 1} and every x ∈ A, we have |x⊤ θ − x⊤ θbs | ⩽ βs ∥x∥Vs−1 , √ where βs = 1 + s. Here the case s = 0 holds deterministically, since θb0 = 0 and |x⊤ θ| ⩽ ∥x∥2 ∥θ∥2 ⩽ ∥x∥V −1 with 0 V0 = Id . The second ingredient is a deterministic bound on the number of stages. Lemma 25 (Stage count). Let m⋆ := ⌈d log2 (1 + T 2 /d)⌉. For any M ⩾ 3 and δ ∈ (0, 1), at most m⋆ stages are completed, and at most m⋆ + 1 stages are initiated before the horizon is exhausted. Proof. By the choice of εs and the matrix determinant
lemma, each completed stage doubles the 2 determinant, since det(Vs ) = det(Vs−1 ) 1 + ε−2 s ∥xs ∥V −1 = 2 det(Vs−1 ), so after m completed stages s−1

det(Vm ) = 2m . Applying the arithmetic–geometricP mean inequality to the eigenvalues of Vm , and −2 m/d using ∥xk ∥2 ⩽ 1, we obtain d 2 ⩽ tr(Vm ) ⩽ d + m k=1 εk . On the other hand, each completed P Pm −1 Pm −2
1/2 stage k occupies exactly qk rounds within the horizon, so T ⩾ m , k=1 qk ⩾ k=1 εk ⩾ k=1 εk P P 2
1/2 using CP for ak ⩾ 0. 1 log(M/δ) ⩾ 1, which holds since M ⩾ 3 and δ < 1, and k ak ⩾ k ak −2 2 , which is Hikima et al. [2024, Lemma C.3] specialized to η = 1. Combining Hence m ε ⩽ T k=1 k the two bounds gives 2m/d ⩽ 1 + T 2 /d, so at most m⋆ stages are completed. At most one further stage is in progress when the horizon is exhausted, and hence at most m⋆ + 1 stages are initiated. Proposition 26 (General action sets). Run the algorithm above with M :=
max{3, m⋆ + 1}. With probability at least 1 − δ, its regret satisfies R(T ) = O d3/2 log3/2 (T ) log dT δ . Taking δ = 1/T gives
3/2 3/2 E[R(T )] = O d log (T ) log(dT ) . Proof. By Lemma 25, the number m of initiated stages satisfies m ⩽ m⋆ + 1 ⩽ M , so Lemma 24 applies, and we condition on its event. Fix an initiated stage s and let x⋆ ∈ arg maxx∈A x⊤ θ. By Lemma 24 applied at stage s − 1 to x⋆ , the selection rule, and Lemma 24 applied at stage s − 1 ⊤ b to xs , we have (x⋆ )⊤ θ ⩽ (x⋆ )⊤ θbs−1 + βs−1 ∥x⋆ ∥V −1 ⩽ x⊤ s θs−1 + βs−1 εs ⩽ xs θ + 2βs−1 εs , so every s−1 round of stage s incurs instantaneous regret at most 2βs−1 εs . This applies to the final stage as well, whether or not it completes, since its action is selected from the confidence set of the preceding stage. Stage s occupies at most qs ⩽ Cεs1 log M stage s is at most δ + 1 rounds, so the regret incurred in √ M 2C1 βs−1 log δ + 2βs−1 εs . There are at most M initiated stages, and βs−1 ⩽ 1 + M , so summing
over stages gives R(T ) = O M 3/2 log M on this event, which is the assembly of Hikima et al. [2024, δ Proposition 5.2] with η = 1. Since M = O(d log T ) and log(M/δ) = O(log dT δ ), the high-probability bound follows. Finally, take δ = 1/T . Since µ(A) ⊆ [0, 1], each round incurs regret at most 1 and R(T ) ⩽ T deterministically, so the failure event contributes at most δT = 1 to the expected regret, and log(M T ) = O(log(dT )) gives the expected bound. 26

References Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. A. Acin. Statistical distinguishability between unitary operations. Physical review letters, 87(17): 177901, 2001. Z. Allen-Zhu, Y. Li, A. Singh, and Y. Wang. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 186(1):439–478, 2021. J.-Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In Colt, pages 217–226, 2009. P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48–77, 2002. R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. De Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778–797, 2001. P. Borwein and T. Erdelyi. Polynomials and Polynomial Inequalities, volume 161. Springer Science & Business Media, 1995. S. Buchholz, J. M. Kübler, and B. Schölkopf. Multi-armed bandits and quantum channel oracles. Quantum, 9:1672, 2025. B. Casalé, G. Di Molfetta, H. Kadri, and L. Ralaivola. Quantum bandits. Quantum Machine Intelligence, 2(1):11, 2020. W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011. A. Cornelissen and Y. Hamoudi. A sublinear-time quantum algorithm for approximating partition functions. In Proceedings of the 2023 annual ACM-Siam symposium on discrete algorithms (SODA), pages 1245–1264. SIAM, 2023. Z. Dai, G. K. R. Lau, A. Verma, Y. Shu, B. K. H. Low, and P. Jaillet. Quantum bayesian optimization. Advances in neural information processing systems, 36:20179–20207, 2023. V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In 21st Annual Conference on Learning Theory, number 101, pages 355–366, 2008. R. Duan, Y. Feng, and M. Ying. Entanglement is not necessary for perfect discrimination between unitary operations. Physical review letters, 98(10):100503, 2007. T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32, 2019. M. I. Ganzburg. On a remez-type inequality for trigonometric polynomials. Journal of Approximation Theory, 164(9):1233–1237, 2012. Y. Hikima, K. Murao, S. Takemori, and Y. Umeda. Quantum kernelized bandits. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. 27

J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363–366, 1960. T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4–22, 1985. T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020. T. Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International conference on machine learning, pages 5662–5670. PMLR, 2020. Y. Li, Y. Wang, and Y. Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173–2174. PMLR, 2019. J. Lumbreras and M. Tomamichel. Linear bandits with polylogarithmic minimax regret. In The Thirty Seventh Annual Conference on Learning Theory, pages 3644–3682. PMLR, 2024. J. Lumbreras, E. Haapasalo, and M. Tomamichel. Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states. Quantum, 6:749, 2022. J. Lumbreras, M. Terekhov, and M. Tomamichel. Learning pure quantum states almost without regret. npj Quantum Information, 2026. N. S. Mande and R. de Wolf. Tight Bounds for Quantum Phase Estimation and Related Problems. Quantum, 10:2140, June 2026. ISSN 2521-327X. A. Montanaro. Quantum speedup of monte carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010. H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527–535, 1952. ISSN 0273-0979. M. Soare, A. Lazaric, and R. Munos. Best-arm identification in linear bandits. Advances in neural information processing systems, 27, 2014. Y. Su, Z. Yang, P. Huang, T. Li, and Y. Ye. Quantum algorithms for bandits with knapsacks with improved regret and time complexities. arXiv preprint arXiv:2507.04438, 2025. Z. Wan, Z. Zhang, T. Li, J. Zhang, and X. Sun. Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10087–10094, 2023. D. Wang, X. You, T. Li, and A. M. Childs. Quantum exploration algorithms for multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10102–10110, 2021. X. Wang, Y.-Z. J. Chen, M. Guedes de Andrade, J. Allcock, M. Hajiesmaili, J. C. Lui, and D. Towsley. Best arm identification with quantum oracles. In The 39th Annual AAAI Conference on Artificial Intelligence, 2025. 28

Y. Wu, C. Guan, V. Aggarwal, and D. Wang. Quantum heavy-tailed bandits. arXiv preprint arXiv:2301.09680, 2023. B. Yi, Y. Kang, and Y. Li. Quantum lipschitz bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 27844–27851, 2026.

29

Related documents

• The Single-Copy Quantum Bandit Is Classical: An Exact Spectral Collapse#1154598
• How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games#1130092
• Simple QKD keyrate computations from tangent-line bounds#996664
• Joint Optimization of Qubit Leasing and Quantum Circuit Distribution#246481
• Pareto Q-Learning with Reward Machines#287146