Pith. sign in

REVIEW 1 major objections 6 minor 37 references

Matrix inversion polynomials for the quantum singular value transformation

T0 review · 1 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read The paper claims to identify, in closed form, the degree-optimal odd polynomial approximating $1/x$ on $[-1,-1/\kappa]\cup[1/\kappa,1]$, with minimal error given by an exact formula.

desk verdict Useful closed-form optimal polynomial for QSVT inversion; the proof has a fixable gap around the normalization constraint. read the letter →

arxiv 2507.15537 v1 pith:LFPIR4EG submitted 2025-07-21 quant-ph

classification quant-ph MSC 41A1041A5081P68
keywords quantumsingularvaluetransformationmatrixinversionminimaxpolynomialapproximationChebyshevpolynomialslinearsystemsolverssignalprocessingdegree
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

Quantum matrix inversion via QSVT needs an odd polynomial that uniformly approximates $1/x$ on the two intervals $[-1,-1/\kappa]\cup[1/\kappa,1]$, and that polynomial's degree sets the circuit depth. This paper claims to identify the optimal polynomial in closed form: for odd degree $d=2n-1$ it gives the polynomial explicitly and proves that its worst-case error is exactly $\varepsilon_{2n-1}(a)=(1-a)^n/(a(1+a)^{n-1})$, with $a=1/\kappa$. The closed form turns degree selection into a single formula, so a practitioner can read off the minimum degree for any target $\varepsilon$ without an expensive numerical minimax search. It also enables a direct comparison showing that, for large $\kappa\log(\kappa/\varepsilon)$, the optimal polynomial has the smallest maximum magnitude on $[-1,1]$ among the methods considered, which lowers QSVT normalization overhead.

What carries the argument

The load-bearing object is the family $L_n(x;a)=2^{1-n}(T_n(x)+\frac{1-a}{1+a}T_{n-1}(x))$, a linear combination of Chebyshev polynomials that encodes the equioscillation structure of the minimax problem. The proof imports a weighted minimax theorem, stated as Theorem 2 of the cited reference, and specializes it to two weight nodes $\alpha_1=(1+a^2)/(a^2-1)$ and $\alpha_2=\infty$; the substitution $y=(2x^2-(1+a^2))/(1-a^2)$ turns approximation of $1/x$ on the two intervals into weighted polynomial approximation on $[-1,1]$. The identity $L_n(-(1+a^2)/(1-a^2);a)=(-1)^n 2^{2-n}a(1+a)^{n-2}/(1-a)^n$ fixes the denominator, and the recurrence $L_{n+1}(x)=xL_n(x)-\frac14 L_{n-1}(x)$, rescaled as $\mathcal{L}_n(x,a)=x\mathcal{L}_{n-1}(x,a)/\alpha(a)-\mathcal{L}_{n-2}(x,a)/(4\alpha(a)^2)$ with $\alpha(a)=(1+a)/(2(1-a))$, gives stable evaluation.

What would settle it

For a fixed example such as $a=1/4$ and $n=8$, evaluate the degree-15 formula on a fine grid over $[-1,-a]\cup[a,1]$, record its maximum deviation from $1/x$, and compare with the best degree-15 polynomial from an independent high-precision numerical minimax computation. If the formula's deviation exceeds the numerical optimum by more than tolerance, or if the degree predicted by $\varepsilon_{2n-1}(a)$ fails to achieve the claimed error, Theorem 1 is falsified.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1, stated as an exact minimax result rather than an approximation. For $a\in(0,1)$ and $d=2n-1$, the polynomial $$P_{2n-1}(x;a) = \frac{1}{x} - \frac{L_n\!\left(\frac{$2x^{2}$-(1+$a^{2}$)}{1-$a^{2}$};a\right)}{x\,L_n\!\left(-\frac{1+$a^{2}$}{1-$a^{2}$};a\right)}, \qquad L_n(x;a)=\frac{T_n(x)+\frac{1-a}{1+a}T_{n-1}(x)}{$2^{{n-1}}$},$$ is the odd degree-$(2n-1)$ polynomial minimizing $\lVert p(x)-1/x\rVert_{\infty}$ on $S(a)=[-1,-a]\cup[a,1]$, with minimal error $\varepsilon_{2n-1}(a)=(1-a)^n/(a(1+a)^{n-1})$. Solving this error formula for $n$ gives the minimum degree for any target $\varepsilon$, asymptotically $d\sim\kappa\log(\kappa/\varepsilon)$ with leading constant one. The proof maps $S(a)$ to $[-1,1]$ through $y=2x^2/(1-a^2)-(1+a^2)/(1-a^2)$ and specializes a weighted minimax theorem to the parameters $\alpha_1=(1+a^2)/(a^2-1)$ and $\alpha_2=\infty$.

Load-bearing premise

The load-bearing premise is that the imported weighted minimax theorem, with all its stated hypotheses, applies to the two-node specialization used in the proof; if the hypotheses are violated or the quoted theorem contains an unresolved misprint, the closed form may still approximate $1/x$ but its claimed optimality would not be established.

Editorial extensions

If this is right

  • For a target error $\varepsilon$, the minimum QSVT degree is $d=2n-1$ with $n=\left\lceil \frac{\log(1/\varepsilon)+\log(1/a)+\log(1+a)}{\log(1+a)-\log(1-a)} \right\rceil$, removing the need to search over degrees.
  • The degree asymptotics become $d\sim\kappa\log(\kappa/\varepsilon)$ with leading coefficient $1$, matching the optimal scaling for quantum linear solvers at the level of the polynomial approximation.
  • In the large $\kappa\log(\kappa/\varepsilon)$ regime, the optimal polynomial's maximum magnitude on $[-1,1]$ is smaller than that of the compared power-series, convex-optimization, and Chebyshev-iteration polynomials, reducing the cost of QSVT normalization.
  • The supplied Python implementation evaluates the polynomial in the Chebyshev basis via a stable recurrence, with runtime comparable to the fastest heuristic methods and orders of magnitude below numerical minimax preprocessing.

Reading between the lines

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

  • If the optimality proof is correct, the same weighted-minimax specialization could produce exact optimal polynomials for other two-interval QSVT targets, such as sign or soft-threshold functions, by changing the two weight parameters while keeping the same $L_n$ recurrence.
  • The leading coefficient one indicates that, within this uniform-error definition, no $1/x$ polynomial can improve the asymptotic QSVT query count; remaining savings would have to come from reducing the polynomial's maximum magnitude $M$ or from circuit-level implementation details.
  • The paper's own comparison leaves the small-parameter regime open: there, a slightly higher-degree polynomial with a smaller maximum could win once window-function cost is included, and a concrete benchmark against windowed variants would settle whether the optimal polynomial is always the best practical choice.
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

1 major / 6 minor

Summary. The paper claims an analytic shortcut to the optimal polynomial for quantum matrix inversion under QSVT. Theorem 1 states that the explicit polynomial P_{2n-1}(x;a), defined in terms of the polynomial L_n of Eq. (6), achieves the minimum uniform error epsilon_{2n-1}(a) = (1-a)^n/(a(1+a)^{n-1}) on the two-interval domain S(a)=[-1,-a] ∪ [a,1]. The paper compares this polynomial with Taylor-expansion, Chebyshev-iteration, and convex-optimization constructions, reporting that it requires lower degree and has competitive runtime and boundedness properties, and it supplies Python code in Appendix B. The main mathematical contribution is the proof of Theorem 1 in Appendix A, which is meant to close a gap in the authors' earlier conference announcement [9].

Significance. If Theorem 1 is correct, the paper provides the first closed-form minimax polynomial for the matrix-inversion primitive inside QSVT, eliminating the need for expensive Remez preprocessing and giving an exact degree formula with leading constant 1. The runtime comparisons and the released Python code are practical contributions that should be useful to practitioners. The derivation is not empirical: no free parameters are fitted, and the proof is a reduction to the external minimax theorem of Privalov [10], with a Mathematica-checked identity for the denominator. However, the proof as written contains a load-bearing gap in the optimality argument, so the central claim is not yet established.

major comments (1)
  1. [Appendix A, Proposition 2, Eqs. (A16)-(A18)] The proof that q_n = L_n/L_n(y0) is optimal is incomplete. Theorem 2 solves the unconstrained monic weighted-minimax problem: it minimizes ||r(y)/sqrt(w(y))|| over monic degree-n polynomials r(y). The actual task after the change of variable in Eq. (A15) is to minimize ||r(y)/sqrt(w(y))|| / |r(y0)| over monic r(y), because the side condition q(y0)=1 fixes the scale. The manuscript only shows that L_n minimizes the numerator of this ratio; it does not show that L_n also maximizes |r(y0)| relative to its norm. A different monic polynomial could have a slightly larger weighted norm but a substantially larger value at y0, yielding a smaller ratio. The missing step is an alternation argument: the affine space {q : deg q <= n, q(y0)=1} is an n-dimensional Haar space because y0 = -(1+a^2)/(1-a^2) < -1, and L_n(y)/L_n(y0), inheriting n+1 equioscillation points from L_n via Theorem 2, satisfies the alternation condition and is therefore the unique minimizer. Without this step, Theorem 1 is not proven.
minor comments (6)
  1. [Section II A, Theorem 1] The theorem statement should explicitly say that the minimization is over odd polynomials of degree at most 2n-1. The proof in Appendix A uses oddness essentially: only then is 1-xP(x) an even polynomial and hence a polynomial in y. As written, 'the polynomial p(x) of degree d minimizing the uniform error' could be misread as allowing even-degree terms.
  2. [Appendix A, proof of Proposition 2] The display 'min_{q_n(y) in R[y] | deg(q_n(y))=2n}' contains a typo: q_n(y) is a polynomial of degree n in y, not 2n. Also, the sentence 'The coefficient \bar q can be determined as \bar q = 1/L_n(...)' is confusing, since \bar q is fixed by the side condition only for the particular candidate L_n, not by the minimization.
  3. [Section II A, Eqs. (9)-(13)] The notation \mathcal{L}_n(x;a) versus L_n(x;a) is not defined clearly; please state explicitly that \mathcal{L}_n = L_n / \alpha(a)^n.
  4. [Appendix A, Proposition 6, Eq. (A27)] The exponent of 2 is inconsistent: the text has 2^{n-2} in one place while the Mathematica output gives 2^{2-n}. The latter matches the final error formula, so please correct the text.
  5. [Figure 3 caption] The caption notes that CVX and Remez runtimes are for a single run with fixed degree; please add the words 'single run' to the caption itself, since the figure legend alone does not convey this.
  6. [Section III, Eq. (26)] The notation 'max_{x in D_N = 25d}' is awkward; it would be clearer as 'with N = 25d'.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity; the optimality proof rests on an external minimax theorem, and the only self-citation is a non-load-bearing conference announcement.

full rationale

The central derivation of Theorem 1 is not circular. The optimal polynomial P_{2n-1}(x;a) and its error formula are obtained by specializing Privalov's Theorem 2, an external weighted-Chebyshev minimax result attributed to Bernstein, and then deriving the explicit Chebyshev representation L_n(x;a) via recurrences and initial conditions. The proof does not assume the target error formula or the optimality of P; it derives both from that imported theorem and elementary Chebyshev identities. The only self-citation is reference [9], a prior conference announcement of the same theorem, but the paper explicitly supplies a proof 'which was absent in [9]' and does not rely on [9] for any step. A possible gap concerning the side condition q_n(y0)=1 in Proposition 2 is a correctness or rigor concern about whether Theorem 2 has been applied correctly, not a circularity: even if the proof is incomplete, that does not make the conclusion equivalent to its inputs by construction. No fitted parameters are renamed as predictions, and no uniqueness claim is imported from the authors' own prior work. Accordingly, the circularity score is minimal, reflecting only the non-load-bearing self-citation.

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

No free parameters are fitted or hand-tuned; a = 1/kappa and epsilon are problem inputs. No new physical or mathematical entities are postulated. The central claim rests on Privalov's weighted minimax theorem plus standard Chebyshev identities.

assumptions (3)
  • standard math Theorem 2 of Privalov [10], attributed to Bernstein: the exact minimax polynomial for the weighted expression (sum c_j x^j + x^n)/sqrt(w(x)) with prescribed poles alpha_j.
    Imported as a known theorem in Appendix A. The optimality proof of Theorem 1 reduces to this result with N=2, alpha_1 = (1+a^2)/(a^2-1), alpha_2 = infinity. If this theorem is misquoted or its hypotheses fail, the optimality conclusion lacks support.
  • standard math Standard Chebyshev polynomial identities, including T_n(x) = (v_+(x)^n + v_-(x)^n)/2, and the recurrence L_{n+1} = x L_n - (1/4) L_{n-1}.
    Used in Propositions A3 through A6 to identify L_n(x; a) and compute the denominator value L_n(-(1+a^2)/(1-a^2); a). These identities are standard and low risk.
  • standard math The minimizer of uniform error against the odd function 1/x can be restricted to odd polynomials.
    Used implicitly in the reduction to q_n(y) = 1 - x P_{2n-1}(x) in Proposition 2. For an odd target, replacing any approximant by its odd part does not increase the uniform error on the symmetric domain S(a).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Matrix inversion polynomials for the quantum singular value transformation." pith.science (2026). https://pith.science/paper/LFPIR4EG

@misc{pith2026250715537,
  author       = {Pith},
  title        = {Pith review of: Matrix inversion polynomials for the quantum singular value transformation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LFPIR4EG}},
  note         = {Machine review of arXiv:2507.15537}
}
abstract

Quantum matrix inversion with the quantum singular value transformation (QSVT) requires a polynomial approximation to $1/x$. Several methods from the literature construct polynomials that achieve the known degree complexity $\mathcal{O}(\kappa\log(\kappa/\varepsilon))$ with condition number $\kappa$ and uniform error $\varepsilon$. However, the \emph{optimal} polynomial with lowest degree for fixed error $\varepsilon$ can only be approximated numerically with the resource-intensive Remez method, leading to impractical preprocessing runtimes. Here, we derive an analytic shortcut to the optimal polynomial. Comparisons with other polynomials from the literature, based on Taylor expansion, Chebyshev iteration, and convex optimization, confirm that our result is optimal. Furthermore, for large $\kappa\log(\kappa/\varepsilon)$, our polynomial has the smallest maximum value on $[-1,1]$ of all approaches considered, leading to reduced circuit depth due to the normalization condition of QSVT. With the Python code provided, this paper will also be useful for practitioners in the field.

Figures

Figures reproduced from arXiv: 2507.15537 by the authors.

Figure 1
Figure 1. FIG. 1. Example optimal polynomial Eq. (5) from Sec [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. FIG. 3. Runtime of generating polynomial coefficients in the [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. FIG. 4. Example optimal polynomial Eq. (5). Its maximum [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

37 extracted references · 21 canonical work pages

  1. [9]

    Y. Dong, L. Lin, and Y. Tong, Ground-state prepara- tion and energy estimation on early fault-tolerant quan- tum computers via quantum eigenvalue transformation of unitary matrices, PRX Quantum 3, 10.1103/prxquan- tum.3.040305 (2022)

  2. [10]

    B. K. Berntson and C. S¨ underhauf, Two exact quantum signal processing results, in 2024 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)(IEEE, 2024) p. 625–626

  3. [1]

    P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Bab- bush, and D. W. Berry, Optimal scaling quantum lin- ear systems solver via discrete adiabatic theorem (2021), arXiv:2111.08152 [quant-ph]

  4. [2]

    Jennings, M

    D. Jennings, M. Lostaglio, S. Pallister, A. T. Sornborger, and Y. Suba¸ sı, Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and de- tailed running costs (2025), arXiv:2305.11352 [quant-ph]

  5. [3]

    A. M. Dalzell, A shortcut to an optimal quantum linear system solver (2024), arXiv:2406.12086 [quant-ph]

  6. [4]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. Low, and N. Wiebe, Quantum Sin- gular Value Transformation and beyond: Exponential Improvements for Quantum Matrix Arithmetics, in Proc. Annu. ACM Symp. Theory Comput., STOC 2019 (Asso- ciation for Computing Machinery, New York, NY, USA,

  7. [5]

    ChebIter

    and “ChebIter” [17] polynomials. Figure 5 shows the estimated M ≈ 1.001 maxx∈DN |p(x)|, which is provably accurate up to ca. 0 .1%. The optimal polynomial has smallest maximum in the large κ log(κ/ε) regime. How- ever, in the small κ log(κ/ε) regime, it could be favor- able to use another polynomial depending on the degree tradeoff between 1 /x polynomial...

  8. [6]

    A. M. Childs, R. Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponen- tially improved dependence on precision, SIAM Journal on Computing 46, 1920–1950 (2017)

Show all 37 references
  1. [7]

    Gribling, I

    S. Gribling, I. Kerenidis, and D. Szil´ agyi, An opti- mal linear-combination-of-unitaries-based quantum lin- ear system solver, ACM Transactions on Quantum Com- puting 5, 10.1145/3649320 (2024)

  2. [8]

    Y. Dong, X. Meng, K. B. Whaley, and L. Lin, Effi- cient phase-factor evaluation in quantum signal process- ing, Phys. Rev. A 103, 042419 (2021)

  3. [11]

    Privalov, Approximation of 1 /x by polynomials on [−1, −a] ∪ [a, 1], Math

    I. Privalov, Approximation of 1 /x by polynomials on [−1, −a] ∪ [a, 1], Math. Notes 81, 415 (2007)

  4. [12]

    L. Trefethen, Approximation Theory and Approximation Practice, Extended Edition (Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019) https://epubs.siam.org/doi/pdf/10.1137/1.9781611975949

  5. [13]

    QSPPACK contributors, Remez.ipynb – juliasolver notebook, https://github.com/qsppack/QSPPACK/ blob/aeed1c9f0b46a8a548efd5a078899c3547ed8a28/ Solvers/JuliaSolver/Remez.ipynb (2023), accessed: 2025-06-05

  6. [14]

    Quantum linear system problems, QSPPACK Documen- tation (2025), accessed: 2025-06-11

  7. [15]

    Diamond and S

    S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, Journal of Machine Learning Research 17, 1 (2016)

  8. [16]

    Agrawal, R

    A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd, A rewriting system for convex optimization problems, Jour- nal of Control and Decision 5, 42 (2018)

  9. [17]

    Martyn, Z

    J. Martyn, Z. Rossi, A. Tan, and I. Chuang, Grand Unifi- cation of Quantum Algorithms, PRX Quantum2, 040203 (2021)

  10. [19]

    (17) and its truncation in- troduce an error ε, so we have halved it in Eq

    Note that in the literature, b and D are described such that both approximations Eq. (17) and its truncation in- troduce an error ε, so we have halved it in Eq. (17) to keep the overall error at ε in line with our convention

  11. [20]

    I. Chuang and contributors, pyqsp: Python package for quantum signal processing, https://github.com/ichuang/pyqsp/blob/ 834520bad0030d260b303fb238ba3ba4899f7300/pyqsp/ poly.py#L238 (2024), accessed: 2025-06-12

  12. [21]

    See arxiv:2109.04248 for an older arxiv version of [6]

  13. [22]

    Pfister and Y

    L. Pfister and Y. Bresler, Bounding multivariate trigono- metric polynomials with applications to filter bank design (2018), arXiv:1802.09588 [eess.SP]

  14. [23]

    Aaronson, Read the fine print, Nature Phys

    S. Aaronson, Read the fine print, Nature Phys. 11, 291 (2015)

  15. [24]

    G. H. Low, V. Kliuchnikov, and L. Schaeffer, Trading t gates for dirty qubits in state preparation and unitary synthesis, Quantum 8, 1375 (2024)

  16. [25]

    K. Gui, A. M. Dalzell, A. Achille, M. Suchara, and F. T. Chong, Spacetime-efficient low-depth quantum state preparation with applications, Quantum 8, 1257 7 (2024)

  17. [26]

    O’Brien and C

    O. O’Brien and C. S¨ underhauf, Quantum state prepara- tion via piecewise QSVT, Quantum 9, 1786 (2025)

  18. [27]

    Chakraborty, A

    S. Chakraborty, A. Gily´ en, and S. Jeffery, The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019)

  19. [28]

    S¨ underhauf, E

    C. S¨ underhauf, E. Campbell, and J. Camps, Block- encoding structured matrices for data input in quantum computing, Quantum 8, 1226 (2024)

  20. [29]

    Q. T. Nguyen, B. T. Kiani, and S. Lloyd, Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra, Quan- tum 6, 876 (2022)

  21. [30]

    Lapworth and C

    L. Lapworth and C. S¨ underhauf, Preconditioned block encodings for quantum linear systems (2025), arXiv:2502.20908 [quant-ph]

  22. [31]

    Patterson and L

    A. Patterson and L. Lapworth, Measurement schemes for quantum linear equation solvers, Quantum Science and Technology 10, 025037 (2025)

  23. [32]

    Akahoshi, K

    Y. Akahoshi, K. Maruyama, H. Oshima, S. Sato, and K. Fujii, Partially fault-tolerant quantum comput- ing architecture with error-corrected clifford gates and space-time efficient analog rotations, PRX Quantum 5, 10.1103/prxquantum.5.010337 (2024)

  24. [33]

    B. K. Berntson and C. S¨ underhauf, Complementary polynomials in quantum signal processing, Communica- tions in Mathematical Physics 406, 10.1007/s00220-025- 05302-9 (2025)

  25. [34]

    Alexis, L

    M. Alexis, L. Lin, G. Mnatsakanyan, C. Thiele, and J. Wang, Infinite quantum signal processing for arbitrary szego functions (2024), arXiv:2407.05634 [quant-ph]

  26. [35]

    Ni and L

    H. Ni and L. Ying, Fast phase factor finding for quantum signal processing (2024), arXiv:2410.06409 [quant-ph]

  27. [36]

    Laneve, Generalized quantum signal processing and non-linear fourier transform are equivalent (2025), arXiv:2503.03026 [quant-ph]

    L. Laneve, Generalized quantum signal processing and non-linear fourier transform are equivalent (2025), arXiv:2503.03026 [quant-ph]

  28. [37]

    H. Ni, R. Sarkar, L. Ying, and L. Lin, Inverse nonlin- ear fast Fourier transform on SU(2) with applications to quantum signal processing (2025), arXiv:2505.12615 [quant-ph]

  29. [38]

    ""Compute optimal polynomial approximating 1/x

    L. Laneve, nlft-qsp, https://github.com/ LorenzoLaneve/nlft-qsp (2025), accessed: 2025-07-14. Appendix A: Optimal approximation of the function1/x In this appendix we prove the analytic result Theorem 1 for the optimal polynomial in Section II A, based on [10]. While the refer...

Pith tools

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