Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
Authors: Tongyang Li
Xinzhao Wang
Yexin Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Quantum algorithms
equilibrium computation
correlated equilibrium
query complexity
online learning in games
Primary area: theory

Abstract: Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing $\varepsilon$-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})$. Both algorithms demonstrate a near-optimal scaling in the number of players $m$ and actions $n$, as confirmed by our quantum query lower bounds.

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
Tongyang Li
Xinzhao Wang
Center Frontiers of Computing Studies, and School of Computer Science, Peking University,
Center on Frontiers of Computing Studies, and School Computer Science, Peking University, Beijing, China
Beijing, China
Nongyangli@pker edu. cn
wangxz@stu, wwt.:/ttuuuuuuu..... edu. cn
Yexin Zhang
Center on Frontiers of Computing Studies, and School of Computer Science,
Peking University,
Beijing, China
zhangyexin@stu. pku. edu.
Abstract
Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is more general concept called correlated equi- libria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing s-approximate correlated equílibria (CE) and coarse correlated equilibria (CCE) in multi-playe normal-form games. the multi-scale Multiplicative
PPAD-hard and the computing
Our approach utilizes quantum improvements Weight Update (MWU) method for CE calculations, achieving query complex- ity of (mm)n) for fixed For CCE, we extend techniques from quantum algo- rithms for zero-sum games multi multi-player settings, achieving query complexity Both algorithms demonstrate near-optimal scaling the number of players m and actions n, confirmed by our quantum query lower bounds.
Introduction
Motivations. Game theory is a branch of mathematics that studies the interactions between strate- gies of rational decision-maken depends not only their own strategies but also the strategies of others. One of the simplest sce- narios two-player zero-sum game, where the total payoff of the two players does not change regardless of their individual strategies. A key concept in game theory is Nash equilibrium, which describes a situation where no player can unilaterally change their strategy to achieve better pay- off, with the strategies of the other players being fixed. Notably, Nash equilibrium in a two-player zero-sum game can reached by no-regret online learning: when both players repeatedly adjust their strategies to minimize regret, the average play converges the equilibrium. This observa- tion central to the design of several classical and quantum algorithms for computing equilibria.
focuses the situations where the outcome of each participant
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Loss matrix where D = fp(C, A) = 2 p., B) = 1 is a CCE but not a CE: Player can
2
change B D and C - A to reduce the loss.
Player
B
C
D
A
(1,2)
(3,2)
(2,2)
(2,2)
B
(2,2)
(2,2)
(2,2)
(2,2)
Player
C
(2,2)
(2,2)
(2,2)
(2,2)
D (3,2)
(1,2)
(2,2)
(2,2)
Grigoriadis and Khachiyan [199] showed that finding pair of e-near Nash equilibrium strategies of a two-player zero-sum game with n actions could be realized using O(n/E²) classical queries, which is sub-linear with respect the problem size. For quantum algorithms, Refs. [25]] and [G]
achieved quadratic speedup in with ((VnfE*) and ((Vn/=²) quantum queries, respectively,
and the optimality in n is proven in Li et al. [25]] Currently, the state-of of-the-art results [9, [ل] have
improved the e-dependency of the query complexity to ((v7//225)
Many scenarios in game theory cannot be modeled as two-player zero-sum games, such as the congestion game [+3I] and the scheduling game [IG. 28J. In a congestion game, each player chooses strategy from set of actions, and the loss of each player depends on the number of players choosing the same action. The congestion game a widely used model in traffic routing. a scheduling game, strategies are a set of machines and the loss of choosing machine depends on the total load of the machine. Both congestion games and scheduling games are examples of normal- form games. In m-player normal-form game, player i chooses strategy a; in A, with actions, and then suffers a loss C,(ai,.... am).
For general normal-form game, finding a Nash equilibrium is PPAD-hard [02]]. A more general concept than the Nash equilibrium is the correlated equilibrium proposed by Aumann [ In this setting, trusted coordinator pulls an action profile from distribution 'D on the joint action set of all players and sends each player its action. We call D an e-correlated equilibrium (CE) no player can reduce its loss by by changing their action based on what the coordinator sends. For any player, if cannot reduce its loss by e by choosing a fixed action regardless of what the coordinator sends, we call the distribution D an E-coarse correlated equilibrium (CCE). The coarse correlated equilibrium is a relaxation of the correlated equilibrium, hence it is casier to find one (see Dable
Computing the correlated equilibrium and coarse correlated equilibrium of a normal-form game has been extensively studied in the classical setting. Since the size of description of a normal- form game is exponential in m, any algorithm needs ((cxp(m) time to solve the problem in the worst case. A standard approach to handle this issue is to assume that the algorithm can query the loss function of the game black-box and study the query complexity of the problem. In this case, correlated equilibrium can be computed using poly (n, m) queries by LP-based algorithms [23] 28). The algo-
rithm proposed by Jiang and Leyton-Brown [23] can compute an exact correlated equilibrium but the degree of its query complexity is high. Analogous to the case of Nash equilibrium, an approx- be computed using a no-swap-regret learning algorithm [TS]] (see
imate correlated equilibrium
its definition in Section 2). This connection has motivated a line of research focused on designing efficient no-swap-regret algorithms in normal-form games. In particular, Dagan et al. [T3) Peng and Rubinstein [2%]] designed the first algorithms computing an e-correlated equilibrium using ((m) queries for a fixed precision e. Similarly, an E-coarse correlated equilibrium can be computed by a no-external-regree learning algorithm. While recent variants of the Multiplicative Weights Update (MWU) algorithm, such as optimistic, clairvoyant, and cautious MWU [144 GI, 62, 533, achieve remarkable polylog(T) regret bounds after T rounds, these bounds scale polynomially with the number of players m. This leads to a total query complexity that is super-linear in m.
Our work differs from the field of quantum games strategies and quantum equílibria are considered. In contrast, we use quantum algorithms to more efficiently find classical equilibria in purely classical games.
26
Mi
[6), where players play quantum
Contributions. In this paper, we initiate the study of quantum algorithms for computing the CE and CCE of multi- player normal-form games, aiming for near-optimal complexity in both the num-

---

ber of players m and actions For computing e-CE, our algorithm quantizes the state-of-the-e multi-scale MWU framework [[3 29], which provides the fastest known classical convergence for a fixed e. For computing e-CCE, our approach is specifically designed to achieve optimal m and n scaling. We therefore build upon the algorithm of Grigoriadis and Khachiyan [[1,, whose regret bound is crucially independent of the number of players. This choice is key to designing quantum algorithm with a query complexity that is linear in m, which is optimal.
We assume that quantum computer can access the game by querying a unitary oracle Og and study the query complexity of finding an E-(coarse) correlated equilibrium.
Definition 1. For an m-player normal-form game (fA,) {())))) unitary oracle Or satis- fying
Ocli)la1) ... lam) =0)|1a)) ... (am) ( [C, ... am))
(1)
for all E [m]] and E AI...., am E Am is an oracle of the game, and the query complexity of an algorithm is the number of queries to Oc.
The unitary oracle Og can constructed efficiently if the game has a succinct representation that allows for an efficient classical algorithm to compute the loss function [a dm [6]. For ex- ample, congestion game, a player's loss is determined by the costs of their chosen resources, where the cost of each resource depends on the total number of players who selected it. This struc- ture allows for efficient loss calculation. Given access to Og, we state the following problem of computing E-(coarse) correlated equilibrium:
Problem Given an m-player normal-fomn game (e..) m)))) with n actions for each player, error parameter O, and a failure probability a >> O, prepare a quantum state
((b)) =.EA Va(a)aa)lv..
for some normalized states Wa) such that q is an 8-(coarse) correlated equilibrium of the game with success probability at least 1 a.
In particular, give quantum algorithms for computing s-CE and c-CCE as follows:
computes an e-correlated equilibrium of an m-player normal-font game with n actions for each player using m m//n(log(mm)) )01) queries to Oc and m² (i(log(mn)))ot (1./e) time.
Theorem (Informal version of Theorem K). Algorttim 1
Theorem (Informal version of Theorem Algorithm 2 outputs the classical description of an e-coarse correlated equilibrium of an m-player normal-form game with n actions for each player using Omm/n//22 queries to Og and Ó(m² en.5..5) time.
We measure the time complexity by the number of one and two-qubit gates in the quantum algo- rithm. The overhead in time complexity, in comparison to query complexity, arises from the gate complexity of the QRAM. If we adopt the convention established by previous quantum algorithms for zero-sum games [3% 9. 18), which assumes that QRAM access incurs a unit cost, then the time complexities presented in [Theorem I] and Theorem 2 align with the query complexities, differing only by a poga-togcii factor. addition, we note that the output of Algorithm 4 is a classical description of a Ó (1)2/62) > e-coarse correlated equilibrium, hence we can prepare the state (1b) in Emoble 1 ((mB² /=²) time [20].
On the other hand, we prove the following quantum lower bounds on computing CE and CCE:
Theorem 3 (Restatement of [Teoremm T). For m-player normal-form game with actions for each player, lei B denote an upper bound on the loss function. Assume 0 < é < min 3 3m }. to compute an e-(coarse) correlated equilibrium with success probability more than 5. we need ((mmn) quantum queries.
27
The scaling of our query complexity lower bounds with respect to the number of players and actions n matches our algorithms' upper bounds up to a poly-logarithm factor, indicating the near- optimality of our quantum algorithms in and
3

---

Table Complexity bounds for computing s-CE.
Reference
Setting
Query complexity
Time complexity
2
classical
mmn(lg((mn))ouu
mmn(lg((mn))004/
this paper
quantum
my (nllooo(mmm)))02 (11/)) A(mvn)
m² Vn(log(man))00 0(1/))
Table 3: Complexity bounds for computing e-CCE.
Reference
Setting
Query complexity
Time complexity
[
classical
O(mn/=²)
O(mn/E²) Vn/e44b)
this paper
quantum
O(m² (
Techniques. Our algorithm for CE quantizes the multi-scale MWU algorithm [2%]. Classical multi-scale MWU algorithm needs 22(1) queries to compute the loss vector of one player in each round and then takes the exponential of the loss vector to update its strategy. This (2()) query com- plexity can be improved in quantum algorithms by constructing an peplitude-encodiing vector and then using the quantum Gibbs sampler to sample from the exponential of the loss vec- tor. The standard approach to construct the amplitude-encodiee
of the loss
is to store the frequency of history action samples in a QRAM and maintain tree data structure [[3, 9, I8 However, in an m-player normal-form game with actions for each player, the size of the joint action space is n so the QRAM requires ((("") gates to implement. Furthermore, the multi-scale MWU algorithm runs O(1/E) instances of the MWU algorithm in parallel, thus standard amplitude-encoding schemes re- quire ((1/2) QRAMs to store the frequency of history action samples in different time intervals for different MWU instances. To overcome these issues, we use single, unified QRAM to store all history action samples rather than the frequency vector. We then demonstrate how the necessary amplitude-encoding for any MWU subroutine can be constructed from this single QRAM. Crucially, instead of treating QRAM access as a unit-cost oracle, we analyze its gate-level construction cost, showing that it requires only m log (llog(mn))) O(1//)) gates.
Our algorithm for CCE is built upon the quantum algorithm by Bouland et al. [5]] which quantizes the classical approach of Grigoriadis and Khachiyan [T9] for two-player zero-sum games. We extend their quantum framework to the m-player normal-fore game setting, using the "ghost iteration" technique to prove that the algorithm converges to an e- s-CCE in Ö(1/=²) iterations. We adapt the amplitude-encoding schemes from our CE algorithm to avoid the exponential gate overhead in the QRAM construction.
For the lower bound, reduce the direct product of m instances of the unstructured search prob- lem to the problem of computing an e-CE (e-CCE) of an m-player normal-form game. Then, we combine the lower bound the unstructured search problem [Ø]] with the direct product theorem [24]] to prove the lower bound on computing an s-CE (s-CCE) of an m-player normal-form game.
Open questions.
Our results leave several natural open questions for future investigation:
An open question whether the & dependence of our CCE algorithm can be improved. While quantizing the optimistic MWU algorithm of Daskalakis et al. [14]] is natural target, its analysis relies on high-order smoothness properties of the loss vectors. These properties are highly sensitive to the sampling noise introduced by quantum Gibbs sampler, making a direct quantization challenging (see the discussion in Appendix (D). A more promising di- rection would be to quantize the Regularized Value Update (RVU) framework of Syrgkanis et al. [G5]], which relies on more robust first-order properties. This could serve as a crucial first step towards quantizing recent, highly-efficient algorithms like Cautious MWU [32]. which build upon the RVU framework.
Beyond normal- form games, equilibria of Bayesian games and extensive-fome games are also studied in game theory [ B7 Dagan et al. [[]]] Peng and Rubinstein [29] showed
'This algorithm is designed for computing e- Nash equilibrium of two-player zero- sum game, but we show Corollary that it can be used to compute an e-CCE of multi-player normal-forn game.

---

that an E-CE in extensive-fom games can be computed efficiently. Can we design quantum algorithms to compute the equilibrium of Bayesian games and extensive-form games with quantum speedup?
Can reduce the time complexity of computing e-CE and E-CCE to (my/) which aligns with our query complexity? The difficulty is that we need to sample strategies for all players in each round of the game, and each call to the quantum Gibbs sampler requires access to the QRAM, incurring an overhead of (m).
Preliminaries
2.1 Game theory and no-regret learning
Game theory An m m-player normal-form game can be described by a tuple (fAA)== ) where A, with |A,
is the action set of player and C; is the loss function of player i. Without loss of generality, we let A; = [n]. Let A = Ai x ... x Am be the joint action set. The loss function of player is function L A 00, Bj, representing the loss of player i; here B is an upper bound on loss functions. For an action profile a (aI...., am) E A. let a_; denote the profile after removing ag, For any finite set S, we let ASS) denote the probability simplex over S. In each round of the game, player can choose an independent mixed strategy x; E (AA)). The collection of these strategies, (x1, (2i,...., Tm... Fm., is called mixed strategy profile and induces a product distribution over A. A more general concept is a correlated strategy, which is any joint distribution D E A(A). For mixed strategy profile x, we let x denote the profile after removing T₁.
We consider two types of equilibria in normal- games: correlated equilibrium and coarse corre- lated equilibrium.
Definition 2 (Correlated equilibrium). For an m-player normal-form game ([A:) (4.)m a distribution D A(A) called an e-correlated equilibrium if for any [m]] and any function 6. A. + Ai
E ([,c((a,a ((CC(((())))) anD
anD
Definition 3 (Coarse correlated equilibrium), For an m-player normal-form game ([Ai)T=
1m (L:) distribution D A(A) is called an e-coarse correlated equilibrium for any E [m]] and af E E,,
E [L((a,))))) E a anD
(4)
Online learning In the adversarial online learning setting, a player plays against an adversary sequentially for T rounds. In the t-th round, the player plays a distribution (+()) over its action set [n]. Then, the adversary selects loss vector g(t) E [0, B)" and the player suffers from loss (x<(1), g(t)).
The player observes the loss vector g(t) and updates its strategy based on the previous loss vectors to minimize its total regret in T rounds. We consider two kinds of regret: the standard external regret and the swap regret. The external regret of player is defined as
Regret,,r = ΣT (x (1) ((0)) - min,, (Z
(5)
which measures the maximum reduction in loss that could be achieved by switching to a fixed action strategy. Let 4 denote the of functions Φ: [n] + [n]. The swap regret of player defined as
Swap-Regret,.r ET (a (4)) - minser. ΣT E"=,"_10000 (10))))((((()))) (b()).
(1
(6)
which measures the maximum reduction in loss that could be achieved by using a fixed swap function on its history strategies. An algorithm is called a no-regret learning algorithm if the total regret o(T". The Multiplicative Weight Update (MWU) algorithm is a well-known no-external-regret learning algorithm. It updates the strategy by multiplying the previous strategy by the exponential of the negative sum of the loss vectors. This ensures that actions with lower cumulative loss are favored over time, achieving O(yTlog n) external regret. The detailed procedure is shown in Appendix A as Algorithm R.
Theorem 4 (Theorem 1.5 in [RI]). The external regret of the MWU algorithm Algoruhh with step size 1) Vlogn/ n/T/B is at most 2B BBBTTTT Tloo n.
5

---

The multi-scale MWU algorithm, proposed by Peng and Rubinstein [29], achieves polylog(n) swap regret by running multiple instances of the MWU algorithm in parallel different time scales. Each instance aggregates losses over increasingly longer intervals before performing an update, and the final strategy is a uniform mixture of the strategies from each instance. The detailed procedure shown in Appendix A as Algorithm E
Theorem 5 (Theorem 1.1 in [29). For any 0, the multi-scale MWU algorithm Algorithm 4 has at most BT swap regret in T = (16 (ng(m)/22) rounds.
No-regret learning in normal-form games It is known that if all players play according to a no- regret learning algorithm with external (or swap) regret at most s(T) in T rounds, then the uniform mixture of their strategies in all T rounds is an
-approxiaatni of coarse correlated equilibrium (or correlated equilibrium) of the game (see Section of [III]).
For the external regret, when loss vectors are ad adversarial, the celebrated MWU algorithm guarantees O(VTlog n) regret, which optimal (see Section 3.7 of [[[]]). However, the setting of repeated game playing, algorithms with recency bias can do better due to the smoothness of the loss vectors. Syrgkanis et al. [35]] showed that if all m players run an algorithm from specific class of algorithms with recency bias, then each player experiences O(log n vm - T1/4) external regret. Chen and
Peng [|]I] improved this bound to (log n TT16) in two- two-player normal -fomm games when both players run the optimistic MWU algorithm. Daskalakis et al. [[4]] then dramatically improved the T dependency by showing that all players run the optimistic MWU algorithm in an m-player normal- form game, each player experiences Ollgg n m log T) external regret, so the uniform mixture of their strategies is a Óm log n n/TT) -oorre correlated equilibrium after T rounds. The dependence on T is further improved by subsequent algorithms like Clairvoyant, and Cautious MWU [G0, 32), [33].
known that an external-regret minimization algorithm can be converted to a swap-regret min- imization algorithm [8. [d]] Chen and Peng [II],, Anagnostides et al. [M]] and Anagnostides et al.
[ used this reduction to design algorithms with 144), O T), and (log T) swap-regret re- spectively an m-player normal-form game if other players run the same algorithm. However, this reduction incurs an (i))) overhead. Dagan et al. [13] improved this reduction and proposed an al- gorithm that has at most ET swap regret in T (log n/ (01/e) rounds in the standard adversarial online learning setting, which aligns with the upper bound Peng and Rubinstein [29]]
2.2 Quantum computing
The fundamental unit of information in quantum computing is the quantum bit or qubit. Unlike classical bits that are either 0 or 1, qubit can exist in superposition of states, represented as a unit
vector in two-dimensional complex Hilbert space: [ı5) a00) + B]1), where {10), [1}} forms
(orthonormal) computational basis, and the amplitudes a, B E C satisfy |a|2+13 = 1. An n--ubit quantum system resides in the tensor product space of Hilbert space C², which can be written as (C2)d0n 2 with computational basis states {1=))?"-' and quantum state of n qubits can therefore represent a superposition of all 2" possible states: ((b) = Ei-o 2- azli), where E. log 1. Information can be obtained by quantum measurement
computational basis, where measuring state (46) Ei a; (i) on basis ((i)) yields outcome with probability p(i) = la,|2 for every i E [2n]. Quantum states evolve through unitary transformations: ( - Ul+), where U E C x2" a unitary satisfying UUT U = Ize, where Ut is the Hermitian conjugate of operator U. For two quantum states (b) - agli) () and (o) = -/-0" B,((), their inner product is defined by (ilv)) = Σ. of 3r. The tensor product of two quantum states (v) E Cd. and (0) E Cd2 is denoted as |)) = (v) @ (Ø) E Cd1da
In the quantum query model, algorithm accesses the given function f via a quantum oracle. This oracle, denoted O, is defined as a unitary operator that performs the following reversible computation on the computational basis states: 10) [=)])()))- A key advantage of this model is that the oracle can be queried on a superposition of inputs.
The term QRAM can refer to several distinct models in quantum computing. In this work, we use "QRAM" to refer specifically to eircuit providing quantum access to classical data, a model more precisely known as Quantum Read-Only Memory (QROM). We retain the more common term

---

QRAM and the notation UQRAM throughout this paper for consisteney with related literature. For- mally, for memory containing N classical bitstrings {D; J. this unitary performs the mapping UQRAM + Dt). Such circuits can be constructed from elementary gates with complexity linear in N and the bit-length of the entries [+]]
2.3 Quantum algorithms for games
Quantum algorithms for finding Nash equilibria in zero-sum games have been well-studied [G3, 9, 18), and achieve a quadratic speedup in Most of the quantum algorithms for games quantize variants of the MWU algorithm. Note that the strategies output by the MWU algorithm can be written as an exponential of the accumulated loss vectors. For classical MWU algorithm, computing the exponential of a vector u I" requires Q(n) time. To reduce this overhead, quantum algorithms use the quantum Gibbs sampler. Suppose that the quantum algorithm can access a unitary operator V which encodes the vector u:
Definition (Amplitude encoding). unitary operator V is said to be B-amplitdde-enooding of vector u E I=" with non-negative entries, if
(0/cV10)cl))
i) A))))
for all i E [n). Here, 114) B is normalized garbage state in an ancilla register.
Then the quantum Gibbs sampler can prepare the state Ei=ve i) wa)) where the distribution q (qn...., In) is close to exp(-u)/Il exp(-u)]lı: and measuring the first register gives ple approximately from the distribution exp(-u)/l cxp(=x))
Theorem QQaantum Gibbs sampler (LS]). Given access to a unitary V which is a 8-amplitude- encoding of vector R", there is unitary oracle (Gibbe()) such that
OGibbs(8)) (8): 10) Ei= ())))
(8)
where q is 8-close to mented using (i)) queries to V and ((3))) time.
exp(-u)ll in total variation distance. OGibbe can be imple-
In many game-solving algorithms that Gibbs sampling, the underlying vector changes slowly, often receiving only sparse updates in each round. Based on this property, Bouland et al. [*] pro- posed dynamic Gibbs sampler, an oracle Odynamic-Giin for repeatedly sampling from distribu- tion that is 8-close to the changing Gibbs distribution exp(u)/ll exp(u))lı-
(9I) Given 1) > 0,0 and access quantum oracle for A E R xna Now consider a sequence of size T. where each item includes an "Update" operation to a dynamic vector x E Rng each in the form of 2; & I; + dyyaamic- Cenamic-Gibbs during the for some i [nea]. The goal to maintain 5-approximate Gibbs oracle Ox "Update" operations. Let Tupdate denote queries per operation we need, and let Teamp denote the worst-case time needed for Az
Problem (Sampling maintenance for two-player game, Problem
1,
R
20-
Gddnnamie-Gibbs
Bouland et al. [ provided an efficient solution to Problem 2 using a special data structure to store partial information of the Gibbs distribution and maintaining its effectiveness across many rounds to reduce the amortized complexity of each sampling.
3 Quantum algorithm for computing correlated equilibria
In this section, we present the quantum algorithm (Algorithm I) for computing an e-correlated equilibrium (s-CE) in a normal-form game. The high-level ideas of the algorithm are presented below. The implementation details, as well as the formal proof of the algorithms correctness and complexity analysis, provided in Appendix B and Appendix H
Our quantum algorithm (Algorithm T) for computing an &-CE of a normal form game improves on the protocol in Peng and Rubinstein [2%]] The algorithm simulates players playing the game repeatedly and using the multi-scale MWU (Algorithm 4) algorithm to update their strategies. At
the t-th round, to estimate the loss vectors, we use quantum Gibbs sampler to sample from the joint
7

---

distribution of all players' strategies at this round. We sample S action profiles (t.1)) (((.8) E A and let the loss vector of player the t-th round be
(a)) = Σ.= Li(a;;=44) (1 Va, A.
(9)
Let K = = rule of the multi-scale MWU, the strategy Pr, of player i is determined by its accumulated loss vectors:
[oog((1/ + 11, H [ be the internal parameters. According to the update
Pi, 2
1 ExE(2K) Pi,k,t.
(10)
where
Vogn/ (nk 21= lxr(ai)) Va, A.;
(11)
Pk.t and hy,t correspond to the parameters r and h in subroutine MWU,, in the 1-th round of AE gorithm 4. and they can be computed from and The complexity bottleneck of the classical protocol in [29] lies in computing the n-dimensional vector k,t. which requires si(n) queries. To achieve sublinear quantum query complexity in n, we store the historical samples a quantum ran- dom access memory (QRAM) and use quantum Gibbs sampler to approximately sample from the distribution Pi,t.
Algorithm basple- multi-scale MWU for CE
1: Input parameters m (number of players), n (number of actions), e (error parameter), (bound loss functions), (failure probability)
2: Internal parameters K = [log2 (3B/e) 1], H [4log())22K], T H²a S
18B
log
2mnT
8 == z/6B
3: Output quantum state (ebo)
4: for 1,..., ...,,T Tdd do
5: Obtain a unitary Vú such that for any E [m] and [2*), (1]())))))))))) is (Bhg, (Bhr,FHk-1) Hk-1)- amplitude-encoding of the vector
(>== 11
(Etree ( the H
C(lnn a.Ed.
(12)
such that
(rr
Tke
hg
H1
(13)
6: For any i [m]. independently obtain samples a;
(f.1)
(t.S)
from the Gibbs sampling
oracle Gibbbs (8) with uniformly random E [2*].
Vlogn/Hi,
7: Store the samples a (1.8) (a. (t,*)) ke[ml for E [S] in the QRAM.
8: end for
9: Prepare the uniform superposition of / E [7] and k E [2*]]
T 2
A0),,10)
(14)
V2K
xE(m)
Apply Gihbs
(8) to register A; and B, for all i E [m]. Denote (Va) as the resulting state.
Aogn/Hig. return the state (v))
4 Quantum algorithm for computing coarse correlated equilibria
In this section, we present the quantum algorithm (Algorithm 2) for computing an E-coarse corre- lated equilibrium (s-CCE) in normal-form game. The high-level ideas of the algorithm are outlined

---

below. The algorithmic details and the formal proof of correctness and complexity are provided in Appendix B.3 and Appendix B.4
Our quantum algorithm (Algorithm 2) for computing an e-coarse correlated equilibrium a normal- form game improves the classic algorithm in Grigoriadis and Khachiyan [T\] using approximate quantum Gibbs sampling instead of exact computation. The main technique we use is stochastic mirror descent, into which we incorporate an approximate Gibbs sampling. In each round of the algorithm, we perform Gibbs sampling on the current weight of each player, using the sampling result minimize the first-order approximation of loss function with the added KL divergence at current strategy for each player. At high level, for the strategy u; update method satisfies
obtained in each round, our
(++1) so arg minu, { (c..G. u ")) us) + Enem [u]] log
(15)
In the two-player game setting considered in Bouland al. [[] sampler tree data structure is employed, where for each player, an n-dimensional vector is maintained to record the opponents strategies over previous rounds. Extending this to m-pllaer game presents significant challenge, since the number of opponent strategies is on the order n n To enable an efficient dynamic Gibbs sampler, improve upon this approach by leveraging QRAM to directly store the strategies from each round. This allows us to achieve the same functionality as the sampler tree with identical query complexity but improved time complexity. See Appendix B for implementation.
Algorithm 2 Sample- based MWU for CCE
1: Input parameters m (number of players), n. (number of actions), & (error parameter), (failure probability)
2: Internal parameters
max
64B logn
512 lng(4/o) }1 n = Vlogn/T/ /
16B(n-1)
3: Output (f:)
4: Initialize d; O,
5: for = O do
6: Independently sample a;
(t) from Odynamic- Et (),a4)) (8) for E [m] and set a())
Odynamic-Gibbs Gibbs
(ai
........ am (2)
(e)
7: Store the sample (9) in the QRAM.
8:
Update é; = às + e e0 for E [m].
9:
end for
10:
return (Z:).e(m)
Note that using exact oracles of Gibbs sampling, the main skeleton of the algorithm is a natural extension of Grigoriadis and Khachiyan [19] from two-player games to multi-player games. Corollary 1. There exists a classical algorithm that computes an E-coarse correlated equilibrium with high probability using Ömmn/e²) classical queries to
5
Quantum lower bounds
In this section, we prove quantum query lower bounds on finding correlated equilibria and coarse correlated equilibria.
5.1
Quantum lower bound for computing correlated equilibria
For computing correlated equilibria, Algorithm 4 solves the problem using Ō(myn) queries. To complement this upper bound, we prove matching quantum lower bound (up logartggaii factors) in m and n..
Theorem 7. Let B denote the bound of loss functions. Assume O < E < min 2R). For m-player normal-form game with n actions for each player, to return an E-correlated equilibrium with success probability more than 2. we need Qi Qmm queries O...

---

To prove Theorem 11 we construct hard instance and claim that finding an e-correlated equilibrium on this instance is sufficiently difficult.
Definition (Hard Instance). Consider an m-player normal- carmmll-fommmma game with v. actions {1, 2, ... n) for each player. Each player i E [mn] selects kis E [mx] uniformly randomly, and then define the loss function as follows:
f0 B
if kej
Li 02,...,,
if a + kG.
Here a; is the action taken by player
The e-correlated equilibrium of Definition is straightforward: each player i [m]] takes action k; with probability more than - e B. Intuitively, each player's 's utility depends only on their own actions and is independent of the strategies of other players. Therefore, the goal of finding the correlated equilibrium is essentially to determine the value of k; for each E [m]] This is similar to computing copies of search problem on the entries of A with |A| query lower bound of correlated equilibria by constructing a reduction between the two problems.
and will establish
Lemma 1. Given an algorithm A finding an e-correlated equilibrium of Defimttinn 3 with success probability more than 5, we solve the copies of n-item search problem with success Em B
probability (6
applying A once.
Finally, for the copies problem, Lee and Roland [24]]] proposed the strong direct product theorem that establishes a lower bound on the query complexity for such problems. In our setting of the cor- related equilibrium problem, this lower bound corresponds to my/ri which matches the complexity of Algorithm 4 This indicates that our quantum algorithm is optimal in terms of both m and n. The formal proof of Theorem 7 and Lemma D are provided in Appendix
5.2 Quantum lower bound for computing coarse correlated equilibria
Now, we consider the quantum query lower bound on finding coarse correlated equilibria. Notice that for our hard instance Dehmition S1 e-correlated equilibria and e-coarse correlated equilibria are equivalent. Therefore, we can directly derive the quantum query lower bound for finding coarse correlated equilibria from the above analysis:
1 28), for Corollary 2. Let B denote the bound of the loss function. Assume O < < minf 3: an m-player normal-fom game with actions for each player, to return an E-coarse correlated equilibrium with success probability more than 2 we need (/m)/n) queries to O.,
Acknowledgments
This work was supported by the National Natural Science Foundation of China (Grant Number 62372006).
References
[1] Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736-749, 2022. arXiv:2111 06008
[2] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with Ollogt) swap regret in mul- tiplayer games. Advances Neural Information Processing Systems, 1-3299--334, 2022.
arXiv:2204 1141/
[3] Joran van Apeldoor and András Gilyén. Quantum algorithms for zero-sum games, 2019.
T9x 03180
[4] Robert J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Math- ematical Economics, 1(1):67-6,, 1974. doi: 10. 00.101660000444406774990007...70 URL. https
//doi, org org/10.0.
10

---

[5] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear complexity. Physical Review X, 8(4))041015, 2018.
[6] Charles H Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Com- puting. 18(4):766-7) 776666777,111 1989.
[7] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510-1522 1997. doi: URL https://doi. http////..1111/00777777666666680
10.1 10.1137/5009753999600333
[8] Avrim Blum and Yishay Mansour. From external to internal regret. In Learning Theory; 1 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005. Proceedings 18, pages 621 6236 Springer. 2005, doi: 10.1007/11503115 42. URL https:
1007/115031111 42.
[9] Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian. Quantum speedups for zero-sum games via improved dynamic Gibbs sampling. In International Confer- ence on Machine Learming, pages 2932-2952. PMLR, 2023. arXiv123m 03746
[10] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge Uni- versity Press, 2006. doi: 10.5555/1137817. URL https://dl. acm. org/dor/10.55555555
[11] Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:18990-18899 2020.
arXiv:2200..0e 04955
[12] Xi Chen, Xiaotie Deng, and Shang- Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3), may 2009. ISSN 0004-5411, doi: 10.1445//166511.1556666 URI. https://doi. org 10. 1145/1516512..1 1516516
[13] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From Exter- nal to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1216-1222, 2024. doi: 10. 1145/361 (44533688200.6440 8260.36496881.1111 1. URL sittps://dl acm. wwc.m.org//oo/////
3649681.
[14] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optime no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604- 27616, 2021. arXiv:2108 06924
[15] Dean P. Foster and Rakesh Vohra, Calibrated learning and correlated equilibrium. Games and Economic Behavior, 2 4105-2):40-55, 1997. doi: 10.1006/game..e 1997.0559. URL https:
odgo0.0r/10.. 1006/
gamee//ame.....oooo...m..... game 1997 0595,
[16) Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul Spirakis. The structure and complexity of Nash equilibria for a selfish routing game. In Inter- national Colloquium on Automata, Languages, and Programminng, pages 123-134. Springer, 2002. doi: 10. (0.1//..cc..008.01...0 URL
tcc. 01.
[17] Kaito Fujii. Bayes correlated equilibria and no-regret dynamics, 2023. arXiv:2304.05005
[18] Minbo Gao, Zhengfeng Ji. Tongyang Li, and Qisheng Wang. Logarithmic-regret quantum learning algorithms for zero-sum games. Advances in Neural Information Processing Systems, 36, 2024. 23X4222434.1197
[19] Michael D. Grigoriadis and Leonid G. Khachiyan. A sublinear-time randomized approxima- tion algorithm for matrix games. Operations Research Letters. 18(2):53-58, 1995, doi: 10. 101601667-6377755000033
URL. https://dl. acm. wtt..aa....././///000110/00/0000
00032-0.
[20] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently inte- grable probability distributions, 2002.
[21] Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016. arXiv-1909
[22] Rahul Jain, Georgios Piliouras, and Ryann Sim. Matrix multiplicative weights updates in quantum zero-sum games: Conservation laws & recurrence. Advances in Neural Information Processing Systems, 35:4123-411 4135,, 2022.

---

[23] Albert Xin Jiang and Kevin Leyton- Polynomial time computation of exact correlated equilibrium in compact games. In Proceedings of the 12th ACM Conference on Electronic Commerce, pages 119-126, 2011. arXiv.IU1I.0253
[24] Troy Lee and Jérémie Roland. A strong direct product theorem for quantum query complexity. Computational Complexity, 42:429-462, 2013. arXiv:i1us, 4468
[25] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for train- ing linear and kernel-basee classifiers.
International Conference on Machine Learning, pages 3815-3824. PMLR, 2019. arXivI904.. 02276
[26] Wayne Lin, Georgios Piliouras, Ryann Sim, and Antonios Varvitsiotis. No-regret learning and equilibrium computation in quantum games. Quantum, 8:1569, 2024.
[27] Kyriakos Lotidis, Panayotis Mertikopoulos, and Nicholas Bambos. Learning in quantum games, arXiv preprint arXiv:2302.02333, 2023.
[28]
Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi- player games. Journal of the ACM (JACM), 55(3):1-29, 2008. doi: 10.1 (0.1144/13797999137999 URL.
111.1/..........1111//77777..... 1379762
[29]
Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approx- imate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pages 1223-1234, 2024. arXiv 19647
[30] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. Ad- vances in Neural Information Processing Systems, 35:22258 22269,, 2022.
[31] Robert W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973. doi: 10. (0.1007/BF07333559 URL https://doi.
org/10. 1007/BF01737558.
[32] Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Cautious optimism: A meta- algorithm for near-constant regret in general games. arXiv preprint vrXiv:2506.0500) 2025.
[33] Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Faster rates for no-regret learning in general games via cautious optimism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 518 529, 2025.
[34] Gilles Stoltz and Gábor Lugosi. Internal regret in on-line portfolio selection. Machine Learn- doi: 10. 10994-005--045544 URL fttps://doi.org//1
ing. 59:125-159, 2005,
1007/810999--00--666----
[35] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
arXiva150%.
[36] Francisca Vasconcelos, Simmanouil-Vasilede los, Georgios Piliouras, and Michael Jordan. quadratic speedup in finding nash equilibria of quantum zero-sum games. Quantum, 9: 9:173,, 2025.
MatakissGGaragkoumm Panayotis Mertikopou-
[37] Bernhard Von Stengel and Françoise Forges. Extensive- form correlated equilibrium: Defini- tion and computational complexity. Mathematics of Operations Research, 1002):000- 2008. doi: 10. 1287/oooo 10800.0340 URL https://pubsonliie informs wwgg/oo////// do1/10.
1287/moors /moor 1080. 0340.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction state the query and time complexity bounds in
Theorem 8, Theorem 9. [heorem 7 and make broader claims beyond those formally proved.
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The "Open Questions" paragraph explicitly notes that the e-dependence and the time complexity bounds are not yet optimal.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitttions"" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: All assumptions are stated with each theorem, and full proofs are given in Appendices B B4 and Q
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiments were performed.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
No data or code are used.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:)
/ hnaps.cc/publiccguiddee (CodeSSub wwtsssummmssioooooooooo ssioniolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:////wripp...co/blllt///ttta
Answer: [Yes]
Justification: This theoretical work that does not involve data, and we do not foresee any socictal or ethical harms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our quantum algorithms can be used to compute correlated equilibria, achiev-
ing asymptotic improvements in query complexity over classical approaches, We do foresee any negative societal or ethical impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g,, deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: No data or generative models are released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards
allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No existing assets are used.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, snperswithcodd www.coocccaa.ooe datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
If assets are released,
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Question:
Answer:
[NA]
Justification:
No new assets are released.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.M policy battps://neune http://arpppccc//aaeeeeeeeeeeeee / for what should or should be described.
19

---

A Omitted Algorithm Details
Below we provide the full pseudocode for the Multiplicative Weight Update (MWU) and multi-scale MWU algorithms, which are referenced in Section
Algorithm 3 Multiplicative Weight Update (MWU)
1: Input parameters T' (number of rounds), (number of actions), B (bound on loss vector)
2: for = mort=1..... .....,TT do
3: Set a1 E ([n)] such that a,00 (i) x exp( exp(-n E (1)) for [n], where r
Vlogn/ n/T
4: Play x(() and observe g(t) E [0, B)"
5: end for
Algorithm 4 Multi-scale MWU
Input parameters (precision), n (number actions), B (bound on the loss vector)
Internal parameters K := [1) H := [4 [4log())22 number of rounds T' == 2 for t I,..., do Let qu E An be the strategy of MWU, (k E [2*] D. play uniformly over them
Pt 2x Eme[2K) Or.t
(16)
end for procedure MWU,, for r = 1,2, ...., T/ do
Initiate MWU with input parameters H, n, H-1
for h = 1, 2,..... ,....,,H H do
Let Zr,h A, be the strategy of MWU the h-th round
Play 2r for = days
Update MWU with the aggregated loss of the last 1-= days
+ho 1b) (0))) [E(N] E [0,
(17)
end for end for end procedure
B Technical details of algorithms
In this appendix, we present the implementation details and formal proofs of our main technical results, [Teorrm I] and [Theorem Specifically, we provide the correctness and complexity analysis of our quantum algorithms,, Algorthhm I and Algorithm 4, for computing an e-correlated equilibrium and an e-coarse correlated equilibrium, respectively.
B.1 Implementation of Algorithm
We now describe the details the implementation of Algorithm At the t-th round, suppose sam- ples before the t-th round are stored in the QRAM. Then we can access the samples in superposition by applying the unitary UQRAM such that
UQRAM: 1+)1)) + |T)
(18)
for any 7 and [S]. Given access to the QRAM, we now show how to implement the unitary V2 in Algorthmm Since Te,k and hg,k be computed efficiently, we can prepare the following
20

---

uniform superposition state given & and t:
(raje-1)ft + t H
Σ
|r)
(19)
H (
Then applying UQRAM, we get the uniform superposition of samples:
(Fr,e-1) + +h,.
Σ
(a
(20)
Vha. H
1)
Using one query to Oc and O¹2 we can map
[i)la))aa (lla)la_.)00 (+)a;))a=;))
(V
[1) (illoaa
V
Cclar,a-)) (0)
(21)
B
B
Combining Eq. (19)) Eq. 22)) and Eq. (2I). for any i E [m], E [2*] and a; E As, we can perform
the following unitary transformation:
1i: (000001000000111110
(PK. 14.e-1)
/Liuu, ((ia)
H (k)1){as)) v hhx 1
Σ
( (V
103
(22)
B
(P 11HH++
Ci Li(an, (T,80)
(1))
(re,e- 11
(a:)
_a,)) TTx HK-I
Σ
1)) + lo:)
(23)
B
(12,,-11)H*
where (et)) is normalized state and (ot) is an unnormalized garbage state, and for any i E [m]. (()()))) is a Bh waap--ll--uiuudeeeeeeeeee
of the vector l. =
(E (1) the (a,)(as)
the Gibbs sampling oracle Gibbs a,EA; Given the amplinde-encoding of Ex,,, can implement
(Er=(r, -1)
Vlogn/HEe, (0) using Thcorem 6
After T rounds, prepare the uniform superposition of E T and k E [2*]. By coherently apply Vi controlled by an ancilla register [t), we can implement ΣiEry Jy [t) @ V.. Then following the previous steps,
apply GGibbs /logn/HE,, (5) conditioning the first two registers containing
[t). The resulting state is the output of Algorithm
B.2 Proof of [Theorem
We give the formal version of [hcorrm and provide its proof.
Theorem 8. For any m-player normal-forn game with n actions for each player and E (0, 1), Algorithm 1] outputs an e-correlated equilibrium of the game with success probability at least 1 using O log(1/o) /o:)) (Iog(n)B/e) O(Bfs) poly (log n, log m, 1/e, B) queries to Oc and O(m /olog(1/a)) (log(n) O(B/e) poly(log n, log m, 1/e, B) time.
Proof. Correctness. At the t-th round, denote the output distribution of the quantum Gibbs sampler Gibbs
(8) by K. and Pi.t := * ExEpx (ik.t. By [heorem we have [| -u.,,ell S
Vlogn/Hle
8 and hence lirr. Pielli < 6. The output state of Algorithm is
2
Σ
V (annaa))laidaWiea))))
(24)
T22
iE [m|m
NazeA:
21

---

which can be written as
3 (e(m] ozEA;
Vina(ar) ai)a, (0a)))
(25)
for some normalized states ((,,). Measuring the register A, for all i E [m]] gives the distribution T DeerT Rijmt
For any player [m], since Pi, is the strategy of the multi-scale MWU algorithm with param- eters K 1ogg(33/s) 1, H 4log(n)222 l.11.... 1,,-111 by Theorem S we have
H2*h at the f-th round given loss vectors
n ΣΣ Phlli) (,()) S De
E (a,)
min
B 3B
(26)
Let lip = 2(:0-1,) be the expected loss vector of player in the 1-th round. Since Ca is the average of L(., a ( for [S] and (t.s) is sampled independently from p-i, by Hoeffding's inequality, we have
E²5 S (
Pr [k),(a))) - (aa(al) 2 2 cxxp
a
-188²/
(27)
mnI
for any i E [m], L E [T]. and as E A,, Taking a union bound over i E [m]] I E [7], and as E Ai, we have
((,((a)) - {a,)(a,)) 6
(28)
for all E [m]. I E (T), and ag E A, with probability at least ac Therefore, for any swap function
D,, we have
piie Reee)
1
Σ
T
pt)(i) ((((()
(29)
T
(=1==1
[=1
1 T
Σ
Pt,(i) - (,,(()()) +
(30)
T
T (=1
t=1
8
8
28
+
(31)
3
3
Let D be the distribution EvErTy Die(m|ps.e Since Pt,e. Pr, is the uniform mixture of ktk, 4t.k,t for k E [2*] respectively and |1 - q. I 8, we have ll Puella S 6. Then we have
EanD [Cr(a,, a)) Ea (awp((i(((aaa) (((((())).
(32)
T
T
1
Pr.e0 Pa.))
ps.(()) 4.(((())
(33)
T
t=1
T
T
(pr., Ea.))
1
Σ
Σ
Pa.(()) (,,( 28B
(34)
T
T
1=1
==
28 8
= E.
(35)
3 3
Therefore, D is an s-CE of the game.
Query complexity. Each call to Vj in Eq. (22) requires one query On and Of By Thee f. we need Bh /lggn/P H vn) calls to V, to get sample from k. Since ha. smaller than and H² < H22 =T for E J, we need
H Vlogn/H. v 0(BH Ö(BT
(36)
22

---

calls to Vi to sample from R.,... Since we need to get S samples for m players in T rounds, the total query complexity is
Ō (BTyn- S m 7) 0
(37)
where the Ô notation hides polynomial factors in log n, log m, 1/e, B. Substituting T = H²* (Iog(n)B/E) O(B/s) the query complexity is
O(m)nlog(LL/)) (log(n)B/e) O(B/c) poly(log n, log m, 1/e, B).
(38)
Time complexity. There are TS entries in the QRAM and each entry has m log n bits, so the time complexity of applying UQRAM and modifying one entry is O logn) [5]. At each round, we need to modify S entries of the QRAM to store the new samples. To prepare and sample from the Gibbs state, need to call UQRAM the same times as the number of queries to Oz. Therefore, the time complexity is
(TS + O(myTlog(LLa)) (log(n)B/E) O(B/)), poly(log n, log m, 1/e, B)) O log n) =0(m² (Tlo""(()) (log(n)B/E)
O(B/e) poly(log n, log m, 1/E,B)
(39)
B.3 Implementation of Algorithm
In this section we introduce our Gibbs sampling method in Algorithm 4 Specifically, we extend the dynamic Gibbs sampling of two-player games, as given in Lemma 1 to multi-player games, and provide a more refined explanation of the query and gate complexity.
Lemma 2 (Theorem 3 in Bouland al. [H]). For failure probability a (0.1) and 5 n, given a quantum oracle for A E R XR2 with | I 1, there is a quantum algorithm which solves Pmoblem A with probability more than
using
(1 VnnIn log"
(/rios
(minT) a
nnanT
max(Taamm Tupdate) =
+ rj log a
time with an additive initialization cost of O 3 log (mnge) + log"
The complexity of this method consists of two parts: maintaining the data structure in each round and sampling from it. It should be noted that here we assume access to a classical-write / quantum- read random access memory at unit cost. In the actual implementation, if we consider the gate complexity of QRAM, we need additional gate complexity, which is proportional to the number of entries in QRAM and the number of bits per entry.
The Gibbs sampling used in Algorithm 2 can be formalized as Problem 3. which is an m-player game version of PProblem 2 Note that the vector of size n maintained in Problem 2 actually records and maintains the combination of opponent's strategies of the previous t rounds, where in each round partieular action is updated. In m-player games, the m 1 opponents have n= possible strategies, and we can use a high-dimensional array to maintain the information of opponent strategies. A simple idea is that we can use the method in Bouland et al. [5]] to store the opponents' strategies in the high-dimensional array of size n n21 using a special data structure called "sampler tree". but the cost would be exponential large in storage space, leading to exponential gate complexity if using QRAM. Considering that the array is sparse, we improved this method by using QRAM to directly store the strategies from each round, achieving better time complexity.
Problem 3 (Sampling maintenance for m-player game). Given > 0. 0 < 8 < 1, and sup- [0, For player i,
pose that we have quantum oracle for the loss function Lilj, (1) consider sequence of size T, where each item includes an "Update" operation (m 1)- dimension dynamic arrays D indexed by actions of the m - opponents' strategies I=i (01, .i, Zit1...., Em-1) where Ij [n]. with each entry D(s 2 0. Each "Update" operation takes the form of D(z_.) + D(z_.) + 17 for some D(z_.) mn]m-11, Let Tupdate denote queries per operation we need to maintain a 8 ô-approximate Gibbs oracle Odynamie-GGii Gibbe of vector dynamie--Cin Gibhs Le(j, D) (for different strategies j), and let Tsamp denote time needed for Lx(.D)
23

---

In the algorithm proposed by Bouland et al. [9] a key step involves using sampler tree to store 220 and prepare trj amapliie encoding of Ax (Corollary 4 [9]:
A B
O O₂ = 10)
Σ VE(M)
1011) + (1)1s)) (z), here 3 2 |||||| and [g) is unnormalized.
(40)
Corollary 4 in [*] shows that we can maintain the oracle As with total building time cost O(T lo after T' rounds, and each call of OAz requires Ollo n) time and O(1) queries to the given oracle Oz. However, this is based on the assumption of access to a classical-writt quantum- read random access memory unit cost. For gate complexity, such an assumption neglects the entries of this data structure (n for two-plat two-player games) and the number of bits used to store informa- tion, which is related the precision we require.
Instead of maintaining the sampler tree in Bouland et al. [ we maintain a QRAM storing the sample of strategies, which means that at time we can access the unitary UQRAM such that
UORAMITXO) - (r))a(r))
(41)
for all 7 < f, where a" E A is the sampler at time т. Accordingly, in our algorithm we need to implement t-amplitude encoding of
Σ (,)
(42)
This is can be implemented by performing
Cilas,a
Li (7)
la.) + la:) Vt ==1
IT)a 1a
[1) + V
10)
(43)
B
B
-lai)
1 Σ Li a
3) + 11:)10)
(44)
IB
for some normalized state (bx)) and unnormalized state lo.). This is a tB-amllitude encoding of Et= (7).
There are entries the QRAM. For the precision be considered, each entry has O(m log bits, and thus the gate complexity of applying one UQRAM and modifying entry is O(Tm log n). Note that we also use a sampler tree to directly store the sparse high-dimensional array D, since D has n22 = n== entries, we will similarly require Ö(log (())))n) tree. However, the additional cost is that the sampler tree itself requires exponentially large storage space, and thus leads to an exponential gate complexity if using QRAM for storage. For query complexity, both construction methods require (1) queries to achieve t-amplitude encoding of L (.)
Ó(m log n) queries to the sampler
Here we present a modified version of Theorem 3 in Bouland et al. [
Lemma (modified version of Lemma 2 for m-player game). Let ng == n m-1 For failure proba- bility a E (0. 1) and 8 < 7, given a quantum oracle Oc, there is a quantum algorithm which solves Prohlem 1 with probability more than a using
max (Taamp Tupdate)
-o + Vn- T' T' log log" (7)
(V
nyil
nnT
+
n log
quantum gates and
ol
o Vn Vn- Tn log* (T)
(pnlos
mn/T")
log
a
queries to Og, with an additive initialization cost of
(187T (znnk) + log" (mxz)
24

---

The proof of the lemma is entirely consistent with Lemma aforementioned QRAM replace the sampler tree implement the t-amplitude encoding of Σ Li(-, (7)), (.). We only need to make slight modifications to the parameters, as noted in Rez mark
where we simply use the
Remark 1. In the results presented in (9], the term related to the number of opponent strategies f2 = n==1 is of the form log" T22- However, in their sampling algorithm, the authors only used O m2)) queries to the sampler tree to prepare oracle Ax within the sampler tree. There are no computations involving time that are dependent on n2 in the other steps. Hence, this term can actually be corrected to log" n22, which corresponds to the time of achieve t-amplitude encoding of Ci By replacing the sampler tree with QRAM, we obtain our gate complexity with the term T' log n, as showed in Lemma Furthermore, as we only need O(1) queries of Oc to achieve the encoding, the query complexity does not include the term I'm log n.
Remark 2. The complexity in [9] has an additive 3 term, which arises from an additive initial- ization cost ( in Lemma 2 This term is unrelated to the number of queries to the loss oracle Oc and appears only in the time complexity. The distinction is that their QRAM model assumes that mathematical operations can be implemented exactly in O(1) time, whereas we further consider the gate complexity of QRAM operations in analysis. When considering query complexity, their dependence on e is ((1/=2.5), which matches ours exactly. However, for the time complexity, due to our additional consideration of the gate complexity of QRAM operations, our overall time complex- ity becomes ( (, which is larger than e-3 Therefore, we do not explicitly include the additive initialization cost ferm e in the final stated result.
B.4 Proof of TTheorm
In this subsection, we will provide a proof showing that Algorthh 2 can output an E-coarse cor- related equilibrium with high probability, and calculate the complexity based on the results in Lemma 3 The formal version of [heorem is stated below:
Theorem 9. For any m-player normal-form game with n actions for each player and a E (0, 1), Algorithm 2 computes an E-coarse corvelated equilibrium of the game with success probability at least a using Ömmn b $) queries to O and Ö(m2n² B 9) time.
Proof. Correctness. For convenience, we denote 8; by the vector for Gibbs sampling of player i in t-th round, i.e., ((9 == - Ei a The proof of the correctness [heorem consists (t) of two main parts: First, demonstrate that the uniform mixture of Gibbs distribution of 8; in each round is an O(e)-coarse correlated equilibrium of this normal-form game. Then we consider the action strategies a!") generated by the Gibbs sampling in our algorithm, and we will show that they can also derive an approximate coarse correlated equilibrium.
exp(s and El = (x(,,a")) for all t = O....,T T 1. The regret bound of Denote u exp
MWU Theorem 4) implies that
T-1
T-1 (u, (10) 5 2B (lg((nT
Σ
(u
Σ
(45)
1=
1=0
for all i E [m] and u E ([x)).
We now "ghost iteration" argument in [X]] to bound the regret of u. (t) (00) = L.(. u ())) Denote τ = ((0)
with respect loss vectors
(1)
=
uz and
1-1 ((7)
!1)
(46)
eepp ( En 11
for < = 1,..,, T Then ['heorem 4 again implies that
T-1
T-1
(u(0)
(1)
2
Σ
(u, 2 s 2B Iog(n)]
(47)
0
0
25

---

for all i E [m] and u E A(n)).
Summing Eq. (95) and Eq. (H7)) gives
T-1
Σ
Σ (u,
)
Σ
(1
- S 4B /By4lo(())
(48)
Considering that u can be arbitrarily chosen in [(m]), we have
T
max (EA(())
Σ (1
Σ
(u,
+
( u
(0)
20 -0000--00 - 4B v log(n)T. (49)
t=0
t=
Taking the expectation of the left-hand side, we have
E
Σ
(4) (u
200)
Σ
(u,
+
u 20 -(7))
(E)((M))
2=
<4B Vlo(n)TT.
(50)
Consider the second term on the left-hand side,
Ea (tt)
(ū) u (
(1)
e(") _att,,... ((t-1) (ū (1) 20 Eat 16,001 (51)
Suppose that the Gibbs sampling oracle gives a, from p!0 by the assumption 1:! (1) || S 5,
we have
X
Jet Pj (())
j+l Uj ll I (n - 1)o. Note that Eaco) [e = L,(, p ) as L, [),
we have
fu (
20 {(:o s 2(n 1)BT8.
(52)
G1B² log n and S 8(n-1JB for
Therefore, summing Eq. (50) and Eq.
taking T
(ū,.... ūm)) = T 1=0
ETD T-1
(wi
Um we have
E Big M2 MT
max (fE)((n))
lawi
E ( a-1)]
ang
E (c a الل
T
E
1
max (E)(M))
(ug
(00)
(u, ((1))
(53)
T
t=0
t=0
(54)
2
Next, by a martingale argument we will prove that with high probability, provides an e-coarse correlated equilibrium
Algortthm
implicitly
Consider filtration given by F, = (s(0),
s(1) .... 8()),, where (()) = (s(0) 82
8m
(0)
Define
martingale sequence of the form D, == (u (()) 2(0 e!!)) (m (0) p()) Ele
F
1)>
Notice that with probability we have [Dr 5 4B. Azuma's 's inequality implies that
T-1
(cTT/4)2
E T D
Pr
< exp
2T (4B)2
exp
512B²
(55)
t=
512B" log 5²
Taking T'
we thus have
(1t
(1)
,
(00)
10)
<
E
10
(1)
+
E
T
(56)
t=0
with probability more than -
26

---

Combining Eq. (99) with Eq. ((52), it gives us
Σ Kun e?00 2 (57)
a[EA([n]
max E [Ci(a,, a=:)] E [C((d,, ac(d,,
Lavi
max HEA((N)
0
35
4
with probability at least 1 4- That is to say, ū is O(e)-coarse correlated equilibrium with probability at least 1 a
Finally, note that Gibbs sampling implicitly implements the sampling oracles for u but cannot directly provide these distribution vectors explicitly. We will prove that coarse correlated equilib- rium (i.e., 22)) can be found with probability least based a (t) from Gibbs sampling in each round.
We previously used the notation (t) to represent the actual distribution of 0; sampled from Gibbs u, ( ll2 S 6, by the convexity of norms we have 11p. 0 I 6, thus for any action aj of player i, loss of player under the two different opponent strategies is nearly the same:
sampling. Let P; == + Ei= P; Since ||p!4
[Li a-)] a~p
E
B [Ci(a,, a.:) S (n 1)B6.
(58)
an
For fixed strategy df of player i, let random variable X denote player i's loss when sampling the opponent's strategy a-; from distribution pd) Thus X, E [0, B) and ((X,) = E
(a) a=:) E
ample)
[0, B). Note that S == (x B(X,)) is martingale sequence generated by filtration F.
Again by Azuma's ' inequality.
< 2 cxp (-
(eT/16)3 .
Tg²
Pr [1st Sol 16
T
cxp
(59)
512B²
This implies that
T-1
T-1
Pr (((((, amp
E (1),
S
8
Pr
X,
Σ
E[X,
2
16
T
16
TE²
< 2 2xxp
(60)
512B2
612Ba 512 log(4/a) combining Eq. (58) and Eq. (6I). with probability at
Take 5 < i- 1)
and T 2
least 1 2 we have
C(ld,, - E ([C,(a',,
5 8'
(61)
a~B
for any strategy u/.
Summing Eq. (577) and Eq. (bl). we have with success probability least ()
(9)-(1)))) (1 4 2 a.
E [Caaa, E
[C: S
am2
am3
which means the output of Algorithm 2 forms an e-coarse correlated equilibrium for the normal- form game.
Query complexity. In each round, m Gibbs samplings are required, corresponding instances of Problem According to the Lemma each sampling requires Ö(vā- Tn Ö(ynBt $). Therefore, the total query complexity is Ö(T /mmBe 1) = 6 8).
Time complexity. By Lemma 3. each sampling takes time Ō(Vā Tn Tmllgn) n) Ö(VomBig -). O(nem²B& B
The total time complexity is Ö(T m vamBie- + 0(7"T
27

---

Remark 3. Note that by replacing the quantum Gibbs sampling with exact Gibbs sampling oracles, we can follow the correctness proof above and derive a classical query complexity of O(mn/=²), as shown in Corollary 1
C Technical details of lower bounds
In this appendix, we present the formal proofs of the quantum query lower bounds in Section N including Theorem and the associated lemmas.
Proof of Lemma 1 For the search problem with m copies, we can define the corresponding m- player normal-form game with utilities Seliniionn Then we invoke A to obtain a set of strategies. For each player's strategy (may be mixed strategy), we perform sampling and use the sampled result as the output of the search problem for corresponding copy. The probability that all m copies of the search problem succeed is larger than:
(1- 6) 6)- (1- 2 1 (1-1)
E
Em B
Here (1-5) is the success probability of algorithm A, and (1 - n is smaller than the probability that sampling result for index i is exactly corresponded to k, according the form of e-correlated equilibrium in this hard instance.
Proof of [heorem A By Lemma 1I, we only need to consider the query lower bound of solving m
copies of the search problem. For a single search problem (m = 1), it requires (V(n) queries to Og by quantum query lower bound unstructured search by Bennett et al. [[]] For general m,
leverage the strong direct product theorem provided in Lee and Roland [24]], giving
a quantum query
lower bound on an m-copies problem, which shows that computing m copies of function f needs nearly m times the queries needed for one copy.
Lemma 4 (Theorem 1.1 in Lee and Roland [24]], strong direct product theorem). Let f: D + E where D C. D for finite sets D, F.. For integer > O, define f(mi (s+ ;...,, x.)) (f(x))....,, Then, for any 2/3 S k 1
m mm Q1/a(s)
21 (m())
8000
Here Qe(f) denotes the query complexity of generating f with error
Denote the search problem finding k, for single i [m]. Thus we have
Q1/4(f) ((Vn).
From the above analysis, finding an s-correlation equilibrium is equivalent calculating f(m). Taking k = (6 + fm)2/m, we have
(L-(6+em))(1 (s In( (5 3 m
(1/((()
8000
8000
m In
2
-
2
+
cm B
21/1())
Taking 5 = 3. the above analysis gives quantum query lower bound for finding e-correlated equilibrium with success probability more than ?
8000 (m in
(3) 2 In 8
1
1
3
Q1/4(f)
In
2
Q1/((f)
2
8000
CYR
3
B
1
m In
2
2n3
Qu/a(()
8000
Q(m
Vn).
28

---

D Impact of quantum sampling noise on the analysis of optimistic MWU
The primary difficulty in extending the proof of Daskalakis al. [H quantum optimistic MWU algorithm is that the smoothness conditions on the higher-order discrete differentials of the loss vector sequence are violated by the sampling error induced by the quantum Gibbs sampler.
Specifically, let (DnE)(0) = E' (1)) be the order-h finite difference of the loss vectors ,....., ((T), as defined in Daskalakis et al. [144, Definition 4.1]. Let H = log T and E (0, 1/(H + 3)) be two parameters. In classical m-player general-sum game where all players follow OMWU updates with step size 1 S a/ (366em)) the order-h finite difference of the loss vectors for any player is bounded by:
&( a² 1,34
(62)
for all integers H] and [T' h] 14 Lemma 4.4]. This bound crucial for their main result.
To illustrate the difficulty of extending this proof to quantum setting, consider two-player game (m = 2). Let x; be the strategy player E {1, 2} at time t. In the classical setting, the loss vectors given by e A1a2 (4) and e AI æ The proof of Eq. (62) proceeds by induction, first bounding a2) (0 via the induction hypothesis and then bounding (I) (1) the matrix norm inequality:
|| using
h
IID,4)) = A1
h
(-1) A-8
h1
(-1)
h (1+a) x2
= ((()) (0)
111
==0
(63)
However, in the quantum setting, we approximate the loss vector g!0) using a quantum Gibbs sam- pler with accuracy EG. which requires (VVTEE)) queries. This introduces an error term. Since El ( = 2A, the inequality in Eq. (b3) is weakened to:
(D) S (1(Da=2) ( 2"EG.
(64)
For the original induction scheme hold, the error term be absorbed into the bound from Eq. (62). This requires the sampling accuracy &a to satisfy:
2c S 5a hhh 3h-11
(65)
Daskalakis et al. [14] ultimately apply their theorem with 1/(4V2H1/22 To satisfy Eq. (65). we must therefore choose an EG such that:
EG
min ~ 31+41
--
min he(o.
1
min NE(OHH)
182HH/2
1
HE H,
The function f(h) the minimum value is approximately:
attains its minimum at h ( At this point,
8/22T/
exp (-3 3 (8 (8 = exp (-621/0 07/0///100)
Substituting lTg(T), the required precision becomes EG exp(-O T)7/ which is (oly()) for any polynomial in T. Consequently, the query complexity of the quantum Gibbs sampler, which scales with 1/E becomes superpolynomial in T. Since computing an e-CCE requires setting T = (m//s) this superpolynomial overhead T' translates to a superpolynomial overhead in and 1 1/c, rendering the quantum approach impractical under this proof strategy.
29


Reviews:
[{"review_id": "F8ViAlrzOx", "reviewer": "Reviewer_4Fe3", "summary": "The paper proposes quantum algorithms for computing $\\epsilon$-approximate CE and CCE in multi-player normal-form games. The authors also give quantum lower bounds on the query complexity for both CE and CCE, showing that both proposed quantum algorithms achieve nearly-optimal query complexity in the number of players and actions.", "questions": "(1) In Def 1, the paper gives the description of the loss oracle $\\mathcal{O}_{\\mathcal{L}}$. Is it efficient to build this oracle from the corresponding classical oracle? I think it depends on the distributions over the action sets, does it?\n(2) CE is more general than Nash equilibrium. But does it make CE more difficult than Nash equilibrium, complexity-wise?\n(3) related to the weaknesses mentioned above.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Overall, the paper is well-organized and well-written. I didn't check all the proofs in detailed, but they seem correct. \n\nStrengths:\n(1) The paper initiate the study of quantum algorithms for $\\epsilon$-approximate CE and CCE problems in multi-player normal-form games.\n(2) The paper also proves the quantum lower bounds on the query complexity of both problems by reducing the direct product of $m$ instances of the unstructured search problem to the  $\\epsilon$-approximate CE and CCE problems in multi-player normal-form games.\n\nWeaknesses:\n(1) I couldn't find the details of how to construct the QRAM for the history action samples. I think it will be necessary have those details presented with the algorithms, because the QRAM is needed for the amplitude-encoding of loss vectors which is very important for the quantum algorithms to achieve better performance.\n(2) Most of time, QRAM is powerful and too good to have. This also sort of means that the construction of a QRAM useful for solving the problem is often not efficient enough. As the time complexity shown in table 2 and 3, it has $O(1/\\epsilon)$ in the exponent, which will bring the time to exponential if wanting $1/poly(n,m)$ approximation ratio. Hence, I think it will enrich the paper by providing some discussion on this issue. \n\nMinor issues on some clarification of notations:\n(1) formal definition of $\\delta(A)$?\n(2) in line 208, does $q$ represent the vector $(q_1, \\cdots,  q_n)$?\n(3) in Def 4, $|\\psi_i \\rangle$ in reg B can be regarded as garbage?", "was_revised": true, "final_justification": "I recommend to accept this paper because this work proposes quantum algorithms and proves a quantum lower bound as well.", "rebuttal": "We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.\n\n**Detailed response to Weaknesses:** \n\nWe thank the reviewer for raising this important question. We note that the term \"QRAM\" can refer to different concepts in the literature (see the survey \"QRAM: A Survey and Critique\" by Jaques and Rattew). In our work, we use it in the sense of a circuit for accessing classical data---often specifically called a Quantum Read-Only Memory (QROM)---which is significantly less complicated to construct than a QRAM designed to store quantum states. We agree that the details of this construction are essential, and we will add a more detailed explanation to the manuscript based on the following arguments:\n\n(1) In our proposed algorithm, this QROM stores classical data. Specifically, after obtaining the classical descriptions of the history actions $a^{(\\tau,s)}$ (as in Line 6 of Algorithm 3), we store them in a classical table. The algorithm runs for $T$ rounds and generates $S$ samples per iteration, resulting in a total of $TS$ actions that need to be stored. Since each action requires $m\\log(n)$ bits for its classical description, the total size of this table is $TSm\\log(n)$ bits.\n\nThe function of the QROM is to make this classical data accessible to the quantum computer via a unitary operation, $U_{\\mathrm{QRAM}}$, that performs the mapping:\n$$\nU_{\\mathrm{QRAM}}\\colon \\ket{\\tau}\\ket{s}\\ket{0} \\mapsto \\ket{\\tau}\\ket{s}\\ket{a^{(\\tau,s)}}.\n$$\nGiven the classical table, a standard construction for $U_{\\mathrm{QRAM}}$ proceeds as follows: for all pairs $(\\tau, s)$ where $\\tau \\in [T]$ and $s \\in [S]$, one implements a controlled operation that checks if the address register is in the state $\\ket{\\tau}\\ket{s}$. If the condition is met, the corresponding classical data $a^{(\\tau,s)}$ is written to the data register. These controlled operations can be decomposed into a sequence of Toffoli and X gates. The gate complexity of this construction is $O(TSm\\log(TSmn))$  and can be further optimized to $O(TSm\\log(n))$ using the QROM construction from \"Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity\" by Babbush et al. In our complexity analysis, for instance in the paragraph before Eq.~(34), we use this optimal $O(TSm\\log(n))$ gate complexity.\n\n(2) We agree that QRAM can be a resource-intensive component, and this is precisely why our analysis does **not** assume access to a free QRAM oracle. Instead, our time complexity analysis explicitly accounts for the number of elementary gates required to construct the QRAM. \nThis is the reason why our overall time complexity has an $O(m)$ overhead compared to the query complexity. As we mention in the \"Techniques\" paragraph, this $O(m)$ overhead is a significant achievement of our work, as it reduces the $O(n^m)$ gate cost required to construct the QRAM that arises from a direct extension of prior quantum algorithms for two-player games to the $m$-player setting.\n\nWe also wish to clarify that the $O(1/\\epsilon)$ term in the exponent is **not** an artifact of the QRAM construction overhead. This dependence is inherent to the swap-regret-minimization problems.\nFor instance, the classical Correlated Equilibrium (CE) algorithms of Peng and Rubinstein [25] and Dagan et al. [11] also exhibit this exponential dependence on $1/\\epsilon$. Their work further establishes a fundamental lower bound: achieving an $\\epsilon$-swap regret requires a number of rounds that has either a polynomial dependence on $n$ (i.e., $\\tilde{\\Omega}(n/\\epsilon^2)$) or is exponential in $1/\\epsilon$.\n\nMinor issues: (1) $\\Delta(\\mathcal{A})$ is the class of probability distributions on $\\mathcal{A}$.\n(2) Yes. \n(3) Yes.  We thank the reviewer for pointing out these minor issues and for the helpful suggestions. We will clarify these points in the revised manuscript.\n\n**Detailed response to Questions:** \n\nThank you for these insightful questions. We will add these clarifications to the manuscript.\n\n(1) This is a good question. The quantum loss oracle $\\mathcal{O}_{\\mathcal{L}}$ can indeed be constructed efficiently if the corresponding classical oracle is efficient. It is a standard result in computational complexity that any classical circuit that computes a function in time $T$ and space $S$ can be converted into a reversible quantum circuit with a minimal increase in resources (e.g., time $T^{1+\\epsilon}$ and space $S\\log T$ for any $\\epsilon > 0$, as shown in \"Time/Space Trade-Offs for Reversible Computation\" by Bennett). The efficiency of this construction depends on the circuit complexity of the classical oracle itself, not on the input distributions over the action sets.\n\n(2) You are correct that Correlated Equilibrium (CE) is a more general solution concept than Nash Equilibrium (NE). However, for the computational task of finding an equilibrium, this generality makes the problem easier. Since every Nash Equilibrium is also a Correlated Equilibrium, the set of CEs is a superset of the set of NEs. This larger solution space makes the search problem of finding a CE computationally easier than finding an NE in general-sum games."}, {"review_id": "2sqYpgiWPx", "reviewer": "Reviewer_42NM", "summary": "This paper initiates a study on quantum algorithms for computing ε-approximate Correlated Equilibria (CE) and Coarse Correlated Equilibria (CCE) in multi-player normal-form games. \nClassical computation of Nash equilibria in general-sum games is well explored but highly intractable. Quantum algorithms can potentially accelerate the computation, but haven’t been studied much in normal form games > 2 players.", "questions": "1. How is the failure probability handled $\\alpha$ in the complexity analysis? Are the reported query and time complexities assuming a fixed failure probability? In particular, the lower bound results (e.g., Theorem 7 and Corollary 2) assume a fixed success probability of 2/3. Can I still compare those lower bounds directly with the upper bounds in Tables 2 and 3?\n\n2. I have an intuition-related question: in Bouland et al. (2023), the query complexity for computing an approximate Nash equilibrium in two-player zero-sum games is $\\widetilde{O}(\\sqrt{2n} / \\varepsilon^{2.5})$. In your Table 3, the query complexity for computing an ε-CCE is $\\widetilde{O}(2 \\sqrt{n} / \\varepsilon^{2.5})$ for 2-player. While the difference is just a constant, does this suggest a broader generalization to $\\widetilde{O}(\\sqrt{mn} / \\varepsilon^{2.5})$?\n\n3. Also, Bouland’s work has a $\\varepsilon^{-3}$ term. Could you clarify why this term does not appear in the complexity of your CCE algorithm?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n- The first quantum algorithms for computing approximate CE and CCE, which are important and non-trivial extensions of existing work on multi-player games + quantum algorithms.\n\n- The proposed algorithms achieve quadratic speedups in terms of the number of actions n, compared to known classical algorithms.\n\n- The paper provides detailed proofs and complexity analyses. While I cannot fully verify the correctness of all proofs, the results appear to be presented in a reasonable and well-structured manner.\n\n**Weakness**\n\n- There are relatively few quantum algorithm papers at Neurips, and I found the structure of this one difficult to follow for outsiders. There are too many technical details before introducing the necessary preliminaries, which makes it challenging to understand the main ideas early on. The paper \"Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games\" could be a good reference.\n\n- Algorithms 1 and 2 are existing methods from prior work, and thus could be moved to the appendix. This would free up space for a proper conclusion or wrap-up discussion at the end of the main text.", "was_revised": true, "final_justification": "The authors’ reply clarified my concerns regarding the methodology and novelty. However, the current presentation of the paper does not fully meet the expected NeurIPS standard. Due to the conference policy, which restricts revisions to the PDF and enforces a limited rebuttal period, the evaluation is largely based on the submitted version. The score will therefore remain unchanged.", "rebuttal": "We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.\n\n**Detailed response to Weaknesses:**\n\nWe thank the reviewer for the constructive feedback on the paper's presentation. \n\n(1) We agree that the main ideas should be more accessible early on. We will revise the introduction to better motivate our work and improve the overall flow.\n\n(2) This is a good suggestion. We will move Algorithms 1 and 2 to the appendix and introduce the prior work more concisely in the main text. \n\n**Detailed response to Questions:**\n\nWe sincerely thank the reviewer for their insightful questions, which help us refine our manuscript.\n\n(1) The reported query and time complexities in our work are not for a fixed failure probability. \nFor the sake of brevity, the query and time complexities stated in our main theorems (Theorem 1 and Theorem 2) and Table 2 and 3 use the $\\tilde{O}$ notation, which hides the logarithmic factors in $\\frac{1}{\\alpha}$. For CE, the dependence of $\\alpha$ is shown in Theorem 8; for CCE, the dependence of $\\alpha$ can be found in Lemma 3. (We will clarify this in Theorem 9 of our revised manuscript.) This logarithmic dependence arises from a standard amplification technique allowing us to convert an algorithm with a fixed success probability into one with an arbitrarily high success probability by running the algorithm independently multiple times, and the final failure probability decreases exponentially with the number of repetitions. This boosting strategy works for both classical algorithms and quantum algorithms, and it is applied in the subroutine in our CE and CCE algorithms.\n\nOur quantum query lower bounds (Theorem 7 for CE and Corollary 2 for CCE) are proven with a fixed success probability of 2/3, which is a common and standard practice in quantum query complexity. The $\\Omega(m\\sqrt{n})$ term represents the complexity for the problem dimension, and is consistent with the upper bounds in Tables 2\nand 3.\n\n(2) It should be noted that both our work and Bouland et al. (2023) use $\\tilde{O}$ notation, which hides constant factors of the complexity. For the case of $m=2$, our algorithm matches the complexity of Bouland et al. (2023), achieving a $\\sqrt{n}$ dependence. For a general $m$-player setting, with $m$ held constant, our algorithm retains this $\\sqrt{n}$ complexity. When considering arbitrary $m$, the complexity scales as $m \\sqrt{n}$. Notably, our lower bound is also $m \\sqrt{n}$, which implies that an algorithm with complexity $\\sqrt{mn}$ do not exist.\n\n(3) This is a good observation. \nFirst, there is a subtle difference between Bouland et al.'s work and ours regarding the assumptions on QRAM. Their QRAM model assumes that mathematical operations can be implemented exactly in $O(1)$ time. In contrast, we further consider the gate complexity of QRAM operations in our analysis. Their $\\epsilon^{-3}$ term actually arises from an additive initialization cost $\\tilde{O}(\\eta^3T^3)$ in Lemma 2, which is unrelated to the number of queries to the loss oracle $O_\\mathcal{L}$ and appears only in the time complexity. When considering query complexity, Bouland et al.’s dependence on $\\epsilon$ is $\\tilde{O}({1/\\epsilon^{2.5}})$, which matches ours exactly. However, for the time complexity, due to our additional consideration of the gate complexity of QRAM operations, our overall time complexity becomes $\\tilde{O}({1/\\epsilon^{4.5}})$, which is larger than $\\epsilon^{-3}$. Therefore, we do not explicitly include the additive initialization cost term $\\epsilon^{-3}$ in the final stated result."}, {"review_id": "pLACP9VSfL", "reviewer": "Reviewer_y8aw", "summary": "This paper introduces quantum algorithms for computing correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player general-sum normal-form games. Building on quantum improvements to the multiplicative weights update (MWU) method, the authors design algorithms that achieve query complexities of $\\tilde{O}(m\\sqrt n)$ for CE and $\\tilde{O}(m\\sqrt n / \\epsilon^{2.5})$ for CCE. \nThe algorithms are proven to be nearly optimal by establishing matching lower bounds of $\\Omega(m\\sqrt n)$.", "questions": "To what extent do the proposed algorithms require genuinely new quantum techniques, as opposed to adapting known primitives (e.g., quantum Gibbs sampling and amplitude encoding) within existing classical frameworks like MWU? Are there aspects of the analysis or algorithm design that are specific to the quantum regime?", "limitations": "No limitations", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* The paper makes an interesting contribution by extending quantum algorithmic techniques, previously developed mainly for zero-sum games, to the broader and more challenging setting of general-sum games\n* The authors establish matching lower bounds that confirm the near-optimality of their algorithms, giving strong theoretical support to the efficiency of their proposed methods.\n* The paper is well written, mathematically precise, and the results are well situated within the broader literature on quantum optimization and equilibrium computation.", "was_revised": true, "final_justification": "The authors have addressed my questions. I will retain my score.", "rebuttal": "We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.\n\n**Detailed response to Questions:**\n\nThank you for this question. The new quantum technique in our work is the method for constructing the amplitude encoding. Instead of following prior methods that build a frequency vector of actions, which would require a QRAM of size $\\Omega(n^m)$, our algorithm stores the history of actions and builds amplitude encoding from them (see Section A.1 and A.3). This approach significantly reduces the QRAM size, which is a critical bottleneck for many quantum algorithms. \n\nThe analysis of our algorithm has aspects that are both quantum-specific and shared with classical analysis. The analysis of the amplitude encoding construction, its gate complexity, and how it is used to build the amplitude encoding for the loss vectors are all inherently quantum. The analysis of how sampling errors from the Gibbs sampler affect the algorithm's performance has common ground with classical online learning. This part of the analysis addresses whether an online learning algorithm can still guarantee low regret when it receives a noisy loss vector (see Section A.2 and A.4)."}, {"review_id": "z3vVKsGyTM", "reviewer": "Reviewer_SEAg", "summary": "This paper studies the theoretical convergence rates of quantum algorithms for computing correlated and coarse correlated equilibria in normal form general-sum games. The key results in this paper pertain to the introduction of a multi-scale MWU algorithm for computing CE, and a sample-based MWU algorithm for computing CCE. The analysis of these algorithm results in rates which are near-optimal (compared to the corresponding classical variants of the algorithms) in terms of scaling in the number of players and actions of the game. Meanwhile, the paper also gives lower bounds on the query complexity of computing both approximate CE and CCE in general-sum games.", "questions": "- Can you clarify on the roadblocks towards quantizing the Optimistic MWU algorithm? The difficulties are mentioned in passing in the main text but I would like to understand the details on how the smoothness assumption of the loss vectors would lead to the analysis failing.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper is fairly well written and has clear exposition. The motivation to initiate the theoretical complexity analysis of CE and CCE computation using quantum algorithms is also strong and relevant to the current framework of classical learning in games. The multiscale MWU algorithm for computing CE extends recent work by Peng and Rubinstein/Dagan et al to a quantum setting.\n\nWeaknesses: While the theoretical rates are near optimal as compared to existing classical algorithms, I would have appreciated more thorough comparison between the classical and quantum time complexity, and when the quantum algorithms exhibit speedup (for example, in terms of time complexity the quadratic speedup in n comes at the cost of worse dependence on m). To my knowledge, much of the technical analysis is derived similarly to prior works, and if there is significant technical novelty here it is not made clear. It is also unclear to me why the authors focus on the algorithm of Grigoriadis and Khachiyan for CCE computation, when there are several recently proposed MWU variants that have better query/time complexity. For example, in addition to Optimistic MWU, some recent papers have introduced Clairvoyant [1] and Cautious [2] MWU which have significantly improved rates for CCE computation in general-sum games. The authors discuss the difficulties of replicating the proof of Daskalakis et al for OMWU, but fail to discuss the original RVU bound in [3]. Indeed, the proof of Daskalakis et al is highly intricate and I do not doubt that quantizing the analysis would be challenging, but the original bound in [3] would be more feasible as a first step.\n\n[1] Piliouras, G., Sim, R., & Skoulakis, S. (2022). Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 35, 22258-22269.\n\n[2] Soleymani, A., Piliouras, G., & Farina, G. (2025). Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games. arXiv preprint arXiv:2506.05005.\n\n[3] Syrgkanis, V., Agarwal, A., Luo, H., & Schapire, R. E. (2015). Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28.\n\nOverall, while the results in this paper are a good first step in terms of CE and CCE computations with quantum algorithms, I am unconvinced as to the relevance/usefulness of the CCE algorithm introduced as compared to modern (classical) algorithms such as optimistic MWU.", "was_revised": true, "final_justification": "- My concerns about the quantization of the Grigoriadis and Khachiyan algorithm as opposed to other 'near-optimal' algorithms have been alleviated.\n- A remaining concern regards the structure of the paper, and making it more readable for a neurips audience. However, given the authors suggestions (making space for more quantum algorithm preliminaries), I think this can be done in a camera ready version should the paper be accepted. \n- I will update my score to a borderline accept -- while the authors have addressed my major concern, I still feel that the paper needs a bit of work to be readable to a general audience. Moreover, having more concrete discussion/analysis towards quantizing the optimistic algorithms which are considered 'standard' in the classical literature would make the paper a lot stronger.", "rebuttal": "We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.\n\n**Detailed response to Weaknesses:**\n\nWe thank the reviewer for their insightful comments and constructive feedback, which will help us improve the manuscript.\n\nOur manuscript focuses on the complexity of computing CE and CCE as a function of the number of players $m$ and the number of actions $n$. While in self-play settings, each player running Optimistic MWU [3] or Clairvoyant and Cautious MWU [1,2] achieves $o(T^{1/2})$ regret, the $m$ dependence is $O(\\sqrt{m})$ or $O(m)$. Since we still need $O(m)$ queries per iteration to update the strategies of all $m$ players, the total query complexity of the CCE computation algorithm is super-linear in $m$, which is suboptimal. In contrast, the Grigoriadis and Khachiyan algorithm achieves a regret bound that is independent of the number of players. This property allows us to compute CCE with optimal query complexity in $m$. We will make sure to clarify this important motivation in the revised manuscript.\n\nRegarding the point on improving the error dependence, we agree with the reviewer that extending the RVU bound in [3] to quantum cases is a good start. Its reliance on first-order discrete differentials of the loss vector sequence, rather than the higher-order ones in Daskalakis et al., makes the analysis more robust to the sample error induced by the quantum Gibbs sampler. Furthermore, the Cautious MWU algorithm [2], which builds on a non-negative RVU bound and was posted online after our manuscript's submission at NeurIPS 2025, would be a next step in this direction. This is an excellent suggestion, and we will add a discussion of this promising future direction to our paper.\n\n**Detailed response to Questions:**\n\n\n\nThe primary difficulty in extending the proof of Daskalakis et al. to a quantum Optimistic MWU algorithm is that the smoothness conditions on the higher-order discrete differentials of the loss vector sequence are violated by the sampling error induced by the quantum Gibbs sampler.\n\nSpecifically, let $(  \\mathrm{D}\\_h\\ell)^{(t)}=\\sum\\_{s=0}^h\\binom{h}{s}(-1)^{h-s} \\ell^{(t+s)}$ be the order-$h$ finite difference of the loss vectors $\\ell^{(1)}, \\dots, \\ell^{(T)}$, as defined in [Definition 4.1, Daskalakis et al.]. Let $H = \\log T$ and $\\alpha\\in (0, 1/(H+3))$ be two parameters. In a classical $m$-player general-sum game where all players follow OMWU updates with step size $\\eta\\le \\alpha/(36e^5m)$, the order-$h$ finite difference of the loss vectors for any player $i$ is bounded by:\n\\begin{equation}\n\\tag{1}\n    \\|(  \\mathrm{D}\\_h \\ell\\_i)^{(t)}\\|\\_{\\infty} \\leq \\alpha^h \\cdot h^{3 h+1}\n\\end{equation}\nfor all integers $h\\in [0, H]$ and $t\\in [T-h]$ [Lemma 4.4, Daskalakis et al.]. This bound is crucial for their main result.\n\nTo illustrate the difficulty of extending this proof to a quantum setting, consider a two-player game ($m=2$). Let $x\\_i^{(t)}$ be the strategy of player $i\\in \\{1,2\\}$ at time $t$. In the classical setting, the loss vectors are given by $\\ell\\_1^{(t)}=A\\_1 x\\_2^{(t)}$ and $\\ell\\_2^{(t)}=A\\_2^{\\top} x\\_1^{(t)}$. The proof of Eq. (1) proceeds by induction, first bounding $\\|(  \\mathrm{D}\\_h x\\_2)^{(t)}\\|\\_1$ via the induction hypothesis and then bounding $\\|(  \\mathrm{D}\\_h \\ell\\_1)^{(t)}\\|\\_{\\infty}$ using the matrix norm inequality:\n\\begin{equation}\n\\tag{2}\n    \\|(  \\mathrm{D}\\_h \\ell\\_1)^{(t)}\\|\\_{\\infty}=\\left\\|A\\_1 \\sum\\_{s=0}^h\\binom{h}{s}(-1)^{h-s} x\\_2^{(t+s)}\\right\\|\\_{\\infty} \\leq \\left\\|\\sum\\_{s=0}^h\\binom{h}{s}(-1)^{h-s} x\\_2^{(t+s)}\\right\\|\\_1=\\|(  \\mathrm{D}\\_h x\\_2)^{(t)}\\|\\_1.\n\\end{equation}\nHowever, in the quantum setting, we approximate the loss vector $\\ell\\_i^{(t)}$ using a quantum Gibbs sampler with accuracy $\\varepsilon\\_G$, which requires $O(\\sqrt{n}/\\varepsilon\\_G^2)$ queries. This introduces an error term. Since $\\sum\\_{s=0}^h |\\binom{h}{s}| = 2^h$, the inequality in Eq. (2) is weakened to:\n\\begin{equation}\n    \\|(  \\mathrm{D}\\_h \\ell\\_1)^{(t)}\\|\\_{\\infty}\\le\\|(  \\mathrm{D}\\_h x\\_2)^{(t)}\\|\\_1+2^h \\varepsilon\\_G.\n\\end{equation}\nFor the original induction scheme to hold, the error term must be absorbed into the bound from Eq. (1). This requires the sampling accuracy $\\varepsilon\\_G$ to satisfy:\n\\begin{equation}\n\\tag{3}\n    2^h \\varepsilon\\_G\\le \\frac{1}{2} \\alpha^h h^{3h+1}.\n\\end{equation}\nDaskalakis et al. ultimately apply their theorem with $\\alpha = 1/(4\\sqrt{2}H^{7/2})$. To satisfy Eq. (3), we must therefore choose an $\\varepsilon\\_G$ such that:\n$$\n\\varepsilon\\_G \\le \\min\\_{h\\in [0,H]} \\frac{1}{2} \\cdot 2^{-h} \\alpha^h h^{3h+1} \\approx \\min\\_{h\\in [0,H]} \\frac{1}{2}\\left(\\frac{\\alpha h^3}{2}\\right)^h = \\min\\_{h\\in [0,H]} \\frac{1}{2}\\left(\\frac{h^3}{8\\sqrt{2}H^{7/2}}\\right)^h.\n$$\nThe function $f(h):=\\left(\\frac{ h^3}{8\\sqrt{2}H^{7/2}}\\right)^h$ attains its minimum at $h=e^{-1}(8\\sqrt{2}H^{7/2})^{1/3}$. At this point, the minimum value is approximately:\n$$\n\\exp\\left(-\\frac{3}{e}(8\\sqrt{2}H^{7/2})^{1/3}\\right) = \\exp\\left(-\\frac{6}{e}2^{1/6} H^{7/6}\\right).\n$$\nSubstituting $H=\\log(T)$, the required precision becomes $\\varepsilon\\_G = \\exp(-\\Theta((\\log T)^{7/6}))$, which is $o(1/\\mathrm{poly}(T))$ for any polynomial in $T$. Consequently, the query complexity of the quantum Gibbs sampler, which scales with $1/\\varepsilon\\_G^2$, becomes superpolynomial in $T$. Since computing an $\\varepsilon$-CCE requires setting $T = \\tilde{O}(m/\\varepsilon)$, this superpolynomial overhead in $T$ translates to a superpolynomial overhead in $m$ and $1/\\varepsilon$, rendering the quantum approach impractical under this proof strategy.\n\n**Response to Paper Formatting Concerns**\n\nThank you for identifying these typos. We will fix them in the revised manuscript."}]

Author rebuttal:

Meta-review: This paper introduces the first quantum algorithm for computing correlated equilibria (CE) and coarse correlated equilibria (CCE) in general-sum games, which are key solution concepts in algorithmic game theory. Its key contributions include a set of algorithms that provide a quadratic speedup in the number of actions compared to classical methods. Complementary to these upper bounds the paper provides new quantum query lower bounds, demonstrating that their algorithms' scaling in the number of players and actions is near-optimal. The work is technically solid and initiates a new direction at the intersection of quantum computation and multi-agent systems. Given other recent work in terms of quantum generalizations of normal-form games and their corresponding solution concepts (e.g. quantum CCEs) (see [1-4] and references therein) I believe that this paper could trigger advancements in other related areas in the intersection of these two areas. I would encourage the authors to examine how the literature above could inform the frontier of open problems in this area. Moreover, the faster learning algorithms for classical computation of CCE are now corresponding to the cautious optimism framework (see [5,6]). Lastly, as requested, make sure to improve the paper's accessibility by revising the introduction and prelims appropriately for the NeurIPS audience.


[1] Jain, Rahul, Georgios Piliouras, and Ryann Sim. "Matrix multiplicative weights updates in quantum zero-sum games: Conservation laws & recurrence." Advances in Neural Information Processing Systems 35 (2022): 4123-4135.
[2] Lotidis, Kyriakos, Panayotis Mertikopoulos, and Nicholas Bambos. "Learning in quantum games." arXiv preprint arXiv:2302.02333 (2023).
[3] Lin, Wayne, et al. "No-Regret Learning and Equilibrium Computation in Quantum Games." Quantum 8 (2024): 1569.
[4] Vasconcelos, Francisca, et al. "A quadratic speedup in finding Nash equilibria of quantum zero-sum games." Quantum 9 (2025): 1737.
[5] Soleymani, Ashkan, Georgios Piliouras, and Gabriele Farina. "Faster Rates for No-Regret Learning in General Games via Cautious Optimism." Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025.
[6] Soleymani, Ashkan, Georgios Piliouras, and Gabriele Farina. "Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games." arXiv preprint arXiv:2506.05005 (2025).
Decision: Accept (poster)