Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games

We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.

Detailed response to Weaknesses:

We thank the reviewer for their insightful comments and constructive feedback, which will help us improve the manuscript.

Our 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.

Regarding 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.

Detailed response to Questions:

The 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.

Specifically, 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:

$

\tag{1} |( \mathrm{D}_h \ell_i)^{(t)}|_{\infty} \leq \alpha^h \cdot h^{3 h+1}

$

for 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.

To 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:

$

\tag{2} |( \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.

$

However, 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:

$

\|(  \mathrm{D}\_h \ell\_1)^{(t)}\|\_{\infty}\le\|(  \mathrm{D}\_h x\_2)^{(t)}\|\_1+2^h \varepsilon\_G.

$

For 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:

$

\tag{3} 2^h \varepsilon_G\le \frac{1}{2} \alpha^h h^{3h+1}.

$

Daskalakis 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:

The 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:

Substituting $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.

Response to Paper Formatting Concerns

Thank you for identifying these typos. We will fix them in the revised manuscript.

We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.

Detailed response to Questions:

Thank 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.

The 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).

We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.

Detailed response to Weaknesses:

We thank the reviewer for the constructive feedback on the paper's presentation.

(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.

(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.

Detailed response to Questions:

We sincerely thank the reviewer for their insightful questions, which help us refine our manuscript.

(1) The reported query and time complexities in our work are not for a fixed failure probability. For 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.

Our 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 and 3.

(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.

(3) This is a good observation. First, 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.

We thank the reviewer for their valuable feedback. We address the specific points raised in the review below.

Detailed response to Weaknesses:

We 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:

(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.

The 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:

Given 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.

(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. This 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.

We 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. For 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$.

Minor issues: (1) $\Delta(\mathcal{A})$ is the class of probability distributions on $\mathcal{A}$. (2) Yes. (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.

Detailed response to Questions:

Thank you for these insightful questions. We will add these clarifications to the manuscript.

(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.

(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.