Optimistic matrix mirror-prox (OMMP) computes ε-approximate Nash equilibria in quantum zero-sum games with an O(1/ε) average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an Ω(1/ε) lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium Θ(1/t) and duality gap Θ(1/t3) for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as Θ(1/t), while the duality gap decays as Θ(1/t2).
Figures & tables
Figure 1: One Alice projection for OGDA in the (u,w) cross-section of the Bloch sphere. The pure input satisfies u2+w2=1 . Subtracting hQ , where h≥0 , shifts the Bloch vector from (u,w) to (u,w+h) along the orange arrow. The blue arrow is the radial projection onto the unit circle, giving (u′,w′)=(u/N,(w+h)/N) with N=1+2hw+h2 . Writing c=u/2 and c′=u′/2 for the input and output coherences, we have c′=c/N≥c/(1+h) . Thus a small shift changes the coherence only slightly.
Figure 2: OMMWU in the (x,z) cross-section of the Bloch ball. Alice’s state αt has Bloch radius tanhRt and lies on the radius through the pure state Pt+ associated with the leading eigenvector of Ht . The orange segment represents the radial concentration 1−tanhRt=O(e−2κt) . The angle between this radius and the equilibrium direction satisfies θt∼p∞/(κt) . Thus Alice’s state approaches the moving pure state Pt+ exponentially fast, while its direction approaches P at rate 1/t . The radial separation is enlarged to distinguish the two errors.
Figure 3: OGDA on UG=Q⊗Q from (ρr,P) with η=1/8 . Top: gap and distance versus iteration. Bottom: errors normalized by their initial values versus tηr . Open circles mark Tr ; dotted lines mark the normalized thresholds 1/2 and 1/2 from ( 4.15 ). The top panels use logarithmic vertical axes and symlog horizontal axes to include t=0 .
Figure 4: Initialization control for OGDA on UG=Q⊗Q with η=1/8 . Normalized gap (left) and distance (right) from the maximally mixed state (black) and coherent starts (colored). Open circles mark the mixed run’s first zero at t=13 and the coherent horizon T10−1=12 ; the other horizons exceed the displayed window.
Figure 5: OGDA from (I/2,I/2) on UGmix with η=1/8 . Played-iterate distance (left) and gap (right) on logarithmic axes, with dashed asymptotes 32/t and 2048/t3 from Theorem 4.9 . Annotated slopes are fitted over 104≤t≤105 . Open circles mark the final recorded iterate.
Figure 6: OMMWU from (I/2,I/2) on UM with η=1/8 . Solid curves show the played-iterate errors on logarithmic axes; dashed curves show the asymptotes from Theorem 5.2 . Annotated slopes are fitted over 104≤t≤105 .