Imperfect-information games with a graded-reward structure present significant computational challenges for equilibrium computation, since the payoff expectations must be estimated across exponentially large strategy spaces. Counterfactual Regret Minimization over the years has proven effective for approximating Nash equilibria, but Monte Carlo variants create a large overhead of sampling costs when the counterfactual values are estimated from sampled game-tree trajectories. We propose a novel Quantum-Assisted Counterfactual Regret Minimization, a framework that uses Quantum Amplitude Estimation to reduce the computational complexity of the regret updates in bounded-payoff imperfect-information games, while preserving the convergence of its classical counterpart. We give a theoretical analysis of the resulting exploitability bound, discuss NISQ-compatible amplitude-estimation variants, the structure of their resource requirements, and outline what is needed to validate the potential advantage empirically.
Imperfect-information games with a graded-reward structure present significant computational challenges for equilibrium computation, since the payoff expectations must be estimated across exponentially large strategy spaces. Counterfactual Regret Minimization over the years has proven effective for approximating Nash equilibria, but Monte Carlo variants create a large overhead of sampling costs when the counterfactual values are estimated from sampled game-tree trajectories. We propose a novel Quantum-Assisted Counterfactual Regret Minimization, a framework that uses Quantum Amplitude Estimation to reduce the computational complexity of the regret updates in bounded-payoff imperfect-information games, while preserving the convergence of its classical counterpart. We give a theoretical analysis of the resulting exploitability bound, discuss NISQ-compatible amplitude-estimation variants, the structure of their resource requirements, and outline what is needed to validate the potential advantage empirically.
As quantum processors advance, the emergence of large-scale decentralized systems involving interacting quantum-enabled agents is on the horizon. Recent research efforts have explored quantum versions of Nash and correlated equilibria as solution concepts of strategic quantum interactions, but these approaches did not directly connect to decentralized adaptive setups where agents possess limited information. This paper delves into the dynamics of quantum-enabled agents within decentralized systems that employ no-regret algorithms to update their behaviors over time. Specifically, we investigate two-player quantum zero-sum games and polymatrix quantum zero-sum games, showing that no-regret algorithms converge to separable quantum Nash equilibria in time-average. In the case of general multi-player quantum games, our work leads to a novel solution concept, that of the separable quantum coarse correlated equilibria (QCCE), as the convergent outcome of the time-averaged behavior no-regret algorithms, offering a natural solution concept for decentralized quantum systems. Finally, we show that computing QCCEs can be formulated as a semidefinite program and establish the existence of entangled (i.e., non-separable) QCCEs, which are unlearnable via the current paradigm of no-regret learning.
We demonstrate how quantum computing can provide a promising framework for addressing imperfect information games, using the popular German card game Skat as a case study. Our approach employs quantum registers to encode the game's hidden and public information, along with tailored quantum gates to model the game's progress while respecting its rules. To evaluate player decisions, we introduce a score operator that projects the quantum state onto the winning subspace, enabling the estimation of winning probabilities via quantum algorithms such as quantum counting. This allows the efficient exploration of alternative strategies and potential improvements in computational speed compared to classical methods. By maximizing the payoff function, our framework yields actionable recommendations for optimal play. As classical computation faces severe limitations due to the exponential complexity of the game tree, we discuss the specific structural properties of Skat that may give rise to a quantum advantage once the problem size surpasses classical feasibility.
In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the O(1/T) convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an O(T−1/4) rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
This thesis studies the exploration and exploitation trade-off in online learning of properties of quantum states using multi-armed bandits. Given streaming access to an unknown quantum state, in each round we select an observable from a set of actions to maximize its expectation value. Using past information, we refine actions to minimize regret; the cumulative gap between current reward and the maximum possible. We derive information-theoretic lower bounds and optimal strategies with matching upper bounds, showing regret typically scales as the square root of rounds. As an application, we reframe quantum state tomography to both learn the state efficiently and minimize measurement disturbance. For pure states and continuous actions, we achieve polylogarithmic regret using a sample-optimal algorithm based on a weighted online least squares estimator. The algorithm relies on the optimistic principle and controls the eigenvalues of the design matrix. We also apply our framework to quantum recommender systems and thermodynamic work extraction from unknown states. In this last setting, our results demonstrate an exponential advantage in work dissipation over tomography-based protocols.
In this paper, we study the problem of learning in quantum gamesand other classes of semidefinite games-with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the O(1/ √ T) convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an O(T −1/4) rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.
Quantum algorithms for trading span computational tasks with different input models and standards of evidence. This structured critical review describes its search scope, selection criteria and limitations, and distinguishes reported findings from author assessments. Amplitude estimation estimates bounded expectations to additive error ϵ with O(ϵ−1) oracle queries rather than the O(ϵ−2) samples of plain classical Monte Carlo at fixed confidence. This query advantage does not establish an end-to-end runtime advantage: state preparation, arithmetic, error correction and classical competitors must also be costed. Published resource estimates for benchmark exotics require thousands of logical qubits and demanding logical operation rates. An illustrative sensitivity analysis shows how the crossover depends on classical throughput, oracle depth and the comparison window; its numbers are scenarios, not calibrated hardware forecasts. Portfolio and trading-trajectory formulations have device demonstrations, but a 250-instance benchmark of discretized minimum-variance allocation finds classical mixed-integer programming and a tailored heuristic superior on the tested formulation. Specific low-rank quantum machine learning algorithms have been dequantized under analogous sampling-access assumptions. Separately, a controlled study of quantum kernels for Chinese equity returns finds no significant advantage and demonstrates sensitivity to evaluation design; this does not settle other learning tasks. Entanglement-assisted coordination offers advantages in specified nonlocal games without computational-complexity assumptions, while its financial implementation and economics remain open. We distinguish computational performance from economic value and identify input/output costs, structured algorithms, reproducible benchmarking and explicit financial evaluation as priorities.