Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices

T0 review · 3 major / 5 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 With purified access to a quantum state, estimating Tr(ρ^k O) costs only O(√k ∥O∥/ϵ) queries—a quadratic, provably optimal speedup over copy-based methods.

desk verdict The upper bound is a real contribution; the matching lower bound is not proven, so treat the optimality claim as open. read the letter →

arxiv 2509.01571 v1 pith:53ZKYJGS submitted 2025-09-01 quant-ph

Yukun Zhang , Yusen Wu , You Zhou , Xiao Yuan This is my paper
classification quant-ph
keywords nonlinearpropertyestimationpurifiedquantumqueryaccesssamplequadraticspeedupChebyshevpolynomialapproximationsingularvaluetransformationRényientropyvirtualdistillation
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

Estimating a nonlinear property such as Tr(ρ^k O) is traditionally done by collecting k copies of ρ, and this paper proves that the resulting linear cost in k is unavoidable when only copies are available. The central result is that the situation changes when one has a unitary that prepares a purification of ρ: there the query cost is Θ(√(k log(||O||/ϵ))||O||/ϵ), and the paper constructs an algorithm that reaches this bound. The algorithm approximates x^{k-1} by a Chebyshev polynomial of degree about √k and block-encodes p(ρ)O, then extracts the trace with amplitude estimation. Consequently entropy estimation, quantum Fisher information estimation, and virtual distillation/cooling inherit a quadratic speedup whenever a purification is available.

What carries the argument

The load-bearing object is a low-degree Chebyshev approximation of the power function x^{k-1}. A classical derivative bound for polynomials shows that a polynomial of degree ℓ bounded on [−1,1] can have slope as large as ℓ² at the boundary but only ℓ/√(1−x²) in the interior; because x^k is steepest at x=1, this asymmetry lets a degree-Θ(√k) polynomial track it to accuracy ϵ. Quantum singular value transformation (QSVT) converts that polynomial into a block encoding of p(ρ)O, with query cost equal to the degree; a Hadamard-test circuit reads out Tr(ρp(ρ)O) and amplitude estimation makes the readout efficient. The identity Tr(ρ^k O) = Tr(ρ · ρ^{k−1}O) is the bridge that allows the polynomial p

What would settle it

Take the two-state family used in the sample lower bound: ρ0=|0⟩⟨0|, ρ1=(1−c/k)|0⟩⟨0|+(c/k)|1⟩⟨1|, O=|0⟩⟨0|, each with an explicit purification unitary. Simulate the paper's Chebyshev-QSVT estimator for increasing k at fixed ϵ and count queries to Uρ. The theorem predicts a Θ(√k) query count; observing a count that grows like k would refute the algorithm's claimed complexity, while a count growing slower than √k would refute the lower bound.

Watch

Extended reading notes

Core claim

At the paper's core is a claim about query complexity depending on access model. With sample access to ρ, the cost of estimating Tr(ρ^k O) to additive error ϵ is Θ(k||O||^2/ϵ^2), matching the generalized swap test. With purified query access—a unitary Uρ that prepares a purification of ρ—the cost is Θ(√(k log(||O||/ϵ))||O||/ϵ). The algorithm works by block-encoding p(ρ)O, where p is a polynomial of degree Θ(√(k log(1/ϵ))) that uniformly approximates x^{k-1} on [0,1]; a Hadamard-test circuit plus amplitude estimation then outputs Tr(ρ p(ρ)O), which is ϵ-close to Tr(ρ^k O). The lower bound combines a new degree lower bound for polynomial approximation of x^k with a recent characterization of q

Load-bearing premise

The lower-bound proof assumes that an optimal purified-access estimator must first construct an approximate block encoding of ρ^{k-1} and then estimate an expectation value against it, so the two query costs multiply; the sparse-matrix lower bound is also transferred to all density matrices by containment rather than by construction of an explicit hard full-rank instance.

Editorial extensions

If this is right

  • Entropy and norm estimation: Rényi, Tsallis, and Schatten-norm quantities that reduce to Tr(ρ^k) can be computed with O(√k) purified queries instead of O(k) copies.
  • Error mitigation: virtual distillation and quantum virtual cooling rely on ratios such as Tr(ρ^k O)/Tr(ρ^k); the paper's algorithm estimates both numerator and denominator with the quadratic speedup and supplies error-propagation bounds for the ratio.
  • Classical shadows: replacing amplitude estimation with randomized measurements in the Hadamard-test construction reduces the k-dependence of nonlinear shadow estimation from linear to √k when a purification of ρ is available.
  • Quantum metrology: the Krylov-subspace formula for quantum Fisher information contains terms of the form Tr(Oρ^l Oρ^{k-l+1}), which the block-encoding adaptation estimates with the same quadratic improvement.
  • Complexity classification: the decision problem for whether Tr(ρ^k O) exceeds a threshold is BQP-complete, so the task captures universal quantum speedups.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The degree-√k phenomenon follows from the fact that polynomials are steepest at the interval boundary; the paper mentions similar boundary-sensitive polynomial methods driving quadratic gains in quantum fast-forwarding and ground-state preparation, so the power-function result is plausibly one instance of a general 'approximate the boundary, then block-encode' principle.
  • The Chebyshev truncation error is literally a binomial tail, which suggests exact tail bounds could improve constant factors in the algorithm's degree and might extend the construction to fractional powers or to functions with logarithmic singularities; the paper does not explore these variants.
  • Because the algorithm's final step needs a block encoding of O, the practical speedup is clearest when O is a linear combination of few unitaries; for observables defined only through sampling, the encoding overhead would have to be accounted for separately.
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

3 major / 5 minor

Summary. The paper studies the estimation of the nonlinear functional Tr(ρ^k O) under two access models. For sample access to ρ, it claims a lower bound of Ω(k||O||²/ε²) copies, matching the generalized swap test. For purified query access via a unitary Uρ that prepares a purification of ρ, it claims matching lower and upper bounds Θ(√(k log(||O||/ε)) ||O||/ε), demonstrating a quadratic speedup over sample access. The upper bound is obtained by block-encoding an optimal Chebyshev approximation to ρ^{k−1}, applying a Hadamard-test-type circuit, and using amplitude estimation. The paper also proves that the decision version of the problem is BQP-complete. The main claims are Theorem 1 (sample lower bound), Theorem 2 (purified-query lower bound), Theorem 3 (matching algorithm), and Theorem 4 (BQP-completeness).

Significance. If the claimed bounds are correct, the separation between sample and purified access to a quantum state is a significant conceptual and technical result, with consequences for entropy estimation, quantum Fisher information, virtual distillation, virtual cooling, and classical shadows. The proposed algorithm is explicit and builds on standard QSVT and Chebyshev approximation tools; the BQP-completeness reduction is clean and self-contained. However, the central optimality claims rest on lower-bound proofs that have serious gaps. The upper bound and BQP-completeness parts are valuable, but the advertised quadratic optimality is not established by the present arguments.

major comments (3)
  1. [Supplementary, Theorem 8 (main Theorem 2)] The proof multiplies two lower bounds, but query lower bounds cannot be composed this way. Corollary 2 lower-bounds the task of constructing a block encoding of ρ^{k−1}; an algorithm for the scalar estimation problem Tr(ρ^kO) is not required to construct such an encoding first. Even if a two-phase structure were imposed, the queries spent in the first phase are also queries to Uρ and would contribute to the second phase, so at most an additive combination Ω(a)+Ω(b) would follow, not the product. The hard instance of Lemma 11 (A=δ|ν⟩⟨ν| with input |ν⟩) is also not shown to be realizable as ρ^{k−1} for a valid density matrix with its purification; for 0<δ<1 the spectrum {δ,0} cannot be the (k−1)-th power of a trace-one density matrix. Thus Theorem 2 is not established.
  2. [End Matter, Proof of Theorem 1] The proof gives two separate lower bounds: Ω(k) for fixed ε with O=|0⟩⟨0|, and Ω(||O||²/ε²) via Le Cam. The second part is applied to Tr(ρ_i^kO), but the calculation in Eqs. (10)–(12) concerns Tr(ρ_iO). For the states in Eq. (10), the gap in Tr(ρ_i^kO) is ||O||[(1/2+δ)^k−(1/2−δ)^k], which is of order k2^{-k}δ||O|| for large k; for k larger than about log(||O||/ε) this gap is below the estimation error ε, so the reduction to two-point discrimination fails. Moreover, the theorem asserts a single (ρ,O) requiring the product Ω(k||O||²/ε²), but the two hard instances are different and no product construction is given.
  3. [Supplementary, Lemma 10 and Corollary 2] The stated Lemma 10 asserts existence of a unitary using Θ(gdeg_ε(f)) queries; the proof of Theorem 8 uses it as a lower bound on any algorithm. The lower-bound half should be stated explicitly, together with its hypotheses (O(1)-sparse A and ||A||≤1−δ). Corollary 2 drops the δ condition and Remark 3 transfers the bound to all density matrices by inclusion; while inclusion is valid for a worst-case lower bound, the transfer does not supply the missing reduction from estimating a scalar expectation to implementing a block encoding, nor does it identify a density-matrix instance that simultaneously realizes the hard cases of both stages.
minor comments (5)
  1. [Main text, 'Main results'] The sentence 'the query complexity for approximating matrix function ρk is also lower bounded by Ω(k)' should read Ω(√k); otherwise it contradicts Lemma 1/Corollary 1.
  2. [Main text, proof of Theorem 3] 'Based on Theorem 1' appears to be a typo; the cited degree bound follows from Lemma 1 (or Lemma 7), not from the sample-access lower bound.
  3. [Supplementary, Algorithm Formulation, Eq. (81)] The probability P(|0⟩_c) is computed without the normalization αO that appears in the main-text circuit and estimator Eq. (2). With the block encoding of p(ρ)O normalized by αO, the probability is (1+Re Tr(ρp(ρ)O)/αO)/2, and the estimator is αO(2P−1). Please reconcile the two derivations.
  4. [Main text, Definition 1 and Theorem 3] The problem definition does not state how O is accessed. The algorithm assumes an error-free block encoding of O with normalization αO (Corollary 3). Without specifying this access model, Theorem 3 is not well-defined for a general observable O; please add the assumption explicitly (e.g., O is given by an LCU or block encoding).
  5. [Supplementary, Lemma 10] State the lower-bound half of the 'optimal query complexity' result explicitly. The current wording 'there exists a unitary...' is an upper bound and is insufficient for the later lower-bound argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core derivations rely on external QSVT, Montanaro–Shao, and classical approximation theory; self-citations are not load-bearing.

full rationale

The paper's central claims are not circular. The upper bound (Theorem 3) is built from an external QSVT block-encoding result [16] and a self-contained Chebyshev approximation construction (Lemma 7/12), with polynomial-approximation error and amplitude-estimation error combined by a triangle inequality. The sample-access lower bound uses standard Helstrom/Le Cam reductions. The purified-access lower bound invokes the external Montanaro–Shao matrix-function query bound [19] and classical approximation theory (Rivlin), not a result of the present authors. The paper's self-citations (e.g., [9,11,46]) appear in application/comparison contexts and are not load-bearing for the main theorems. The main non-circularity concern is that the proof of Theorem 2 (Supplementary Theorem 8) assumes an optimal estimator must first construct a block encoding of rho^{k-1} and then query it, multiplying independent lower bounds; this is a proof gap about algorithm structure, not a definitional or self-citational reduction, and is therefore a correctness risk rather than a circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests on external results (QSVT, Montanaro-Shao, approximation theory) and two domain assumptions about the access model and the block encodability of O. The only potentially unproven ingredient is the existence of O(1)-sparse hard instances, which is waved through in Remark 3.

assumptions (7)
  • domain assumption Purified quantum query access: existence of a unitary Uρ that prepares a purification of ρ
    The entire purified-access model and Theorems 2 and 3 depend on this oracle model. Stated in Definition 3.
  • standard math QSVT polynomial transformation (Lemma 5) from Gilyén et al. [16]
    Used to implement p(ρ) from a block encoding; external theorem.
  • standard math Block encoding of ρ from purification (Lemma 4) from [16]
    Constructs a (1,a+n,0)-block encoding of ρ with two queries to Uρ; external theorem.
  • standard math Montanaro and Shao query complexity lower bound (Lemma 10) from [19]
    Relates query complexity to polynomial approximation degree for matrix functions; foundation of the lower bound.
  • standard math Bernstein's inequality and the Chebyshev vs best approximation error relation (Lemma 9)
    Classical approximation theory used for the √k polynomial degree and its optimality.
  • domain assumption Existence of O(1)-sparse hard density matrices for the lower bound
    Remark 3 assumes such instances exist and that the lower bound transfers to all density matrices by inclusion.
  • domain assumption O is block-encodable with an error-free (α_O, b, 0) block encoding
    Algorithm assumes O is a linear combination of unitaries so its block encoding is exact (used in Corollary 3).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices." pith.science (2026). https://pith.science/paper/53ZKYJGS

@misc{pith2026250901571,
  author       = {Pith},
  title        = {Pith review of: Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/53ZKYJGS}},
  note         = {Machine review of arXiv:2509.01571}
}
abstract

A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $\mathrm{Tr}(\rho^k O)$. Intuitively, one expects that computing a $k$-th order quantity generally requires $O(k)$ copies of the state $\rho$, and we rigorously establish this lower bound under sample access to $\rho$. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of $\rho$, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of $\Theta(\sqrt{k})$, and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory -- specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling, and evaluating other multiple nonlinear quantum observables with classical shadows.

Figures

Figures reproduced from arXiv: 2509.01571 by the authors.

Figure 1
Figure 1. FIG. 1. The quantum circuit for estimating Tr [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] 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.

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

    quant-ph 2025-09 conditional novelty 7.0 of 10

    A quantum estimator achieves near-optimal query complexity for integer-order Tsallis entropy, and the same technique yields a new information-theoretic proof that approximating x^n needs polynomials of degree Ω(√n).

Reference graph

Works this paper leans on

68 extracted references · 57 canonical work pages · cited by 1 Pith paper

  1. [1]

    Construct the controlled block encoding of ˆp(ρ) := p(ρ)O with normalization factor αO using the quan- tum singular value transformation (QSVT) algo- rithm [16], where p(x) is an optimal approximation of g(x) = xk−1

    work page

  2. [2]

    1 with W = I for estimating the real parts of the nonlinear property function

    Implement the quantum circuit as illustrated in Fig. 1 with W = I for estimating the real parts of the nonlinear property function

    work page

  3. [3]

    Apply amplitude estimation [30] to estimate the probability P (0) of the first ancilla qubit in state |0⟩ to error ϵ 2

    work page

  4. [4]

    (2) In step 1, ˆp(ρ) is realized by first constructing a block encoding of p(ρ) with error ϵ/(2 ∥O∥) using degree m =p 2(k − 1) ln(4αO ∥O∥ /ϵ) (see proof below)

    The final estimation is given by eE := αO(2P (0) − 1)). (2) In step 1, ˆp(ρ) is realized by first constructing a block encoding of p(ρ) with error ϵ/(2 ∥O∥) using degree m =p 2(k − 1) ln(4αO ∥O∥ /ϵ) (see proof below). Then, we can block encode the product of p(ρ) and O, which is a feature enabled by the QSVT framework. Here, we assume an error-free block ...

    work page

  5. [5]

    purifying

    Moreover, by employing the replica trick, one may approximate the min-entropy S∞(ρ) = − ln ∥ρ∥∞ or the von Neumann entropy S(ρ) = Tr (ρ log ρ) by taking the limit of k → ∞and k → 1, respectively, of which have been widely used in quantum field theory [33, 34] and gravity [35]. Our method also applies to more sophisticated quan- tum information quantities,...

    work page

  6. [6]

    Quantum entropy and its use

    Masanori Ohya and D´ enes Petz. Quantum entropy and its use . Springer Science & Business Media, 2004

    work page 2004

  7. [7]

    Exponential error suppression for near- term quantum devices

    B´ alint Koczor. Exponential error suppression for near- term quantum devices. Physical Review X, 11(3):031057, 2021

    work page 2021

  8. [8]

    Vir- tual distillation for quantum error mitigation

    William J Huggins, Sam McArdle, Thomas E O’Brien, Joonho Lee, Nicholas C Rubin, Sergio Boixo, K Birgitta Whaley, Ryan Babbush, and Jarrod R McClean. Vir- tual distillation for quantum error mitigation. Physical Review X, 11(4):041036, 2021

    work page 2021

Show all 68 references
  1. [9]

    Quantum virtual cooling

    Jordan Cotler, Soonwon Choi, Alexander Lukin, Hrant Gharibyan, Tarun Grover, M Eric Tai, Matthew Rispoli, Robert Schittko, Philipp M Preiss, Adam M Kaufman, et al. Quantum virtual cooling. Physical Review X , 9(3):031013, 2019

    2019

  2. [10]

    Direct estimations of linear and nonlinear func- tionals of a quantum state

    Artur K Ekert, Carolina Moura Alves, Daniel KL Oi, Micha l Horodecki, Pawe l Horodecki, and Leong Chuan Kwek. Direct estimations of linear and nonlinear func- tionals of a quantum state. Physical review letters , 88(21):217901, 2002

    2002

  3. [11]

    Measuring polynomial functions of states

    Todd A Brun. Measuring polynomial functions of states. arXiv preprint quant-ph/0401067 , 2004

    2004 arXiv

  4. [12]

    Shadow tomography of quantum states

    Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th annual ACM SIGACT sympo- sium on theory of computing , pages 325–338, 2018

    2018

  5. [13]

    Predicting many properties of a quantum system from very few measurements

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050– 1057, 2020

    2020

  6. [14]

    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(1):62, 2024

    2024

  7. [15]

    Prin- cipal eigenstate classical shadows

    Daniel Grier, Hakop Pashayan, and Luke Schaeffer. Prin- cipal eigenstate classical shadows. In The Thirty Seventh Annual Conference on Learning Theory , pages 2122–

  8. [16]

    Auxiliary-free replica shadow estimation

    Qing Liu, Zihao Li, Xiao Yuan, Huangjun Zhu, and You Zhou. Auxiliary-free replica shadow estimation. arXiv preprint arXiv:2407.20865, 2024

    2024

  9. [17]

    A hierarchy for replica quantum advantage

    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. A hierarchy for replica quantum advantage. arXiv 6 preprint arXiv:2111.05874, 2021

    2021 arXiv

  10. [18]

    Exponential separations between learning with and without quantum memory

    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd An- nual Symposium on Foundations of Computer Science (FOCS), pages 574–585. IEEE, 2022

    2021

  11. [19]

    An optimal trade- off between entanglement and copy complexity for state tomography

    Sitan Chen, Jerry Li, and Allen Liu. An optimal trade- off between entanglement and copy complexity for state tomography. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1331–1342, 2024

    2024

  12. [20]

    Quantum detection and estimation theory

    Carl W Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics , 1:231–252, 1969

    1969

  13. [21]

    Quantum singular value transformation and be- yond: exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and be- yond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages 193– 204, 2019

    2019

  14. [22]

    Faster algorithms via approximation theory

    Sushant Sachdeva, Nisheeth K Vishnoi, et al. Faster algorithms via approximation theory. Foundations and Trends® in Theoretical Computer Science, 9(2):125–210, 2014

    2014

  15. [23]

    Approximation theory and approxi- mation practice, extended edition

    Lloyd N Trefethen. Approximation theory and approxi- mation practice, extended edition . SIAM, 2019

    2019

  16. [24]

    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 The- ory of Computing , pages 573–584, 2024

    2024

  17. [25]

    Convergence of estimates under dimen- sionality restrictions

    Lucien LeCam. Convergence of estimates under dimen- sionality restrictions. The Annals of Statistics , pages 38– 53, 1973

    1973

  18. [26]

    Tsybakov

    Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, NY, 2009

    2009

  19. [27]

    Many-body topological invariants from random- ized measurements in synthetic quantum matter

    Andreas Elben, Jinlong Yu, Guanyu Zhu, Mohammad Hafezi, Frank Pollmann, Peter Zoller, and Benoit Ver- mersch. Many-body topological invariants from random- ized measurements in synthetic quantum matter. Science Advances, 6(15):eaaz3666, 2020

    2020

  20. [28]

    Lanyon, Peter Zoller, Rainer Blatt, and Christian F

    Tiff Brydges, Andreas Elben, Petar Jurcevic, Benoit Ver- mersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, and Christian F. Roos. Probing renyi en- tanglement entropy via randomized measurements. Sci- ence, 364(6437):260–263, 2019

    2019

  21. [29]

    Mixed- state entanglement from local randomized measurements

    Andreas Elben, Richard Kueng, Hsin-Yuan (Robert) Huang, Rick van Bijnen, Christian Kokail, Marcello Dalmonte, Pasquale Calabrese, Barbara Kraus, John Preskill, Peter Zoller, and Beno ˆ ıt Vermersch. Mixed- state entanglement from local randomized measurements. Phys. Rev. Lett....

    2020

  22. [30]

    Inequalities of a

    AC Schaeffer. Inequalities of a. markoff and s. bernstein for polynomials and related functions. 1941

    1941

  23. [31]

    Quantum fast- forwarding: Markov chains and graph property testing

    Simon Apers and Alain Sarlette. Quantum fast- forwarding: Markov chains and graph property testing. arXiv preprint arXiv:1804.02321 , 2018

    2018 arXiv

  24. [32]

    Nearly- frustration-free ground state preparation

    Matthew Thibodeau and Bryan K Clark. Nearly- frustration-free ground state preparation. Quantum, 7:1084, 2023

    2023

  25. [33]

    On solving classes of positive-definite quantum linear systems with quadrati- cally improved runtime in the condition number

    Davide Orsucci and Vedran Dunjko. On solving classes of positive-definite quantum linear systems with quadrati- cally improved runtime in the condition number. Quan- tum, 5:573, 2021

    2021

  26. [34]

    A theory of quantum differential equation solvers: limitations and fast-forwarding

    Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao. A theory of quantum differential equation solvers: limitations and fast-forwarding. arXiv preprint arXiv:2211.05246, 2022

    2022 arXiv

  27. [35]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055 , 2000

    2000 arXiv

  28. [36]

    New quantum algorithms for comput- ing quantum entropies and distances

    Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying. New quantum algorithms for comput- ing quantum entropies and distances. IEEE Transactions on Information Theory , 2024

    2024

  29. [37]

    Estimat- ing operator norms using covering nets

    Fernando GSL Brandao and Aram W Harrow. Estimat- ing operator norms using covering nets. arXiv preprint arXiv:1509.05065, 2015

    2015 arXiv

  30. [38]

    Entanglement en- tropy and quantum field theory.Journal of statistical me- chanics: theory and experiment , 2004(06):P06002, 2004

    Pasquale Calabrese and John Cardy. Entanglement en- tropy and quantum field theory.Journal of statistical me- chanics: theory and experiment , 2004(06):P06002, 2004

    2004

  31. [39]

    Evolution of en- tanglement entropy in one-dimensional systems

    Pasquale Calabrese and John Cardy. Evolution of en- tanglement entropy in one-dimensional systems. Jour- nal of Statistical Mechanics: Theory and Experiment , 2005(04):P04010, 2005

    2005

  32. [40]

    Quantum corrections to holographic entanglement entropy

    Thomas Faulkner, Aitor Lewkowycz, and Juan Malda- cena. Quantum corrections to holographic entanglement entropy. Journal of High Energy Physics , 2013(11):1–18, 2013

    2013

  33. [41]

    Statistical distance and the geometry of quantum states

    Samuel L Braunstein and Carlton M Caves. Statistical distance and the geometry of quantum states. Physical Review Letters, 72(22):3439, 1994

    1994

  34. [42]

    Quantum metrol- ogy from a quantum information science perspective

    G´ eza T´ oth and Iagoba Apellaniz. Quantum metrol- ogy from a quantum information science perspective. Journal of Physics A: Mathematical and Theoretical , 47(42):424006, 2014

    2014

  35. [43]

    Quantum speed limit for physical processes

    M´ arcio M Taddei, Bruno M Escher, Luiz Davidovich, and Ruynet L de Matos Filho. Quantum speed limit for physical processes. Physical review letters, 110(5):050402, 2013

    2013

  36. [44]

    Fisher information and multiparticle entanglement

    Philipp Hyllus, Wies law Laskowski, Roland Krischek, Christian Schwemmer, Witlef Wieczorek, Harald We- infurter, Luca Pezz´ e, and Augusto Smerzi. Fisher information and multiparticle entanglement. Physi- cal Review A—Atomic, Molecular, and Optical Physics , 85(2):022321, 2012

    2012

  37. [45]

    Krylov shadow tomogra- phy: Efficient estimation of quantum fisher information

    Da-Jian Zhang and DM Tong. Krylov shadow tomogra- phy: Efficient estimation of quantum fisher information. Physical Review Letters, 134(11):110802, 2025

    2025

  38. [46]

    Quantum fisher information from randomized measurements

    Aniket Rath, Cyril Branciard, Anna Minguzzi, and Beno ˆ ıt Vermersch. Quantum fisher information from randomized measurements. Physical Review Letters , 127(26):260501, 2021

    2021

  39. [47]

    Purification-based quantum error mitigation of pair-correlated electron simulations

    Thomas E O’Brien, G Anselmetti, Fotios Gkritsis, VE Elfving, Stefano Polla, William J Huggins, Oumarou Oumarou, Kostyantyn Kechedzhi, Dmitry Abanin, Ra- jeev Acharya, et al. Purification-based quantum error mitigation of pair-correlated electron simulations. Na- ture Physics, ...

    2023

  40. [48]

    Shadow distillation: Quantum error mitiga- tion with classical shadows for near-term quantum pro- cessors

    Alireza Seif, Ze-Pei Cian, Sisi Zhou, Senrui Chen, and Liang Jiang. Shadow distillation: Quantum error mitiga- tion with classical shadows for near-term quantum pro- cessors. PRX Quantum , 4(1):010303, 2023

    2023

  41. [49]

    Lo- calized virtual purification

    Hideaki Hakoshima, Suguru Endo, Kaoru Yamamoto, Yuichiro Matsuzaki, and Nobuyuki Yoshioka. Lo- calized virtual purification. Physical Review Letters , 133(8):080601, 2024

    2024

  42. [50]

    Expo- nential distillation of dominant eigenproperties

    Bence Bak´ o, Tenzan Araki, and B´ alint Koczor. Expo- nential distillation of dominant eigenproperties. arXiv 7 preprint arXiv:2506.04380, 2025

    2025

  43. [51]

    Nearly query-optimal classical shadow estimation of uni- tary channels

    Zihao Li, Changhao Yi, You Zhou, and Huangjun Zhu. Nearly query-optimal classical shadow estimation of uni- tary channels. arXiv preprint arXiv:2410.14538 , 2024

    2024

  44. [52]

    Optimal trace distance and fidelity esti- mations for pure quantum states

    Qisheng Wang. Optimal trace distance and fidelity esti- mations for pure quantum states. IEEE Transactions on Information Theory, 2024

    2024

  45. [53]

    Sample-optimal quantum estimators for pure-state trace distance and fi- delity via samplizer

    Qisheng Wang and Zhicheng Zhang. Sample-optimal quantum estimators for pure-state trace distance and fi- delity via samplizer. arXiv preprint arXiv:2410.21201 , 2024

    2024 arXiv

  46. [54]

    Quantum principal component analysis

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature physics, 10(9):631–633, 2014

    2014

  47. [55]

    Cryptographic distinguishability measures for quantum- mechanical states

    Christopher A Fuchs and Jeroen Van De Graaf. Cryptographic distinguishability measures for quantum- mechanical states. IEEE Transactions on Information Theory, 45(4):1216–1227, 2002

    2002

  48. [56]

    Classical and quantum computation

    Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vya- lyi. Classical and quantum computation . Number 47. American Mathematical Soc., 2002

    2002

  49. [57]

    The theory of quantum information

    John Watrous. The theory of quantum information. Cam- bridge university press, 2018

    2018

  50. [58]

    Real analysis

    Neal L Carothers. Real analysis. Cambridge University Press, 2000

    2000

  51. [59]

    Lecture notes on quantum algorithms for sci- entific computation

    Lin Lin. Lecture notes on quantum algorithms for sci- entific computation. arXiv preprint arXiv:2201.08309 , 2022

    2022 arXiv

  52. [60]

    T.J. Rivlin. Chebyshev Polynomials: From Approxima- tion Theory to Algebra and Number Theory . Pure and Applied Mathematics: A Wiley Series of Texts, Mono- graphs and Tracts. Wiley, 1990

    1990

  53. [61]

    Strengths and weaknesses of quantum computing

    Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing , 26(5):1510–1523, 1997

    1997

  54. [62]

    Quantum lower bounds by quantum arguments

    Andris Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 636– 643, 2000

    2000

  55. [63]

    Grand unification of quantum algo- rithms

    John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algo- rithms. PRX quantum , 2(4):040203, 2021. END MATTER Proof of Theorem 1 Theorem 5 (Restated). For algorithms that estimates Tr(ρkO) to additive error ϵ with constant success prob- ...

    2021

  56. [64]

    A polynomial-size (in n) quantum circuit CΓ that prepares a purification |Γ⟩ASR of an m-qubit state ρ via ρ = TrA |Γ⟩ ⟨Γ|ASR , where A is an ancilla register and SR denotes the system on which ρ acts

  57. [65]

    A succinct classical description of an observable O of operator norm ∥O∥ = O(1); and

  58. [66]

    The promise is that either Tr(ρkO) ≥ a (YES) or Tr(ρkO) ≤ b (NO)

    Thresholds a, b with the promise gap a − b ≥ 1/ poly(n), where n denotes the input length. The promise is that either Tr(ρkO) ≥ a (YES) or Tr(ρkO) ≤ b (NO). Then, NonLineark is BQP-complete. Proof. The containment in BQP [51, 52] is seen by the problem is efficiently solved by...

  59. [67]

    For any x ∈ (−1, 1): |P ′(x)| ≤ ℓ√ 1−x2 ,

  60. [68]

    Moreover, the bound at the endpoints is achieved by the Chebyshev polynomial Tℓ(x)

    For the endpoints: |P ′(±1)| ≤ℓ2. Moreover, the bound at the endpoints is achieved by the Chebyshev polynomial Tℓ(x). To understand why this inequality is remarkable, consider what it tells us about polynomial derivatives. At first glance, one might expect that if a polynomial...

Pith tools

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