We propose a quantum multi-level estimation framework for a functional ∑_{i=1}^n f(p_i) of a discrete distribution (p_i)_{i=1}^n. We partition the values p_i into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant p_i, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the q-Tsallis entropy of discrete distributions. Specifically, - For q > 1, we obtain a near-optimal quantum algorithm with query complexity Θ̃(1/ε^{max{1/(2(q-1)), 1}}), improving the prior best O(1/ε^{1+1/(q-1)}) due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). - For 0 < q < 1, we obtain a quantum algorithm with query complexity Õ(n^{1/q-1/2}/ε^{1/q}), exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized q-entropy for non-integer q.

Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called correlated equilibria has been widely explored in game theory. In this paper, we initiate the study of quantum algorithms for computing $\varepsilon$-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) in multi-player normal-form games. Our approach utilizes quantum improvements to the multi-scale Multiplicative Weight Update (MWU) method for CE calculations, achieving a query complexity of $\tilde{O}(m\sqrt{n})$ for fixed $\varepsilon$. For CCE, we extend techniques from quantum algorithms for zero-sum games to multi-player settings, achieving query complexity $\tilde{O}(m\sqrt{n}/\varepsilon^{2.5})$. Both algorithms demonstrate a near-optimal scaling in the number of players $m$ and actions $n$, as confirmed by our quantum query lower bounds.

Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares ann-dimensional quantum state Σni=1√pi|i⟩, for α > 1 and 0Hα(p) to within additive error ϵ with probability at least 2/3 using Õ(n1-1/2α/ϵ + √n/ϵ1+ 1/2α) and Õ(n1/2α/ϵ1+ 1/2α) queries, respectively. This improves the best known dependence in ϵ as well as the joint dependence betweennand 1/ϵ. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.