Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

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

T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read 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

desk verdict 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. read the letter →

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

Qisheng Wang This is my paper
classification quant-phcs.CCcs.ITmath.CAmath.IT MSC 41A1068Q1294A17 PACS 03.67.Ac03.67.-a
keywords TsallisentropyquantumquerycomplexityestimationapproximatedegreemonomialapproximationsingularvaluetransformationHellingerdistanceamplitude
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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 ε.

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.

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

Extended reading notes

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 ε=Θ(δ),

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.

Editorial extensions

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).

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, 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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 4 assumptions · 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.

assumptions (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.

how reviews work

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}
}
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 the authors.

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 lower bound of… view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

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

    quant-ph 2026-07 accept novelty 8.0 of 10

    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.

Reference graph

Works this paper leans on

133 extracted references · 36 canonical work pages · cited by 1 Pith paper

  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

Show all 133 references
  1. [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

    2017

  2. [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

    2003

  3. [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

    2007 doi

  4. [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

    2010 doi

  5. [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

    2011 arXiv

  6. [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

    2001

  7. [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.1...

    2014

  8. [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

    2015 doi

  9. [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/PhysRe...

    2005 doi

  10. [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:...

    2015 doi

  11. [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

    2001 doi

  12. [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

  13. [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

    2005 doi

  14. [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

    2019 doi

  15. [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

    1914 doi

  16. [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

  17. [25]

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

    1905

  18. [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

    1984 doi

  19. [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

    2011

  20. [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:...

    2002 doi

  21. [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

    2020 doi

  22. [30]

    Learning entropy

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

    2016

  23. [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

    1981 doi

  24. [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

    2004 doi

  25. [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

    2022 doi

  26. [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

    2012 doi

  27. [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:...

    2019 doi

  28. [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

    2024 arXiv

  29. [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

    1920 doi

  30. [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

    2020 arXiv

  31. [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

    1970 doi

  32. [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

    2012 doi

  33. [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

  34. [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

    2023

  35. [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

    2025 arXiv

  36. [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:1...

    2002 doi

  37. [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

    2007 doi

  38. [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

    2008 doi

  39. [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

    1979 doi

  40. [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

    2020 arXiv

  41. [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

    2021 arXiv

  42. [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

    2024 arXiv

  43. [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

    2019

  44. [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

  45. [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

    2020 doi

  46. [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.1...

    2022 doi

  47. [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

    2022 arXiv

  48. [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. htt...

    2019

  49. [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

    2010 doi

  50. [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

    2017

  51. [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

    2009 doi

  52. [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

    1911 doi

  53. [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...

    2019 doi

  54. [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

    2015 doi

  55. [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

    2017 doi

  56. [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

    2015

  57. [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

    2017

  58. [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.o...

    2020

  59. [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

    2005 doi

  60. [68]

    Applied Analysis

    Cornelius Lanczos. Applied Analysis . Prentice Hall, 1956

    1956

  61. [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

    2017 arXiv

  62. [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

    2019 doi

  63. [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

    2023 arXiv

  64. [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

    2006

  65. [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

    1998 doi

  66. [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

    2019

  67. [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

    2025 doi

  68. [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

    2024

  69. [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

    2025 doi

  70. [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

  71. [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...

    1916 doi

  72. [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

    2024

  73. [81]

    Entropy and information in neural spike trains: progress on the sampling problem

    Ilya Nemenman, William Bialek, and Rob de Ruyter van Steveninck. Entropy and information in neural spike trains: progress on the sampling problem. Physical Review E , 69(5):056111, 2004. https://doi.org/10.1103/PhysRevE.69.056111 doi:10.1103/PhysRevE.69.056111

    2004 doi

  74. [82]

    Donald J. Newman. Approximation to x^n by lower degree rational functions. Journal of Approximation Theory , 27(3):236--238, 1979. https://doi.org/10.1016/0021-9045(79)90104-7 doi:10.1016/0021-9045(79)90104-7

    1979 doi

  75. [83]

    D. J. Newman and T. J. Rivlin. Approximation of monomials by lower degree polynomials. Aequationes Mathematicae , 14(3):451--455, 1976. https://doi.org/10.1007/BF01835995 doi:10.1007/BF01835995

    1976 doi

  76. [84]

    Newman and A

    Donald J. Newman and A. R. Reddy. Rational approximation to x^n . Pacific Journal of Mathematics , 67(1):247--250, 1976. https://doi.org/10.2140/pjm.1976.67.247 doi:10.2140/pjm.1976.67.247

    1976 doi

  77. [85]

    Newman and A

    Donald J. Newman and A. R. Reddy. Rational approximation to x^n II . Canadian Journal of Mathematics , 32(2):310--316, 1980. https://doi.org/10.4153/CJM-1980-023-9 doi:10.4153/CJM-1980-023-9

    1980 doi

  78. [86]

    Trefethen

    Yuji Nakatsukasa and Lloyd N. Trefethen. Rational approximation of x^n . Proceedings of the American Mathematical Society , 146(12):5219--5224, 2018. https://doi.org/10.1090/proc/14187 doi:10.1090/proc/14187

    2018 doi

  79. [87]

    Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the Lanczos method and an O(m) -time spectral algorithm for balanced separator. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing , pages 1141--1160, 2012. https://...

    2012

  80. [88]

    Efficient quantum tomography

    Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages 899--912, 2016. https://doi.org/10.1145/2897518.2897544 doi:10.1145/2897518.2897544

    2016

  81. [89]

    Efficient quantum tomography II

    Ryan O'Donnell and John Wright. Efficient quantum tomography II . In Proceedings of the 49th Annual ACM Symposium on Theory of Computing , pages 962--974, 2017. https://doi.org/10.1145/3055399.3055454 doi:10.1145/3055399.3055454

    2017

  82. [90]

    Quantum spectrum testing

    Ryan O'Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics , 387(1):1--75, 2021. https://doi.org/10.1007/s00220-021-04180-1 doi:10.1007/s00220-021-04180-1

    2021 doi

  83. [91]

    Estimation of entropy and mutual information

    Liam Paninski. Estimation of entropy and mutual information. Neural Computation , 15(6):1191--1253, 2003. https://doi.org/10.1162/089976603321780272 doi:10.1162/089976603321780272

    2003 doi

  84. [92]

    Estimating entropy on m bins given fewer than m samples

    Liam Paninski. Estimating entropy on m bins given fewer than m samples. IEEE Transactions on Information Theory , 50(9):2200--2203, 2004. https://doi.org/10.1109/TIT.2004.833360 doi:10.1109/TIT.2004.833360

    2004

  85. [93]

    Yihui Quek, Eneet Kaur, and Mark M. Wilde. Multivariate trace estimation in constant quantum depth. Quantum , 8:1220, 2024. https://doi.org/10.22331/Q-2024-01-10-1220 doi:10.22331/Q-2024-01-10-1220

    2024 doi

  86. [94]

    Soorya Rethinasamy, Rochisha Agarwal, Kunal Sharma, and Mark M. Wilde. Estimating distinguishability measures on quantum computers. Physical Review A , 108(1):012409, 2023. https://doi.org/10.1103/PhysRevA.108.012409 doi:10.1103/PhysRevA.108.012409

    2023 doi

  87. [95]

    A. R. Reddy. On certain problems of Chebyshev , Zolotarev , Bernstein and Akhieser . Inventiones mathematicae , 45(1):83--110, 1978. https://doi.org/10.1007/BF01406225 doi:10.1007/BF01406225

    1978 doi

  88. [96]

    A. R. Reddy. Approximations to x^n and |x| ---a survey. Journal of Approximation Theory , 51(2):127--137, 1987. https://doi.org/10.1016/0021-9045(87)90027-X doi:10.1016/0021-9045(87)90027-X

    1987 doi

  89. [97]

    On measures of entropy and information

    Alfr \' e d R \' e nyi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematics, Statistics and Probability , pages 547--562, 1961. URL: https://static.renyi.hu/renyi_cikkek/1961_on_measures_of_entropy_and_information.pdf

    1961

  90. [98]

    R. D. Riess and L. W. Johnson. Estimates for E_n(x^ n+2m ) . Aequationes Mathematicae , 8(3):258--262, 1972. https://doi.org/10.1007/BF01844499 doi:10.1007/BF01844499

    1972 doi

  91. [99]

    Principles of Mathematical Analysis

    Walter Rudin. Principles of Mathematical Analysis . International Series in Pure and Applied Mathematics. McGraw Hill, 1976

    1976

  92. [100]

    Yi g it Suba s ı, Lukasz Cincio, and Patrick J. Coles. Entanglement spectroscopy with a depth-two quantum circuit. Journal of Physics A: Mathematical and Theoretical , 52(4):044001, 2019. https://doi.org/10.1088/1751-8121/aaf54d doi:10.1088/1751-8121/aaf54d

    2019 doi

  93. [101]

    Shenkin, Batu Erman, and Lucy D

    Peter S. Shenkin, Batu Erman, and Lucy D. Mastrandrea. Information-theoretical entropy as a measure of sequence variability. Proteins: Structure, Function, and Bioinformatics , 11(4):297--313, 1991. https://doi.org/10.1002/prot.340110408 doi:10.1002/prot.340110408

    1991 doi

  94. [102]

    Quantum algorithm for estimating -renyi entropies of quantum states

    Sathyawageeswar Subramanian and Min-Hsiu Hsieh. Quantum algorithm for estimating -renyi entropies of quantum states. Physical Review A , 104(2):022428, 2021. https://doi.org/10.1103/PhysRevA.104.022428 doi:10.1103/PhysRevA.104.022428

    2021 doi

  95. [104]

    C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal , 27(4):623--656, 1948. https://doi.org/10.1002/j.1538-7305.1948.tb00917.x doi:10.1002/j.1538-7305.1948.tb00917.x

    1948

  96. [105]

    Resource-efficient algorithm for estimating the trace of quantum state powers

    Myeongjin Shin, Junseo Lee, Seungwoo Lee, and Kabgyun Jeong. Resource-efficient algorithm for estimating the trace of quantum state powers. Quantum , 9:1832, 2025. https://doi.org/10.22331/q-2025-08-27-1832 doi:10.22331/q-2025-08-27-1832

    2025 doi

  97. [106]

    Herbert R. Stahl. Best uniform rational approximation of x^ on [0, 1] . Acta Mathematica , 190(2):241--306, 2003. https://doi.org/10.1007/BF02392691 doi:10.1007/BF02392691

    2003 doi

  98. [107]

    Sushant Sachdeva and Nisheeth K. Vishnoi. Faster algorithms via approximation theory. Foundations and Trends in Theoretical Computer Science , 9(2):125--210, 2014. https://doi.org/10.1561/0400000065 doi:10.1561/0400000065

    2014 doi

  99. [108]

    Unitary property testing lower bounds by polynomials

    Adrian She and Henry Yuen. Unitary property testing lower bounds by polynomials. In Proceedings of the 14th Innovations in Theoretical Computer Science Conference , pages 96:1--96:17, 2023. https://doi.org/10.4230/LIPIcs.ITCS.2023.96 doi:10.4230/LIPIcs.ITCS.2023.96

    2023 doi

  100. [109]

    Aleksandr F. Timan. Theory of Approximation of Functions of a Real Variable , volume 34 of International Series of Monographs on Pure and Applied Mathematics . Pergamon Press, 1963. https://doi.org/10.1016/c2013-0-05307-8 doi:10.1016/c2013-0-05307-8

    1963 doi

  101. [110]

    Trefethen

    Lloyd N. Trefethen. Approximation Theory and Approximation Practice . Other Titles in Applied Mathematics. SIAM, extended edition, 2019. https://doi.org/10.1137/1.9781611975949 doi:10.1137/1.9781611975949

    2019 doi

  102. [111]

    Possible generalization of Boltzmann-Gibbs statistics

    Constantino Tsallis. Possible generalization of Boltzmann-Gibbs statistics. Journal of Statistical Physics , 52:479--487, 1988. https://doi.org/10.1007/BF01016429 doi:10.1007/BF01016429

    1988 doi

  103. [112]

    C. Tsallis. I. nonextensive statistical mechanics and thermodynamics: Historical background and present status. In Sumiyoshi Abe and Yuko Okamoto, editors, Nonextensive Statistical Mechanics and Its Applications , volume 560 of Lecture Notes in Physics , pages 3--98. Springer,...

    2001 doi

  104. [113]

    Quantum SDP -solvers: Better upper and lower bounds

    Joran van Apeldoorn, Andr\' a s Gily\' e n, Sander Gribling, and Ronald de Wolf. Quantum SDP -solvers: Better upper and lower bounds. Quantum , 4:230, 2020. https://doi.org/10.22331/q-2020-02-14-230 doi:10.22331/q-2020-02-14-230

    2020 doi

  105. [114]

    Testing symmetric properties of distributions

    Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing , 40(6):1927--1968, 2011. https://doi.org/10.1137/080734066 doi:10.1137/080734066

    1927 doi

  106. [115]

    S. J. van Enk and C. W. J. Beenakker. Measuring Tr ( ^n) on single copies of using random measurements. Physical Review Letters , 108(11):110503, 2012. https://doi.org/10.1103/PhysRevLett.108.110503 doi:10.1103/PhysRevLett.108.110503

    2012 doi

  107. [116]

    J. v. Neumann. Thermodynamik quantummechanischer gesamheiten. Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse , 1927:273--291, 1927. URL: http://eudml.org/doc/59231

    1927

  108. [117]

    Mathematische Grundlagen der Quantenmechanik

    John von Neumann. Mathematische Grundlagen der Quantenmechanik . Springer, 1932. URL: http://eudml.org/doc/203794

    1932

  109. [118]

    Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs

    Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs . In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing , pages 685--694, 2011. https://doi.org/10.1145/1993636.19937...

    2011

  110. [119]

    The power of linear estimators

    Gregory Valiant and Paul Valiant. The power of linear estimators. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science , pages 403--412, 2011. https://doi.org/10.1109/FOCS.2011.81 doi:10.1109/FOCS.2011.81

    2011 doi

  111. [120]

    Estimating the unseen: improved estimators for entropy and other properties

    Gregory Valiant and Paul Valiant. Estimating the unseen: improved estimators for entropy and other properties. Journal of the ACM , 64(6):37:1--37:41, 2017. https://doi.org/10.1145/3125643 doi:10.1145/3125643

    2017 doi

  112. [121]

    Optimal trace distance and fidelity estimations for pure quantum states

    Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory , 70(12):8791--8805, 2024. https://doi.org/10.1109/TIT.2024.3447915 doi:10.1109/TIT.2024.3447915

    2024

  113. [122]

    Limits on the power of quantum statistical zero-knowledge

    John Watrous. Limits on the power of quantum statistical zero-knowledge. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science , pages 459--468, 2002. https://doi.org/10.1109/SFCS.2002.1181970 doi:10.1109/SFCS.2002.1181970

    2002 arXiv

  114. [123]

    New quantum algorithms for computing quantum entropies and distances

    Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying. New quantum algorithms for computing quantum entropies and distances. IEEE Transactions on Information Theory , 70(8):5653--5680, 2024. https://doi.org/10.1109/TIT.2024.3399014 doi:10.1109/TIT.2024.3399014

    2024

  115. [124]

    Jingxiang Wu and Timothy H. Hsieh. Variational thermal quantum simulation via thermofield double states. Physical Review Letters , 123(22):220502, 2019. https://doi.org/10.1103/PhysRevLett.123.220502 doi:10.1103/PhysRevLett.123.220502

    2019 doi

  116. [125]

    Variational quantum Gibbs state preparation with a truncated Taylor series

    Youle Wang, Guangxi Li, and Xin Wang. Variational quantum Gibbs state preparation with a truncated Taylor series. Physical Review Applied , 16(5):054035, 2021. https://doi.org/10.1103/PhysRevApplied.16.054035 doi:10.1103/PhysRevApplied.16.054035

    2021 doi

  117. [126]

    Minimax rates of entropy estimation on large alphabets via best polynomial approximation

    Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory , 62(6):3702--3720, 2016. https://doi.org/10.1109/TIT.2016.2548468 doi:10.1109/TIT.2016.2548468

    2016

  118. [127]

    Fast quantum algorithms for trace distance estimation

    Qisheng Wang and Zhicheng Zhang. Fast quantum algorithms for trace distance estimation. IEEE Transactions on Information Theory , 70(4):2720--2733, 2024. https://doi.org/10.1109/TIT.2023.3321121 doi:10.1109/TIT.2023.3321121

    2024

  119. [128]

    Time-efficient quantum entropy estimator via samplizer

    Qisheng Wang and Zhicheng Zhang. Time-efficient quantum entropy estimator via samplizer. IEEE Transactions on Information Theory , 2025. https://doi.org/10.1109/TIT.2025.3576137 doi:10.1109/TIT.2025.3576137

    2025

  120. [129]

    Quantum algorithm for fidelity estimation

    Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, and Mingsheng Ying. Quantum algorithm for fidelity estimation. IEEE Transactions on Information Theory , 69(1):273--282, 2023. https://doi.org/10.1109/TIT.2022.3203985 doi:10.1109/TIT.2022.3203985

    2023

  121. [130]

    A quantum algorithm framework for discrete probability distributions with applications to R\' e nyi entropy estimation

    Xinzhao Wang, Shengyu Zhang, and Tongyang Li. A quantum algorithm framework for discrete probability distributions with applications to R\' e nyi entropy estimation. IEEE Transactions on Information Theory , 70(5):3399--3426, 2024. https://doi.org/10.1109/TIT.2024.3382037 doi:...

    2024

  122. [131]

    Quantum algorithms for estimating quantum entropies

    Youle Wang, Benchi Zhao, and Xin Wang. Quantum algorithms for estimating quantum entropies. Physical Review Applied , 19(4):044041, 2023. https://doi.org/10.1103/PhysRevApplied.19.044041 doi:10.1103/PhysRevApplied.19.044041

    2023 doi

  123. [132]

    Qubit-efficient entanglement spectroscopy using qubit resets

    Justin Yirka and Yi g it Suba s ı. Qubit-efficient entanglement spectroscopy using qubit resets. Quantum , 5:535, 2021. https://doi.org/10.22331/q-2021-09-02-535 doi:10.22331/q-2021-09-02-535

    2021 doi

  124. [133]

    A hybrid framework for estimating nonlinear functions of quantum states

    You Zhou and Zhenhuan Liu. A hybrid framework for estimating nonlinear functions of quantum states. npj quantum information , 10:62, 2024. https://doi.org/10.1038/s41534-024-00846-5 doi:10.1038/s41534-024-00846-5

    2024 doi

  125. [134]

    Measuring less to learn more: Quadratic speedup in learning nonlinear properties of quantum density matrices

    Yukun Zhang, Yusen Wu, You Zhou, and Xiao Yuan. Measuring less to learn more: Quadratic speedup in learning nonlinear properties of quantum density matrices. ArXiv e-prints, 2025. https://arxiv.org/abs/2509.01571 arXiv:2509.01571

    2025 arXiv

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.