{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiddaynd4py2p2gaezwwp3wbvqdkwo3v3nz6cywdzun5pai3mnqp5y",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3ml62vpatz6b2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.03685v1",
  "publishedAt": "2026-05-06T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Kean Chen",
    "Minbo Gao",
    "Tongyang Li",
    "Qisheng Wang",
    "Xinzhao Wang"
  ],
  "textContent": "**Authors:** Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang\n\nWe propose a quantum multi-level estimation framework for a functional $\\sum_{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: (i) For $q > 1$, we obtain a near-optimal quantum algorithm with query complexity $\\tildeΘ(1/\\varepsilon^{\\max\\\\{1/(2(q-1)), 1\\\\}})$, improving the prior best $O(1/\\varepsilon^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0 < q < 1$, we obtain a quantum algorithm with query complexity $\\tilde{O}(n^{1/q-1/2}/\\varepsilon^{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$.",
  "title": "Quantum Multi-Level Estimation of Functionals of Discrete Distributions"
}