Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
Authors: Minbo Gao
Zhengfeng Ji
Tongyang Li
Qisheng Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Online learning
quantum computing
zero-sum games
optimistic multiplicative weight update
TL;DR: We propose the first online quantum algorithm for zero-sum games with logarithmic regret under the game setting.

Abstract: We propose the first online quantum algorithm for zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.

Logarithnic-Regret Quantum Learning Algorithms for Zero-Sum Games
Minbo Gao
Zhengfeng Ji Department of Computer Science and Technology, Tsinghua University, Beijing, China ji fengegg edu. cn
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
and University of Chinese Academy of Sciences, Beijing, China gmbl 70t wwg.isiii.a....nee.. org. cn
Tongyang Li
Qisheng Wang
Center on Frontiers of Computing Studies, and School Computer Science, Peking University, Beijing, China tongyangli@pku edu. en
Graduate School of Mathematies, Nagoya University, Nagoya, Japan
Qi shengWanggl wwwp://wwnng99999900 994 com
Abstract
We propose the first online quantum algorithm for solving zero-sum games with (1) regret under the game setting Moreover, our quantum algorithm computes e-approximate Nash equilibrium of an X matrix zero-sum game in quantum time Ö(V m n/52..). Our algorithm standard quantum inputs and generates classical outputs with succinet descriptions, facilitating end-to-end applications. Technically, online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is fast quantum multi-sampping procedure for the Gibbs sampling problem, which may be of independent interest.
Introduction
Nash equilibrium one of the most important concepts in game theory. It characterizes and predicts rational agents' behaviors in non-cooperative games, finding vast host of applications ranging from analyzing wars and designing auctions (35 to optimizing networks [43]
It was shown in Daskalakis et al. [16), Chen and Deng [12] that finding a Nash equilibrium is PPAD-hard for general games. Nevertheless, computing the Nash equilibrium for specific types of games, such as zero-sum games, is particularly interesting. A zero-sum game requires that the utility of one player is the opposite of the other's, condition that often appears in, for example, chess games. Von Neumann's 's minimax theorem [5]] promises that every finite two-player zero-sum game has optimal mixed strategies.
Throughout this paper, Ö(-) suppresses polylogarithmic factors such log(n) and log(1/e), and O*(-) hides quasi- polylogrioyoo factors such (1) and (1),
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Zero-Sum Games. For two-player zero-sum game represented by an m x и matrix A, the Nash equilibrium is the solution pair (x,y) the following min-max problem:
min max x AAy, xcAm yC
where x E Am and y E An are m- and nn-dimensional probability distributions, respectively. Usually, we are satisfied with an approximate Nash equilibrium rather than an exact one. An e-approximate Nash equilibrium is solution pair (x, such that:
max x Ay' min A'y S y y
x'E
Online Learning. Since the matrix A of the zero-sum game usually has a large dimension in practice, is common that we trade accuracy for space and time efficiency. Thus, online learning becomes increasingly significant in these scenarios. Online learning studies the situation when data only available in sequential order and aims at making good decisions in this setup. In evaluating online learning algorithms, regret is an important criterion that measures how good an algorithm is compared with the optimal static loss (see more details in Section 2.3).
The idea of the online learning algorithms for zero-sum games stems from repeated play in game theory, e.g., fictitious play [[I]. Specifically, simulate the actions of two players for multiple rounds. In each round, players make decisions using a no-regret learning algorithm, considering the opponent's previous actions. For example, famous algorithm of this type was proposed in Grigoriadis and Khachiyan [22] inspired by the exponential Hedge algorithm. The algorithm has regret ((VT( and T rounds, establishing the convergence rate of ((1/ VT).
It takes about two decades before the next improvement in Daskalakis et al. 117 to happen, where the authors proposed strongly- -nnouulldee algorithm, achieving Õ(1) total regret if both players use the algorithm. They used the technique of minimizing non-smooth functions using smoothed approximations proposed Nesterov 37,, and this technique was later developed in Nesterov (38, Nemirovski [36 for broader classes of problems. Later, it was found in Syrgkanis et al. (46]
that the optimistic multiplicative weight algorithm also leads to O(1) ) total regret with regret bounded by variation in utilities; this algorithm was recently extended correlated equilibria multi-playe general-sum games in Anagnostides et al. B. It was proved in Hsieh et al. [30] that optimistic mirror
descent with time- varying learning rate can also achieve Ö(1) total regret for multi multi-players. Our quantum algorithm follows the overall idea of the optimistic multiplicative weight update and the regret bounded by variation methods 46
Quantum Computing and Learning. Quantum computing has been rapidly advancing recent years. Specifically, many machine learning problems are known to have significant quantum speedups, c.g., support vector machines [42], principal component analysis [34], classification [31 33], etc. The combination of quantum computing and online learning has recently become a popular topic. For instance, online learning tools have been applied to solving semidefinite programs (SDPs) with quantum speedup in the problem dimension and the number of constraints 7 as an important quantum information task, the online version of quantum state learning has been systematically developed with good theoretical and empirical guarantees
50 g 49 In addition,
For finding the Nash equilibrium of zero-sum games, a quantum algorithm was proposed van Apeldoorn and Gilyén 48 by "quantizing" the classical algorithm in Grigoriadis and Khachiyan [22], achieving a quadratic speedup in the dimension parameters m and n. At the same time, quantum algorithms for training linear and kernel-based classifiers were proposed in Li et al. [33), which have similar problem formulations to zero-sum games. Recently, an improved quantum algorithm for zero-sum games proposed in Bouland et al. [6] using dynamic Gibbs sampling. All of the above quantum algorithms are based on the multiplicative weight update method, and as a consequence, they all share the ((VT) regret bound.
2 The complexity given in Bouland et al. 66 is Ō / + n/225 + 1/E3), wherein the former term m + 2/ dominates the complexity. See Footnote 3 Here, require that the input matrix A satisfies [|| 1. while other works require |Atyl S 1.
4 and Remark 4.4 for discussions.
for

---

Table I: Online Algorithms for e-Approximate Nash Equilibria of Zero-Sum Games.
Approach
Type
Regret
Update Cost Per Round
Classical/Quantum Time Complexity
22
Classical
Ö(vT
Óm + n)
((mm + +
48
Quantum
(
O(ym + n/E)
Ó m + =²
6
Quantum
Õ(VT)
O n/E
0 V m n /
46
Classical
Õ(1)
Ómm)
0mn/e
10
Classical
((1)
O(v mn m + +n)
O (mn + V /mn(m + n)/e)
Our result
Quantum 0(1)
O m + n/tl/
O O (ym + 225)
1.1
Main Result
Our result in this paper establishes a positive answer to the following open question: Does there exist a learning algorithm with Õ(1) regret allowing quantum speedups?
Inspired by the optimistic gellowthh-regularizzee we propose a sample-based quantum online learning algorithm for zero-sum games with Olog (m))
algorithm proposed in Syrgkanis et al. [46].
total regret, which is near-optimal. If we run this algorithm for T rounds, it will compute (1)
approximate Nash equilibrium with high probability, achieving a quadratic speedup dimension parameters In and n. Formally, we have the following quantum online learning algorithm:
Theorem 1.1 (Online learning for zero-sum games), Suppose T < Ö(m + n). There is quantum online algorithm for zero-sum game A E Rm*x with ||A]] 1 such that it achieves a total regret of Ollgg(mm))) mn) with high probability after T rounds, while each round takes quantum time O(T15/m nt.
Our algorithm does not need to read all the entries of the input matrix A at once. Instead, we assume that our algorithm can query its entries when necessary. The input model is described as follows:
Classically, given any E [m], E [n]. the entry As, can be accessed in Ö(1) time.
Quantumly, we assume that the entry Ar,j can be accessed in Ö(1) time coherently.
This is the standard quantumn input model for zero-sum games adopted in previous literature 33
48
See more details in Section 2.4
In addition, same as prior works 48 our algorithm outputs purely classical vectors with succinct descriptions because they are sparse (with at most T nonzero entries). Overall, using standard quantum inputs and generating classical outputs significantly facilitate end-to-end applications of our algorithm in the near term.
As a direct corollary, we can find an e-approximate Nash equilibrium by taking T = Õ(1/e). resulting in quantum speedup stated as follows. A detailed comparison to previous literature is presented in Table [
Corollary 1.2 (Computing Nash equilibrium). There is a quantum online algorithm for zero-sum game A E IR m with || S 1 that, with high probability, computes an E-approximate Nash equilibrium in quantum time Ö(ym (1ym+ri 2
Quantum Lower Bounds. In the full version of 33 they showed a lower bound Q / m + n) for the quantum query complexity of computing an e-approximate Nash equilibrium zero-sum games for constant e. Therefore, our algorithm is tight in terms of mı and n.
II fact, a condition of = Q((m + n) =) ) is required in our quantum algorithm. Nevertheless, our claim still holds because when O((m n1 -1), we directly apply the classical algorithm in Grigoriadis and Khachiyan 22] with time complexity Ö((m m)te?) & Ō(vm 25)
3

---

1.2
Our Techniques
Our quantum online algorithm a stochastic modification of the optimistic multiplicative weight update proposed by Syrgkanis et al. [46]. We choose to "quantize" the optimistic online algorithm because it has a better convergence rate for zero-sum games than general multiplicative weight update algorithms. During the update of classical online algorithms, the update term (gradient vector) is computed in linear time by arithmetic operations. However, we observe that it is not necessary to know the exact gradient vector. This motivates to apply stochastic gradient methods for updates so that certain fast quantum samplers can be utilized here and bring quantum speedups.
Specifically, in our quantum online algorithm, we need to establish upper bound on the expectation of the total regret of our stochastic update rule, and also deal with errors that may appear from noisy samplers. To reduce the variance of the gradient estimator, distributions) at a time. To this end, we develop a fast quantum multi-Gibbs sampler that produces multiple samples by preparing and measuring quantum states.
need multiple samples (from Gibbs
Sample- Based Optimistic Multiplicative Weight Update. Optimistic online learning adds
"prediction loss" term to the cumulative loss for regularized minimization, giving a faster convergence rate than the non-optimistic versions for zero-sum games. Arora al. (4) surveyed the use of the multiplicative weight update method in various domains, but little was known for the optimistic learning method at that time. Daskalakis et al. [17] proposed an extragradient method that largely resembles the optimistic multiplicative weight. Syrgkanis et al. [46] gave a characterization of this update rule-RVU (Regret bounded by Variation in Utilities) property, which is very useful in proving regret bounds. Subsequently. the optimistic learning method is applied to other areas, including training GANs [8] and multi-agent learning
However, when implementing the optimistic learning methods, we face a fundamental difficulty- cannot directly access data from quantum states without measurement. To resolve this issue, we get samples from the desired distribution and use them to estimate the actual gradient. This idea is commonly seen in previous literature on quantum SDP solvers
49 Then we prove the regret bound (see Theorem 3.2p of our algorithm by showing that it has a property similar to the RVU property [46). Moreover, we need multiple samples to obtain a small "variance" of the stochastic gradient (by taking the average of the samples), to ensure that the expected regret is bounded. Our fast quantum multi-Gibbs sampler produces the required samples and ensures further quantum speedups. In nutshell, we give an algorithm (Algorithm[]] (T] which modifies the optimistic multiplicative weight algorithm in Syrgkanis et al. (46) to fit the quantum implementation. This is the first quantum algorithm that implements optimistic online learning to the best of our knowledge.
Fast Quantum Multi-Gibbs Sampling. The key our sample-based approach is to obtain multiple samples from the Gibbs distribution after common preprocessing step. For a vector p E R" with maxic[n] [pal S B. a sample from the Gibbs distribution with respect to p is a random variable j E [*I]
such that Pr 1] Ei, ( Gibbs sampling on quantum computer was first studied in Poulin
exp(pt)
and Wocjan 41 and was later used as subroutine in quantum SDP solvers 77 50 8, 49 However, the aforementioned quantum Gibbs samplers produce one sample from an n-dimensional Gibbs distribution in quantum time Ö(Bvn); thus, we can produce k samples in quantum time Ö(Bk/n). Inspired by the recent work Hamoudi (26) about preparing multiple samples of quantum states, we develop a fast quantum Gibbs sampler (Theorem 4.2p which produces k samples from a Gibbs distribution in quantum time Ö(B nk). Our quantum multi-Gibie sampling may have potential applications in sasple-based approaches for optimization tasks that require multiple samples.
Technically, the main idea is based on quantum rejection sampling 24 39], where the target quantum state (u) is obtained by post-selection from quantum state (Mguess) that is easy to prepare (see Section 4). The algorithm has the following steps (Here we assume f = O(1) for simplicity): To bring (uguess) closer to the target [u), we find the k (approximately) most dominant amplitudes of [u) by quantum k-maximum finding [99 in quantum time Ō O(Vnk), nk). In quantum k-maximum finding, we need to estimate the amplitudes of |u) and compare them coherently, which requires the estimation should be consistent. To address this issue, we develop consistent quantum amplitude
estimation (see Appendix C for our purpose based on consistent phase estimation 2 47,, which is of independent interest. Then, we correct the tail amplitudes of [guuess) by quantum singular

---

value transformation [20]. resulting in an (approximate) target state with amplitude (vvk/n) (see Appendix(] Dfoor details). Finally, we post-select the target state by quantum amplitude amplification in quantum time O(vn/k). This follows that k samples of the target quantum state can be obtained in k. Ö(vn/k) = (vvv(())))) time.
We believe that our technique be extended to wide range of distributions whose mass function is monotonic and satisfies certain Lipschitz conditions.
2 Preliminaries
2.1 General Mathematical Notations
For convenience, we use [n]] denote the set { (1,2,...,n1. We use ej denote vector whose i-th coordinate is 1 and other coordinates are O. For a vector v E IR", Dj is the i-th coordinate of denote the result of f applied ((n))(())))))))))())) )). We use An to represent the set of n-dimensional probability i.e. f(v) = (f(r)), (22), ((t) distributions, i... An := {u E R" Σ di 1, Vi E [n], di 2 0}. Here the i-th coordinate represents the probability of event takes place. We use ||-Il for vector norms. The l norm ||-1|, for vector R" is defined as ||0||| == Σ |0 For two n-dimennional probability distributions
For function f: R + R, we write f(v)
its coordinates,
p.q E Ag. their total variance distance is defined as: dTv(p,9) = llp gl11 2 Ei [p; 9:l We will use E R= to denote a matrix with m rows and n columns. A1j is the entry of A in the i-th row and j-th column. || denotes the operator norm of matrix A. For vector v E R" we use diag(v) to denote the diagonal matrix in RRIX whose diagonal entries are coordinates of with the same order.
2.2 Game Theory
Let us consider two players, Alice and Bob, playing a zero-sum game represented by a matrix A E RR"*" with entries Atj. where [m]] is the labeled action set of Alice and [ı|] of Bob. Usually, Alice is called the row player and Bob is called the column player. Aij is the payoff to Bob and AL is the payoff to Alice when Alice plays action i and Bob plays action j. Both players want to maximize their payoff when they consider their opponent's strategy.
Consider the situation that both players' actions are the best responses to each other. In this case, we call the actions form Nash equilibrium. A famous minimax theorem by von Neumann (51] states that we can exchange the order of the min and max operation and thus the value of the Nash equilibrium of the game can be properly defined. To be more exact, have: min maXyeA, x Ay maXyea, minzeA., xT Ay. Here the value of the minimax optimization problem is called the value of the game. Our goal is to find an approximate Nash equilibrium for this problem. More formally, we need two probabilistic vectors
Am, y E An such that the following holds: maxy'Ed, xT Ay' min AT S We will call such a pair (x, y) an é-approximate Nash Equilibrium for the two-player zero-sum game A. Computing an e-approximate Nash for zero-sum game is not as hard for a general game, For a general game, approximately computing its Nash equilibrium is PPAD-hard 16 12
Here, emphasize an important observation that will be used throughout our paper: constant or multiply by positive constant on all A's entries without changing the solution pair of the Nash equilibrium. This is because, in the definition of the Nash equilibrium, the best response is always in comparison with other possible actions, so only the order of the utility matters. Thus n matrix with
add
without loss of generality, we can always rescale A to (A + c1) / where 1 is an all entries being 1 with c being the largest absolute value of A's 's entries, and let A' = A/ |||]| to guarantee that A has non- -egativte entries and has operator norm no more than 1.
2.3
Online Learning
2.3.1
Notions of online learning
In general, online learning focuses on making decisions in an uncertain situation, where decider not aware of the current loss and is required make decisions based on observations of previous
5

---

losses. To be more exact, we fix the number of rounds T and judge the performance of the algorithm (in the following of this subsection we use "decider" with the same meaning as the "algorithm") in these T rounds. Assume that the decider is allowed to choose actions in the domain X, usually a convex subset of a finite-dimensiona Fuclidean space. Let f E [T] denote the current number of rounds. At round f, the decider chooses an action X X. (The action may depend on the decider's ' previous observation of the loss functions I for all i E [t - 11.) Then the decider will get the loss (x+) for the current round. We assume that the decider can also observe the full information of 14, i.e., the formula of the function. We judge the performance of the algorithm by its regret: RTT) = En= (xx) - min 1 4xx).. Intuitively, the regret shows how far the total loss in T rounds caused by the algorithm is from the optimal static loss.
2.3.2 Online learning in zero-sum games
To demonstrate how to compute the approximate Nash equilibrium using online learning algorithms. we present a useful proposition here. It states that from any sublinear regret learning algorithm A with regret R (T). we can find an ((3(T)/T)-approximma)) Nash equilibrium of the zero-sum game in T rounds.
To be more precise, let us consider the following procedure. Let A be the matrix for the two-player zero-sum game. The algorithm starts with some initial strategies uo E Am, Do E A, for the two players. Then at each round f, for each player, it makes decisions with previous observations of the opponent's 's strategy. In particular, the row player is required to choose his/her action u, E Am after considering the previous loss functions & (x() = o/ x for i E [t 1]. Similarly, the column player chooses his/her action D; E A with respect to the previous loss functions (y) = - uu Ay for E [t - 1). After both players choose their actions at this round t, they will receive their loss functions g: (xx == 1. ATx and h2 = ut Ay. respectively.
Suppose after T rounds, the regret of the row player with respect to the loss functions g: (x) is RT)., and the regret of the column player with loss functions h (y) is RR We can write the total regret RTT) + R' (T) explicitly: R(T) + (T) = T(max (D, ATa) min (u, Ad)), ), where the
average strategy is defined as A = Σ /:/T, a E._ D./T. This pair is a good approximation of the Nash equilibrium for the game A if the regret is O(T).
2.4 Quantum Computing
In quantum mechanics, a d-dimensional quantum state is described by a unit vector v (vo, P4.-.., usually denoted as (D) with the Dirac symbol |-), in a complex Hilbert space CV. The computational basis of Cd is defined as (l() [[=)]==0 where (i) = (O, 0, 1,0,...,00) O)T with the i-th (0-indexed) entry being 1 and other entries being O. The inner product of quantum states (D) and (w) is defined by (u) E D. wi where 2" denotes the conjugate of complex number 2. The norm of (b) is defined by ||bb| || = (olo). The tensor product of quantum states (D) E Cdi and (w) E Cd2 is defined by (D) & (w) (Powo, -0 E Cdid2, denoted as (b) (z)) for short.
A quantum bit (qubit for short) is a quantum state (4) in C2, which can be written as |4) = a a + B|1) with 22|2+10 | = 1. An rt-qubit quantum state is in the tensor product space of N Hilbert spaces C..i.e., (C2)om 2 with the computational basis {10), (1),,..,,12"
1)}. To obtain classical information from an n--uubit quantum state (D), we measure (8) on the computational basis and obtain outcome with probability p(i) = 1 for every 0 S < 2", The evolution of a quantum state lo) is described by unitary transformation U: (o) + U|a) such that uu+ u'u I, where Lt is the Hermitian conjugate of U, and I is the identity operator. A quantum gate a unitary transformation that acts on 1 or 2 qubits, and quantum circuit is a sequence of quantum gates.
Throughout this paper, we assume the quantum oracle O for matrix A E R=XH which is unitary operator such that for every row index i E [m] and column index j E [n]. O OΛlilãlo) = i)) Intuitively, the oracle OA reads the entry A, and stores in the third register; this is potentially stronger than the classical counterpart when the query is a linear combination of basis vectors, e.g.. Et agg) lix) lik) with Ee la 2 = 1. This is known as the superposition principle in quantum computing.

---

Note that this input model for matrices is commonly used in quantum algorithms, e.g., linear system solvers [28] and semidefinite programming solvers
49
quantum (query) algorithm AA a quantum circuit that consists a sequence of unitary operators ...,
G₁, G2.-.., GT. each of which is either quantum gate quantum oracle. The quantum time com- plexity of A is measured by the number T of quantum gates and quantum oracles in A. The execution of A on n qubits starts with quantum state (0) @n, then it performs unitary operators G1, G2...., GT on the quantum state in this order, resulting in the quantum state [4) = GT G2G [0] S7 Finally, we measure (Φ) on the computational basis (i) for S i 2", giving a classical output i with probability (i
3 Quantum Algorithm for Online Zero-Sum Games by Sample-Basel Optimistic Multiplicative Weight Update
Now, we present our quantum algorithm for finding an approximate Nash equilibrium for zero- sum games (Algorithm[] D. This algorithm is modification of the optimistic multiplicative weight algorithm [46), which we use stochastic gradients to estimate true gradients. This modification utilizes the quantum advantage of Gibbs sampling (as will be shown in Section 4). It is the source of quantum speedups in the algorithm and also the reason that we call the algorithm sample-based. based. To this end, we first give the definition of Gibbs sampling oracles.
Definition 3.1 (Approximate Gibbs sampling oracle). Let p E R" be an n-dimensional vector, c <> the approximate error. We let of (k, denote the oracle which produces independent samples from a distribution that is e-close to the Gibbs distribution with parameter p in total variation distance. Here, for random variable j taking value in [n] following the Gibbs distribution with parameter p. we have Pr| i = exp(pi) exp(p:).
Algorithm Sample-Based Optimistic Multiplicative Weight Update for Matrix Games
Input: A E IR"XX", additive approximation E, approximate Gibbs sampling oracle Gibbs with error EG. total episode T. learning rate À E (0, /366)
Output: (f, 8) as the approximate Nash equilibrium of the matrix game A.
1: Initialize A + Om. 0 +- O,, X1 + 0m. 1/1 + O,,
2: Set g1 f X1, h1 f 5/1
3: for port=1 l,.
T do
4: Get T independent samples ii.
it from the Gibbs sampling oracle Gihhb 5: Choose the action L = Ei==1 et,, /T.
Ah, (T,
6: Update X1+1 + Xt + AC., 81+1 f- Xt+1 + AC.. a +- + +t+
7: Get T independent samples 11.12....,, from the Gibbs sampling oracle 0 ATg EG).
8: Choose the action 1/+ = =KK=1 f// /T.
9: Update VI+1 &- Vt + Anp h1+1 + Vi+1 + Atp. 0 O5 0 ++ tnl-
10:
end for
11:
return (),
Suppose the zero-sum game is represented by matrix A E R with |||]| < 1. Our sample- based optimistic multiplicative weight update algorithm is given in Algorithm T Algorithm is inspired by the classical optimistic gellow-thereggllarize-eeedd information). In that classical algorithm, the update terms are essentially E[[e] and E(m,). which are computed deterministically by matrix arithmetic operations during the update. In contrast, we do this probabilistically by sampling from the Gibbs distributions and ç, and 1); Line 5 and Line 10 are the corresponding averages of the samples. For this to work, we need to bound the expectation of the total regret (see Appendix [ based on the RVU property (Definition A.2).. Technically, the h variances of LA and 17: turn out to be significant in the analysis. To reduce the variances, we need multiple independent samples identically distributed from Gibbs distributions (see Line 4 and Line 7 in Algorithm[] []. Because of the randomness from Gibbs sampling oracles, the total regret RTT) + (T) of Algorithm| [ is random variable. Nevertheless, we can bound the total regret by (mn) with high probability follows.
algorithm (see Appendix Afror more
7

---

Theorem 3.2. Let = 1/T. After T rounds of playing the zero-sum game A by Algorithm 1 the total regret will be bounded by
R(T) + (T) S 144A 3log(mn)
+ 12,
with probability at least 2/3. Then, for any constant À E (0, /3/6), the total regret is ((log(m)) mn)).
Moreover, if we choose T ((1/e), then Algorithm will return E-approximate Nash equilibrium of the game A.
The proof of Theorem 3.2 is deferred to Appendix B B.2
Combining Theorem 3.2 and our fast quantum
multi-Gibbs sampler in Theorem 4.2 (which will be developed the next section), we obtain quantum algorithm for finding an e-approximate Nash equilibrium of zero-sum games.
Corollary 3.3. If we choose T = ((1/E) and use quantum multi-Gibbs sampling (Algorithm) 2 with EG 1/T, then Algorithm will return an e-approximate Nash equilibrium quantum time Õ(v ))
4 Fast Quantum Multi-Gibbs Sampling
In [ the vectors h, and & updated in each round are used to generate independent samples from Gibbs distributions Gibbs and Gibbs. Here, h; and gi are supposed to be stored in classical Ah, registers. To allow quantum speedups, we store h; and gt in quantum-read classical-win random access memory (QRAM) [2I]. which is commonly used in prior work [49] 6]. Specifically, QRAM can store/modify an array 41 42, .. ag of classical data and provide quantum (read-only) access to them, i.e., unitary operator UORAM given such that UQRAM: [ (0) + [ lay],;)- Without loss of generality (see Remark 4.3), suppose
have quantum oracle O for A R"** with Ai, E [0, 1], and QRAM access to vector E R" with 2 O. We also need the polynomial approximation of the exponential function for applying the QSVT technique [20]:
Lemma 4.1 (Polynomial approximation, Lemma of 48
). Let B 2 1 and Ep E (0,1/2). There classically efficiently computable polynomial PB R[x] of degree O(Blgg(c7)) such that
IPp(x) < f.ror x E [-1,1], and maxxel-1.0) (x(x)) - exp(Bx) Ep.
Then, we can produce multiple samples from Gibbs efficiently by Algorithm on a quantum computer. Algorithm is inspired by Hamoudi 26 about preparing multiple samples of quantum state, with quantum access to its amplitudes. However, we do have access the exact values of the amplitudes, which are (Az); in our case. To resolve this issue, we develop consistent quantum amplitude estimation (see Appendix C to estimate (Az); with a unique answer (Line 1). After having prepared initial quantum state [lguess), we use quantum singular value decomposition (20 to correct the tail amplitudes (Line 6), and finally obtain the desired quantum state (äGabs) by quantum amplitude amplification
[9] (Line 7). We have the following (see Appendix D for its proof):
Theorem 4.2 (Fast quantum multi-Gibi sampling). For k E [n], we Ep @ /n), then Algorithm 2 will produce k independent and identical distributed samples from a distribution that is cloclose to Gibbs in total variation distance, in quantum time Ö(Bvnn) nk).
Remark 4.3. If A E R is not a square matrix, then by adding 0's we can always enlarge A to an (m + n) dimeensoonl square matrix. For Gihhs required in Algorithm 1 note that Gihhb Ajh;
indicates the same distribution Gibhs Ah, where 1 has the same size as A with all entries being 1. From the above discussion, we can always convert A to another matrix satisfying our assumption, i..., with entries in the range [0, 1].
Remark 4.4. The description of the unitary operator uex defined by the polynomial P2s can be classically computed to precision Ep in time Ō(B3) by Haah 25), which is Ō(1/=²) in our case as B < AT = @(1/E) required in Corollary 3.3 This extra cost can be neglected because Ō(Vm m + 2.5) dominates the complexity whenever = ((( ( Remark 4.5. Our multi-Gibbs sampler is based on maximum finding and consistent amplitude estimation, with a guaranteed worst-case performance each round. In comparison, the dynamic Gibbs sampler in (6] maintains hint vector, resulting in amortized time complexity per round.

---

Algorithm 2 Quantum Multi-Gibbs Sampling Giibbs Ek,
Input: Quantum oracle Oa for A E R QRAM access to E R" with |z||| S p. polynomial Pas with parameters ep by Lemma 4.1 number of samples. We write и Az.
Output: k independent samples 11, .g.
1: Obtain Oz: (1)(0) + [i) (;)) by consistent quantum amplitude estimation such that ij 1 új S
N; +1
2: Find the set _ [n]] of indexes of the largest i by quantum k-maximum finding, with access
to Og-
3: Obtain ūN for all E S from Og, then compute i = min û and W = Σ ex) + iES
iES
(n kn-k) (np((")) 4: for l I,...,k do
5: Prepare the quantum state |Mguess) Lics
i) + Eies exp(il
6: Obtain unitary Lrxp such that (o QSVT.
diag P2 max ū, a² 1)) /48 by
7: Post-select (aGibbs) (0) (O]@aL/eNP) Mguuess) [0) @r by quantum amplitude amplification.
8: Let ig be the measurement outcome of (/Gibbs) in the computational basis.
9: end for
10: return 12.
5 Discussion
In our paper, we propose the first quantum online algorithm for zero-sum games with near-optimal regret. This is achieved by developing sample-based stochastic version of the optimistic multi- plicative weight update method [6]. Our core technical contribution is a fast multi-Gibbs sampling, which may have potential applications in other quantum computing scenarios.
Our result naturally gives rise to some further open questions. For instance: Can we improve the dependence on for the time complexity? And we further explore the combination of optimistic learning and quantum computing into broader applications? Now that many heuristic quantum approaches for different machine learning problems have been realized, e.g.in Havlfčck et al. [29], Saggio et al. [44), Harrigan et al. (27). can fast quantum algorithms for zero-sum games be realized in the near future?
Acknowledgments
We would like to thank Kean Chen, Wang Fang, Guan, Junyi Liu, Xinzhao Wang, Chenyi Zhang, and Zhicheng Zhang for helpful discussions. MG would like to thank Mingsheng Ying for valuable suggestions.
Minbo Gao was supported by the National Key R&D Program of China (2018YFA0306701) and the National Natural Science Foundation of China (61832015). Zhengfeng was supported by startup fund from Tsinghua University, and the Department of Computer Science and Technology. Tsinghua Univeristy. Tongyang Li was supported by startup fund from Peking University, and the Advanced Institute of Information Technology, Peking University. Qisheng Wang was supported by the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grants No. JPMXS0120319994,
References
[1] S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. Online learning of quantum states. In Advances in Neural Information Processing Systems, vol- ume 31, 2018. URL httppss//ppooceednnggee/ c1a3d347 La5aaa53331ccae057700-0---e2
[2] A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear alge- bra problems. In Proceedings of the 29th Symposium Theoretical Aspects of Computer

---

Science, volume 14, pages 636-647 2012. URL htwpppppe/ha...accceeeeeeeeeeee. Er/hal-00578197
[3] I. Anagnostides, C. Daskalakis, G. Farina, M. Fishelson, N. Golowich, and T. Sandholm. Near- optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Anmual ACM SIGACT Symposium on Theory of Computing, pages 736-749, 2022. URL https: /ttp:://dooo.ee /tct:p::/ddi..rg//g1// 001gg/10.114//5111 9935. 3520031
[4] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta algoritm and applications. Theory of Computing, 866):121-164, 2012. URL hittps://doi.rrg/
4086/Eoc. 2012. v008a006
[5] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating Hamiltonian dynamics with truncated Taylor series. Physical Review Letters, 114(9)0900502, 2015. URL
https://do: http:://doi.org/////// org/ www.1111c///y/esttte..m 114. 096502
[6] A. Bouland, Y. M. Getachew, Y. Jin, A. Sidford, and K. Tian. Quantum speedups for zero- sum games via improved dynamic Gibbs sampling. In Proceedings of the 40th International Conference on Muchine Leurning, volume 202, pages 2932-2952, 2023. URL https://
proceedings mlr. wwwpss/vw2//ouu....eee
[7] F. G. Brandão and K. M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science, pages 415-
426, 2017. URL https:://oo..org//..... 11t9///01...11..1..11 2017. 45
[8] F. G. S. L. Brandão, A. Kalev, Li, C. Y-Y. Lin, K. M. Svore, and X. Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium Automata, Languages, and Programming, volume 132, pages 27:1 17:14, 2019. URL htth::::::// doi org 100 w2w.:114422............. ICALP 2019.27
[9] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Information, 305:53-72 2002. URL hatpp:://oi..ooot #090/conm, 1090/coom/330/05222
[10] Y. Carmon, Y. Jin, A. Sidford, and K. Tian. Variance reduction for matrix games. In Advances in Neural Information Processing Systems, volume 32, pages 11377- 11388, 2019. URL
htw.:oocceednnnn..enne.sss. www.nnuuii.... wttpc///ppppc wttpcc/pppppp....3. 201er////////e file/
[11] N. Cesa- and G. Lugosi Prediction, Learning, and Games. Cambridge University Press, 2006. htt.tttpss//oo..r//1111111001110
[12] X. Chen and X. Deng. Settling the complexity of two-player nash equilibrium. Proceedings of the 47th Annual Symposium Foundations of Computer Science, pages 261-272, 2006.
2006. 69
[13] X. Chen, E. Hazan, T. Li, Lu, X. Wang, and R. Yang. Adaptive online learning of quantum states, 2022. URL / http:///wwwlvv.o/a////////s 2206
00220
[14] Y. Chen and X. Wang. More practical and adaptive algorithms for online quantum state learning, 2020. URLhttts:://axtt
abs /2000 01013]
[15] A. M. Childs and Wiebe. Hamiltonian simulation using linear combinations of unitary
operations. Quantum Information and Computation, 12(11-12):0119244 2012. URL https
//doi. .rgg 26421//1C.22.111122
[16] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-255 2009. URL
8 lam.org/dot /1tp://////001111771553333333
[17] C. Daskalakis, A. Deckelbaum, and A. Kim. Near-optimal no-regret algorithms for zero-sum games. Games and Economic Behavior, 92:327-348, 2015. URL http:/ttts///o..org///////
1016 j. geb. 2014. 01. 003
10

---

[18] C. Daskalakis, A. Ilyss, V. Syrgkanis, and H. Zeng. Training gans with optimism. In Proceedings of the 6th International Conference on Learning Representations. 2018.
[19] C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310-1328, 2006. URL http::/doi. org/ 10. 10.1137/050644733
[20] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 5 Anmual ACM SIGACT Symposium on Theory of Computing, pages 193-204, 2019. URL
ht http://oooooooo111111111//1/2132
[21] V. Giovannetti, S. Lloyd, and L. Maccone. Quantum random access memory. Physical Review Letters, 100(16):10000,, 2008 URL
100. 160501
[22] M. D. Grigoriadis and L. G. Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2):53-58, 1995. httph:h/t///bbt
org/10 10l.1111611666500
(95) 00032-0
[23] L. Grover and T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions, 2002.
[24] L. K. Grover. Synthesis of quantum superpositions quantum computation. Physical Re- view Letters, 85(6):1334, 2000. URL /tt.://s///ol...or/....11///////
1334
[25] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. URL httpt://p/::d
[26] Y. Hamoudi. Preparing many copies of quantum state in the black-box model. Physical Review A, 105(6):062440, 2022. URL 2200:1/2223111111-2212
062440
[27] M. P. Harrigan, K. J. Sung, M. Neeley, K. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, Ben Chiaro, R. Collins, W. Courtney, S. Demura, A. Dunsworth, D. Eppens, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, S. Habegger, A. Ho, Hong, T. Huang,
L. B. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, N. Korotkov, Kostritsa, D. Landhuis, P. Laptev, M. Lindmark, M. Leib, O. Martin, J. M. Martinis, J. R. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, W. Mruezkiewicz, J. Mutus, O. Naaman, C. Neill, F. Neukart, M. Y. Niu, T. O'Brien, B. O' O'Gorman, F. Ostby, A. Petukhov, H. Putterman, C. Quintana, P. Roushan, N. C. Rubin, D. Sank, A. Skolik, V. Smelyanskiy, D. Strain, M. Streif, M. Szalay, A. Vainsencher, T. White, J. Yao, P. Yeh, A. Zalcman, I.. Zhou, H. Neven, D. Bacon, E. Lucero, F. Farhi, and R. Babbush. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17(3):332-336, 2021. URL /ttt::::/ool.orr/1101133333 $41567-020 00100-1105-0
V. Klimov,
[28] A. W. Harrow A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. equation Physical Review Letees, 103(15))150502, 2009. URL htt.https//ooll.og//00000000 PhyskevLett wtteevveeet.......... 103.150502.
[29] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature. 567(7747): 209-212, 2019, httlhttts///d:. wtwpo/ooooo..ooooo 1038//11..100///1
[30] Y.-G. Hsieh, K. Antonakopoulos, and Mertikopoulos. Adaptive learning continuous games: Optimal regret bounds and convergence to nash equilibrium. In Proceedings of the 34th Conference on Learning Theory, volume 134, pages 2388-2423 2021. URL https!
//proceedings mlr, pttps//////ssisileaaaa..
11

---

[31] A. Kapoor, N. Wiebe, and K. Svore. Quantum perceptron models. In Advances in Neural Infor- mation Processing Systems, volume 29, 2016. URL /
[32] I. Kerenidis and A. Prakash. Quantum recommendation systems. In Proceedings of the 8th
Innovations Theoretical Computer Science Conference, volume 67, pages 49:1-49:21, 2017.
URL //t::///oi..o http:///i....g/.....//.111111 4230/LIPICSS ITCS TCS.2017. 2017.
[33] T. Li, S. Chakrabarti, and X. Wu. Sublinear quantum algorithms for training linear and kernel- based classifiers. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 3815 3824, 2019. URL
mlr. press/v97/
1119b.ber html
[34] S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):63--633, 2014. URL htttt::t///oo...ooo org/ http:///11..111////g//eee./ 1038//pphs332299
[35] R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73,
1981. http:/t:/a...oogg//////// 1287 2022//000002// moorr 6.1.6..... 58
[36] A. Nemirovski. Prox-method with rate of convergence o for variational inequalities with lipschitz continuous monotone operators and smooth
saddle point problems.
SIAM Journal on Optimization, 15(1):229 251, 2004. httts:ts::///d .rgg 0. 1
$1052623403425629
[37] Y. Nesterov. Smooth minimization of non-smooth functions. Muthematicall ProgiiccaalloPruui Programming, 103 (1):127-152, may 2005. URL httpp:://cc..rrt. /1////0000 10. 0007//111770000055500
[38] Y. Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1):235-26) 2005. URL https:://6l..0r/200..11
$1052623403422288
[39] M. Ozols, M. Roetteler, and J. Roland. Quantum rejection sampling. ACM Transactions Computation Theory, 5(3):11:1-33, 2013. (ttp:/tpp://bb...o//..0.1//////3
[40] S. Pattathil, K. Zhang, and A. Ozdaglar. Symmetric (optimistic) natural policy gradient for multi-agent learning with parameter convergence, 2022. URL htt.t:ttp//eae. /tttps://axxiv..o////...
2210. 12812
[41] D. Poulin and Woejan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with quantum computer. Physical Review Letters, 103(22):20000,, 2009. URL httpt::t:///tt.t.. wtt.://..00....../../a.o......//
103 220502
[42] Rebentrost, M. Mohseni, and S. Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113:130503, Sep 2014. URL httphtttss://do..rr
10. N0.1103/PhysRevlets 113. 130503
[43] T. Roughgarden and E. Tardos. How bad selfish routing? Journal of the ACM, (9()):36-236 mar 2002. URL https://doi. org 10. 1145/ 00116611111115....
[44] V. Saggio, B. E. Asenbeck, A. Hamann, T. Strömberg. P. Schiansky, V. Dunjko, N. Friis, N. C. Harris, M. Hochberg, D. Englund, S. Wölk, H. J. Briegel, and P. Walther. Experimental quantum speed-up in reinforcement learning agents. Nature, 571(799))2229-233 2021. URL https://dom wtw.ooo..rg//.... 1038/
021-0321--0000000 03242-7
[45] т. C. Schelling. The Strategy of Conflict: with new Preface by the Author. Harvard university press, 1980.
[46] V. Syrgkanis, Agarwal, Luo, and F. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 2989-2997, 2015.
[47] A. Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 881-890, 2013. URL.
https: / doi org 1ttp:/11..11/2228881 2488720
12

---

[48] J. van Apeldoorn and A. Gilyén. Quantum algorithms for zero-sum games, 2019. URL
http://arxiv.org wwss/s90a 03180
[49] van Apeldoorn and A. Gilyén. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium Automata, Languages, and Program- ming. volume 132. pages 99:1-99:15, 2019. URL
ICALP 20 2019.11.0 99
[50] J. van Apeldoom, A. Gilyén, S. Gribling, and R. de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In Proceedings of the 58th Anmual Symposium on Foundations of Computer Science, pages 403-414, 2017. htttssss:: wtt/////..../.1.../////0/0.....
Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100(1):295-320, [51] 1928.
[52] F. Yang, J. Jiang, J. Zhang, and X. Sun. Revisiting online quantum state learning. Proceedings of the AAAI Conference on Artificial Intelligence, 34((4)::607-6611 2020.
13

---

A Revisit of Optimistic Online Learning
In this section, we briefly review some important properties the classical optimistic online learning algorithms. Some of the propositions in this section will be frequently used in the proof of the regret bound.
For convenience, we will use (-()) to denote the negative entropy function, i.e., yp An -> R. (p)) Dn P: log py- Note that log stands for the natural logarithm function with base e.
For a vector norm ||- its dual norm is defined as:
lyll. = max ( (xx,y) || S 11.
Proposition A.1. Let a vector in n n--iiensional space. pf = arg min {(p, + 4 (p)}, then pedn
p" can be written as:
exp (-L)
p'
1xxp (-L)
and vice versa.
Proof. Write L (L1, Ln) By definition, we know that p" is the solution to the following
Ln).
convex optimization problem:
minimize P1 Pr. Pn
Σ
P:L
log Pi
subject to
Σ Pi 1,
1=1
Vi, Pi 2
The Lagrangian is
((,,uv) Σ L Pi log Pi
Σ u:P: +
Σ 1=1
Pi
1=1
From KKT conditions, we know that the stationarity is:
L + 1
log p; u; + 0.
(1)
The complementary slackness is:
uip:
The primal feasibility is
Vi, 2 0; Σ 1-1
P: 1.
The dual feasibility is
1; 0.
иj * then pi O. from stationarity we know 4; co, but that violates the dual feasibility. So we can conclude that = 0 for all i E [m]. thus a exp(-Li) and the result follows.
Now we present generalized version of the optimistic multiplicative weight algorithm called optimisitically follow the regularized leader (Opt-FTRL) in Algorithm 3 In the algorithm, my has the same meaning as mt) for notation consistency.
Algorithm 3 Optimistic hollow-teeregullaiiee-leaad
Input: The closed convex domain X.
Output: Step size A, loss gradient prediction m.
Initialize Lo 0, choose appropriate mi.
for | 1,..., do
Choose x; arg min {A (L,-1 + M4 x) (x)).
xEX
Observe loss 4, update I 14-1 + 4.
Compute mi-1 using observations till now.
end for
14

---

Now we study a crucial property that leads to the fast convergence of the algorithm, called the Regret bounded by Variation in Utilities (RVU short). For simplicity, we only consider the linear loss function (x) = (4, x). (There is little abuse of notation here.)
Definition A.2 (Regret bounded by Variations in Utilities (RVU), Definition 3 in Syrgkamis et al. [66). Consider an online learning algorithm A with regret R(T) oTT), we say that it has the property of regret bound by variation in utilities if for any linear loss sequence I 11,42...,44 /T, there exists parameters & > 0,0 < $ S Y such that the algorithm output decisions x1, x2, .....,,............... XT, XT that satisfy:
Σ (1xxx
min Σ (4,x) S a + Σ xEX
1441
41I. - 7 Σ x x:112,
where ||- is the dual norm of |1-11-
We do not choose the norm be any specific one here. In fact, Syrgkanis et al. 46 have already hhelwwwhh-regullrized--
shown that the above optimistic respect to any norm ||-|| in which the negative entropy function yp is 1-strongly convex. So, from Pinsker's inequality, for l2 norms the following result holds:
algorithm has the RVU property with
Proposition A.3 (Proposition 7 in Syrgkanis et al. 46 ). we choose m; 14-1 in the optimistic follow-the thw-ttteeeeeeeee setee--egalarrdd--eee variation in utilities property with the parameters log n / A, λ Andd y = 1/ (4A). where is the dimension X.
algorithm with step size X 1/2, then it has the regret bound by
B Regret Bound and Time Complexity of Our Algorithm
B.1 Ideal Samplers
We assume that after the execution of our algorithm, the sequences we get are (x),,))) exp Ahr)
T+1 I+1 and
(-A))l and R = corresponding Gibbs distribution, will first assume that the Gibbs oracle in our algorithm has no error (i.e. EG = 0) until Theorem B.5 proved.
(gg, ht T respectively. We denote 44 ==
Texp (ATg:)] to the
exp (ATge)
Observation B.1. The sequence {ut) can be seen as the decision result of applying optimistic FTRL algorithm to the linear loss function ATj; with linear prediction funcctin Atj; and similarly for fur 1 with the loss function AT the prediction function -AT,--1-
exp (-h))
Proof. By symmetry, we only consider u, Since u, = write
1eepp Ahill from Proposition A.1 we can
14 = arg min {(Ahi, u) + (4))-
uEAm
Then we notice the iteration of A Algorithm T gives
h = A
Σ 11
+ A1
So from the definition of the Algorithm we know that our observation holds.
This observation, together with Proposition A.3 v E Ag, we have:
gives the following inequalities. For any An
log m
Σ (u - u, And) <
+
[A - -
Σ
|4441 - 11l12,
(2)
A
41
log
1 T-1
(Dr U. ATT <
A
Σ
Σ
||
Dell
(3)
A
4A
15

---

However, we find that the loss function is slightly different from what we expect.
Let us consider the difference 9: = A A 1/1)) and Pt = AT (e), have the decomposi- tion of the regret:
Σ (ut u, Avi) = Σ (4--wa U, Ani) + Σ (ut n,
Notice that E[q.]] Lemma B.2.
1B [ppi]
O, we have:
IE Σ (ut u, u,
= -, E Σ (ot U, u, =0
Proof. By symmetry, we only prove the case for u. It suffices to prove that for every t, E [u u, 9:):] = 0. Since u is fixed, E [(u, 9:)1 = (u, IB [q.]) = O.
Now consider E (u)). notice that given 7),, "/,...., then u, is constant. We have:
E [ut, [
E [E] [(u, q1) 1//1 7/2 ... 7/2 1]] E (u,, IE 1q (/1, 7/2 //-1)>]]
= E [1 0)] = 0.
Now we are going to bound the term Σ TEA|||(11:: [|]([]+111 101+111100 n0112.
Lemma B.3.
T
A - < 6
Σ
||:411 - Del12
(4)
1=1
T-1
- 31)1 2 6 Σ
|| 1
(5)
Proof. Recall that by rescaling we have ||||| < 1. Hence,
A - 11)11
Mh-1 1//11
Write M/+1 - 1/+ = (1/411 - 11+1) + (V/+1 - v/) + (0:
1/:)) Using the triangle inequality the I
norm and the Cauchy inequality (a + b bcc)² c)² < 33a² 62 + c2)
we get
T
Σ |1 -
11+1-
mrl1 < 6
Σ || - +3 Σ
|1/11 - 2
(6)
Similarly, have:
T E 13+1 - 21ll2 < 6
T-1
Σ
11
uell
+3
Σ
1441 -
Observing that in our algorithm we collect T independent and identically distributed samples and take their average, we have:
E
11:
1,112
1,
E
Σ || - 0t11?
1.
Combining the result above, just get the desired equation.
16

---

We also need the following lemma to guarantee that the sum of the regret is always non negative. Lemma B.4. The sum of the regrets of two players Algorithm Tis always non non-negant non-negative. In other words:
T Σ
max max #Edm o'án
wn u, Avi)
Σ (0)
-ATu) 2 0.
Proof.
max max HEdm D'Ay
[1 - u, Avi) +
(i) - 0, - AATu))
Σ u, Avi) + Σ (e,ATu)
max max NEAm DEAr
max v
(1, (T))
min Σ
(u, 2
ucAm 1=1
The last step is because
max DC
(z, AT)) 2
Σ
3 T,
4t
1=1
and
min MC Am
Σ Au,) v
A
Σ
U1
u
Combining the result above, finally have the following theorem.
Theorem B.5. Suppose that in our Algorithm I we choose the episode T @(1/e), and choose
constant learning rate that satisfies X < /3/6. Then with probability at least 2/3 the total regret of the algorithm is Õ(1). To be more clear, we have:
3 3lggmmn)
T max (2, ATa) min (u, Ad) oCAn
36A +
vCdm
A
and our algorithm returns an e-approximate Nash equilibrium.
Proof. Adding the inequalities and 3 together, we get
log m
log 11
Σ (n
And) +
(D D, ATG() <
A
A
(1) 11 - 11)1
10 1/11
(8)
41
1
A
[[AT(1 -1)11
|| uzl12
4A
Taking expectation, and using the inequalities
6
we have
E
A
A
A
-1))1
1
|| 22l1
41 1=1
1=1
T Σ
3A
E
|| vell
+ + EE
11 12
41
< 6A.
17

---

Similarly we can prove
A
AT (G 21)12-
u1l?
S 61.
41
So, taking expectations of Equation
g and using the above inequalities and the Lemma B.2 we get
(o) - 0, - ATu)) S 12A + log(mn)
E
max Σ MCAm 1=1
(ur - u, Avi) + max vCA, 1=1
Σ
-,--,,AAu))
(9)
A
Using the fact that
E[a]] T
EE E[ee].
E(6)
E B(orl
we have
T 121 + log(mn)
F max (u, A ATa) min (u, Ad)
(10)
pCAn
NCAm
A
By Lemma B.4 we know that the regret is always non-negative. So applying Markov's inequality, we know with probability at least 2/3, the following inequality holds:
max (v, ATa) min (u, A0) = 7 36A + DEAn
3 3log(mn)
EEAm
A
B.2 Samplers with Errors
Theorem B.6 (Restatement of Theorem 3.2 Suppose that in our Algorithm we choose the episode
= Õ(1/e), and choose a constant learning rate that satisfies < À /3/6. The quantum implementation of the oracle in the algorithm will return T independent and identically distributed samples from a distribution that is EG- Eg-close to the desired distribution in total variational distance in quantum time T-.
Then with probability least 2/3 the total regret of the algorithm Ö(1+ec/4 and the algorithm returns an Õ( + -approximit Nash equilibrium in quantum time Ô(T /E).
+
Proof. We will follow similar steps of proof for Theorem B.5 Since the sampling is not from the ideal distribution, we must bound the terms where 7); and Ge take place.
Notice that in this case, have
| - Ein]I < || E[m]l S EG.
So for the term qt in Lemma B.2 we now have the bound:
E
[u u A(p y:))
E
Σ (1) u, A(D - -(Tm-()))))
E
Σ (n) u, A(E(p) n1))
E
Σ (u u1 -,,(oo-Elnill E(n-))
2TEc,
where the last step is by Hölder's inequality.
18

---

Then for the other term, we have
T
T Σ 0z E bp
E
Σ 11 1/11
2- E
Σ
1/
E(ni]12
+
- + 2Te..
So following the similar steps of proof for Theorem B.5 and using the above bounds, we can get
max Σ (u u, Av;) + max vedn
Σ (0, - v, - ATu))
log(mn) +4TcG-
$ 24A + 24ATE2 +
A
Again using linearity of expectation and Markov's inequality, we conclude that with probability at least 2/3
3 3log (m))
max (D, ATa) min (u, A6) 722 + vCAr
+7TTAEG 12Tec.
иеλm
A
C Consistent Quantum Amplitude Estimation
Suppose U is unitary operator. For every positive reals e, ô, there a quantum algorithm (a unitary quanium circuit) such that, on input (log((=")) -bit -bit random string s, it holds that
Theorem C.1 (Consistent phase estimation, 12. 47
For every eigenvector (()) of u (where Ul4a) exp(ii) (+) with probability 2 1 E:
2 -
f(, is function of and I such that (f(s, 0 8,
with time complexity Ö(ō 1) poly(c 1).
Theorem C.2 (Consistent quantum amplitude estimation). Suppose U is unitary operator such that
O)) vpl0) a Al /1- al1)
where p [0, and (00) and (41) are normalized pure quantum states. Then for every positive reals e, there quantum algorithm that, on input ((ogg(=")) random string s, outputs f(s, [0,1] such that
Pr [If(ss)) pl < 1-66, 1
with time complexity Ö(8-1) (o)y(e-1).
Proof. Suppose U is a unitary operator such that
a))) = vPI0) + / p|1) 1l
Let
= - - ( (0) @ 10), [ (1-0) @ TB).
Similar to the analysis in Brassard et al. 9 we have
u (0)
(exp(iep)) (1+) AB exp(-i88)) V2
-i
(e AB).
where sin sin) = 20S00p T/2), and
1
1/ AB
(10)^(00)
l
22
19

---

Note that (+==) Ab are eigenvectors of Q...e Q exp(=120p)) (
Now applying the algorithm A of consistent phase estimation of by Theorem C.1 state a @ c (with (l)) random string s), we obtain
A( @ 10)c) = -i
-
V2
Since each (4=) AB is an eigenvector of Q, it holds that, with probability 2 1 --6 E.
(12 which implies that A(U1)))a0) & (0)
-ee.
O to
in trace distance, where (s, = -0pp < 6. Measuring register C, denote the outcome Y, which will be either f(s, 20,) or f(s, -20p). Finally, output sin? (7/ as the estimate of p (which is consistent). Since sin²()) is even and 2-L-ipscittz, the additive error is bounded by
sin 1 2
p -
1
10pl < 6.
Note that A makes 0(0-1) po 1) queries to Q. thus consistent amplitude estimation has quantum time complexity Ö(8-1) (o
Theorem C.3 (Error-Reduced Consistent quantum amplitude estimation). Suppose is a unitary
operator such that
u a))) =
+ V1 111-p1).A A
where p [0,1] and (0o) and (41) are normalized pure quantum states. Then for every positive integers r and positive real 8, there is a quantum algorithm that, on input O(r) random string s, outputs f (s) [0, 10 such that
Pr IIf" pl s 8) 21 (0(x0(xx((-)).
with time complexity Ö(6-1) poly(r).
Proof. Consider that we divide the input random string s into r strings $1, $2, of length O(1). For each i E [r], use Theorem C.2 with input string s; and parameter e = 1/10. So get, for each E [r).
9
Pr [s((ss)))
S
10
Now we set (s p) be the median of the estimations f(s; p) for E [r]. We claim it satisfies the desired property. To show that, we define random variables X, for E [r] as follows:
11, if if(si pl S
x; = l0, otherwise.
Noticing E EL= Xi] 2 9r/10, and by Chernoff bound, we have:
87
Pr
Σ
Xi
<
< exp
45
Thus with probability at least exp( 8r 8454 we know that at least half of the estimations fall into the interval [p - 8, p + 8). and then f (s, p) returns a correct answer.
20

---

D Details and Proofs of Fast Quantum Multi-Gibbs Sampling
We present the detailed version of the fast quantum multi-Gibss sampling. Here, we use the shorthand G G (1,0), and it also means the distribution of the sample.
We first define the notion of amplitude-encoding (a unitary operator that encodes vector in its amplitudes).
Definition D.1 (Amplitude-nncodnng A unitary operator V said be a (samplitude-enoodnng of a vector E IR" with non-negnn non-neeative entries, if
(0lcV10)c1)al00/> V
for all [n].
we can construct a quantum multi-Gibbs sampler for a vector u if an Then, as shown in Algorithm 4
amplitude eetioiddddeenoiigggggggg of the vector is given. To complete the proof of Theorem 4.2 only have to construct an amplitude-encoding of Az (see Appendix D.2 for details).
Algorithm 4 Quantum Multi-Gibbs Sampling implementing O (k)
Input: Sample count k, f-amplitude-encoding V of vector u E IR", polynomial P2ş E R[x] that
satisfies Lemma 4.1 with parameter cp /
Output: k independent samples 12,
1: Obtain Oμ: ( (0) + (āt) using ((6) queries to V, where ui S úū S + 1, by consistent quantum amplitude estimation (Theorem C.3
2: Find the largest f7, s by quantum k-maximum finding (Theorem D.3 and let be the set of their indexes. This can be done with ((Vnk) queries to Oa.
3: Compute _² min üj and W = (n k) exp(a") + Σ exp().). IES
iES
4: for f= 1,.., do
5: Prepare the quantum state
exp ū
exp(1i*)
I Mguuss)
Σ
W
W
iFS
6: Obtain U, = CAB & (DD( @ Ic) being block-encoding of diag(u) B. Similarly,
obtain Lmmax being a block-encoding of diag (max [i, N² 222
7: Obtain u being a block-encoding of diag(u max { [1, a= /0*))/4 by the LCU (Linear- Combination-of-Unntaarie technique (Theorem D.6 using O(1) queries to Un and Ugpa
8: Obtain LTexp being block-encoding of P26 (diag(u max (ū, n* /)/))))))))))))))))))))))))))))) by the QSVT tech- nique (Theorem D.7. using O (oog(ep))) queries to U- Post-sclect [7 post) (0) [0] (rep (guess) [0) e4 by quantum amplitude amplification (Theo-
9:
rem D.8 and obtain (RGibbs) [opost) / [pps)))))))) (Suppose Lrxp has a ancilla qubits.)
10: Measure (aabbb)) in the computational basis and let ig [n] be the outcome.
11: end for
12:
Return in, i2.,,
D.I
Useful Theorems
Theorem D.2 (Quantum state preparation, (23, There is a data structure implemented on QRAM maintaining an array di A, of positive numbers that supports the following operations.
Initialization: For any value c, set a; &- c all i E [e].
Assignment: For any index i and value set a; f-
21

---

State Preparation: Prepare quantum state
la) = Σ iE(0
ai ||a]]
(i).
Each operation costs polylog(E) time.
Theorem D.3 (Quantum k-maximum finding, Theorem 6 of Dür et al. [9)). Given k E [n] and quanttum oracle for an array u1, U2,..... Un for every? E [n].
Oali) [0) 1
there is quantum algorithm that, with probability 2 0.99, finds set S [n]] of cardinality |S| = k
such that u; 2 for every i E S and] j $ S, using O ( nk queries to O.-
We now recall the definition of block-encee bockk-nncoding, crucial concept in quantum singular value transfor- mation (20), which is used in line 9 to 12 in Algorithm 4
Definition D.4 (Block-encoding). Suppose A is linear operator on b qubits, a 2 0 and a is positive integer. A (b + a)-qubit unitary operator U said be an (a, block)bbocc- of A, if
( S4 u| &a Allop S.
Definition D.5 (State Preparation Pair, Definition 28 of Gilyén et al. 20 ). Let y E IR" be a vector, specially in this context the number of coordinates starts from O. Suppose |ly B. Let be positive real. We call pair of unitaries (PL, PR) acting on b qubits a (B, -ttate--ttte-pepaaae y if
pair for
2h
Pr(0) 8h
Σ
g/i),,
1=0
2
PR|0) 0h Σ
azli).
1=0
such that:
m-1 Σ
Bcfd; Vi Se
and for j E [2*], 2 mi, we require o7d 0.
We state theorem about linear combination of unitary operators, introduced by Berry al. (5] and Childs and Wiebe [15]. The following form is from Gilyén et al. [20] Again we restrict ourselves the case of real linear combinations.
Theorem D.6 (Linear Combination of Unitaries, Lemma 29 of Gilyén al. (00). Let be positive real number and E IR" be a vector as in Definition D.5 with (B,e1) state preparation pair (Pt, PR). Let {
1 be a set of linear operators on qubits, and forall j, we have U, as an (a, (.,.)))-ooc--enodiin of Aj acting on a + qubits. Let
m=1
+ (1- m-1
W
Σ
1i 17 U; +
& Latsr
Then can implement (aB,ae1 -lock--bocc--nncoddig of A from pt, PR. and W.
1m-1 1 YjA with query Ly
Theorem D.7 (Eigenvalue transformation, Theorem 31 of Gilyén et al. (0).. Suppose U is an (a, 2l--blok--nnooole
of an Hermitian operator A. For every > 0 and real polynomial P E R|x] of degree d such that P(x) < 1/2 all x E [-1,1], there is an efficiently computable quantum circuit Ü, which is a (1, / (1l++88-blon -block-encodingg of ((A/ a)), using O(d) queries U.
22

---

Finally, for quantum amplitude amplification without knowing the exact value of the amplitude, we need the following theorem:
Theorem D.8 (Quantum amplitude amplification, Theorem 3 of Brassard et al. 9 Suppose U is unitary operator such that
u {))) = VDI0) A Al0)) + /1 -
where E [0,1] is unknown and (40) and (&1) are normalized pure quantum states. There is
quantum algorithm that outputs (0) A (40) with probability 2 0.99, using O(1/ /p) queries to U.
D.2 Main Proof
We generalize Theorem as follows.
Theorem D.9. Algorithm 4 will produce k independent and identical distributed samples from
distribution that is close to Giibbs in total variation distance, in quantum time Ô (Bv nkk
is immediate to show Theorem 4.2 from Theorem D.9 by constructing a B-ampiitude-encoding of Az. To see this, let u Az, then u; (Az); E 00, p). By Theorem D.2, we can implement unitary operator u URA such that
u @OAMM 10)
10)c E jE(n]
V
V
M + (1)))))
Using two queries to OA, we can construct unitary operator O', such that
0A (l) (VArr10) + V Aigl1>E li)
Let
V = (00) @ O'A + (1) & TCAB) (uQRAM @ TEA)
(11)
It can be verified (see Proposition D.10 that
Aijz
E
V
(i) Al)
B
JELN
and thus ())) = /u//lia for some 14:). Therefore, V is a B- amplitude-encoding Az.
Now, we will show Theorem D.9 in the following.
Proof of Theorem D.9 Now start describe our algorithm. By our consistent quantum amplitude estimation (Theorem C.3 we choose an -br)-bit random string s, then we can obtain a quantum algorithm Og such that, with probability 1- (((ep(-rr) for every [xx], it computes f"(s us/ with ((6-)) (r) queries to V, where f*(s, p) a function that only depends on s and p, and it holds that
(s, p) - pl 8 8
for every p [-11]. Here, r, 8 are parameters be determined. Note that
g |(00c\11):cc)>)10)){11)
so when applying consistent quantum amplitude estimation, we just use controlled-XOR gate conditioned on the index and with the target system, before every query to V.
By quantum k-maximum finding algorithm (Theorem D.3). we can find set S C [x]] with [|] such that ft (s,u:/B) > (s, for every E S and j & S with probability
0.99 - ((Vinexp((r))) using O o(vnk) queries to Og. To obtain constant probability, is sufficient to choose + (log(n)).
23

---

For each i E S, again applying our consistent quantum amplitude estimation (Theorem C.3 we can obtain the value of (s, /z/B8 (8) with probability O(exp(-r)), using O 1) poly(r) queries to V; then we set
0 =f
s, Mij
for all E S, with success probability O( (-r) and using (kk--1) poly (r) queries to V in total. It can be seen that |0; 4;| - 66 for every E S.
Let ii Q. + Bb, and then we store ù; for all in the data structure as in Theorem D.2 (which costs (kk QRAM operations). Then, we calculate
W
(n - k) exp((")) E exp(i;)
iES
by classical computation in Okk) time, where
ni min ū;
iES
By Theorem D.2 we can prepare the quantum state
exp(a;
exp (ū²))
(gguess)
Σ
1))
+ Σ
11)
W
W
idS
in Ö(1 time.
Now we introduce another system D, and then let
Uu (V (D))VAAB Ic).
It can be shown (see Proposition D.11 that Uy is a (1,0) (.o-)-booc--enodding of diag(a) u)) /p. By QRAM access to ūj, we can implement a unitary operator
max{";, (7)
max [ū at)
Va: 1)) - 1
10) + 1
[1)
2B
2B
in Ó(1) time by noting that max ( (ū; 11"} = ū; if E S and f7* otherwise. We introduce one-qubit system C, and let
U umaa
V Ic) (SWAPBC & lA)(V @ Ic).
It can be shown that Ummax is blocck---nnnn of diag(max( i1 i1 /2/s) Applying the LCU technique (Theorem D.6.. we can obtain a unitary operator U that is (1,0)-block-encokl of diag(u max 11, 77446, using O(1) queries Uy and Ummax. By the QSVT technique
(Theorem D.7 and Lemma 4.1 we can construct unitary operator Texp that is (1,0)-block-
encoding of aa P2 max ū1 ū²" / using O ((Blog(pp))) queries to U where
1 (x - exp(28x) s <pp 4
for every x E |- and cp E (0,1/2) is to be determined. Suppose L has an a-qubit ancilla system, and let (āposa) (0)@* [[epp [gguess) (0) @a Note that
(
P28
M4
exp (i:) W
(1)
Σ FES
P2p
M4
11t
exp exp (1*)
46
48
W
icS
It can be shown (Proposition D.12 that (Tpost)) |12 2 (kk/n) /n); thus by quantum amplitude amplifi- cation (Theorem D.8
we can obtain
(iiibbs)
[ ||
24

---

using O (vvn/ queries to u By measuring [TGbbbs) on the computational basis, we return the outcome as sample from the distribution Rihhss can be shown (Proposition D.13 that the total variation distance between liiibb and G is bounded by
drv (Ciibbs, Gibbs
S8nE
(
By taking ò = 1/2B and ep /300n, we can produce one sample from iibbbs using O(Bvn/k) queries to Uy and L with O(Bynk nk)-time precomputation.
Finally, by applying times the above procedure (with the precomputation processed only once), we can produce k independent and identically distributed samples from AGibbs that is GGibbs to the Gibbs distribution O with total time complexity
(BVVkk + ō B
11
= =Ō(BVnk)
D.3 Technical Lemmas
Proposition D.10. Let V defined by Equation
have
Ar,Z
(10)
Σ
af)
B
jE n
Proof.
110)
=(10)c(0) @ o'A +11)c(11 @ LAB)
(101c101111
E jE(m
3
M) + 11)c0))
V
3 (VAL,10 A,,10)) + 11 (1--)))1)))
=10)c Σ
i + 11)110/01)
jE(n]
Aij2
Ain)
=10)c(0) jE(m]
Σ
+
Σ JE
M B 11)00)
Proposition D.11. In the proof of Theorem D.9
Uy is a (1,0) block-elcc--nnodiing of (aaag()//
Proof. To see this, for every i,j E [n].
=(0lc(00b\(ia @ (DDAR & (c)1))c1))/11111111
= (/ (1lc()) (llccolb(ss/aaa/////o/o//o (V1//11)cc0)))))))))))))))))) (0)cl1))lg))
u; (jli)
B
L
Proposition D.12. In the proof of Theorem D.9 k /300n, then
if = 1/26. E = Eje(n] exp(u:). and Ep =
k
E 16W
22p S |||Mpost)
+ 3ép-
7
16W
25

---

Proof. We first give upper bound for W in terms of uj and ii".. Notice that 0; S + 266 for all E S, we have:
W (n k) exp((i))
Σ
exp((,) S exp(266)
(n= E exp(u:))
iES
:ES
Note that
(n - k) exp(1")
+ Σ exp(uii) IE
11 - k
+ k'
Σ exp(u;)
ic(n)
then we have
E W
exp(u:)
Σ
exp(-266).
(12)
exp(266) k) exp(u*) + Eies exp(u:))
IE(U]
With this, noting that (a - b)2 2 a²
2ab for any real a and b, we have
ppsss) 1|2
Σ
P38
11i di
(xp((;;)
P2$
Ui 11"
*epp(1"
46
W
46
W
iEs
U1
i
exp(ū;;
exp
2σp
4
2
W
ics
11 at
))
2
exp(1i*
exp
2EP
2
1
exp(
exp ui 11*) exp(#i)
Σ
exp
u1:
ūi))
Σ
16
W
VIES
itS
exp
(i)
exp(
2Ep
W
W
iES
ES
E
2cp
16W
k
On the other hand, similar argument using the inequality (a + b)2 a² + 3ab for positive real a > gives
([postt) 112
+ 3Ep.
16W
These yield the proof.
Proposition D.13. the proof of Theorem D.9 distributions U.bbs and Gibbs is bounded by
the total variation distance between the two
88nEP
drv UGiibbe Gibbs)
$ V k kexp(-2f0)
Proof. Define Σ exp(u:) Let jE[n]
exp (i)
[MGibbs)
Σ
l1)
E
(E(m]
26

---

be the intended quantum state with amplitudes the same as the Gibbs distribution Qiibhs The inner product between post) and |tGGihhs) can be bounded by:
pups [
Σ iCS
P2s
Mi
di
exp 11)
exp(ui)
46
W
E
14 f
exp (a*)
exp(u::
P2
4B
W
E
1
dij
exp (ij)
exp(ui)
2
Σ
exp
Cp
4
2
W
E
IES
+
Σ
exp
- 11
- cpp
exp iT*
exp(ui)
4
2
W
igs
1
Σ
exp(u;)
Ep.
WE
The last step is by Cauchy's inequality. By Proposition D.12 and Equation 12 have
( (uGibbb [RGibbs)
1
(uopt (GGibbs) > ||| [poss 1
|
Ep
16W
[ 11?
2 ||l post
1
E
Ep
W
E
2 [1 post) 1
16W
+ 3EP
16W
48cp
E/W
E/W 32
48nEp
SNEp
k e (-28)
k e 226) 32nEp
88nEP
2
k kexp(-266)
Finally, we have
drv (iibbs Gibbb
1
tr
[[ciiths) (ūGübbs
|uciitbs) (Hciibes)
2
(ūGibbs (iCbbbs)) 1
88ncp
(exp(-2280)
which is bounded by EG by the choice of Ep.
27


Reviews:
[{"review_id": "YVzrEWvmaH", "reviewer": "Reviewer_42Uz", "summary": "In this paper the authors consider the task of computing the eps-approximate Nash equilibrium of zero-sum games. In particular, for a matrix A in R^{m x n}, the goal is to find the minimum distributions x,y s.t., max_y x^t A y - min_x x^t A y is at most epsilon, given quantum query access to A.  In this paper the authors are further concerned with the online learning/regret model, i.e., in each round the players need to choose probability distributions (u,v) and their goal is to pick these distributions (u,v) such that it is as close as possible to the optimal choice of eps-Nash equilibrium. \n\nPrior known quantum algorithms for computing the Nash equilibrium ran in time sqrt{m+n}/eps^2.5 but achieved a regret of sqrt{T}  for a T round algorithm. In this paper, the authors show how to obtain a regret of O(1) with the same complexity as sqrt{m+n}/eps^2.5. ", "questions": "I think the definitions of online learning and regret can be defined much better. In particular, the online learning/regret model for Nash equilibrium is very messily written and I'd have appreciated a better explanation. ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength of this paper is in a way it solves an important question of computing Nash equilibrium with a O(1)-based regret algorithm.  Using this, they algorithm obtain a state of the art quantum algorithm for linear programming solvers. I think both of these contributions are interesting on their own right!", "weaknesses": "As for weakness, i feel there are a couple of weaknesses:\n\n(i) The main techniques used in this paper, aren't very novel. Indeed, they do improve upon prior works and need new tools, but the novelty of the main contributions towards obtaining their speedups doesn't make it a strong contribution. For example, obtaining k copies of a Gibbs state in time sqrt{nk} (compared to the trivial k sqrt{n} algorithm) isn't too surprising (indeed new, but not surprising given Hamoudi's algorithm and also complexity of Grover's search with k marked items). \n\n(ii) The speedup to obtain the regret bound is by quantizing the optimistic  online algorithm. I think there are some subtelties when quantizing this algorithm, but the main ideas involved aren't novel.\n\nHaving said the above, i think overall for the ML community, i think the main results and these interesting quantum subroutines above are nice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer identifying potential areas for improvement. However, we believe the core techniques demonstrate non-trivial novelty for the following two points.\n\nFirst, our framework of Sample-based Optimistic Multiplicative Weight Update is considered for the first time in both classical learning theory and quantum algorithm research. The framework of our Sample-based Optimistic Learning algorithm contains a new and detailed analysis of the regret (see Appendix B, Page 15). The regret analysis differs from the classical counterpart that does not involve sampling; moreover, it also differs from all previous quantum approaches that do not consider the technique of Regret bound by Variance in Utilities (RVU, Definition A.2, Page 15).\n\nSecond, while the multi-Gibbs sampler adapts existing ideas of designing quantum samplers like Hamoudi's algorithm (Ref. [29]), creatively extending these methods to efficiently generate independent samples from the Gibbs distribution when only implicitly knowing the parameters represents an innovative application. We propose our novel multi-Gibbs sampler to satisfy the requirement of the sample-based optimistic multiplicative weight update framework, as existing quantum samplers do not. We agree the building blocks of quantum singular value transformation, amplitude estimation, etc. are known. However, we tailored these techniques in novel ways for our application. \n\nIn summary, we appreciate the reviewer highlighting opportunities to further demonstrate novelty. In the revision, we will expand the discussion part to better highlight our contribution.\n\nAs for the question raised by the reviewer regarding the definitions of online learning and regret for finding Nash equilibria, we agree that concisely explaining these concepts would make our paper more understandable. In short, online (machine) learning studies the situation when data arrives in a sequential order and each time the (meta-)algorithm is required to output a predictor for future data. Regret is a commonly-used performance measure in online learning that compares the losses of predictors produced by the algorithm and the optimal fixed predictor. As a concrete example, the well-known multiplicative weight update algorithm is an online learning algorithm with regret $\\tilde{O} (\\sqrt{T})$. We will carefully revise Section 2 to provide an easy-to-follow introduction to online learning and regret for finding Nash equilibria."}, {"review_id": "CFImgELX8K", "reviewer": "Reviewer_UumW", "summary": "This paper considers the problem of developing quantum, low-regret, algorithms for solving zero-sum games. This paper provides a quantum algorithm which matches the state-of-the-art for solving zero-sum games while improving upon the regret of the associated algorithm. The paper achieves this result by providing a stochastic variant of optimistic mirror descent which they then implement by a quantum algorithm for developing multiple samples from a suitable Gibbs distribution. Additionally, the paper discusses implications and lower bounds for linear programming more broadly.", "questions": "My main questions / comments are the items in the previous “Weaknesses” section. Beyond what was written there: How does the Gibb’s sampling compare to prior work? Is it simpler in any way? The same? Is a completely different techniques used? Is there a major insight of the paper beyond the use of stochastic optimistic mirror descent? \n\nBeyond this, below are some more detailed suggestions, questions, and comments:\n\n* Line 1: “for zero-sum games” --> “for solving zero-sum games”\n* Line 4: “yielding a quadratic improvement” as written, I am concerned this is suggesting that it is the first such improvement.\n* Line 27: “For, this approximation task, online learning becomes significant” – I am not exactly sure what was meant by this.\n* Line 33: It might be beneficial to define regret or explain the model more clearly earlier so the improvement over prior work is clearer. (Regret is well-known in general, but when stated for a static optimization problem, the definition is less clear.)\n* Line 39: I believe zero-sum games were shown to be solvable in $\\tilde{O}(1/\\epsilon)$ iterations earlier, e.g. “Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems” by Nemirovski in 2004. I’m less sure about whether this works in regret context but in any event I believe should be mentioned when discussing the history of solving zero-sum games.\n* Line 81: it might be good to clarify whether this is a new feature of this algorithm or not\n* Line 130 – 135: it might be good to clarify why prior work could or could not be used for this problem\nMy main questions / comments are the items in the previous “Weaknesses” section. Beyond what was written there: How does the Gibb’s sampling compare to prior work? Is it simpler in any way? The same? Is a completely different techniques used? Is there a major insight of the paper beyond the use of stochastic optimistic mirror descent? \n\nBeyond this, below are some more detailed suggestions, questions, and comments:\n\n* Line 1: “for zero-sum games” --> “for solving zero-sum games”\n* Line 4: “yielding a quadratic improvement” as written, I am concerned this is suggesting that it is the first such improvement.\n* Line 27: “For, this approximation task, online learning becomes significant” – I am not exactly sure what was meant by this.\n* Line 33: It might be beneficial to define regret or explain the model more clearly earlier so the improvement over prior work is clearer. (Regret is well-known in general, but when stated for a static optimization problem, the definition is less clear.)\n* Line 39: I believe zero-sum games were shown to be solvable in $\\tilde{O}(1/\\epsilon)$ iterations earlier, e.g. “Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems” by Nemirovski in 2004. I’m less sure about whether this works in regret context but in any event I believe should be mentioned when discussing the history of solving zero-sum games.\n* Line 81: it might be good to clarify whether this is a new feature of this algorithm or not\n* Line 130 – 135: it might be good to clarify why prior work could or could not be used for this problem\n", "limitations": "\nThis is primarily a theory paper, and it is unclear how applicable this is. However, the weaknesses and questions discussed reflect limitations for which further discussion might be beneficial.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Zero sum games are an important optimization problem in many disciplines. The mere fact that the paper shows how to depart from previous quantum algorithms for solving zero sum games (in using optimistic mirror descent versus mirror descent) while retaining state-of-the-art bounds is interesting and potentially useful for further study of the problem. Additionally, by following this alternative approach the paper obtains improved regret and a type of parallelism in solving the problem. This is an interesting advancement for the study of the problem. Finally, this alternative optimization method gives rise to a different Gibb’s distribution sampling problem than the one considered in prior work. Furthermore, the paper gives an interesting algorithm for solving it which could motivate further study. Finally, the additional discussion of linear programming provided in the paper (though seemingly straightforward) is a nice addition as well.", "weaknesses": "It is not clear how substantial the departure from this paper from prior work is, how novel the advancements are, and how complete the comparison of this paper to prior work is. While I think the advancements of the paper are interesting and potentially exciting (as discussed in the strength section), I fear that the paper does not well-articulate them or situate them. For example:\n\n* A comparison of the techniques in the Gibb’s sampling algorithm of this procedure and those in prior quantum-zero sum games algorithm does not seem to be provided. This seems particularly important as the techniques were key to recent advances in quantum algorithms for solving zero-sum-games.\n* It is not clear what exactly the benefits of low regret are over prior work and why previous results couldn’t be used to obtain low-regret (e.g. by only considering a subsequence of the iterates taken). I think the low-regret aspect is interesting and this algorithm is potentially more parallel than prior algorithm’s with state-of-the-art complexity and the sampling problems considered may be simpler than in prior work; however I am not sure that the paper argues this clearly.\n* It is not clear what obstacles were present to obtaining the result. It would help if the paper clarified whether moving from mirror-descent to optimistic mirror-descent was the main insight and the rest was straightforward (though technical and important) or if further insights were needed. \n\nSome additional comments along this line are given “Questions.” \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's feedback highlighting opportunities to better articulate the novelty and situate our techniques relative to prior work. \n\nSpecifically, we will include a detailed comparison of our Gibbs sampling approach to existing methods from quantum zero-sum game literature.  Our quantum multi-Gibbs sampler is different from the samplers appearing in prior works (Ref. [50] and Ref. [7]).\nThe sampler in Ref. [50] is a special case of ours when the sample count $k = 1$; also, the learning algorithm in Ref. [50] only requires the case when $k = 1$.\nIn the following we compare the sampler from Ref. [7] with ours:\n\n- Firstly, the two samplers are designed for different goals. We focus on the optimistic multiplicative weight update, while Ref. [7] adopt the non-optimistic version. As a result, we need a good procedure to obtain many samples at a time to reduce the variance. They use the dynamic Gibbs sampler to reduce the amortized time complexity of obtaining a single sample which changes at every step.\n- Secondly, the implementation details are very different. In our quantum multi-Gibbs sampling procedure, we develop a proper version of consistent amplitude estimation to guarantee the correctness of the quantum k-maximum finding. In the dynamic Gibbs sampler, they maintain certain invariants and a hint vector to achieve a good amortized time complexity.\n\nRegarding regret bounds, we will emphasize the concrete advantages of our approach over prior quantum algorithms. Prior works (Ref. [50], [7]) employed the Sample-based Multiplicative Weight Update (SMWU) framework (by Ref. [25]), while we proposed Sample-based Optimistic Multiplicative Weight Update (SOMWU for short) which is a generalization of the Optimistic Multiplicative Weight (OMWU) proposed in Ref. [48]. The regret bounds of these quantum algorithms inherit from their classical framework. However, whether the MWU (or SMWU in Ref. [25]) can achieve $\\tilde{O}(1)$ regret in the zero-sum game setting has been open for more than a decade (see, for example, Ref. [19, Future work in Page 3]). To the best of our knowledge, we are not aware whether previous results (Refs. [50], [7]) can be used to directly obtain low regret under the game setting (this is even not known achievable in the classical setting).\n\nThe reviewer rightly notes that a core insight is moving from mirror descent to optimistic mirror descent. In addition, the following insights are crucial in designing our algorithm:\n\n- Our first insight is the sample-based generalization of OMWU, which, to the best of our knowledge, is a new framework for solving zero-sum games.\n- Our second insight is to point out that SOMWU, equipped with quantum computing, is able to achieve near-optimal regret, beating prior quantum approaches while retaining the computational cost. To implement SOMWU efficiently, we need a specifically-designed sampling algorithm, while known quantum samplers do not apply here as they are not efficient enough.\n- Our third insight is the quantum multi-Gibbs sampler, which, we believe, can serve as a basic subroutine in future quantum machine learning algorithms.\n  \nRegarding the detailed questions for lines, we will address them as follows:\n\n- We will revise the wording on lines 1, 4, 27, and 81 to improve clarity as suggested.\n\n- We will define regret earlier and explain the model more explicitly to make our paper more understandable (Line 33).\n\n- Thanks for pointing out the work of Nemirovski in 2004, which investigates how to find the saddle point in convex-concave minimax optimization problems. This work is highly related to our work, though it has a non-online problem setting. We will cite the paper and discuss the proximal method and other histories of solving minimax optimization problems that are related to solving zero-sum games to properly credit prior work (Line 39).\n\n- We will explain why existing techniques could not achieve our efficiency gains, to motivate the need for new methods (Line 130-135), as noted in the second insight."}, {"review_id": "dVyWfvgZPU", "reviewer": "Reviewer_XSuW", "summary": "The paper studies the online learning quantum algorithms for zero-sum games. It proposes the online quantum algorithm for zero-sum games with near-optimal regret, which makes progress to online learning algorithms in the quantum setting. The algorithm quantizes classical algorithms based on the MMW method and incorporates a fast quantum multi-sampling procedure for the Gibbs sampling problem. By developing a sample-based stochastic version of the optimistic multiplicative weight update method, this method achieves a quadratic improvement over classical algorithms and presents a fast quantum linear programming solver as an application.", "questions": "Refer to the part about weaknesses.", "limitations": "NA.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper addresses a timely and relevant topic in quantum learning theory, proposing the first online quantum algorithm for zero-sum games with near-optimal regret.\n2. The algorithm achieves a quadratic improvement over classical algorithms for computing the approximate Nash equilibrium.\n3. The paper presents a fast quantum linear programming solver as an application.", "weaknesses": "1. The main algorithm is derived from classical methods, and the explanation of the features/contributions of quantum computing in achieving the speedup or advantage could be further elaborated.\n2. As a theory paper, it could benefit from a clear and well-motivated example demonstrating the application of the proposed algorithm. Including such an example would help readers better understand the potential practical implications and usefulness of the work.\n3. Could the authors discuss whether this online quantum algorithm could be dequantized?\n4. In the abstract, the authors claim that \"a fast quantum linear programming solver\" but haven't identified under which setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments.\n\nFor the contributions of quantum computing in achieving the speedup, we would like to explain as follows: to obtain the speedups over prior work, we proposed Sample-based Optimistic Multiplicative Weight Update (SOMWU for short) as the framework for solving zero-sum games. By integrating SOMWU with quantum techniques, we achieve near-optimal regret, surpassing prior quantum approaches at a comparable cost. However, efficiently implementing SOMWU requires a tailored quantum sampling algorithm. Existing methods are insufficient, motivating our novel multi-Gibbs sampler design. We will highlight these ideas in the future version of our paper.\n\nTo demonstrate an application of our zero-sum game algorithm, we discuss its use for solving linear programming problems, as noted in the Introduction (Section 1, Page 3). Specifically, we show how our approach can be leveraged as a quantum linear program solver in Section 5 (Page 9), with further details provided in Appendix E (Page 30). We will expand this example in the revised paper to further illustrate the practical utility.\n\nRegarding dequantization, quantum-inspired algorithms usually assume certain conditions of the matrices, such as the low-rank condition (e.g., Ewin Tang. “A quantum-inspired classical algorithm for recommendation systems” and Nai-Hui Chia et al. “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning”). It is unclear if our algorithm can be efficiently dequantized, as our problem setting does not assume that the input matrix is sparse or low-rank. Therefore, while dequantization may be possible in certain constrained cases, it is unlikely a classical version could match our performance for general inputs. Further investigation of the dequantization question remains an interesting area for future work.\n\nAs for the setting of our quantum linear programming solver, the solver requires quantum oracles to the input matrix and vectors of the linear program, and it outputs a classical value as the approximate optimal value of the program. This setting is standard in quantum algorithms for linear programming. We will expand Section 5 to include the detailed setup of the quantum linear programming solver."}, {"review_id": "IhADLpw5U0", "reviewer": "Reviewer_8qKg", "summary": "The paper presents an improved quantum online learning algorithm for approximating the Nash equilibrium of a zero-sum game. Notably, this is the first algorithm to achieve $\\tilde{O}(1)$ regret with quantum speedup. The presented algorithm can then be applied to linear programming problems using the primal-dual approach. Additional contribution of the paper is a sampling method for Gibbs distribution for obtaining multiple samples with quantum speedups on both the number of samples and the number of possible outcomes.", "questions": "The presented algorithm requires QRAM to work. How does this compare to the quantum algorithms of regret $\\tilde{O}(\\sqrt{T})$, i.e., do they too require QRAM?\n\nTypos:\n- Line 285 should probably say \"Line 7\"", "limitations": "I do not consider the work to have any serious limitations other than the ones that follow from the limited practicality of quantum computing (for now).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Multiple novel contributions on quantum algorithms: speedups for multi-Gibbs sampling and logarithmic regret Nash equilibrium approximation\n- The paper is well-written and easy to follow", "weaknesses": "While the presented theoretical results are interesting, I consider the necessity of QRAM as a minor weakness since (to my knowledge) it is still a highly theoretical model whose physical realizability is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer taking the time to thoroughly review our paper and provide helpful feedback.\n\nRegarding the use of QRAM, we would like to clarify that prior works (Refs. [50] and [7]) also have exactly the same requirement of QRAM (though under slightly different names). Specifically, Ref. [50] utilizes a \"tree-like data structure in QCRAM\" as described on Page 7, Line 4. Furthermore, Theorem 9 of Ref. [50] emphasizes the use of \"a quantum computer with QCRAM.\" Ref. [7] also states they employ the same classical variable data structure as Ref. [50] per Lemma 1. In summary, QRAM was commonly assumed in these prior works.\n\nThank you for catching the typo on Line 285. We will correct this in the revised version."}]

Author rebuttal:

Meta-review: This paper proposes the first online quantum algorithm for zero-sum games with logarithmic regret. In particular, the paper shows how to obtain a regret of $O(1)$ with the same complexity as $sqrt{m+n}/eps^2.5$. We reached a consensus of acceptance for this paper after the discussion. However, the authors should discuss the connections to existing literature (mentioned by all the reviewers, especially reviewer UumW) more carefully for the camera-ready version. I recommend the paper be accepted.
Decision: Accept (poster)