2026-09-08T01:21:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26447 2026-09-05T19:44:08Z ddc:004 open_access

Quantum Multi-Level Estimation of Functionals of Discrete Distributions Chen, Kean Gao, Minbo Li, Tongyang Wang, Qisheng Wang, Xinzhao Quantum algorithms functional estimation entropy estimation query complexity Tsallis entropy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kean Chen and Minbo Gao and Tongyang Li and Qisheng Wang and Xinzhao Wang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.58 urn:nbn:de:0030-drops-264473 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.58 eng https://creativecommons.org/licenses/by/4.0/legalcode