pith. sign in

arxiv: 2606.10994 · v1 · pith:5GWPB4FJnew · submitted 2026-06-09 · 🪐 quant-ph

Adaptive identification of low-degree polynomials in quantum singular value transformation: application to nonlinear quantum properties estimation

Jumpei Kato , Akira Tanji , Hiroyuki Harada , Kaito Wada , Kosuke Ito , Naoki Yamamoto This is my paper

Pith reviewed 2026-06-27 13:25 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QSVTspectral cutoffvon Neumann entropyRényi entropyquantum property estimationadaptive algorithmpolynomial degree
0
0 comments X

The pith

A two-stage algorithm adaptively determines low-degree polynomials for QSVT to estimate nonlinear quantum properties at lower cost.

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

This paper aims to reduce the cost of estimating nonlinear properties of quantum states, such as entropies, using QSVT by avoiding overly conservative polynomial degrees. Standard methods rely on worst-case bounds involving the smallest eigenvalue or matrix rank, leading to high degrees. The authors introduce a spectral cutoff that truncates small eigenvalues based on the specific state and accuracy goal. They implement this through a first stage that searches for the cutoff in the unknown state and a second stage that applies QSVT with the resulting lower degree. The result is an improved overall estimation cost even when the minimum eigenvalue and rank are unknown.

Core claim

The paper claims that by truncating the negligible eigenvalue tail with a task- and state-dependent spectral cutoff, the degree of the polynomial in QSVT can be significantly lowered, and this cutoff can be identified directly from the state using a search algorithm in a two-stage procedure, leading to better estimation costs for properties like von Neumann and Rényi entropy compared to existing bounds.

What carries the argument

The spectral cutoff method, which truncates the eigenvalue tail depending on the task, target accuracy, and state to enable lower-degree polynomials in QSVT.

If this is right

  • Estimation of von Neumann entropy and Rényi entropy can be done with significantly lower cost.
  • The method does not require knowledge of the minimum non-zero eigenvalue or the rank.
  • The polynomial degree adapts to the specific quantum state and desired accuracy.
  • Negligible parts of the spectrum can be ignored without sacrificing accuracy.

Where Pith is reading between the lines

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

  • The approach may apply to other QSVT-based estimations of functions of quantum states.
  • Hardware implementations could benefit if the search stage cost scales favorably.
  • Further work might optimize the search algorithm for even lower overhead.
  • Similar adaptive techniques could appear in related quantum algorithms.

Load-bearing premise

The first-stage search algorithm can identify a suitable spectral cutoff directly from the unknown quantum state at modest additional cost while preserving the target accuracy for the subsequent QSVT stage.

What would settle it

Demonstration that the total query complexity or gate cost of the two-stage procedure is not lower than that of standard methods using conservative bounds for equivalent accuracy and states.

Figures

Figures reproduced from arXiv: 2606.10994 by Akira Tanji, Hiroyuki Harada, Jumpei Kato, Kaito Wada, Kosuke Ito, Naoki Yamamoto.

Figure 1
Figure 1. Figure 1: FIG. 1. The illustration of the idea. (Left) When using a [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. The overall pipeline of the two-stage algorithm. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. The algorithm search steps to find [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
read the original abstract

Estimating properties of unknown quantum states via quantum singular value transformation (QSVT) often requires high-degree polynomials to handle small eigenvalues of density matrices. Specifically, the existing approaches determine the polynomial degree by relying on overly conservative worst-case bounds based on the minimum non-zero eigenvalue or the rank of the density matrices. In this work, we propose a spectral cutoff method that truncates the negligible eigenvalue tail depending on the task, the target accuracy, and the state, which enables the use of significantly lower-degree polynomials. To implement this, we develop a two-stage algorithm to estimate nonlinear properties, particularly von Neumann entropy and R{\'e}nyi entropy. In the first stage, we execute a search algorithm to identify the spectral cutoff directly from the unknown quantum state. In the second stage, we estimate the nonlinear properties utilizing QSVT with the degree of polynomial adaptively determined by the cutoff. This two-stage algorithm significantly improves the overall estimation cost compared to known bounds, even without knowing the minimum eigenvalue or the rank.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a two-stage algorithm for estimating nonlinear properties (von Neumann and Rényi entropy) of unknown quantum states via QSVT. Stage 1 runs a search to identify a task-dependent spectral cutoff directly from the state; Stage 2 then applies QSVT with a lower-degree polynomial whose degree is set by that cutoff. The central claim is that this yields significantly lower overall query cost than existing worst-case bounds that depend on the minimum nonzero eigenvalue or matrix rank, without requiring prior knowledge of those quantities.

Significance. If the first-stage search cost is provably subdominant and the induced approximation error remains within target accuracy, the approach would meaningfully tighten resource estimates for entropy estimation on quantum hardware, especially for states with rapidly decaying spectra. The paper supplies no machine-checked proofs, reproducible code, or explicit end-to-end complexity expressions, so these strengths are not yet realized.

major comments (2)
  1. [Abstract, §4] Abstract and §4 (two-stage algorithm description): the headline claim that the two-stage procedure 'significantly improves the overall estimation cost' rests on the unproven assertion that the Stage-1 search cost is o(the savings realized by the lower-degree QSVT in Stage 2) while preserving end-to-end error. No query-complexity bound, failure-probability analysis, or explicit comparison to the conservative bounds being beaten is supplied.
  2. [§3] §3 (spectral cutoff method): the truncation threshold is described as depending on 'the task, the target accuracy, and the state,' yet no concrete rule, algorithm, or error-propagation lemma is given showing that the chosen cutoff keeps the polynomial approximation error below the target accuracy for von Neumann/Rényi entropy. This is load-bearing for the correctness of the adaptive degree selection.
minor comments (2)
  1. Notation for the spectral cutoff threshold is introduced without a dedicated symbol or equation reference, making it difficult to track through the complexity arguments.
  2. [Abstract] The abstract states the improvement holds 'even without knowing the minimum eigenvalue or the rank,' but the manuscript does not clarify whether the search algorithm itself implicitly recovers equivalent information at comparable cost.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below, indicating planned revisions where appropriate to strengthen the presentation of the two-stage algorithm.

read point-by-point responses

  1. Referee: [Abstract, §4] Abstract and §4 (two-stage algorithm description): the headline claim that the two-stage procedure 'significantly improves the overall estimation cost' rests on the unproven assertion that the Stage-1 search cost is o(the savings realized by the lower-degree QSVT in Stage 2) while preserving end-to-end error. No query-complexity bound, failure-probability analysis, or explicit comparison to the conservative bounds being beaten is supplied.

    Authors: We agree that the manuscript does not supply a full asymptotic query-complexity bound or failure-probability analysis establishing that Stage-1 cost is strictly subdominant. The current work emphasizes the algorithmic construction and provides numerical demonstrations of net cost reduction for states whose spectra decay faster than the worst-case bounds. In revision we will add a dedicated subsection with a heuristic cost comparison (under the assumption of exponentially decaying eigenvalues) and an explicit statement of the conditions under which the overall procedure improves upon the conservative bounds. revision: partial

  2. Referee: [§3] §3 (spectral cutoff method): the truncation threshold is described as depending on 'the task, the target accuracy, and the state,' yet no concrete rule, algorithm, or error-propagation lemma is given showing that the chosen cutoff keeps the polynomial approximation error below the target accuracy for von Neumann/Rényi entropy. This is load-bearing for the correctness of the adaptive degree selection.

    Authors: The spectral cutoff is located by the Stage-1 search procedure described in §4, which is intended to be task-specific for entropy estimation. We acknowledge that §3 currently lacks both an explicit algorithmic rule for cutoff selection and a formal error-propagation lemma. In the revised manuscript we will expand §3 to include (i) a precise description of the search-based cutoff rule and (ii) a lemma that bounds the truncation-induced error in the von Neumann and Rényi entropy functionals, showing that the error can be kept below the target accuracy when the cutoff is chosen appropriately. revision: yes

Circularity Check

0 steps flagged

No circularity: adaptive cutoff is an algorithmic proposal, not a definitional reduction

full rationale

The paper describes a two-stage procedure in which stage 1 searches for a task-dependent spectral cutoff from the unknown state and stage 2 then applies a lower-degree QSVT polynomial whose degree is set by that cutoff. No equations, fitted parameters, or self-citations are exhibited that would make the claimed cost improvement equivalent to its own inputs by construction. The derivation therefore remains self-contained against external complexity bounds; the skeptic concern about stage-1 cost is an assumption-validity issue, not a circularity reduction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Abstract-only review; free parameters and axioms cannot be enumerated in detail. The method implicitly relies on the standard QSVT framework and on the existence of a search routine whose cost is not quantified here.

free parameters (1)
  • spectral cutoff threshold
    Chosen depending on task, target accuracy, and state; value not specified in abstract.
axioms (1)
  • domain assumption QSVT can implement polynomial functions of the singular values of a quantum state or density matrix
    Standard assumption in the QSVT literature referenced by the abstract.

pith-pipeline@v0.9.1-grok · 5726 in / 1199 out tokens · 19966 ms · 2026-06-27T13:25:49.446044+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

43 extracted references · 6 canonical work pages

  1. [1]

    Bravyi, A

    S. Bravyi, A. W. Harrow, and A. Hassidim, Quantum algorithms for testing properties of distributions, IEEE Transactions on Information Theory57, 3971 (2011)

    2011

  2. [2]

    Montanaro and R

    A. Montanaro and R. d. Wolf, A survey of quantum 12 property testing, Theory of Computing Graduate Sur- veys Graduate Surveys, 1 (2016)

    2016

  3. [3]

    Anshu and S

    A. Anshu and S. Arunachalam, A survey on the complex- ity of learning quantum states, Nature Reviews Physics 6, 59 (2024)

    2024

  4. [4]

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, Sample- optimal tomography of quantum states, inProceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16 (Association for Computing Ma- chinery, New York, NY, USA, 2016) p. 913–925

    2016

  5. [5]

    O’Donnell and J

    R. O’Donnell and J. Wright, Efficient quantum tomog- raphy, inProceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16 (Asso- ciation for Computing Machinery, New York, NY, USA,

  6. [6]

    Pelecanos, J

    A. Pelecanos, J. Spilecki, E. Tang, and J. Wright, Mixed state tomography reduces to pure state tomography, arXiv:2511.15806 (2025)

    work page arXiv 2025

  7. [7]

    S. Aaronson, Shadow tomography of quantum states, in Proceedings of the 50th Annual ACM SIGACT Sympo- sium on Theory of Computing, STOC 2018 (Association for Computing Machinery, New York, NY, USA, 2018) p. 325–338

    2018

  8. [8]

    Aaronson and G

    S. Aaronson and G. N. Rothblum, Gentle measurement of quantum states and differential privacy, inProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 (Association for Computing Machinery, New York, NY, USA, 2019) p. 322–333

    2019

  9. [9]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nature Physics16, 1050 (2020)

    2020

  10. [10]

    Acharya, I

    J. Acharya, I. Issa, N. V. Shende, and A. B. Wagner, Estimating quantum entropy, IEEE Journal on Selected Areas in Information Theory1, 454 (2020)

    2020

  11. [11]

    Cerezo, A

    M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles, Vari- ational Quantum Fidelity Estimation, Quantum4, 248 (2020)

    2020

  12. [12]

    K. C. Tan and T. Volkoff, Variational quantum algo- rithms to estimate rank, quantum entropies, fidelity, and fisher information via purity minimization, Phys. Rev. Res.3, 033251 (2021)

    2021

  13. [13]

    Goldfeld, D

    Z. Goldfeld, D. Patel, S. Sreekumar, and M. M. Wilde, Quantum neural estimation of entropies, Phys. Rev. A 109, 032431 (2024)

    2024

  14. [14]

    W. J. Huggins, K. Wan, J. McClean, T. E. O’Brien, N. Wiebe, and R. Babbush, Nearly optimal quantum al- gorithm for estimating multiple expectation values, Phys. Rev. Lett.129, 240501 (2022)

    2022

  15. [15]

    K. Wada, N. Yamamoto, and N. Yoshioka, Heisenberg- limited adaptive gradient estimation for multiple observ- ables, PRX Quantum6, 020308 (2025)

    2025

  16. [16]

    Koizumi, K

    Y. Koizumi, K. Wada, W. Mizukami, and N. Yoshioka, Faster quantum algorithm for multiple observables esti- mation, Phys. Rev. Lett.136, 080605 (2026)

    2026

  17. [17]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, inPro- ceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 (Association for Computing Machinery, New York, NY, USA, 2019) p. 193–204

    2019

  18. [18]

    G. H. Low and I. L. Chuang, Hamiltonian Simulation by Qubitization, Quantum3, 163 (2019)

    2019

  19. [19]

    Gily´ en and T

    A. Gily´ en and T. Li, Distributional Property Testing in a Quantum World, in11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Leibniz In- ternational Proceedings in Informatics (LIPIcs), Vol. 151, edited by T. Vidick (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2020) pp. 25:1–25:19

    2020

  20. [20]

    Gur, M.-H

    T. Gur, M.-H. Hsieh, and S. Subramanian, Sublinear quantum algorithms for estimating von neumann en- tropy, arXiv:2111.11139 (2021)

    work page arXiv 2021

  21. [21]

    Li and X

    T. Li and X. Wu, Quantum query complexity of entropy estimation, IEEE Transactions on Information Theory 65, 2899 (2019)

    2019

  22. [22]

    Subramanian and M.-H

    S. Subramanian and M.-H. Hsieh, Quantum algorithm for estimatingα-Renyi entropies of quantum states, Phys. Rev. A104, 022428 (2021)

    2021

  23. [23]

    Q. Wang, J. Guan, J. Liu, Z. Zhang, and M. Ying, New quantum algorithms for computing quantum entropies and distances, IEEE Transactions on Information Theory 70, 5653 (2024)

    2024

  24. [24]

    X. Wang, S. Zhang, and T. Li, A quantum algorithm framework for discrete probability distributions with ap- plications to R´ enyi entropy estimation, IEEE Transac- tions on Information Theory70, 3399–3426 (2024)

    2024

  25. [25]

    N. A. Nghiem and T.-C. Wei, Estimation of nonlinear physical quantities by measuring ancillas, Phys. Rev. A 112, 062412 (2025)

    2025

  26. [26]

    Wang and Z

    Q. Wang and Z. Zhang, Time-efficient quantum entropy estimator via samplizer, IEEE Transactions on Informa- tion Theory71, 9569 (2025)

    2025

  27. [27]

    Wang and Z

    Q. Wang and Z. Zhang, Fast quantum algorithms for trace distance estimation, IEEE Transactions on Infor- mation Theory70, 2720 (2024)

    2024

  28. [28]

    Gily´ en and A

    A. Gily´ en and A. Poremba, Improved quantum algo- rithms for fidelity estimation, arXiv:2203.15993 (2022)

    work page arXiv 2022

  29. [29]

    Q. Wang, Z. Zhang, K. Chen, J. Guan, W. Fang, J. Liu, and M. Ying, Quantum algorithm for fidelity estima- tion, IEEE Transactions on Information Theory69, 273 (2023)

    2023

  30. [30]

    Utsumi, Y

    T. Utsumi, Y. Nakata, Q. Wang, and R. Tak- agi, Quantum algorithms for Uhlmann transformation, arXiv:2509.03619 (2025)

    work page arXiv 2025

  31. [31]

    Gily´ en, S

    A. Gily´ en, S. Lloyd, I. Marvian, Y. Quek, and M. M. Wilde, Quantum algorithm for Petz recovery channels and pretty good measurements, Phys. Rev. Lett.128, 220502 (2022)

    2022

  32. [32]

    N. Liu, Q. Wang, M. M. Wilde, and Z. Zhang, Quantum algorithms for matrix geometric means, npj Quantum In- formation11, 101 (2025)

    2025

  33. [33]

    O. E. Barndorff-Nielsen and R. D. Gill, Fisher informa- tion in quantum statistics, Journal of Physics A: Mathe- matical and General33, 4481 (2000)

    2000

  34. [34]

    Y. Wang, B. Zhao, and X. Wang, Quantum algorithms for estimating quantum entropies, Phys. Rev. Appl.19, 044041 (2023)

    2023

  35. [35]

    K. Wada, J. Kato, H. Harada, and N. Yamamoto, State-to-hamiltonian conversion with a few copies, arXiv:2509.14791 (2025)

    work page arXiv 2025

  36. [36]

    K. Chen, Q. Wang, and Z. Zhang, A list of complexity bounds for property testing by quantum sample-to-query lifting, arXiv:2512.01971 (2025)

    work page arXiv 2025

  37. [37]

    Lloyd, M

    S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum prin- cipal component analysis, Nature physics10, 631 (2014)

    2014

  38. [38]

    Kimmel, C

    S. Kimmel, C. Y.-Y. Lin, G. H. Low, M. Ozols, and T. J. Yoder, Hamiltonian simulation with optimal sample com- plexity, npj Quantum Information3, 13 (2017). 13

    2017

  39. [39]

    Lin and Y

    L. Lin and Y. Tong, Heisenberg-limited ground-state en- ergy estimation for early fault-tolerant quantum comput- ers, PRX Quantum3, 010318 (2022)

    2022

  40. [40]

    K. Wan, M. Berta, and E. T. Campbell, Randomized quantum algorithm for statistical phase estimation, Phys. Rev. Lett.129, 030503 (2022). 14 Appendix A: Fourier series approximation of the Heaviside step function We review the Fourier series approximation of the Heaviside step function Θ(x) proposed by Wan et al. [40]. The Fourier coefficientsF j,d are exp...

    2022

  41. [41]

    We construct the polynomialF(x) as a product of the step function andx α−1, similar to the method in Ref

    Preparation First, in the preparation stage, we determine a bounding functionP α(δ) and a target value of the error tolerance η. We construct the polynomialF(x) as a product of the step function andx α−1, similar to the method in Ref. [24]. 15 From Ref. [28, Corollary 15], there exists an even real polynomialH(x) of degreeO δ−1 log (1/εpoly) , which provi...

  42. [42]

    Lemma 5(Search algorithm for (η, P α)-spectral cutoff).Letρbe an unknown but accessible quantum state

    Identification Here we introduce a search algorithm for the (η, P α)-spectral cutoff. Lemma 5(Search algorithm for (η, P α)-spectral cutoff).Letρbe an unknown but accessible quantum state. LetH be a Hamiltonian s.t.∥H∥ ≤1, and we have access to controlled Hamiltonian evolutione −iH. Letη∈(0,1/2]be a target value andϑ∈(0,1)be a failure probability. Forα >1...

  43. [43]

    Lemma 6(R´ enyi entropy (α >1) estimation).Letρbe anN-dimensional quantum state

    Estimation and total copy requirement Combining with the previous discussion, we finally obtain the complexity for estimating R´ enyi entropy. Lemma 6(R´ enyi entropy (α >1) estimation).Letρbe anN-dimensional quantum state. For a fixedα >1, ε∈(0,1/(α−1)]andϑ∈(0,1), R´ enyi entropy 1 1−α log(tr[ρα])can be estimated within additive errorεwith a success prob...