Search Results

Documents authored by Wang, Xinzhao

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.58
Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Authors: Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, and Xinzhao Wang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
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.
Cite as

Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, and Xinzhao Wang. Quantum Multi-Level Estimation of Functionals of Discrete Distributions. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.58,
  author =	{Chen, Kean and Gao, Minbo and Li, Tongyang and Wang, Qisheng and Wang, Xinzhao},
  title =	{{Quantum Multi-Level Estimation of Functionals of Discrete Distributions}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{58:1--58:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.58},
  URN =		{urn:nbn:de:0030-drops-264473},
  doi =		{10.4230/LIPIcs.ICALP.2026.58},
  annote =	{Keywords: Quantum algorithms, functional estimation, entropy estimation, query complexity, Tsallis entropy}
}
Document
DOI: 10.4230/LIPIcs.TQC.2024.9
Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits

Authors: Jiachen Hu, Tongyang Li, Xinzhao Wang, Yecheng Xue, Chenyi Zhang, and Han Zhong

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract
We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μ, where the samples come from different random variables with mean close to μ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.
Cite as

Jiachen Hu, Tongyang Li, Xinzhao Wang, Yecheng Xue, Chenyi Zhang, and Han Zhong. Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.TQC.2024.9,
  author =	{Hu, Jiachen and Li, Tongyang and Wang, Xinzhao and Xue, Yecheng and Zhang, Chenyi and Zhong, Han},
  title =	{{Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.9},
  URN =		{urn:nbn:de:0030-drops-206791},
  doi =		{10.4230/LIPIcs.TQC.2024.9},
  annote =	{Keywords: Quantum algorithms, Mean estimation, Non-identical samples, Query complexity}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact