Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence
Authors: Rahul Jain
Georgios Piliouras
Ryann Sim
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning in quantum games
Poincare recurrence
dynamical systems
zero-sum games

Abstract: Recent advances in quantum computing and in particular, the introduction of quantum GANs, have led to increased interest in quantum zero-sum game theory, extending the scope of learning algorithms for classical games into the quantum realm. In this paper, we focus on learning in quantum zero-sum games under Matrix Multiplicative Weights Update (a generalization of the multiplicative weights update method) and its continuous analogue, Quantum Replicator Dynamics. When each player selects their state according to quantum replicator dynamics, we show that the system exhibits conservation laws in a quantum-information theoretic sense. Moreover, we show that the system exhibits Poincare recurrence, meaning that almost all orbits return arbitrarily close to their initial conditions infinitely often. Our analysis generalizes previous results in the case of classical games.

Matrix Multiplicative Weights Updates in Quantum
Zero-Sum Games: Conservation Laws & Recurrence
Rahul Jain NUS
Georgios Piliouras
SUTD
rahul@comp nus edu. sg
georgios@sutd edu.
Ryann Sim SUTD
syann_sim@mymail. sut.ea.iilssddeee. sut..edu..dddddd........ sg
Abstract
Recent advances in quantum computing and in particular, the introduction of quantum GANs, have led to increased interest quantum zero-sum game theory, extending the scope of learning algorithms for classical games into the quantum realm. In this paper, we focus on learning in quantum zero-sum games under Matrix Multiplicatiiv Weights Update (a generalization of the multiplicative weights update method) and its continuous analogue, Quantum Replicator Dynamics. When each player selects their state according quantum replicator dynamics, we show that the system exhibits conservation laws in quantun-information theoretic sense. Moreover, show that the system exhibits Poincaré recurrence, meaning that almost all orbits return arbitrarily close to their initial conditions infinitely often. Our analysis generalizes previous results the case of classical games 48
Introduction
The Nash equilibrium has always been central concept in non-cooperative game theory. While the existence of Nash equilibria well known finite games where mixed strategies are allowed 44) it is less clear how to efficiently compute these equilibria themselves. Indeed, much work revolves around finding methods to solve Nash equilibria different contexts, as well as analyzing complexity of solving for the Nash 33 [5
Despite the dominance of equilibrium computation in classical theory, recent works have begun to move towards attempting to understand the nature of learning in games [23 5T] The family of regret-minimzzing algorithms known as Thelow-Thh-Beee Regularizee--LLadeee (FTRL) have been studied dynamics. These algorithms have found many applications in the domain of machine learning one such example is that of Generative Adversarial Networks (GANs) [25], which have been successfully modeled using zero-sum game theory. This rich connection has led a stronger understanding of adversarial learning and improved practical performance of GANs in various settings [1 32 36
extensively, both for discrete time 7 13
45 49 and continuous time 42
On the other side of the coin, quantum computing is a field which has garnered much interest in the machine learning community. Many quantum machine learning algorithms have been proposed, extending standard classical algorithms. One such example is quantum GANs 14 39 12 While such works describe the architecture of quantum GANs, we still do not fully understand the behavior this paper, we provide an initial analysis of
of learning algorithms in the quantum setting. learning in zero-sum quantum games. We do so by studying the learning behaviour of the ubiquitous
Multiplicative Weights Update (MWU) update rule [37 22 5, a specific instance of the FTRL framework, when applied to such games.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

There have been several important results studying MWU and its continuous counterpart, replicator dynamics. 77] showed that classical MWU does not converge day-to-day behaviour the mixed Nash equilibrium when applied to two player zero-sum games. 42 showed that the orbits of players in zero-sum games exhibit Poincaré recurrence when using replicator dynamics. However, quantum systems can oftentimes behave in radically different ways to their classical counterparts. Indeed, allowing for quantum strategies can create situations wherein players can gain greater payofts than if they were playing using only classical strategies (see e.g. the Mermin-Peres magic square game 40 46) ). As such, our extension of the classical results to the quantum realm has to be treated with care.
We focus on a matrix generalization of MWU known as Matrix Multiplicative Weights Update (MMWU), which changes the paradigm of standard MWU from cost vectors to cost matrices, and from probability vectors to density matrices. This generalization has been independently discovered and studied by [54] as Matrix Exponentiated Gradient Updates and (5] as the Matrix Multiplicative Weights algorithm. Applications of the MMWU algorithm include solving semi-definite programs (SDPs) [6] and obtaining bounds on the sample complexity for learning problems in quantum computing [30]. From a game theoretic standpoint, (88 analyzed the MMWU algorithm for quantum zero-sum games, proving time-average convergence an approximate Nash equilibrium. We extend this result by studying the learning behaviour of MMWU in quantum zero-sum games, which could lay the groundwork for developing novel algorithms that achieve convergence to the Nash in day- soyy-to-dyy behaviour in quantum zero-sum games, similar to the case of their classical analogues [16
Contributions. In this paper, we first study the dynamics of MMWU in quantum zero-sum games, utilizing tools from information theory and classical game theory (Section 3). We provide bounds on the rate of change of the total quantum relative entropy between fully mixed Nash equilibrium and the evolving state of the system. We then study the continuous counterpart of MMWU, which we call quantum replicator dynamies (Section 4. We show that the aforementioned total quantum relative entropy is a constant of motion. Furthermore, the dynamics do not converge to equilibrium (in the day-to-day sense) but rather exhibit weaker form of approximate periodicity known as Poincaré recurrence. Our proof of this result departs from the standard classical method, representing our main technical novelty. Finally, we present several simulations which corroborate our theoretical results (Section
2
Preliminaries and Definitions
2.1 Quantum Theory
Basic concepts. Similarly to (28 and order to make the presentation self-contained, we will start by introducing some basic concepts of quantum information and game theory.
First, we refer to a quantum register as collection of qubits representing a message that is transferred from one party to another. We associate a vector space H = C" with any quantum register. This intuitively represents the maximum number of distinct classical states that can be stored in the register without error. The state of a quantum register is represented by density matrix, which is an n positive semi-definite matrix with trace 1. We will use DHH) to denote the set of all density matrices associated with a register that is described by H. One can naturally view such density matrices as linear operators acting on H.
When two registers with associated spaces A = C and B = C are considered as a joint register, the associated space is the tensor product A & B Cam. If the two registers are independently prepared in states described by & and o, then the joint state is described by the nm x nm density matrix p 3 a.
Next, for a given vector space H. = C",, we define L(H) as the set of all n x n complex matrices. Furthermore, we denote the subset of L(H) given by Hermitian matrices as Herm A Hermitian matrix A satisfies the equality A = At, where A denotes the adjoint (or conjugate transpose) of matrix A. Subsequently, we define Pos(H) as the subset of Herm H)) which consists of all positive semi-definite n X n matrices.
2

---

Finally, the Hilbert-Schmice inner product on L(H) is defined as (A. = Tr(ATB) for all A, B e L(H). Note that (A. B) a real number for any Hermitian matrices A and B, and is also additionally non-negative if A and B are positive semi-definite.
Measurements and observables. the context of game theory, we are also interested in the concepts of quantum measurements and observables. An observable is simply a property of the quantum system which measurable. The measurement of a register having associated vector space H = C" is a collection of linear operators (P: S i S k) C Pos(H) which satisfies Ex= P. 1x. where 14 is the identity matrix on H. If the register corresponding H is in state defined by density matrix p and the measurement described by P; is performed, each outcome i will be observed with probability (P., p). An important note is that two mixed states with the same density matrix are indistinguishable from each other by any measurement.
Additional notation and definitions. A linear mapping of the form & L(B) + L(A) called super-operator. The adjoint super-operator to T is @ L(A) - L(B) and is uniquely determined by the condition:
(A, (B)) (+ (A),
A super-operator 4 L(B)- - L(A) is said to be positive if (PP) is positive semi-definite for every choice of positive semi-definie operator P E (B). In addition, &f is positive if and only if db positive. There is one-to-one and linear correspondence between the collection of operators of the form R T(A 69 B) and the collection of super-operators + I.(B) - I.(A) defined above. Specifically, for each super-operator & we can define an operator as follows:
R
Σ
(EE,,) @ E
15
where E,y is the matrix with a 1 in entry (i.j) and 0 elsewhere. Conversely, given an operator R E L( ( B), define:
+ (B) Tra (R(1 BT)
This correspondence is linear and translate back and forth between the two needed for an given application. R is assumed to be positive semi-definite, so the corresponding super-operator & also positive.
2.2 Quantum Game Theory
quantum system which can be manipulated by any number of agents, and where the utility of the moves is well defined, quantified and ordered can be conceived as a quantum game. In particular, a 2-player zero-sum quantum game sees players Alice and Bob each sending a quantum state to referee, who then performs measurement these two states to determine their payoffs. Let A = C" and = C be the vector spaces that correspond to the state that Alice and Bob send to the referee.
In order to determine the payoffs of the players' actions, the referee performs a joint measurement where Alice's 's and Bob's 's's states are viewed as a single register. Thus, the referee's measurement can be described by a collection
RRa a S} C Pos(A @ B)
which satisfies the condition Σ Rg 1 A-B- We associate each possible measurement outcome with payoff for each player. Since we are only considering zero-sum games, if the payoff that Alice receives from the referee is v(a), then Bob's corresponding payoff will be (a(a). Henceforth, we refer to the states sent by Alice and Bob to the referee and respectively. For given choice of and a, Alice's 's expected payoff is:
k
u(p, 0) = Σ u(a) p 8 (R.
(4)
where R R= E
R.. Likewise, Bob's corresponding expected payoff is -u(p,a) - (R. p r). R. is referred to throughout the rest of the paper as payoff observable. A necessary and sufficient
3

---

condition for matrix R acting on A & B to be obtained from some real valued payoff function is that R Hermitian. From Equation 2 we can equivalently define the expected payoff of Alice as u(p,)) = (p, (())). We will use the latter formulation for the remainder of the paper.
A key notion of equilibrium in classical game theory is the Nash equilibrium. In the quantum setting, we define the pair of quantum states (p", ,a) as a Nash equilibrium of R if
(5) for all p. d. That is, neither Alice nor Bob would prefer to unilaterally deviate from playing p* and ø respectively, On another note, since the set of available strategies (density matrices) for both agents is convex and compact and the utility function of Alice is bilinear, standard extensions of the of von Neumann's 's Min-Max Theorem apply (20]
u(p",0" 2 u(p,o' o²) and u(p', ,0" 2 u(p",a)
Finally, we define the notion of a 'fully mixed' Nash equilibrium. An equilibrium (p'.a") oo") is fully mixed if p² o² are full rank.
2.3 Information Theory
We also introduce several information theoretic concepts which will be referenced throughout the paper.
Shannon entropy. The Shannon entropy of a random variable X where each strategy x obtained with probability p(a:) is given by H()) = - 'x p(z) p(x). This intuitively is a measure of randomness or uncertainty in the system. quantum context is the von Neumann entropy. For quantum mechanical system defined by density matrix p, the von Neumann entropy is given by Sp) = - -Tr(p log p).
natural generalization of the Shannon entropy a
Bregman divergence. We are also interested in the notion of Bregman divergence, which measures the distance between two points. Let x E X be a Nash equilibrium and let x E X' be an arbitrary strategy profile. Also, let F be bontimuoully-diffeeentibbbll strictly convex function. The Bregman divergence from x= to given by (r<a**(>>> F(x*) - F(x)- (VF(+), -2))
In the context of quantum games, the Bregman divergence is defined using matrix notation. We define the quantum relative entropy between two quantum states using the von Neumann entropy S(p). In particular, the quantum relative entropy between two quantum states and a is defined as ((pllr) Tr (p(log p r)).
2.4 Dynamical Systems
Flows. Consider a differential equation أ = fp) on a topological space P. The existence and uniqueness theorem for ordinary differential equations guarantees that we can write the unique solution to the differential equation as a continuous map Φ P x H + P. This is referred to as the flow of the differential equation such that for any point p P, o(p, -) defines a function of time corresponding to the trajectory of p. Conversely, fixing a time provides a map ø' = o(-,t)= P + P. In Section 4 we introduce the notion of quantum replicator dynamies, which are Lipschitz continuous differential equations. Hence, a unique flow & of these replicator dynamics exists.
Liouville's theorem. Liouville's theorem be applied to any system of ordinary differential cquations with a continuously differentiable vector field & on an open domain y E IRd. The divergence of E at E ) is the trace of the Jacobian at div E(y) = Σd as.
(v). Because the divergence is continuous, it is integrable on Lebesgue measurable subsets of y Given any such set C, define the image of C under flow á at time i as C(t) {ø(c, t) : e C). C(t) is measurable and of volume vol) = Seo, du. Liouville's formula states that the time derivative of the volume vol [C()) exists and links it to the divergence of &:
By.
d dt
vol C(I) = Jeco)
[[ div(E)dd
If div E(v) is null at any E V, then the volume is conserved. Since div & is continuous, the converse statement also true if the volume is conserved on any open set, div E(y) has to be null at any point y e y.

---

Algorithm 1: Parallel Approximation of Equilibrium Point
Let y = e/8 and let N = [64 log (nm)/e²1.
Initialize: Ag 1,, Pu 1o/Tr(AA), Bo 1s, and do Bu/TTr(Bi for j = 1..... .N. do
A exp ( Σ (o.))
Pj A (TT))
B) exp E/o 40 (p:))
0j Br/Tr(BB)
end for
Diffeomorphisms of flows. A function f between two topological spaces is called a diffcomorphism i) f is a bijection, ii) is continuously differentiable, iii) has a continuously differentiable inverse. Two flows d' A + A and vv' B + B are diffeomorphic if there exists diffcomorphism f B such that for each x E and E IR, f())(p)) analysis, the replicator dynamics defined in Equations 17 are translated via a diffeomorphism from the interior of P space 1 Rm-1, which allows us to show certain desirable properties.
V (f())). For the purpose of our
Poincaré recurrence. The concept of Poincaré recurrence arises from Henri Poincaré's celebrated 1890 work regarding the three body problem [50] He proved that if a dynamical system preserves volume and always remains bounded in its orbits, almost all trajectories return arbitrarily close to their initial position, and do so infinitely often.
Theorem 2.1 (Poincaré recurrence). a flow preserves volume and has only bounded orbits then for each open set there exist orbits that intersect the set infinitely often.
3 MMWU in Quantum Zero-Sum Games
28 the MMWU algorithm for zero-sum games is shown to exhibit time-average convergence to an approximate Nash equilibrium in two-player quantum zero-sum games. The MMWU algorithm is shown in Algorithm!] !
Note that here we focus specifically on two-player games, and utilize the expected payoffs defined via super-operators & L(A) + L(B) as seen in Equation 2 quantum algorithm.
Moreover, je the step-size in the
In this section, examine closely the update steps for each player in the MMWU algorithm (Algorithm [ and analyze the limiting behaviour of the total quantum relative entropy the system. First, we introduce two useful facts which will aid in the analysis.
Fact 3.1 (Golden-Thonee (Golden-Thommsonn inequality 24 53)) Let A, B be Hermitian matrices. Then
Trexp + B) < Tr (reex((A)exp((
Fact 3.2. Let 0 S A be a PSD matrix and 5 be a real number. Then,
exp(6A) + A
(8)
Next, we put forward two corollaries which will help prove Theorem 3.5 We first define AS(p" I(p;) =
and AS(o* (1o,) S(o'lla)) - (Ho'[o,-))
Corollary 3.3. The change in the sum of quantum relative entropies in quantum zero-sum game between fully-mixes Nash equilibrium and the players' strategies is given by:
TrA; + log TrB3-1
TrB,
AS(p") (S(p" + AS (Io," log TrA
(9)
Corollary 3.4. The following trace inequalities hold for PSD matrices A and B updated with MMWU:
AS(p")le)) + AS(o" 2 (e
(p,0(a,-1)) (esp::/=))))--pppppip((////-10/
(10)
AS(p")le) (le;) + AS(o")la,)) I μexp(u) (e) eexp(-w)Tr (p (11)
5

---

The proof of Corollary relies on Facts 3.1 and 3.2 as well as the equality shown in Corollary 3.3
In many practical scenarios, would decreasing step-sizes when running MMWU. As such, we utilize Corollary 3.4 and and take the limit as step-size goes to 0 in order to show the following theorem:
Theorem 3.5. The change in the sum of quantum relative entropies between a fully mixed Nash equilibrium and the player's 's strategies and in a two-player zero-sum quantum game tends to zero when step-size is + O. Specifically,
lim (AS(p" (Sspp 1-0 j
0
(12)
The proof of Theorem
3.5 along with Corollaries and can be found in Appendix C
Theorem 3.5 further motivates an investigation into the continuous time variant MMWU, which call quantum/matio replicator dynamics. In particular, show that in the continuous case, the sum of quantum relative entropies is invariant. We introduce and study quantum replicator dynamics in detail in Section 4
4 Replicator Dynamics in Quantum Zero-Sum Games
We have seen that in the case of discrete dynamics (MMWU), as the step-size becomes infinitesimal, the total quantum relative entropy between the Nash equilibirum and the system state tends to stabilize. A natural question would then be: does the same result hold in continuous time? In order to explore this question in greater detail, we first need define the continuous analogue of MMWU, the quantum replicator dynamics, which has well known classical analogues [5]]
We start by rewriting the MMWU update steps, but defined over continuous time interval [0,4]:
A(t) = S." ((((T))
(13)
p(t) cxp(A(t)/T((<xp(AA)))
(14)
B(I) = - 1.' xt (p(T))
(15)
(t)
(o((B(t))T((exx(BBB)))
(16)
Note here that we shift the exponential terms from the definition of A()) and B(t) to the corresponding p(t) and of) terms. This will help simplify some of the proof techniques later on in the paper. Furthermore, in the rest the paper we will typically drop from the notation the explicit dependence on é to case with the notational burden.
is important to note the following observation, which will be helpful in our later analysis. Observation 4.1. The discrete-time time trajectories Aj and a, defined in Algorithm [ are a standard Fuler discretization (with step μ)) of the continuous-tims trajectories p(t) and o(t) defined in Equations 14 [6
We now define the quantum replicator dynamics as: d
exp(A) di (T((expA)))
da/dt: d exp(B) dl Tr(exp(B))
dp/dt dt
(17)
worth noting that in the classical/commuting setting, one can write the replicator equations in form that describes the relative utility that one agent obtains as compared to the average utility overall. However, in the quantum case this is not possible in general, since it relies on the assumption that f (T)()d and & (t)),, and respectively So (p(())) and tf (p(t)) commute.
we can also conclude that the dynamical system described by the replicator dynamics defined Equations) 17 is a limit case of the dynamical system described by the MMWU algorithm μ 0.
As consequence of Observation 4.1

---

We are now able to state the main theorem for quantum relative entropy in quantum replicator dynamics.
Theorem 4.2. When applying matris/quantum replicator dynamics in quantum zero-sum game with a fulty-mixed Nash equilibrium (0", o²),, the sum of quantum relative entropies between the fully-mixed Nash equilibrium and the state of the system (p(t), a()) is invariant on every system trajectory, i.e.:
d(S(p=]le(()) + S(o ((o')l((())
(18)
dt
4.1 Poincaré Recurrence Quantum Zero-Sum Games
Now that we have described analytical results surrounding the day-to-day behaviour of quantum replicator dynamics, we seek to understand the dynamics of the trajectories. After all, invariance of quantum relative entropy does not fully describe how the system moves over time. We show that for any two- two-player zero-sum quantum game updated with replicator dynamics, the system exhibits Poincaré recurrence, insofar the game is zero- and has a fully-mixed Nash equilibria. As introduced in Section 2 the notion Poincaré recurrence is a weaker version of periodicity. To be precise, for almost all initial conditions po E P, the replicator dynamics return arbitrarily close po infinitely often.
Theorem 4.3. The quantum replicator dynamics given in Equations are Poincaré recurrent in any two player zero-sum game which has a fully-mixed Nash equilibrium.
arre
The proof of this main theorem involves carefully piecing together several auxiliary results, which we will describe in the rest of the section. Furthermore, we stress that due to the non-commutative nature of quantum systems, the standard (classical) approach of differentiating the discrete- time dynamics in the primal space of probability distributions does not apply directly unless we have the highly unlikely situation where f (T)())d and (a)()) (resp. J Φt (p(T))dr and tt (p(t)) commute. This problem with carrying over the standard approach is explicitly discussed in Appendix
For the proof in the quantum setting, we first define a canonical transformation on the space of the matrices A(t) and (t)), which will be crucial in proving the theorem.
Definition 4.4 (Canonical transformation). We define the canonical transformation of A'(t) and (t()) be mapping of A(t) and (t) as defined by Equations 13 and 15
In particular, we define
A'()) = A(t) A())()) B'(t) B(t) - (o. B(t)c)
(19)
where e is fixed vector defined as v = [1. ...0....0 O) such that the values of A(te and at B()y are real numbers corresponding to the (1,1)-th element of matrices A(t) and B(t) for all t. Notice that this creates matrices A' At) and (t) which have as the (1, 1)-th entry.
Under the transformation in Definition 4.4. the vector fields Á'(t) = F(A') and B'(t) = F(B') are given by:
Á'(t) (((()) (+*)(((())))
(20)
B'(t) = - (p(t)) + (vl (p(t))o)1
where & (vtA(f))) is given by at dd(t)),,
Moreover, the values of p'(t) and o' are defined as:
p(()) cxp(A(())/T((eep((N)))
(21)
o' (t) (xp((B(t))TT((ex)))
Proposition 4.5. The dynamics of p(t) and att) remain the same after undergoing the canonical transformation. Equivalently, (t) and A(t) (resp. B' and B(t)) admit the same strategy p(t) (resp. (t)).
Proposition 4.6. The mappings (1) and p(t) (resp. (1( and (()) are diffeomorphic to one another.
7

---

Proposition 4.6 will be of crucial importance to our proof technique, since we first prove recurrence for the system deseribed by (t) and B' (t), then recover recurrence in p(t) and (t)).
To show Poincaré recurrence of Equations 17 we first prove two key properties: À' is volume preserving, meaning that the trace of the Jacobian of the respective vector fields (t( = F(4') and (t) = F(B') are zero, and (ii) A' and have bounded orbits from any interior initial condition. Then, Poincaré recurrence of A' and B' follows from Poincaré's recurrence theorem.
(i) the flow of
Volume Conservation. We introduce lemma which shows that in two-player zero-sum quantum replicator dynamics, the canonical transformation produces dynamical system which preserves volume.
Lemma 4.7. For two-player sero-sum quantum replicator dynamics, the vector fields that arise result of the canonical transformation in Definition 4.4 are volume preserving.
The proof of Lemma 4.7
follows from considering the flows of (I) and (1) and showing that the divergences of the vector fields defined in Equations 20 equal to zero. A straightforward application of Liouville's 's theorem completes the proof.
Bounded Orbits. We now show that the transformed dynamical system always has bounded orbits when initialized on the interior of the space of probability density matrices.
Lemma 4.8. For any finite initial points A(0) and B(),, the dynamics mapped to (t) and (t via the transformation in Definition 4.4 have bounded orbits.
The proof of Lemma 4.8 relies on Theorem 4.2, and leverages the hermicity of the matrices involved. Moreover, we use the fact that the canonically transformed matrices (t( and B'(t) have zero the (1, 1)-th element to bound the eigenvalues of (f) and ('(t) away from infinity.
Now ready to prove Theorem 4.3 using Lemmas
and 4.8
well as the Poincaré recurrence theorem introduced in Section we immediately see that the system of replicator equations given by d'' 4A'ddt and dB' /dt Poincare recurrent since they are volume preserving and have bounded orbits. Since the flows of A'(t) and p(t) are diffeomorphic to one another (likewise for 13 (t) and (t)), dp/ dt and do / dt are also Poincaré recurrent. This concludes the proof.
Proof of Theorem 4.3 By Lemmas 4.7 and 4.8
All proofs of the results in this section are provided in Appendix D
Experimental Results
62
24 24
24
06 03
33
24
24
24
# log(1 (1
+
2474
/
log(1
gt/a
log
277
/ log
$3/3
Figure I: Eigenvalue trajectories for quantum Matching Pennies game with decreasing l values.
To corroborate the theoretical results presented in prior sections, we performed relevant simulations of quantum games using both discrete MMWU and replicator dynamics. In the rest of this section, we standardize the use of quantum game matrices obtained via basis transform (described more detail in Appendix E. This effectively allows transform classical games to the matrix setting.
First, we show the trajectories of the first eigenvalue of each player in quantum Matching Pennies game, obtained using the discrete MMWU algorithm. We see that in accordance to Theorem 3.5

---

the rate of divergence of the trajectories from the uniform Nash goes to zero for cases with rapidly decreasing learning rate μ.
In the case of replicator dynamics, we present Bloch sphere representations of the trajectories in quantum Matching Pennies game. The Bloch sphere is unit 2-sphere representation of qubit, and we utilize it to visualize the orbits of the replicator dynamics. In particular, the density matrix representing the strategy of each player at each time-step given as point within the sphere, and we plot the movement of these orbits over time. According to Theorems 4.2 and 4.3 we expect the trajectories of the replicator dynamies to stay on the interior of the Bloch sphere, since the surface of the sphere corresponds to the pure states of the system. We see from Figure that over time, the system never reaches the boundary of the sphere, which experimentally agrees with our theory.
[0]
103
10)
10:
11
12
1-1
50
1 --0
t= 1000
Figure 2: Bloch sphere trajectories for quantum Matching Pennies game between Alice (blue) and Bob (red). The arrowheads represent the current state of each player at each time-step. Notice that over time, the orbits oscillate within the interior of the Bloch sphere.
Finally, in the experiments above we have only studied single qubit systems. We provide further experiments which show that our results hold beyond the single qubit setting in Appendix E.2 E.2
6 Conclusion
In this paper, we studied the properties of Matrix Multiplicative Weights Update and its continuous analogue, quantum replicator dynamies, in the context of two-player zero-sum quantum games. First, we provide a formulation of quantum replicator dynamics which arises from MMWU. Then, we show that such systems exhibit quantum coormationntthoreeee constant of motions. Finally, we show that in quantum replicator systems with interior Nash equilibria, the dynamics exhibit Poincaré recurrence.
This work constitutes an initial step towards analyzing learning behaviour in games with quantum information. In the classical world, showing that conservation laws and recurrence holds has led to a better understanding of game dynamics in increasingly complex settings 52 43 47). Similar work is now potentially possible in the quantum setting.
Moreover, key implication which can be derived from our recurrence results is to encourage novel discretization methods that preserve the connections to volume preservation and more generally, conservative dynamical systems (e.g. Hamiltonians). This line of research has received increased interest in recent years [5 [56] 17]. It is a natural question to explore whether such techniques can lead to similar advantages in the quantum setting well.
Finally, some other interesting directions for future work include:
extending our results to multi- agent network generalizations of quantum pero-sum games,
understanding the potential behavior of quantum GANs using our results about learning in quantum zero-sum games, and
understanding the quantum setting for different classes of games, e.g., potential games.
Acknowledgements
This research/project is supported by the National Research Foundation, Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2020-016 NRF2019- NRFANRO95 ALIAS grant, grant PIE-SGP-AI-2020-001 NRF 2018 Fellowship NRF-NRFF2018--0

---

and AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR). Rahul Jain's research is supported by the National Research Foundation, Singapore, also through the grant N under the Research Centers of Excellence program. Ryann Sim gratefully acknowledges support from the SUTD President's Graduate Fellowship (SUTD--PGF).
and the Ministry of Education, Singapore
References
[1] S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. Online learning of quantum states. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124019, 2019.
[2] I. Accardi and A. Boukas. Von neumann's minimax theorem for continuous quantum games. Journal of Stochastic Analysis, 1(2), Jun 2020.
[3] Z. Allen-Zhu and Y. Li. Follow the compressed leader: Faster online learning of eigenvectors and faster mmwu. In International Conference on Machine Learning, pages 116-125. PMLR, 2017.
[4] Z. Allen-Zhu, Z. Liao, and L. Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings the forty-seventh annual ACM symposium on Theory of computing, pages 237-245, 2015.
[5] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121-14, 2012.
[6] S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63(2), May 2016.
[7] Bailey and G. Piliouras. Multiplicative weights update zero-sum games. Proceedings of the 2018 ACM Conference Economics and Computation, pages 321-338, 2018.
[8] J. Biamonte, P. Wittek, N. Pancotti, P. Rehentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. Nature, 549(7671)) 195-220,, 2017.
[9] R. Bondesan and M. Welling. The hintons in your neural network: quantum field theory view of deep learning, 2021.
[10] J. Bostanci and J. Watrous. Quantum game theory and the complexity of approximating quantum nash equilibria. arXiv preprini 10Xiv:2102.005/2, 2021.
[11] G. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu. Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning. arXiv preprint 170.0217, 2017.
[12] S. Chakrabarti, H. Yiming, T. Li, S. Feizi, and X. Wu. Quantum wasserstein generative adversarial networks. Advances in Neural Information Processing Systems, 32, 2019.
[13] Y. Cheung. Multiplicative weights updates with constant step-size in graphical constant-sum games. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamettt, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[14] P.-. Callaire-Demers and N. Killoran. Quantum generative adversarial networks. Physical Review A, 90(1))(())) ::012224,,, 2018.
[15] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009.
[16] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GANs with optimism. In JCLR, 2018.
[17] Diakonikolas and M. Jordan. Generalized momentum-basee methods: hamiltonian perspective. SIAM Journal Optimization, 31(1):915-944, 2021.
10

---

[18] D. Dong, C. Chen, H. Li. and T.-J. Tarn. Quantum reinforcement learning. JEEE Transactions on Systems, Man, and Cybernetics, Part (Cyberneties), 38(5):200--1220, Oct 2008.
[19] V. Dunjko, J. M. Taylor, and H. J. Briegel. Advances in quantum reinforcement learning. 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Oct 2017.
[20] K. Fan. Minimax theorems. Proceedings of the National Academy of Sciences, 39(1): 1):42477,
1953.
[21] L. Flokas, E.-V. Vlatakis SaaadiisGGaaaggouiiis, and G. Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient- puadient-descent-ascee for non-convex non-concave zero-sum games, 2019.
[22] Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-100 1999.
[23] D. Fudenberg and D. K. Levine. The theory of learning in games, volume 2. MIT press, 1998.
[24] Golden. Lower bounds for the helmholtz function. Phys. Rev. 137:B1127-B1122 Feb 1965.
[25] I. Goodfellow, J. Pouget-Abadic, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[26] E. Hazan, Kale, and S. Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. In Conference on Learning Theory, pages 38-1. JMLR Workshop and Conference Proceedings, 2012.
[27] S. B. Hopkins, J. Li, and F. Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. arXiv preprint arXiv:2007.15839 2020.
[28] R. Jain and J. Watrous. Parallel approximation non-interactive zero-sum quantum games. In 2009 24th Annual IEEE Conference Computational Complexity, pages 243-253. IEEE, 2009.
[29] J. R. Johansson, P. D. Nation, and F. Nori. Qutip: An open-source python framework for the dynamics of open quantum systems. Computer Physics Communications, 18600):170 2012.
[30] Kale, Efficient algorithms using the multiplicative weights update method. Princeton University, 2007.
[31] S. Khan, N. Solmeyer, Balu, and S. Humble. Quantum games: a review of the history, current state, and interpretation. Quantum Information Processing. 17(11), 10 2018.
[32] N. Kodali, J. Abernethy, Hays, and Z. Kira. On convergence and stability of gans, arXiv preprint tete: 2017.
[33] C. E. Lemke and T. Howson, Jr. Equilibrium points bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2):413-423, 1964.
[34] T. Li, S. Chakrabarti, and X. Wu. Sublinear quantum algorithms for training linear and kernel- based classifiers. In International Conference on Machine Learning, pages 3815-3824, PMLR, 2019.
[35] T. Li, C. Wang, S. Chakrabarti, and X. Wu. Sublinear classical and quantum algorithms for general matrix games. arXiv preprint arXiv:2012.06511 2020.
[36] Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference Machine Learning, pages 6083-6093, PMLR, 2020.
[37] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and computation, 102221, 1994.

---

[38] S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411 2013.
[39]
Lloyd and C. Weedbrook. Quantum generative adversarial learning. Physical review letters, 12 121(4)004500, 2018.
[40] N. D. Mermin. Simple unified form for the major no-hidden-variabll theorems. Physical review letters, 65(27):3373, 1990.
[41] Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Op- timistic mirror descent in saddle-point poilte problems: Going the extra(-gradien) mile. In ICLR, 2019.
[42] P. Mertikopoulos, C. H. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In SODA '18 Twenty-Ninit Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717, New Orleans, United States, Jan. 2018.
[43] S. G.G. Nagarajan, D. Balduzzi, and G. Piliouras. From chaos to order: Symmetry and conservation laws in game dynamics. In International Conference on Machine Learning, pages 7186-7196. PMLR, 2020.
[44] J. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951.
[45] G. Palaiopanos. I. Panageas, and G. Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos, 2017.
[46] A. Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3-4):007-18, 1990.
[47] J. Perolat, R. Munos, J.-B. Lespiau, S. Omidshafiei, M. Rowland, P. Ortega, N. Burch, T. An- thony, D. Balduzzi, B. D. Vylder, G. Piliouras, M. Lanctot, and K. Tuyls. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regulariza- tion, 2020.
[48] G. Piliouras and J. Shamma. Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence. In SODA, 2014.
[49] G. Piliouras, R. Sim, and S. Skoulakis. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint arXiv:2111.14737, 2021.
[50] H. Poincaré. Sur le problème des trois corps et les équations de la dynamique. Acta mathematica, 13(1):A3-A270, 1890.
[51] W. H. Sandholm. Population Games and Evolutionary Dynamics. The MIT Press, 2010.
[52] S. Skoulakis, T. Fiez, R. Sim, G. Piliouras, and I.. Ratliff. Evolutionary game theory squared: Evolving agents in endogenously evolving zero-sum games. arXiv preprint arXiv:2012.08382 2020.
[53] C. J. Thompson. Inequality with applications in statistical mechanics. Journal of Mathematical Physics, 6(1 6(11):1812-1813 1965.
[54] K. Tsuda, G. Rätsch, and M. K. Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. Journal of Machine Learning Research, 6(Jun):995-100 -0188 2005.
[55] J. van Apeldoom and A. Gilyén. Quantum algorithms for zero-sum games. arXiv preprint 190400090 2019.
[56] A. Wibisono, M. Tao, and G. Piliouras. Alternating mirror descent for constrained min-max games. arXiv preprint N.Xi:2206.04///0 2022.
[57] A. Wibisono, A. C. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 113(47))77351--7358 2016.
12

---

[58] A. Youssry, C. Ferrie, and M. Tomamichel. Efficient online quantum state estimation using matrix exttrii-exponetiattedd gradient method. New Journal of Physics, 21(3):03300,, 2019.
[59] Zhang. Quantum strategic game theory. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 39-59, 2012.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The contributions and scope are clearly stated and derived directly from our results.
(b) Did you describe the limitations of your work? [Yes] The limitations of our work described in the introduction and in the main text.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] See Section 6
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions stated either in the main body the appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are provided in the main text or appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] The code is compiled several formats and provided in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [No] Our simulations do not require training.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [No] Our simulations are deterministic.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Details of the resources and packages used described in the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the code packages used.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] Our work does not utilize human- data.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A] Our work does not include crowdsourcing or research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "W_GnwX2fMuY", "reviewer": "Reviewer_TGZ4", "summary": "Quantum computing is an interesting research area these days, and this paper studies a specific problem in quantum computing, quantum zero-sum games. The authors consider a standard algorithm in zero-sum games, matrix multiplicative weight update (MMWU), and study its behavior of convergence in continuous time, in the sense of dynamical systems. Specifically, the authors prove that under the quantum replicator dynamics, the system exhibits conservation laws in a quantum information-theoretic sense. Moreover, the system exhibits the Poincare recurrence, i.e., all orbits return arbitrarily close to their initial conditions infinitely often. Numerical experiments are performed to corroborate the theoretical claims.", "questions": "My question is about the connection between this work and the machine learning community in general. Please see my discussions above.", "limitations": "Although the checklist mentioned that the limitations of the paper are described in the introduction and in the main text, I found a bit hard to locate that explicitly... It would be helpful if the authors can highlight this.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, both quantum computing and game theory are very important and interesting fields, and it’s great to see that the authors are able to prove some theoretical results for quantum games. As far as I see, previous quantum computing papers relevant to the topic studies different perspectives, and this result on the conservation law of quantum games under MMWU is novel to me. This is also a significant result and I believe that it can bring further attention to the interdisciplinary research between quantum computing and game theory.\n\nIn all, I think this paper can appropriately fit into NeurIPS 2022. However, the paper still has space to improve. In particular, the authors might be able to make more efforts to build the relevance of this work to the general machine learning audiences. To me, the conservation law & recurrence result is definitely nice to know, specifically that the authors are able to prove this in the quantum computing domain, but these are more like pure math results and I didn’t immediately see the implication to machine learning. From the perspective of game theory, does that imply any fast quantum/classical algorithm based on MMWU such that we can solve relevant quantum/classical game theory problems (or maybe other problems relevant to machine learning) faster? \n\nFor the specific perspective of dynamical systems which covers the conservation law and recurrence properties studied by the paper, a similar story that has been well received by the ML community is the study of gradient descent methods in continuous time limit, in other words, characterization of optimization methods by differential equations. For instance, speaking of the methodology, this paper by Wibisono, Wilson, and Jordan published at PNAS https://www.pnas.org/content/113/47/E7351.short proposes a framework of continuous-time dynamics for understanding accelerated gradient descent methods, which is also based on the Bregman divergence (similar to this submission). It is noted that papers along this line have been well-received by the ML community with various NeurIPS and other top-venue papers. After reading this submission, I believe that it also has the potential to become more relevant as a systematic tool to understand game theory, but the authors should put more effort on this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lgvbf3d90cC", "reviewer": "Reviewer_VXhb", "summary": "The paper studies a specific case of two-player zero-sum games where each player strategy is to probabilistically prepare a quantum pure state that he/she sends to a referee who then performs a joint measurement on the two quantum states to determine the payoffs of the players. The restriction is that each player updates their strategy according to the Matrix Multiplicative Weight Update (MMWU) methods. The validity of their strategies is guaranteed by the trace normalization performed after updating according to MMWU. The main results of the paper are Theorem 3.5 and 4.2: the total quantum relative entropy is a constant of motion. \n", "questions": "1. How are the main results similar or different from classical counterparts?\n2. What happens if the two players share randomness and/or entangled states? \n3. Will the experiments with multi-qubit strategies differ from the current experiments with single-qubit strategies? \n", "limitations": "Not applicable. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find the results of the papers are interesting with the strengths in the rigorous theoretical analysis deriving the main results of the papers. \nNevertheless, I am having difficulties to understand the impact of the results to the quantum learning theory. Especially, the results are restricted to the specific rules of updating strategies according to the MMWU, which seems to be quite restrictive. \n \nAnother weakness is the lack of comparison to the classical counterparts. Introducing quantum strategies can add more powers either to players. For example, what will happen if the two players share entangled states? Do Theorems 3.5 and 4.3 hold? Or, what if the players can only have shared random numbers but not entangled states? \n\nI also think the experimental results are weak as they are essentially 1-qubit strategy for each player. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "L_tDxfwUek8", "reviewer": "Reviewer_Tz9L", "summary": "A two-player zero-sum quantum game consists of three steps. \n\n1) Two players prepare two mixed states $\\sigma,\\rho$.\n2) A third party makes a joint measurement $R$ on the tensor product $\\rho\\otimes \\sigma$.\n3) The payoff of the first player receives is the result of the measurement, whereas the second player receives the negative of that value.\n\nOne may naturally define a notion of Nash equilibrium for such games. The general problem addressed here is the following: assuming a repeated game, do both players converge to the/a Nash equilibrium?\n\nThe present paper considers this problem in the case where both players follow a matrix multiplicative weights (MMW) algorithm, which (for suitable step sizes) achieves vanishing regret. Before I state the main results of this submission, I wish to mention two results in the corresponding classical setting with the multiplicative weights (MW) algorithm.\n\n1) Bailey and Piliouras (2018 ACM Conference on Economics and Computation) prove that (under suitable assumptions) there is no convergence to Nash equilibria. \n2) Mertikopoulos et al (SODA 2018) that players' states are Poincaré recurrent in a continuous-time limit of MW (or more generally of \"follow the regularized leader\"). \n\nThe present paper proves variants of the above results for the continuous-time limit of MMW, called quantum replicator dynamics (under suitable conditions). The proof of Poincaré recurrence is related to the second reference above, in that it requires showing that the quantum replicator flow is volume preserving (after a certain transformation) and has bounded trajectories. Another result shows that the quantum replicator dynamics leaves invariant a sum of relative entropies, each comparing \"one half of a Nash equilibrium\"(ie. one of the states in the pair constituting the equilibrium) to \"one half of the quantum replicator dynamics\". Additional bounds are given for the evolution of the relative entropies in discrete time. \n\nThe above results are complemented by experiments.The introduction motivates these results by their relationship to quantum learning and quantum GANs. These connections are taken up in the conclusion as part of a discussion on future directions. \n", "questions": "Q1) Can you explain the results about Quantum GANs that you would like to formalize (as per your conclusion)?\n\nQ2) In the argument for Theorem 3.5, $\\rho_j$ and $\\sigma_j$ also depend on $\\mu$. However, I do not quite see how the proof of the theorem accounts for this. Can you explain this point? Also, the reasoning in line 648 about evolving $\\rho_j$ does not seem very rigorous (thought it could be made rigorous). \n\nQ3) Can you explain how exactly Definition 4.4 is used in the proof? Where would the proof \"break\" if this definition did not hold? \n\n*Update on 08/07*\n\nI thank the authors for their clarifications.", "limitations": "The submission is good in this regard. It is \"limited\" in that it does not fully generalize the results from the classical setting. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\nThe paper is mostly clearly written (although not everywhere). Its main strength of the present paper is the (partial) extension of the two papers mentioned in the summary to the quantum setting. The conservation of the sum of relative entropies is a nice result, and the proof, although relatively simple, is different from those in the main references.  \n\n*Weaknesses*\n\n1. Unlike the first paper papers in the above summary, the present submission only considers the continuous-time limit, not the actual repeated game. \n2. Unlike the second paper, only multiplicative weights are considered (though this may be a limitation of online learning theory in the matrix setting). \n3. Although the main results are motivated by applications to quantum GANs, the connection seems somewhat tenuous. This raises the question of whether NeurIPS is a good fit for the paper. \n4. I have some reservations about the proofs of Theorems 3.5 and 4.3. Mostly they stem from the fact that $\\rho_j,\\sigma_j$ also depend on $\\mu$. In particular, there seems to be a \"order of limits\" question there that I will discuss later. \n\n-- \n\n*Other comments \\& suggested corrections*\n\nLine 153: \"can also be defined\"- no, that's the actual definition.\n\nLine 158: in general, how does one define a differential equation in a topological space?\n\nThe notation $A(t)$ used in Liouville's Theorem has another meaning later in the paper.\n\nThe use of time derivatives in (17) is confusing.\n\nLine 234: here \"typically\" apparently should mean \"in the classical (or commuting) case\".\n\n--\n\n*Review update on 08/07*\n\nThe authors' answers to point 4 above have convinced me. I am satisfied that the proofs are correct. I am also clearer on the literature and their motivation for considering this specific algorithm.\n \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-zbuUhpk-x2", "reviewer": "Reviewer_wK2r", "summary": "The authors consider (2 player) quantum zero-sum games and analyze two algorithms for learning the Nash equilibrium: matrix multiplicative weights and its continuous-time analog, the quantum replicator dynamics. As far as I understand, both algorithms have been previously described in the literature. The authors prove the convergence some entropic quantities during the execution of the algorithms. The main technical contribution is the proof of Poincare recurrence of quantum replicator dynamics.", "questions": " - Why do you analyze the change in the relative entropy instead of its actual value? Naively, it seems that proving that the change converges to 0 implies only that the relative entropy has converged to a fixed value which might or might not be 0. Has [25] already estabilished this convergence?\n - Are Theorems 3.5 and 4.2 interesting in their own right? How are they used to prove the main result, Theorem 4.3?", "limitations": "The work is purely theoretical, no direct social impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and provides just enough details to be understood at a superficial level. On the more fundamental level, some motivation and intuition should be given about the connections between section 4.1 and the part of the paper before it. Some space could be easily reclaimed by removing the definitions and claims that are not used outside of the appendix.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept