Coherent Swap Regret and Channel-Proof Learning

Sohail Sarkar

quant-phJun 1, 2026

Coherent Swap Regret and Channel-Proof Learning

Authors: Sohail Sarkar

Organizations: University of Toronto

Abstract

External regret certifies stability only against replacing one's behavior by a fixed alternative. In a quantum game, this misses a natural physical move: a player can apply a local completely positive trace-preserving (CPTP) map to the state it actually received or prepared. We introduce coherent swap regret as the regret benchmark against all such local CPTP deviations, and give an algorithm achieving $O(\sqrt{dT\log d})$ coherent swap regret via entropic mirror ascent on the CPTP Choi slice with a fixed-point play rule. The main result is a three-level deviation-class landscape. Replacement channels recover ordinary external regret at rate $Θ(\sqrt{T\log d})$ . Unital channels, including unitary deviations and mixtures of unitaries, have zero minimax regret. Deterministic measurement-and-preparation channels already force $Ω(\sqrt{dT\log d})$ regret in the moderate-horizon regime, and this rate is also sufficient for all CPTP deviations. Thus the hardness comes from non-unital use of the recommendation register, not from quantum coherence alone. As an application, decentralized full-information learning in finite quantum games reaches an $\varepsilon$ -approximate separable quantum correlated equilibrium after $T=O(\max_i d_i\log d_i/\varepsilon^2)$ rounds. We identify these equilibria with channel-proofness of mediated quantum recommendation protocols, give an SDP audit for local CPTP exploitability applicable to arbitrary finite-dimensional states, and include a probing-bandit extension with pseudo-regret $O(d^{4/3}T^{2/3}(\log d)^{1/3})$ under Haar-random pure-state probes.

Explore similar work

Aug 4, 2026cs.GT

Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best previous guarantee when every player follows the same dynamics grows logarithmically in the horizon

T

. We construct uncoupled dynamics under which every player incurs only

O(nm^2\sqrt{\log m\log T})

swap regret, where

n

is the number of players and

m

bounds the number of actions per player. To our knowledge, this is the first sublogarithmic individual guarantee in this setting, and it implies that the time-averaged product distribution of play is an

O(nm^2\sqrt{\log m\log T}/T)

-approximate correlated equilibrium. The key algorithmic choice is to combine the Blum--Mansour reduction with optimistic follow-the-regularized-leader using a hybrid regularizer that separately weights negative Shannon entropy and the log-barrier: the entropy controls the optimistic prediction error, whereas the log-barrier controls the transition-matrix movement through its Bregman divergence. A new sensitivity theorem for stationary distributions of Markov chains, which involves neither mixing parameters nor the smallest transition probability, transfers this control to the played strategies and yields a simpler analysis without local-norm or self-concordance arguments. The guarantee is preserved by an adversarially robust variant that additionally ensures

O(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})

swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of

T

Taira Tsuchiya

Imperfect-Information Games Horizon

Ask PDF

Jul 10, 2026quant-ph

When Routes Run Out: Adversarial Co-Learning and Explainable Robustness in Quantum Repeater Networks

We study an adversarial bandit problem for entanglement-based quantum-network routing over a modest graph corpus. Alice selects an end-to-end repeater route for an Ekert-91 protocol (E91) representing her move, while Eve selects an attack surface, either edge intercept--resend or repeater memory degradation. Payoffs are drawn from cached SeQUeNCe-simulated E91 transcripts, and Alice accepts a turn when the finite-sample statistic violates the Clauser-Horne-Shimony-Holt (CHSH) bound. Performing adversarial co-learning across 50 structured topologies, we find that learned retention tracks a full-matrix minimax reference closely (Pearson

r=0.99

): under a one-surface Eve action model, bottleneck families have zero retention, while non-bottleneck families follow a

1-1/N

coverage principle. We then fit decision-tree explanation models to graph-, attack-, and route-level topology-corpus targets and report their faithfulness. Finally, we construct prompt records for local language models to summarize the tree evidence, resulting in an open-source explanation workflow for quantum-repeater network games.

Brennan Bell, Inti Gabriel Mendoza Estrada, Andreas Trügler +1

Entanglement Adversarial Training Lane Topology

Ask PDF

Jul 2, 2026quant-ph

Optimal Stabilizer Testing and Learning with Limited Quantum Memory

We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown

n

-qubit state, but may keep only

k

qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test

n

-qubit stabilizer states using

6

copies, which is dimension independent, unlike the learning complexity of

Θ(n)

. We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the

k

-qubit memory framework is

Θ(n-k)

. Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with

k

qubits of memory, in the non-adaptive framework, is

Θ(n^2/k)

. As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with

k=0.99n

qubits of memory, there is no constant-copy stabilizer tester; furthermore for

k=cn

qubits of memory (for

0< c < 1

), stabilizer testing is as hard as learning, with both requiring

Θ(n)

copies.

Srinivasan Arunachalam, Louis Schatzki

N$-Qubit Stabilizer States Sample Complexity

Ask PDF