Pith. sign in

REVIEW 2 major objections 3 minor 2 cited by

The paper proves a quantum estimator for Tsallis entropy with query complexity O(√log(1/qε)/(√q ε)) and a matching Ω(1/√qε) lower bound, and it turns the lower bound into an information-theoretic proof that approximating x^n requires degree

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-05 10:53 UTC pith:6JCDEUB5

load-bearing objection A sound and interesting paper: new optimal (up to polylog) quantum query algorithm for integer-order Tsallis entropy, plus a novel information-theoretic proof of a known monomial approximate-degree lower bound; minor typo and an over-claimed 'first' that are easy to fix. the 2 major comments →

arxiv 2509.03496 v1 pith:6JCDEUB5 submitted 2025-09-03 quant-ph cs.CCcs.ITmath.CAmath.IT

Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation

Qisheng Wang This is my paper
classification quant-ph cs.CCcs.ITmath.CAmath.IT MSC 41A1068Q1294A17 PACS 03.67.Ac03.67.-a
keywords Tsallis entropyquantum query complexityentropy estimationapproximate degreemonomial approximationquantum singular value transformationHellinger distancequantum amplitude estimation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes tight quantum query complexity for estimating the Tsallis entropy of integer orders. The author gives a quantum algorithm that, given a state-preparation circuit for a quantum state ρ, estimates S_q(ρ) to additive error ε with O(√log(1/qε)/(√q ε)) oracle queries, and proves every quantum algorithm needs Ω(1/(√q ε)) queries, leaving only a polylogarithmic gap. This is the first quantum entropy estimator claimed optimal in q and ε simultaneously; it replaces the folklore Shift-test method's O(1/ε) cost with a √q speedup. As a by-product, the lower-bound proof supplies a new information-theoretic route to a classical approximation-theory result: any polynomial approximating x^n on [-1,1] to constant error needs degree Ω(√n), previously derived analytically. The connection runs through a two-outcome hard distribution whose Hellinger distance and Tsallis-entropy gap are tuned by q and ε.

Core claim

At its center is Theorem 1.7/5.1: for every integer q≥2 and ε∈(0,1/q], with a purified query oracle for ρ, the q-Tsallis entropy S_q(ρ) can be estimated to within ε using O(√(log(1/qε))/(√q ε)) queries, and any estimator needs Ω(1/(√q ε)) queries. The upper bound comes from replacing x^{q-1} with a bounded even/odd polynomial of degree O(√(q log(1/ε))) and using quantum singular value transformation to implement p(ρ), then a Hadamard test and amplitude estimation. The lower bound uses the two distributions p_± with probabilities 1-1/q±δ and 1/q∓δ: their Tsallis entropies differ by Ω(δ) while their Hellinger distance is O(√(qδ)), so distinguishing them, and hence estimating entropy to ε=Θ(δ),

What carries the argument

The machinery is a meta-algorithm (Algorithm 1) that estimates S_q(ρ) by estimating tr(ρ^q). It block-encodes ρ with two queries, applies quantum singular-value transformation to a bounded even/odd polynomial p that approximates x^{q-1} to precision ε_poly, runs a Hadamard test to recover tr(ρ p(ρ)) ≈ tr(ρ^q), and uses quantum amplitude estimation to read off the probability. The lower bound is carried by the two-point family p_± above and a Hellinger-distance-based distribution-discrimination lower bound. The load-bearing approximation-theoretic input is the known theorem that such polynomials exist with degree O(√(q log(1/ε))) and are efficiently computable.

Load-bearing premise

Everything rests on the cited theorem that x^{q-1} has an efficiently computable bounded even/odd polynomial approximation of degree O(√(q log(1/ε))); the paper does not reprove it, and if the true degree dependence on q were worse than √q the query-optimality claim would fail.

What would settle it

Implement the estimator for q=2 on the two-outcome distributions p+=(1-1/q+δ,1/q-δ) and p-=(1-1/q-δ,1/q+δ) with ε=Θ(δ). The lower bound says distinguishing them requires Ω(1/√(qδ)) queries; a concrete algorithm that reliably distinguished them in o(1/√(qδ)) queries—or a direct measurement showing the Hellinger distance is ω(√(qδ)) while the entropy gap stays Ω(δ)—would refute the claimed optimum.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • The oracle query complexity of integer-order Tsallis entropy estimation is now Θ(1/√(qε)) up to a factor independent of q, so for fixed ε the cost drops as q grows—unlike the Shift test, whose O(1/ε) cost does not improve with q.
  • Estimating the Tsallis entropy of a probability distribution inherits the same optimal bound, since a distribution is a diagonal quantum state.
  • The monomial approximate degree has an information-theoretic proof, not just analytic ones; the proof works for every constant ε<1/(2e), a slightly wider range than the previous analytic constant.
  • The lower-bound technique—tune two distributions by q and ε so their entropy gap is large while their Hellinger distance is small—can be applied to other entropic functionals defined by tr(ρ^q).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same block-encode, approximate, QSVT, Hadamard-test template should yield optimal estimators for other spectral functionals, such as Schatten norms or Rényi entropies of integer order, whenever a matching polynomial approximation with degree O(√(q log(1/ε))) is available; the paper does not develop these cases.
  • An immediate testable question is whether the √log(1/qε) gap is real: if a sharper polynomial approximation theorem existed with degree O(√q) and the same bounded-parity guarantee, the estimator would match the lower bound exactly.
  • The lower-bound construction suggests a recipe for proving approximate-degree lower bounds for other functions: encode the function as a matrix polynomial, connect it to a quantum estimation task with a tunable hard distribution, and read off the degree from the Hellinger-distance constraint.
  • One could probe the limits of the method by asking whether the same two-distribution family can separate the quantum query complexity of Tsallis entropy from the sample complexity, since the sample-complexity lower bounds cited in the paper have a different ε dependence.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies the quantum query complexity of estimating the Tsallis entropy of integer order q ≥ 2 for quantum states and probability distributions. It presents a quantum estimator based on a block-encoding of ρ, quantum singular value transformation applied to a polynomial approximation of x^{q−1}, a Hadamard test, and quantum amplitude estimation. The claimed upper bound is O(√(log(1/qε))/(√q ε)) queries, improving the prior Shift-test-based O(1/ε). The paper also proves a matching lower bound Ω(1/(√q ε)) using a two-point hard instance and the Hellinger-distance lower bound of Belovs. Combining the meta-algorithm with this lower bound yields a new information-theoretic proof that the approximate degree of the monomial x^n on [-1,1] is Ω(√n) for constant ε < 1/(2e). The central theorems are Theorem 5.1, Theorem 5.2, and Theorem 6.3.

Significance. If the stated results hold, the paper makes a genuine contribution: it gives a query-optimal quantum estimator for integer-order Tsallis entropy, improving the quadratic dependence on q and the linear dependence on 1/ε; and it provides a conceptually new proof of a known approximate-degree lower bound by connecting quantum entropy estimation to approximation theory. The proof is modular and the bounds are explicit. The monomial lower bound itself is not new, but the information-theoretic route is novel. The paper also contains a very thorough review of classical and quantum entropy estimation. The reliance on the cited polynomial approximation theorem of Sachdeva–Vishnoi is legitimate, though the paper does not re-prove it.

major comments (2)
  1. [Theorem 5.3, Eq. (51)] The displayed Hellinger-distance bound is algebraically wrong. From Eq. (50), d_H^2 ≤ δ^2/(1−1/q) + qδ^2 = q^2δ^2/(q−1), so d_H ≤ qδ/√(q−1), not qδ√(q−1). As printed, the claimed d_H = O(√q δ) does not follow. The corrected bound is sufficient for Eq. (62), so the lower bound survives, but the equation must be fixed.
  2. [Theorem 5.3, Eqs. (56)–(60)] The equality leading to Eq. (57) is false. The j=0 term in Eq. (55) equals (2q/(q−1))[(1−1/q)^{q−1} − (1/q)^{q−1}]δ, whose limit is 2δ/e, not the displayed expression 2[(1−1/q)^q − (1−1/q)(1/q)^{q−1}]δ, whose limit is δ/e. Since the correct expression is larger, the desired lower bound H_q(p^−)−H_q(p^+) > 2tδ with t ∈ (0,1/e) still holds for sufficiently large q; however, Eqs. (56)–(60) need to be corrected and their subsequent use adjusted.
minor comments (3)
  1. [Abstract, Section 1.2, Section 1.3] The claim of being 'the first quantum entropy estimator with optimal query complexity' is overstated in view of the concurrent work [ZWZY25], which the paper itself cites and which gives the same query complexity. Please qualify the claim (e.g., 'independently' or 'one of the first').
  2. [Theorem 3.5 and Theorem 5.1] There are several typos: 'sybsystem' in Theorem 3.5, 'state-prepraration' in Theorem 5.1, and inconsistent use of tilde notation (e.g., eΘ in the abstract vs. O with explicit log). A careful proofreading pass is needed.
  3. [Theorem 6.3 and Section 1.1] The paper should state more clearly that the monomial approximate-degree lower bound is a known result and that the contribution is a new proof, not a new bound. The current wording sometimes suggests novelty of the bound itself; the distinction should be explicit.

Circularity Check

0 steps flagged

No significant circularity: the monomial lower bound follows from an independent information-theoretic query lower bound, and self-citations are contextual.

full rationale

The derivation chain is self-contained against external results. The approximate-degree lower bound (Thm 6.2/6.3) is obtained by combining Lemma 6.1, which converts any degree-d polynomial approximating x^{q-1} to a Tsallis entropy estimator with O(d/(qε)) queries (proved in full in Section 4 via QSVT, Hadamard test and amplitude estimation), with Theorem 5.3, an independent lower bound Ω(1/(√q ε)) for Tsallis entropy estimation. That lower bound is proved from the Hellinger-distance hard instance p± and the external [Bel19, Thm 4], with the entropy gap H_q(p-)-H_q(p+) and Hellinger bound computed directly in the paper. No step assumes gdeg_ε(x^n)=Ω(√n); instead the lower bound is forced by the contradiction that a small gdeg would yield an entropy estimator faster than the proven query lower bound. The entropy upper bound (Thm 5.1) relies on the external polynomial-approximation theorem [SV14, Thm 3.2], which is a known upper bound, not the target lower bound. Self-citations such as [CWYZ25] for the hard-instance idea and [LW25]/[WZ25] for context are not load-bearing: the paper re-derives the needed estimates. The footnote about non-uniformity of the best-polynomial estimator is a stated limitation, not a circular step. The minor line issue in Eq. (51) (qδ/√(q-1) vs O(√q δ)) does not affect the argument.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No free parameters are fitted to data; the algorithm's parameters ε_poly, ε_QSVT, ε_QAE are chosen symbolically to balance errors. The hard-instance constants t, γ in the lower bound are arbitrary existential constants, not fitted values. The axioms are standard QSVT and polynomial-approximation theorems from cited prior work, plus the standard existence of best approximations. No invented entities are introduced.

axioms (4)
  • standard math Existence of an even/odd best approximation polynomial with the same parity (Lemma A.1)
    Used in Lemma 6.1 to assume the best approximating polynomial of x^{q-1} is even/odd with parity (q-1) mod 2.
  • domain assumption Quantum singular value transformation for even/odd polynomials (Theorem 3.1, from [GSLW19])
    The meta-algorithm in Section 4 relies on QSVT to implement a block-encoding of p(ρ) using O(deg(p)) queries.
  • domain assumption Polynomial approximation for monomials, [SV14, Theorem 3.2]: degree O(√(q log(1/ε))) with |p| ≤ 1 and correct parity
    Yields the uniform upper bound in Theorem 5.1 and the query complexity O(√log/(√q ε)).
  • domain assumption Quantum query lower bound for distinguishing probability distributions, [Bel19, Theorem 4]: Ω(1/dH)
    Basis of the entropy lower bound in Theorem 5.3.

pith-pipeline@v1.4.0-alltime-deepseek-medium · 29367 in / 26727 out tokens · 236166 ms · 2026-08-05T10:53:19.417999+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation." pith.science (2026). https://pith.science/paper/6JCDEUB5

@misc{pith2026250903496,
  author       = {Pith},
  title        = {Pith review of: Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6JCDEUB5}},
  note         = {Machine review of arXiv:2509.03496}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

This paper reveals a conceptually new connection from information theory to approximation theory via quantum algorithms for entropy estimation. Specifically, we provide an information-theoretic lower bound $\Omega(\sqrt{n})$ on the approximate degree of the monomial $x^n$, compared to the analytic lower bounds shown in Newman and Rivlin (Aequ. Math. 1976) via Fourier analysis and in Sachdeva and Vishnoi (Found. Trends Theor. Comput. Sci. 2014) via the Markov brothers' inequality. This is done by relating the polynomial approximation of monomials to quantum Tsallis entropy estimation. This further implies a quantum algorithm that estimates to within additive error $\varepsilon$ the Tsallis entropy of integer order $q \geq 2$ of an unknown probability distribution $p$ or an unknown quantum state $\rho$, using $\widetilde \Theta(\frac{1}{\sqrt{q}\varepsilon})$ queries to the quantum oracle that produces a sample from $p$ or prepares a copy of $\rho$, improving the prior best $O(\frac{1}{\varepsilon})$ via the Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki and Kwek (Phys. Rev. Lett. 2002). To the best of our knowledge, this is the first quantum entropy estimator with optimal query complexity (up to polylogarithmic factors) for all parameters simultaneously.

Figures

Figures reproduced from arXiv: 2509.03496 by Qisheng Wang.

Figure 1
Figure 1. Figure 1: Quantum circuit for the Shift test. Fact 1.6 (Folklore quantum estimator for Tsallis entropy of integer order, implied by [EAO+02, BHMT02]). Given a unitary oracle O that prepares a quantum state ρ, for (non-constant) integer q ≥ 2, Sq(ρ) can be estimated to within additive error ε using O( 1 ε ) queries to O. The quantum estimator for Tsallis entropy in Fact 1.6 is not known to be optimal, and only a lowe… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Towards Minimax Estimation of High-Order Functionals by Quantum Arguments

    quant-ph 2026-07 accept novelty 8.0

    Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.

  2. Quantum Multi-Level Estimation of Functionals of Discrete Distributions

    quant-ph 2026-05 unverdicted novelty 7.0

    A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.

Reference graph

Works this paper leans on

133 extracted references · 36 canonical work pages · cited by 2 Pith papers · 1 internal anchor

  1. [1]

    Optimal-degree polynomial approximations for exponentials and Gaussian kernel density estimation

    Amol Aggarwal and Josh Alman. Optimal-degree polynomial approximations for exponentials and Gaussian kernel density estimation. In Proceedings of the 37th Computational Complexity Conference , pages 22:1--22:23, 2022. https://doi.org/10.4230/LIPIcs.CCC.2022.22 doi:10.4230/LIPIcs.CCC.2022.22

    work page doi:10.4230/lipics.ccc.2022.22 2022

  2. [2]

    Sample-efficient learning of interacting quantum systems

    Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. Sample-efficient learning of interacting quantum systems. Nature Physics , 17(8):931--935, 2021. https://doi.org/10.1038/s41567-021-01232-0 doi:10.1038/s41567-021-01232-0

    doi:10.1038/s41567-021-01232-0 2021

  3. [3]

    J. S. Andrade, Jr. , G. F. T. da Silva, A. A. Moreira, F. D. Nobre, and E. M. F. Curado. Thermostatistics of overdamped motion of interacting particles. Physical Review Letters , 105(26):260601, 2010. https://doi.org/10.1103/PhysRevLett.105.260601 doi:10.1103/PhysRevLett.105.260601

    work page doi:10.1103/physrevlett.105.260601 2010

  4. [4]

    Shende, and Aaron B

    Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende, and Aaron B. Wagner. Estimating quantum entropy. IEEE Journal on Selected Areas in Information Theory , 1(2):454--468, 2020. https://doi.org/10.1109/JSAIT.2020.3015235 doi:10.1109/JSAIT.2020.3015235

    arXiv 2020

  5. [5]

    A polynomial quantum algorithm for approximating the Jones polynomial

    Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica , 55(3):395--421, 2009. https://doi.org/10.1007/s00453-008-9168-0 doi:10.1007/s00453-008-9168-0

    doi:10.1007/s00453-008-9168-0 2009

  6. [6]

    Convergence properties of functional estimates for discrete distributions

    Andr \' a s Antos and Ioannis Kontoyiannis. Convergence properties of functional estimates for discrete distributions. Random Structures & Algorithms , 19(3--4):163--193, 2001. https://doi.org/10.1002/rsa.10019 doi:10.1002/rsa.10019

    doi:10.1002/rsa.10019 2001

  7. [7]

    Theory of Approximation

    Naum Il'ich Akhiezer. Theory of Approximation . Frederick Ungar Publishing Company, 1956

    1956

  8. [8]

    Variable time amplitude amplification and quantum algorithms for linear algebra problems

    Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science , pages 636--647, 2012. https://doi.org/10.4230/LIPIcs.STACS.2012.636 doi:10.4230/LIPIcs.STACS.2012.636

    doi:10.4230/lipics.stacs.2012.636 2012

  9. [9]

    Estimating Renyi entropy of discrete distributions

    Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. Estimating Renyi entropy of discrete distributions. IEEE Transactions on Information Theory , 63(1):38--56, 2017. https://doi.org/10.1109/TIT.2016.2620435 doi:10.1109/TIT.2016.2620435

    arXiv 2017

  10. [10]

    Adiabatic quantum state generation and statistical zero knowledge

    Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing , pages 20--29, 2003. https://doi.org/10.1145/780542.780546 doi:10.1145/780542.780546

    arXiv 2003

  11. [11]

    Berry, Graeme Ahokas, Richard Cleve, and Barry C

    Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians . Communications in Mathematical Physics , 270(2):359--371, 2007. https://doi.org/10.1007/s00220-006-0150-x doi:10.1007/s00220-006-0150-x

    doi:10.1007/s00220-006-0150-x 2007

  12. [12]

    Quantum expanders: motivation and construction

    Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma. Quantum expanders: motivation and construction. Theory of Computing , 6(3):47--79, 2010. https://doi.org/10.4086/toc.2010.v006a003 doi:10.4086/toc.2010.v006a003

    doi:10.4086/toc.2010.v006a003 2010

  13. [13]

    An inequality for the trace of matrix products, using absolute values

    Bernhard Baumgartner. An inequality for the trace of matrix products, using absolute values. ArXiv e-prints, 2011. https://arxiv.org/abs/1106.6189 arXiv:1106.6189

    Pith/arXiv arXiv 2011

  14. [14]

    Quantum lower bounds by polynomials

    Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM , 48(4):778--797, 2001. https://doi.org/10.1145/502090.502097 doi:10.1145/502090.502097

    arXiv 2001

  15. [15]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians . In Proceedings of the 46th Annual ACM Symposium on Theory of Computing , pages 283--292, 2014. https://doi.org/10.1145/2591796.2591854 doi:10.1145/2591796.2591854

    arXiv 2014

  16. [16]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters , 114(9):090502, 2015. https://doi.org/10.1103/PhysRevLett.114.090502 doi:10.1103/PhysRevLett.114.090502

    doi:10.1103/physrevlett.114.090502 2015

  17. [17]

    Direct measurement of nonlinear properties of bipartite quantum states

    Fabio Antonio Bovino, Giuseppe Castagnoli, Artur Ekert, Pawe Horodecki, Carolina Moura Alves, and Alexander Vladimir Sergienko. Direct measurement of nonlinear properties of bipartite quantum states. Physical Review Letters , 95(24):240407, 2005. https://doi.org/10.1103/PhysRevLett.95.240407 doi:10.1103/PhysRevLett.95.240407

    work page doi:10.1103/physrevlett.95.240407 2005

  18. [18]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science , pages 792--809, 2015. https://doi.org/10.1109/FOCS.2015.54 doi:10.1109/FOCS.2015.54

    doi:10.1109/focs.2015.54 2015

  19. [19]

    Quantum fingerprinting

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters , 87(16):167902, 2001. https://doi.org/10.1103/PhysRevLett.87.167902 doi:10.1103/PhysRevLett.87.167902

    doi:10.1103/physrevlett.87.167902 2001

  20. [20]

    Classical lower bounds from quantum upper bounds

    Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari. Classical lower bounds from quantum upper bounds. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science , pages 339--349, 2018. https://doi.org/10.1109/FOCS.2018.00040 doi:10.1109/FOCS.2018.00040

    arXiv 2018

  21. [21]

    The complexity of approximating the entropy

    Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity of approximating the entropy. SIAM Journal on Computing , 35(1):132--150, 2005. https://doi.org/10.1137/S0097539702403645 doi:10.1137/S0097539702403645

    doi:10.1137/s0097539702403645 2005

  22. [22]

    Quantum algorithms for classical probability distributions

    Aleksandrs Belovs. Quantum algorithms for classical probability distributions. In Proceedings of the 27th Annual European Symposium on Algorithms , pages 16:1--16:11, 2019. https://doi.org/10.4230/LIPIcs.ESA.2019.16 doi:10.4230/LIPIcs.ESA.2019.16

    doi:10.4230/lipics.esa.2019.16 2019

  23. [23]

    Sur la meilleure approximation de |x| par des polynomes de degr \'e s donn \'e s

    Serge Bernstein. Sur la meilleure approximation de |x| par des polynomes de degr \'e s donn \'e s. Acta Mathematica , 37(1):1--57, 1914. https://doi.org/10.1007/BF02401828 doi:10.1007/BF02401828

    work page doi:10.1007/bf02401828 1914

  24. [24]

    Sur la meilleure approximation de |x|^p par des polynômes de degrés très élevés

    Serge Bernstein. Sur la meilleure approximation de |x|^p par des polynômes de degrés très élevés. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya , 2(2):169--190, 1938. URL: https://www.mathnet.ru/eng/im3513

    1938

  25. [25]

    S. N. Bernstein. The constructive theory of functions (1905--1930). In Collected Works , volume 1. Atomic Energy Commission, 1958

    1905

  26. [26]

    Friedman, Richard A

    Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees . Chapman & Hall/CRC, 1 edition, 1984. https://doi.org/10.1201/9781315139470 doi:10.1201/9781315139470

    doi:10.1201/9781315139470 1984

  27. [27]

    Harrow, and Avinatan Hassidim

    Sergey Bravyi, Aram W. Harrow, and Avinatan Hassidim. Quantum algorithms for testing properties of distributions. IEEE Transactions on Information Theory , 57(6):3971--3981, 2011. https://doi.org/10.1109/TIT.2011.2134250 doi:10.1109/TIT.2011.2134250

    arXiv 2011

  28. [28]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information , volume 305 of Contemporary Mathematics , pages 53--74. AMS, 2002. https://doi.org/10.1090/conm/305/05215 doi:10.1090/conm/305/05215

    doi:10.1090/conm/305/05215 2002

  29. [29]

    The polynomial method strikes back: tight quantum query bounds via dual polynomials

    Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: tight quantum query bounds via dual polynomials. Theory of Computing , 16(10):1--71, 2020. https://doi.org/10.4086/toc.2020.v016a010 doi:10.4086/toc.2020.v016a010

    doi:10.4086/toc.2020.v016a010 2020

  30. [30]

    Learning entropy

    Mohammad Bavarian, Saeed Mehraban, and John Wright. Learning entropy. A manuscript on von Neumann entropy estimation, private communication, 2016

    2016

  31. [31]

    Peter B. Borwein. Approximation of x^n by reciprocals of polynomials. Journal of Approximation Theory , 32(3):241--246, 1981. https://doi.org/10.1016/0021-9045(81)90119-2 doi:10.1016/0021-9045(81)90119-2

    work page doi:10.1016/0021-9045(81)90119-2 1981

  32. [32]

    Todd A. Bruni. Measurimg polynomial functions of states. Quantum Information and Computation , 4(5):401--408, 2004. https://doi.org/10.26421/QIC4.5-6 doi:10.26421/QIC4.5-6

    work page doi:10.26421/qic4.5-6 2004

  33. [33]

    Approximate degree in classical and quantum computing

    Mark Bun and Justin Thaler. Approximate degree in classical and quantum computing. Foundations and Trends in Theoretical Computer Science , 15(3--5):229--423, 2022. https://doi.org/10.1561/0400000107 doi:10.1561/0400000107

    doi:10.1561/0400000107 2022

  34. [34]

    Algebraic Approximation: A Guide to Past and Current Solutions

    Jorge Bustamante. Algebraic Approximation: A Guide to Past and Current Solutions . Frontiers in Mathematics. Birkh \" a user Basel, 2012. https://doi.org/10.1007/978-3-0348-0194-2 doi:10.1007/978-3-0348-0194-2

    work page doi:10.1007/978-3-0348-0194-2 2012

  35. [35]

    The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation

    Shantanav Chakraborty, Andr\' a s Gily\' e n, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming , pages 33:1--33:14, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.33 doi:10.4230/LIPIcs....

    doi:10.4230/lipics.icalp.2019.33 2019

  36. [36]

    Canonne, Robin Kothari, and Ryan O'Donnell

    Cl \'e ment L. Canonne, Robin Kothari, and Ryan O'Donnell. Uniformity testing when you have the source code. ArXiv e-prints, 2024. https://arxiv.org/abs/2411.04972 arXiv:2411.04972

    Pith/arXiv arXiv 2024

  37. [37]

    Childs, Robin Kothari, and Rolando D

    Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing , 46(6):1920--1950, 2017. https://doi.org/10.1137/16M1087072 doi:10.1137/16M1087072

    doi:10.1137/16m1087072 1920

  38. [38]

    Chowdhury, Guang Hao Low, and Nathan Wiebe

    Anirban N. Chowdhury, Guang Hao Low, and Nathan Wiebe. A variational quantum algorithm for preparing quantum Gibbs states. ArXiv e-prints, 2020. https://arxiv.org/abs/2002.00055 arXiv:2002.00055

    Pith/arXiv arXiv 2020

  39. [39]

    W. J. Cody. A survey of practical rational and polynomial approximation of functions. SIAM Review , 12(3):400--423, 1970. https://doi.org/10.1137/1012082 doi:10.1137/1012082

    work page doi:10.1137/1012082 1970

  40. [40]

    Childs and Nathan Wiebe

    Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation , 12(11--12):901--924, 2012. https://doi.org/10.26421/QIC12.11-12-1 doi:10.26421/QIC12.11-12-1

    doi:10.26421/qic12.11-12-1 2012

  41. [41]

    Improved sample upper and lower bounds for trace estimation of quantum state powers

    Kean Chen and Qisheng Wang. Improved sample upper and lower bounds for trace estimation of quantum state powers. In Proceedings of the 38th Conference on Learning Theory , pages 1008--1028, 2025. URL: https://proceedings.mlr.press/v291/chen25d.html

    2025

  42. [42]

    Unitarity estimation for quantum channels

    Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying. Unitarity estimation for quantum channels. IEEE Transactions on Information Theory , 69(8):5116--5134, 2023. https://doi.org/10.1109/TIT.2023.3263645 doi:10.1109/TIT.2023.3263645

    arXiv 2023

  43. [43]

    Simultaneous estimation of nonlinear functionals of a quantum state

    Kean Chen, Qisheng Wang, Zhan Yu, and Zhicheng Zhang. Simultaneous estimation of nonlinear functionals of a quantum state. ArXiv e-prints, 2025. https://arxiv.org/abs/2505.16715 arXiv:2505.16715

    Pith/arXiv arXiv 2025

  44. [44]

    Ekert, Carolina Moura Alves, Daniel K

    Artur K. Ekert, Carolina Moura Alves, Daniel K. L. Oi, Micha Horodecki, Pawe Horodecki, and L. C. Kwek. Direct estimations of linear and nonlinear functionals of a quantum state. Physical Review Letters , 88(21):217901, 2002. https://doi.org/10.1103/PhysRevLett.88.217901 doi:10.1103/PhysRevLett.88.217901

    doi:10.1103/physrevlett.88.217901 2002

  45. [45]

    Uniform approximation of sgn x by polynomials and entire functions

    Alexandre Eremenko and Peter Yuditskii. Uniform approximation of sgn x by polynomials and entire functions. Journal d'Analyse Math \' e matique , 101(1):313--324, 2007. https://doi.org/10.1007/s11854-007-0011-3 doi:10.1007/s11854-007-0011-3

    work page doi:10.1007/s11854-007-0011-3 2007

  46. [46]

    Franchini, A

    F. Franchini, A. R. Its, and V. E. Korepin. Renyi entropy of the XY spin chain. Journal of Physics A: Mathematical and Theoretical , 41(2):025302, 2008. https://doi.org/10.1088/1751-8113/41/2/025302 doi:10.1088/1751-8113/41/2/025302

    work page doi:10.1088/1751-8113/41/2/025302 2008

  47. [47]

    Ganelius

    T. Ganelius. Rational approximation to x^ on [0, 1] . Analysis Mathematica , 5(1):19--33, 1979. https://doi.org/10.1007/BF02079347 doi:10.1007/BF02079347

    work page doi:10.1007/bf02079347 1979

  48. [48]

    Alexandru Gheorghiu and Matty J. Hoban. Estimating the entropy of shallow circuit outputs is hard. ArXiv e-prints, 2020. https://arxiv.org/abs/2002.12814 arXiv:2002.12814

    Pith/arXiv arXiv 2020

  49. [49]

    Sublinear quantum algorithms for estimating von Neumann entropy

    Tom Gur, Min-Hsiu Hsieh, and Sathyawageeswar Subramanian. Sublinear quantum algorithms for estimating von Neumann entropy. ArXiv e-prints, 2021. https://arxiv.org/abs/2111.11139 arXiv:2111.11139

    Pith/arXiv arXiv 2021

  50. [50]

    On the sample complexity of purity and inner product estimation

    Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. ArXiv e-prints, 2024. https://arxiv.org/abs/2410.12712 arXiv:2410.12712

    Pith/arXiv arXiv 2024

  51. [51]

    Quantum Singular Value Transformation & Its Algorithmic Applications

    Andr\' a s Gily\' e n. Quantum Singular Value Transformation & Its Algorithmic Applications . Phd dissertation, University of Amsterdam, 2019. URL: https://pure.uva.nl/ws/files/35292358/Thesis.pdf

    arXiv 2019

  52. [52]

    Variabilit \`a e Mutabilit \`a : contributo allo studio delle distribuzioni e delle relazioni statistiche

    Corrado Gini. Variabilit \`a e Mutabilit \`a : contributo allo studio delle distribuzioni e delle relazioni statistiche . Tipografia di Paolo Cuppin, 1912. URL: https://www.byterfly.eu/islandora/object/librib:680892

    1912

  53. [53]

    Distributional property testing in a quantum world

    Andr \'a s Gily \'e n and Tongyang Li. Distributional property testing in a quantum world. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference , pages 25:1--25:19, 2020. https://doi.org/10.4230/LIPIcs.ITCS.2020.25 doi:10.4230/LIPIcs.ITCS.2020.25

    doi:10.4230/lipics.itcs.2020.25 2020

  54. [54]

    Andr \' a s Gily \' e n, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M. Wilde. Quantum algorithm for Petz recovery channels and pretty good measurements. Physical Review Letters , 128(22):220502, 2022. https://doi.org/10.1103/PhysRevLett.128.220502 doi:10.1103/PhysRevLett.128.220502

    work page doi:10.1103/physrevlett.128.220502 2022

  55. [55]

    Improved quantum algorithms for fidelity estimation

    Andr\' a s Gily\' e n and Alexander Poremba. Improved quantum algorithms for fidelity estimation. ArXiv e-prints, 2022. https://arxiv.org/abs/2203.15993 arXiv:2203.15993

    Pith/arXiv arXiv 2022

  56. [56]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    Andr\' a s Gily\' e n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 193--204, 2019. https://doi.org/10.1145/3313276.3316366 doi:10.1145/3313276.3316366

    arXiv 2019

  57. [57]

    Hastings, Iv \' a n Gonz \' a lez, Ann B

    Matthew B. Hastings, Iv \' a n Gonz \' a lez, Ann B. Kallin, and Roger G. Melko. Measuring Renyi entanglement entropy in quantum Monte Carlo simulations. Physical Review Letters , 104(15):157201, 2010. https://doi.org/10.1103/PhysRevLett.104.157201 doi:10.1103/PhysRevLett.104.157201

    doi:10.1103/physrevlett.104.157201 2010

  58. [58]

    Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu

    Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory , 63(9):5628--5641, 2017. https://doi.org/10.1109/TIT.2017.2719044 doi:10.1109/TIT.2017.2719044

    arXiv 2017

  59. [59]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters , 103(15):150502, 2009. https://doi.org/10.1103/PhysRevLett.103.150502 doi:10.1103/PhysRevLett.103.150502

    doi:10.1103/physrevlett.103.150502 2009

  60. [60]

    On Krylov subspace approximations to the matrix exponential operator

    Marlis Hochbruck and Christian Lubich. On Krylov subspace approximations to the matrix exponential operator. SIAM Journal on Numerical Analysis , 34(5):1911--1925, 1997. https://doi.org/10.1137/S0036142995280572 doi:10.1137/S0036142995280572

    doi:10.1137/s0036142995280572 1911

  61. [61]

    Quantum Chebyshev's inequality and applications

    Yassine Hamoudi and Fr \'e d \'e ric Magniez. Quantum Chebyshev's inequality and applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming , pages 69:1--69:16, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.69 doi:10.4230/LIPIcs.ICALP.2019.69

    doi:10.4230/lipics.icalp.2019.69 2019

  62. [62]

    Preiss, M

    Rajibul Islam, Ruichao Ma, Philipp M. Preiss, M. Eric Tai, Alexander Lukin, Matthew Rispoli, and Markus Greiner. Measuring entanglement entropy in a quantum many-body system. Nature , 528(7580):77--83, 2015. https://doi.org/10.1038/nature15750 doi:10.1038/nature15750

    doi:10.1038/nature15750 2015

  63. [63]

    Steiger, and Matthias Troyer

    Sonika Johri, Damian S. Steiger, and Matthias Troyer. Entanglement spectroscopy on a quantum computer. Physical Review B , 96(19):195136, 2017. https://doi.org/10.1103/PhysRevB.96.195136 doi:10.1103/PhysRevB.96.195136

    doi:10.1103/physrevb.96.195136 2017

  64. [64]

    Minimax estimation of functionals of discrete distributions

    Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Transactions on Information Theory , 61(5):2835--2885, 2015. https://doi.org/10.1109/TIT.2015.2412945 doi:10.1109/TIT.2015.2412945

    arXiv 2015

  65. [65]

    Maximum likelihood estimation of functionals of discrete distributions

    Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Maximum likelihood estimation of functionals of discrete distributions. IEEE Transactions on Information Theory , 63(10):6774--6798, 2017. https://doi.org/10.1109/TIT.2017.2733537 doi:10.1109/TIT.2017.2733537

    arXiv 2017

  66. [66]

    Randomized linear algebra approaches to estimate the von Neumann entropy of density matrices

    Eugenia-Maria Kontopoulou, Gregory-Paul Dexter, Wojciech Szpankowski, Ananth Grama, and Petros Drineas. Randomized linear algebra approaches to estimate the von Neumann entropy of density matrices. IEEE Transactions on Information Theory , 66(8):5003--5021, 2020. https://doi.org/10.1109/TIT.2020.2971991 doi:10.1109/TIT.2020.2971991

    arXiv 2020

  67. [67]

    Quantum lower bound for the collision problem with small range

    Samuel Kutin. Quantum lower bound for the collision problem with small range. Theory of Computing , 1(2):29--36, 2005. https://doi.org/10.4086/toc.2005.v001a002 doi:10.4086/toc.2005.v001a002

    work page doi:10.4086/toc.2005.v001a002 2005

  68. [68]

    Applied Analysis

    Cornelius Lanczos. Applied Analysis . Prentice Hall, 1956

    1956

  69. [69]

    Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification. ArXiv e-prints, 2017. https://arxiv.org/abs/1707.05391 arXiv:1707.05391

    Pith/arXiv arXiv 2017

  70. [70]

    Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum , 3:163, 2019. https://doi.org/10.22331/q-2019-07-12-163 doi:10.22331/q-2019-07-12-163

    doi:10.22331/q-2019-07-12-163 2019

  71. [71]

    Space-bounded quantum state testing via space-efficient quantum singular value transformation

    Fran c ois Le Gall, Yupan Liu, and Qisheng Wang. Space-bounded quantum state testing via space-efficient quantum singular value transformation. ArXiv e-prints, 2023. https://arxiv.org/abs/2308.05079 arXiv:2308.05079

    Pith/arXiv arXiv 2023

  72. [72]

    Data streaming algorithms for estimating entropy of network traffic

    Ashwin Lall, Vyas Sekar, Mitsunori Ogihara, Jun Xu, and Hui Zhang. Data streaming algorithms for estimating entropy of network traffic. ACM SIGMETRICS Performance Evaluation Review , 34(1):145--156, 2006. https://doi.org/10.1145/1140103.1140295 doi:10.1145/1140103.1140295

    arXiv 2006

  73. [73]

    M. L. Lyra and C. Tsallis. Nonextensivity and multifractality in low-dimensional dissipative systems. Physical Review Letters , 81(1):53, 1998. https://doi.org/10.1103/PhysRevLett.80.53 doi:10.1103/PhysRevLett.80.53

    work page doi:10.1103/physrevlett.80.53 1998

  74. [74]

    Quantum query complexity of entropy estimation

    Tongyang Li and Xiaodi Wu. Quantum query complexity of entropy estimation. IEEE Transactions on Information Theory , 65(5):2899--2921, 2019. https://doi.org/10.1109/TIT.2018.2883306 doi:10.1109/TIT.2018.2883306

    arXiv 2019

  75. [75]

    On estimating the trace of quantum state powers

    Yupan Liu and Qisheng Wang. On estimating the trace of quantum state powers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 947--993, 2025. https://doi.org/10.1137/1.9781611978322.28 doi:10.1137/1.9781611978322.28

    doi:10.1137/1.9781611978322.28 2025

  76. [76]

    Succinct quantum testers for closeness and k -wise uniformity of probability distributions

    Jingquan Luo, Qisheng Wang, and Lvzhou Li. Succinct quantum testers for closeness and k -wise uniformity of probability distributions. IEEE Transactions on Information Theory , 70(7):5092--5103, 2024. https://doi.org/10.1109/TIT.2024.3393756 doi:10.1109/TIT.2024.3393756

    arXiv 2024

  77. [77]

    Wilde, and Zhicheng Zhang

    Nana Liu, Qisheng Wang, Mark M. Wilde, and Zhicheng Zhang. Quantum algorithms for matrix geometric means. npj Quantum Information , 11:101, 2025. https://doi.org/10.1038/s41534-025-00973-7 doi:10.1038/s41534-025-00973-7

    doi:10.1038/s41534-025-00973-7 2025

  78. [78]

    A. Markov. Ob odnom voproce d. i. mendeleeva. Zapiski Imperatorskoi Akademii Nauk SP6 , 62:1--24, 1890. URL: https://history-of-approximation-theory.com/fpapers/mar1.pdf. English version: https://history-of-approximation-theory.com/fpapers/markov4.pdf

  79. [79]

    U ber Polynome, die in einem gegebenen Intervalle m\

    Vladimir Markov. O funktsiyakh, naimeneye uklonyayushchikhsya ot nulya v dannom promezhutke, 1892. URL: https://history-of-approximation-theory.com/fpapers/vmar.pdf. German version: Markoff, Wladimir. \" U ber Polynome, die in einem gegebenen Intervalle m\" o glichst wenig von Null abweichen. Mathematische Annalen, 77:213--258, 1916. https://doi.org/10.10...

    work page doi:10.1007/bf01456902 1916

  80. [80]

    Quantum and classical query complexities of functions of matrices

    Ashley Montanaro and Changpeng Shao. Quantum and classical query complexities of functions of matrices. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 573--584, 2024. https://doi.org/10.1145/3618260.3649665 doi:10.1145/3618260.3649665

    arXiv 2024

Showing first 80 references.