betaFeedback

WorksPhysics and Astronomy

Degree and normalization frontiers for bounded QSVT inversion

Abstract

Quantum singular value transformation (QSVT) implements matrix inversion using bounded polynomials. Increasing polynomial degree can improve normalization and reduce amplified query cost, with savings that depend on the error criterion. However, existing bounded methods either fix the normalization or work far below the condition numbers of fault-tolerant resource estimates. We therefore analyze this trade-off for absolute reciprocal error, which controls inverse-operator accuracy, and for residual error, which suffices for normalized linear solves. For absolute reciprocal error, we establish a scaling limit to a constrained least-norm problem for entire functions and characterize its high-accuracy frontier using elliptic integrals. Constructions built from near-optimal limiting functions achieve certified query-cost savings over the rescaled minimax baseline of at least 11.8 percent at condition number ten thousand with error one millionth, and at least 22.8 percent at one million with error one ten-billionth. A simpler two-term rule also has certified savings, and its phase factors at condition number ten thousand pass numerical checks at selected points. For residual error, a sparse Chebyshev construction achieves certified savings over the residual-minimax baseline of at least 8.7 percent at condition number ten thousand with normalized-state error at most one hundred-millionth, and at least 13.1 percent at one million with error at most one ten-billionth. These results quantify the saving that a joint choice of degree and normalization gives beyond the minimax baselines.

Introduction

Quantum algorithms for linear systems, Green’s functions and related linear-algebra tasks often require implementing a matrix inverse from a block-encoding. Quantum singular value transformation (QSVT) enables this operation by applying a polynomial approximation of the reciprocal function to the singular values of the encoded matrix [1, 2]. However, QSVT requires the polynomial to be bounded in magnitude by one on [−1,1][-1,1]. If qq approximates 1/x1/x on [1/κ,1][1/\kappa,1] for condition number κ\kappa, QSVT implements a scaled polynomial cqcq, where the normalization cc cannot exceed the reciprocal of the maximum of ∣q∣|q| on [0,1][0,1]. With amplitude amplification, the query cost depends on both the polynomial degree and the inverse norm 1/c1/c. Minimizing degree alone therefore need not minimize the total query cost.

Existing approaches address this constraint in different ways. Explicit constructions enforce boundedness by design [1, 3]. For example, Gilyén et al. multiply the polynomial of Childs, Kothari and Somma by a rectangle function, with normalization 1/(2κ)1/(2\kappa) [1]. In contrast, the minimax polynomial minimizes the uniform approximation error for a fixed degree and is known in closed form [4, 5]. Its approximation properties are related to classical two-interval results, whose asymptotics Eremenko and Yuditskii attribute to Akhiezer [6]. At equal error, the fitted degree of the minimax polynomial is smaller than that of the Childs–Kothari–Somma construction by a factor of about 2.62.6 [5]. However, inside the spectral gap (0,1/κ)(0,1/\kappa) it exceeds κ\kappa by a factor that grows slowly with increasing accuracy. The additional normalization required for QSVT consequently offsets part of its degree advantage. This tension suggests a different strategy. A higher degree can reduce the polynomial’s maximum magnitude, which allows a larger normalization and can lower the amplified query cost.

Although this trade-off has been recognized, its quantitative behavior remains poorly understood at large condition numbers. S¨underhauf et al. discuss the balance between degree, maximum magnitude and windowing cost, but regard an analytic treatment as impractical [5]. Numerical approaches have also explored bounded polynomial design. Dong, Larsen, Lin and Sarkar use constrained Remez and nonlinear Fourier methods at condition number ten with fixed normalization 1/κ1/\kappa [7]. Their constrained Remez method checks candidate extrema numerically. Their nonlinear Fourier retraction instead returns phase factors whose polynomial is bounded by one on the full interval in exact arithmetic. This bound does not by itself certify the approximation error of the realized polynomial. Deiml and Peterseim choose the polynomial and its normalization jointly for an L2L^2 error, at condition numbers 3 and 5 and degrees up to 16 [8]. Adhikari formulates an L2L^2 problem with a bound on the polynomial maximum [9]. These studies leave open the potential savings from jointly optimizing degree and normalization in the high-condition-number regime.

The error criterion is particularly important in this regime. Fault-tolerant resource estimates consider condition numbers up to 10610^6 with stringent normalized-state accuracy requirements [10, 11]. However, a normalized-state error target does not directly specify the required absolute accuracy of the inverse operator. We therefore distinguish two criteria: absolute reciprocal error (criterion A), which controls inverse-operator accuracy, and residual error (criterion B), which suffices for normalized linear solves. Each criterion has its own known minimax baseline [5]. The saving from a joint choice of degree and normalization is therefore assessed separately under each criterion.

In this work, we quantify this trade-off with a query cost proportional to polynomial degree divided by normalization. Our analysis characterizes the scaling limit under criterion A and establishes certified finite-condition-number savings under both criteria. Each gain we report is measured against the minimax baseline for the same error criterion. Our main contributions are as follows:

  1. We establish a scaling limit for criterion A as the condition number grows with the error held fixed relative to the condition number. In this limit the least feasible polynomial norm, divided by the condition number, converges to the optimum of an extremal problem for entire functions subject to an error constraint outside a fixed gap. We also identify its feasibility threshold. While classical limit theorems connect polynomial approximation errors to entire-function approximation [12, 13], our result concerns minimizing the norm under a prescribed error constraint.

  1. We characterize the high-accuracy frontier of the limiting problem using elliptic integrals and derive the optimal asymptotic cost constant, 2.9492. The leading term of the limiting gain is 0.1530 times the square root of the logarithm of the condition-number-to-error ratio.

  1. This leading term exceeds one only when that logarithm exceeds 42.7, so at practical accuracies we certify two-sided bounds on the optimal limiting gain directly, at five accuracy levels. The near-optimal entire functions used in our finite constructions achieve limiting gains within 0.1 percent of this optimal gain.

  1. We compute finite degree–normalization frontiers under both criteria at condition numbers 20 and 40. We further develop a simpler two-term rule, perform selected-point phase checks, examine windowing costs and evaluate polynomial substitutions in two reproduced cells of a published query model. The near-optimal constructions under criterion A have certified query-cost savings over the rescaled minimax baseline of at least 11.8 percent at condition number 10410^4 with error 10−610^{-6}, and at least 22.8 percent at 10610^6 with error 10−1010^{-10}. The sparse Chebyshev construction under criterion B has certified savings over the residual-minimax baseline of at least 8.7 percent at condition number 10410^4 with normalized-state error at most 10−810^{-8}, and at least 13.1 percent at 10510^5 and 10610^6 with error at most 10−1010^{-10}.

The study map below summarizes the three questions these results address, with the corresponding analyses and evidence.

QuestionAnalysis and sectionEvidence and scope
How much does joint optimization save?Linear programs (III) and finite constructions (V)Numerical frontiers and certified savings under criteria A and B
How do savings depend on accuracy and condition number?Entire-function limit and asymptotic frontier (IV)Distinct limiting regimes and certified bounds at errors held fixed relative to the condition number
What is required for implementation and use?Phase factors (V.C), windowing (VI) and cost models (VII)Selected-point phase checks, specified window comparisons and conditional application estimates

Table 1. Study map.

The Supplemental Material provides the proofs, certificates and computational details in Sections S1–S12. The supplement and verification set accompany the arXiv version as ancillary files. Appendix § 15 describes the programs, the verification records and their availability.

Problem setting and cost model

Let a=1/κa=1/\kappa. We consider odd polynomials in the span of the first mm odd Chebyshev terms,

q(x)=∑k=0m−1ckT2k+1(x),(1)q(x)=\sum_{k=0}^{m-1}c_kT_{2k+1}(x), \tag*{(1)}

whose degree is at most 2m−12m-1. Under criterion A, such a qq is feasible for absolute reciprocal error ε\varepsilon when

∣q(x)−1/x∣≤εfor all x∈[a,1].(2)|q(x)-1/x|\le\varepsilon\qquad\text{for all }x\in[a,1]. \tag*{(2)}

The error ε\varepsilon bounds q−1/xq-1/x itself, not its ratio to 1/x1/x. For a matrix AA with ∥A∥≤1\|A\|\le1 and ∥A−1∥≤κ\|A^{-1}\|\le\kappa, the inversion algorithm applies qq to the singular values of AA, which lie in [a,1][a,1]. For A=UΣV†A=U\Sigma V^\dagger, QSVT applied to a block-encoding of A†A^\dagger gives Vq(Σ)U†Vq(\Sigma)U^\dagger, which approximates A−1=VΣ−1U†A^{-1}=V\Sigma^{-1}U^\dagger. The computed vector therefore differs from A−1bA^{-1}b by at most ε∥b∥≤ε∥A−1b∥\varepsilon\|b\|\le\varepsilon\|A^{-1}b\|. Hence ε\varepsilon bounds the relative error of the solution vector. In a solve we take ε<1\varepsilon<1, so the computed vector is nonzero. Since the circuit applies cqcq and the solution state is normalized, the error of the normalized solution state does not depend on the normalization. This error is at most 2ε2\varepsilon. The bounded frontier is

M(m,ε)=min⁡{max⁡x∈[0,1]∣q(x)∣:q feasible}.(3)M(m,\varepsilon)=\min\left\{\max_{x\in[0,1]}|q(x)|:q\text{ feasible}\right\}. \tag*{(3)}

Because qq is odd, its maximum over [0,1][0,1] equals its maximum over [−1,1][-1,1]. QSVT can therefore implement cqcq with c=1/Mc=1/M.

Cost model. In a linear solve with amplitude amplification and a unit vector bb, the QSVT circuit prepares the solution state with an amplitude equal to cc times the norm of the computed vector. By the bound above, this norm lies within a factor 1±ε1\pm\varepsilon of ∥A−1b∥\|A^{-1}b\|, which is common to all polynomials. The amplitude is therefore proportional to cc up to this factor. The number of amplification rounds is proportional to 1/c1/c. Each round uses a transformation of degree at most 2m−12m-1. We count its query budget as 2m−12m-1, so the amplified query budget is proportional to (2m−1)/c(2m-1)/c. We use

C(m)=mM(m,ε)(4)C(m)=mM(m,\varepsilon) \tag*{(4)}

as the cost. We assume that the block-encoding of AA is exact and count each query to it at the same cost. The certified savings do not cover errors in AA or in its block-encoding. State preparation adds the same cost to every amplification round. Including it would raise the gains, because the bounded polynomials need fewer rounds. Leaving it out is therefore conservative. The norm of the computed vector can change a ratio of two solve costs by a factor between (1−ε)/(1+ε)(1-\varepsilon)/(1+\varepsilon) and its reciprocal. At the certified points of § 5 this factor differs from one by less than 3×10−63\times10^{-6}. Section VII discusses uses of the inverse in which the cost depends on cc differently.

Baseline. The minimax polynomial without the bound is known in closed form [5]. Sec. S1 proves the value of its error. With t(y)=(2y−(1+a2))/(1−a2)t(y) = (2y - (1 + a^2))/(1 - a^2), β=(1−a)/(1+a)\beta= (1 - a)/(1 + a) and ℓm=Tm+βTm−1\ell_m = T_m + \beta T_{m-1},

qm∗(x)=1x[1−ℓm(t(x2))ℓm(t(0))],Em=max⁡x∈[a,1]∣qm∗(x)−1/x∣=(1−a)ma(1+a)m−1.(5)q_m^*(x) = \frac{1}{x}\left[1-\frac{\ell_m(t(x^2))}{\ell_m(t(0))}\right], \qquad E_m = \max_{x\in[a,1]}\left|q_m^*(x)-1/x\right| = \frac{(1-a)^m}{a(1+a)^{m-1}}. \tag*{(5)}

Let mum_u be the least mm with Em≤εE_m \le\varepsilon. Let ρu=max⁡[0,1]∣qmu∗∣/κ\rho_u = \max_{[0,1]} |q_{m_u}^*|/\kappa be the overshoot of this polynomial in units of κ\kappa. The rescaled minimax polynomial qmu∗/(ρuκ)q_{m_u}^*/(\rho_u\kappa) is realizable and costs muρuκm_u\rho_u\kappa. In the gap qm∗q_m^* grows pointwise with mm (Corollary S1.4). At every criterion-A parameter point where this paper reports a gain, ball arithmetic gives qmu∗(3a/4)>κ+εq_{m_u}^*(3a/4) > \kappa+\varepsilon (program overshoot-scan.py). The right-hand side bounds ∣qmu∗∣|q_{m_u}^*| over [a,1][a,1]. The maximum therefore lies in the gap. Every qm∗q_m^* with m>mum > m_u then has norm at least ρuκ\rho_u\kappa and a larger rescaled cost. Hence mum_u is also the best degree for rescaling. We report the gain

G(κ,ε)=muρuκmin⁡m≥mumM(m,ε)≥1.(6)G(\kappa,\varepsilon) = \frac{m_u\rho_u\kappa}{\min_{m\ge m_u}mM(m,\varepsilon)} \ge1. \tag*{(6)}

A gain GG is a cost reduction by the fraction 1−1/G1-1/G. Using (2m−1)M(2m-1)M instead of (4) lowers every criterion-A gain below by a relative amount of at most 1/(6mu−2)1/(6m_u-2) over the degrees we compare, m≤1.5mum \le1.5m_u. This amount is about 10−310^{-3} in Table I, below 1.5×10−61.5 \times10^{-6} at κ=104\kappa=10^4 and below 10−710^{-7} at κ=105\kappa=10^5 and 10610^6.

η\etaLLmu/κm_u/\kappaGG, κ=20\kappa=20GG, κ=40\kappa=40m∗/mum^*/m_uρuκ/M\rho_u\kappa/Mcost reduction
10−710^{-7}16.128.071.0401.0351.271.323.4–3.9%
10−810^{-8}18.429.221.0771.0691.241.33–1.346.5–7.2%
3×10−93 \times10^{-9}19.629.821.0921.0931.241.368.4–8.5%
10−910^{-9}20.7210.381.1011.0991.241.36–1.379.0–9.1%
3×10−103 \times10^{-10}21.9310.971.1261.1171.211.35–1.3710.5–11.2%
10−1010^{-10}23.0311.531.1371.1371.211.3812.0–12.1%

Table I. LP estimate of the gain of the bounded optimum over the rescaled minimax polynomial under criterion A.

Criterion B and its baseline. Alternatively, require ∣xq(x)−1∣≤δ|xq(x)-1| \le\delta on [a,1][a,1], with 0<δ<10 < \delta< 1. If Q=Vq(Σ)U†Q = Vq(\Sigma)U^\dagger, then

Q−A−1=V(Σq(Σ)−I)V†A−1.Q-A^{-1}=V\left(\Sigma q(\Sigma)-I\right)V^\dagger A^{-1}.

Thus ∥(Q−A−1)b∥≤δ∥A−1b∥\|(Q-A^{-1})b\| \le\delta\|A^{-1}b\|, the normalized-state error is at most 2δ2\delta in the 2-norm, and ∥Q−A−1∥≤κδ\|Q-A^{-1}\| \le\kappa\delta. The cost model above applies with 1±δ1\pm\delta in place of 1±ε1\pm\varepsilon.

Matrix functions, absolute-error matrix elements and products of inverse block-encodings need the operator guarantee of AA [14 Theorems 17 and 23 and Sec. 3.2], as does the operator-norm statement of Gilyén et al. [1, Theorem 41]. Normalized solves [3, 10, 11, 15, 16] need only B after conversion to the state norm in question. Our 2δ2\delta bound uses the 2-norm and does not identify it with a 1-norm or trace-distance target.

The residual-minimax polynomial is [5 Eq. (21)]

qR,m(x)=1−Tm(t(x2))/Tm(t(0))x,∥xqR,m−1∥[a,1]=sech⁡(2martanh⁡a).q_{R,m}(x)=\frac{1-T_m(t(x^2))/T_m(t(0))}{x}, \qquad\|xq_{R,m}-1\|_{[a,1]}=\operatorname{sech}(2m\operatorname{artanh}a).

Its least feasible number of odd terms is mR=⌈arcosh⁡(1/δ)/(2artanh⁡a)⌉m_R=\left\lceil\operatorname{arcosh}(1/\delta)/(2\operatorname{artanh}a)\right\rceil. Write ρR=∥qR,mR∥[0,1]/κ\rho_R=\|q_{R,m_R}\|_{[0,1]}/\kappa. For a feasible degree-2m−12m-1 polynomial of norm at most MM, we report GB=mRρRκ/(mM)G_B=m_R\rho_R\kappa/(mM). The Chebyshev window of Section VI is xqR,ℓ(x)xq_{R,\ell}(x).

The choice of error criterion changes the comparison. At the three criterion-A points of Table III, equal state guarantees mean δ=ε\delta=\varepsilon. Then qRq_R costs 0.499 to 0.568 times the rescaled A minimax polynomial and 0.567 to 0.722 times our A near-optimal construction. At equal operator error, δ=ε/κ\delta=\varepsilon/\kappa, our A construction is 1.17 to 1.32 times cheaper than qRq_R. These are numerical evaluations of the stated cost model. We use no other pairing for a comparison of costs across the criteria.

κ\kappaconstructionodd termsM/κM/\kappa, upperGG, lowerCKS factor
10410^{4}CKS times rectangle, 1/(2κ)1/(2\kappa)290 9332–1
rescaled minimax (baseline)mu=115 130m_u = 115\,130ρu=2.21947\rho_u = 2.2194712.27
near-optimal, 321 coefficients139 6711.6119301.134972.58
two-term family, rule (16)142 2231.6252581.105462.51
10510^{5}CKS times rectangle, 1/(2κ)1/(2\kappa)4 196 1782–1
rescaled minimax (baseline)mu=1 726 940m_u = 1\,726\,940ρu=2.69590\rho_u = 2.6959011.80
near-optimal, 321 coefficients2 224 2481.6460301.271622.29
two-term family, rule (16)2 015 1031.9131701.207612.17
10610^{6}CKS times rectangle, 1/(2κ)1/(2\kappa)45 279 2902–1
rescaled minimax (baseline)mu=18 420 682m_u = 18\,420\,682ρu=2.78144\rho_u = 2.7814411.76
near-optimal, 321 coefficients23 437 8241.6865931.296132.29
two-term family, rule (16)21 330 6511.9654891.222082.16

Table III. Certified target polynomials under criterion A.

Scaling variables. We write μ=m/κ\mu=m/\kappa, η=ε/κ\eta=\varepsilon/\kappa and L=ln⁡(1/η)=ln⁡(κ/ε)L=\ln(1/\eta)=\ln(\kappa/\varepsilon). We call η\eta the scaled error because it compares ε\varepsilon with the largest value κ\kappa of 1/x1/x on [a,1][a,1]. Because aEm≈e−2μaE_m\approx e^{-2\mu} for small aa, the minimal unbounded degree satisfies mu/κ≈L/2m_u/\kappa\approx L/2. We write μu=L/2\mu_u=L/2. At κ=104\kappa=10^4 with ε=10−6\varepsilon=10^{-6}, L=23.0L=23.0 and mu/κ=11.5m_u/\kappa=11.5. At κ=106\kappa=10^6 with ε=10−10\varepsilon=10^{-10}, L=36.8L=36.8 and mu/κ=18.4m_u/\kappa=18.4. The degree 2mu−12m_u-1 is then 3.7×1073.7\times10^7. In the same limit the overshoot of the minimax polynomial tends to

ρ∞(μ)=max⁡0≤s≤1h2μ(s),hσ(s)=1−e−σ[cosh⁡(σw)+wsinh⁡(σw)]s,w=1−s2.(7)\rho_\infty(\mu)=\max_{0\le s\le1}h_{2\mu}(s), \qquad h_\sigma(s)=\frac{1-e^{-\sigma}\left[\cosh(\sigma w)+w\sinh(\sigma w)\right]}{s}, \qquad w=\sqrt{1-s^2}. \tag*{(7)}

where s=xκs=x\kappa is the scaled gap coordinate. For large μ\mu, ρ∞(μ)∼c0μ\rho_\infty(\mu)\sim c_0\sqrt{\mu} with c0=(1−e−z0)/z0=0.6381726863c_0=(1-e^{-z_0})/\sqrt{z_0}=0.6381726863 and ez0=1+2z0e^{z_0}=1+2z_0 (Sec. S4). At finite κ\kappa we evaluate ρu\rho_u from (5). It equals 2.69590 at (κ,ε)=(105,10−10)(\kappa,\varepsilon)=(10^5,10^{-10}) and 2.78144 at (106,10−10)(10^6,10^{-10}).

Measured trade-off

Method. This section measures the gain (6) directly, by linear programs at condition numbers up to 40. For given (m,ε)(m,\varepsilon) we solve (3) as a linear program in the coefficients ckc_k and the bound MM. The error constraint is imposed on a finite set of points of [a,1][a,1]. The bound constraint is imposed on a finite set of points of [0,1][0,1]. Both sets grow by cutting planes taken from a verification grid. The grid uses all Chebyshev nodes of the full degree and, in addition, Chebyshev nodes mapped onto [a,1][a,1] and clustered at x=ax=a. The clustering is needed because the error of the extremal oscillates near x=ax=a on a scale far below the node spacing of [−1,1][-1,1]. The large local maxima of the error and of ∣q∣|q| on the grid are refined by golden-section search. We use HiGHS 1.15.1 [17] with one thread, scaled iterative refinement and a continuation in ε\varepsilon. The reported MM is the Ehlich–Zeller upper bound computed from the values at Chebyshev nodes [18]. It exceeds the attained maximum by at most 3.1×10−43.1 \times10^{-4} relative. We compute ρu\rho_u with the same bound. This factor therefore cancels in GG to about 10−510^{-5}. Accepted solutions satisfy (2) on the verification grid to within 10−510^{-5} relative plus a floor of 4×10−15max⁡∣1/x∣4 \times10^{-15}\max|1/x|. At η=10−10\eta=10^{-10} the floor amounts to 4×10−54 \times10^{-5} relative. As a control, the program reproduces the exact error EmE_m of (5) within 4.2×10−64.2 \times10^{-6} relative in all 9 tested cases, at κ∈{10,30,100}\kappa\in\{10,30,100\} and mm from 10 to 900. Six further controls of the node evaluation and of the Ehlich–Zeller bound also pass. Double precision limits the method to η≥10−10\eta\ge10^{-10}. Sec. S10 gives the details.

Result. Table I reports the gain at κ=20\kappa=20 and 40. Its column mu/κm_u/\kappa is the scaled minimal unbounded number of terms at κ=40\kappa=40. The column m∗/mum^*/m_u is the degree ratio at the minimum cost on the grid. The column ρuκ/M\rho_u\kappa/M is the increase of the normalization at that degree. In the table, GG and the cost reduction 1−1/G1-1/G are computed from the unrounded gains and rounded down. At η=10−10\eta=10^{-10} and κ=40\kappa=40, 9 of the 12 grid points converged. For each η\eta the minimum over mm is taken on a grid of twelve values of m/mum/m_u from 1 to 1.5. A minimum over a grid can only overestimate the least cost. Up to the stated tolerances, each reported GG therefore underestimates (6). The LP estimate of the bounded optimum lowers the cost by 3.4 to 12.1 percent. The gain rises steadily with LL. The gains at the two condition numbers agree within 0.009 in GG. In four of the six rows GG is slightly lower at κ=40\kappa=40.

The certified point κ=104\kappa=10^4 with ε=10−6\varepsilon=10^{-6} of § 5 has L=23.03L=23.03, as in the last row of the table. Two condition numbers do not fix the gain at κ=104\kappa=10^4. As κ\kappa grows at fixed η\eta, the gain converges to the limiting gain of Section IV. At this LL the limiting gain lies between 1.1382 and 1.1387. Table III gives certified values at κ=104\kappa=10^4 for a near-optimal construction and for the two-term rule.

Mechanism. At the minimal degree mum_u itself, the LP estimate improves on the overshoot ρu\rho_u by at most 0.14 percent in this range. The larger gains in Table I therefore require a higher degree. The cost-optimal polynomial uses 21 to 27 percent more degree than mum_u and in return raises the normalization by 31 to 38 percent. Below mu/κ=7m_u/\kappa=7 the gain is at most 1.01, because the overshoot ρu\rho_u is itself small.

δ\deltaGB, κ=20G_{\mathrm{B}},\ \kappa=20GB, κ=40G_{\mathrm{B}},\ \kappa=40m∗/mRm^{*}/m_{\mathrm{R}}
10−710^{-7}1.04671.05111.27
10−810^{-8}1.08421.08931.24
3×10−93 \times10^{-9}1.10711.10501.23
10−910^{-9}1.11551.11911.22
3×10−103 \times10^{-10}1.13521.13331.21
10−1010^{-10}1.14251.14401.20

Table 2. LP estimates under criterion B.

The sign function behaves differently. At fixed degree, we obtain a bounded minimax polynomial for the odd sign function by dividing the unbounded minimax polynomial by one plus its uniform error. This comparison indicates that the large values of 1/x1/x near the gap account for the gain above. It does not compare costs across degrees.

Proposition 1. For 0<ϑ<10 < \vartheta< 1, let Λ\Lambda be the least uniform error on [ϑ,1][\vartheta,1] of an odd polynomial with mm odd terms approximating the constant 1, and assume Λ<1\Lambda< 1. Among such polynomials that are also bounded by one in magnitude on [−1,1][-1,1], the least error on [ϑ,1][\vartheta,1] is exactly 2Λ/(1+Λ)2\Lambda/(1+\Lambda). It is attained by the unbounded minimax polynomial divided by 1+Λ1+\Lambda.

The proof is in Appendix § 11. Linear programs at ϑ∈{0.01,0.02,0.05,0.1}\vartheta\in\{0.01, 0.02, 0.05, 0.1\} agree with 2Λ/(1+Λ)2\Lambda/(1+\Lambda) within 2.1×10−52.1 \times10^{-5} relative in 46 of 48 cases. The other two lie at the double-precision floor (Sec. S10). The bound costs about ln⁡2/(2artanh⁡ϑ)\ln2/(2\operatorname{artanh}\vartheta) additional odd terms. At ϑ=0.01\vartheta= 0.01 this is 17 percent of the degree at error 10−210^{-2} and 4 percent at 10−810^{-8} in our linear programs. We did not find this identity in the sources we searched. It may nevertheless be known. For the reciprocal no such reduction holds, because the unbounded extremal overshoots inside the gap to ρuκ\rho_{u\kappa}, far above its values on [a,1][a,1].

Residual-error frontier. Table II gives the counterpart under B. The LP uses t(x2)t(x^2) as its variable, so it constrains the residual directly. A formulation in xx loses accuracy when coefficients of order κ\kappa cancel to a residual of order δ\delta, and fails at δ≤10−9\delta\leq10^{-9}. These are LP estimates of the bounded optimum. They are not interval certificates. The gains use the Ehlich–Zeller norm bound. The residual Ehlich–Zeller upper bounds of the LP solutions exceed δ\delta by up to 0.031 percent. At δ=10−6\delta= 10^{-6} the estimated gains are 1.0042 and 1.0083, and at 10−510^{-5} and 10−410^{-4} the estimates agree with the baseline within 0.0020. With δ=η\delta= \eta from 10−710^{-7} downwards, the B gains exceed those of Table I by 0.005 to 0.020. This pairing equates the tolerances at the gap edge s=1s = 1. In scaled coordinates the constraints are ∣f(s)−1/s∣≤η|f(s)-1/s| \leq\eta under A and ∣f(s)−1/s∣≤δ/s|f(s)-1/s| \leq\delta/s under B for s≥1s \geq1. Sec. S12 gives the method and independent checks.

Scaling limit and the asymptotic frontier

The limiting problem

The linear programs of Section Section III stop at κ=40\kappa= 40, far below the condition numbers of resource estimates. We therefore study criterion A as κ→∞\kappa\to\infty at fixed scaled error. In this limit ϵ=η/κ\epsilon= \eta/\kappa tends to infinity, so this is an approximately theoretical scaling limit and not a family of increasingly accurate solves. For μ>0\mu> 0 and 0<η<10 < \eta< 1, let

Φ(μ,η)=inf⁡{∥f∥R:f odd entire of exponential type at most 2μ, ∣f(s)−1/s∣≤η for all s≥1}.(8)\Phi(\mu,\eta)=\inf\left\{\lVert f\rVert_{\mathbb{R}}: f\text{ odd entire of exponential type at most }2\mu,\ \lvert f(s)-1/s\rvert\leq\eta\text{ for all }s\geq1\right\}. \tag*{(8)}

Here ∥f∥R=sup⁡s∈R∣f(s)∣\lVert f\rVert_{\mathbb{R}}=\sup_{s\in\mathbb{R}}\lvert f(s)\rvert. The substitution F(s)=a q(as)F(s)=a\,q(as) maps a feasible polynomial with mm odd terms to an odd function that approximates 1/s1/s on [1,κ][1,\kappa] with error η\eta. Its Bernstein–Walsh growth tends to exponential type 2μ2\mu as a→0a \to0.

Theorem 2 (Scaling limit). Fix 0<η<10 < \eta< 1, and let aj→0a_j \to0 and mjaj→μm_j a_j \to\mu. If μ>L/2\mu> L/2, then ajM(mj,η/aj)→Φ(μ,η)a_j M(m_j,\eta/a_j) \to\Phi(\mu,\eta). If μ=L/2\mu= L/2, the same holds along every sequence of feasible finite

problems, that is, with (1+aj)βjmj≤η(1+a_j)\beta_j^{m_j}\le\eta for βj=(1−aj)/(1+aj)\beta_j=(1-a_j)/(1+a_j), and along some sequences with mjaj→L/2m_ja_j\to L/2 the finite problems are eventually all infeasible. If μ<L/2\mu<L/2, the finite problems are eventually infeasible. For μ≥L/2\mu\ge L/2 the infimum in (8) is attained.

The threshold case uses the uniqueness of hLh_L as a feasible function at μ=L/2\mu=L/2, proved in Proposition S2.4 with the dual identities (10).

Sec. S2 proves Theorem 2. Fix constants γ0>0\gamma_0>0 and C0>0C_0>0. For margins 2μ−L≥γ02\mu-L\ge\gamma_0 and types γ0≤2μ≤C0ln⁡(1/a)\gamma_0\le2\mu\le C_0\ln(1/a), explicit transfer bounds give

∣aM−Φ∣=O(a2/3[ln⁡(1/a)]5/2),(9)|aM-\Phi|=O\left(a^{2/3}[\ln(1/a)]^{5/2}\right), \tag*{(9)}

where the implied constant depends on γ0\gamma_0 and C0C_0. Theorem 2 is a limit theorem of the kind studied by Bernstein and Ganzburg, which relates polynomial approximation on dilated intervals to approximation by entire functions of exponential type [12, 13]. For ∣x∣α|x|^\alpha, Lubinsky proved that the rescaled best polynomials converge to the unique best entire function [19]. The results of this kind that we read treat the error of best approximation of a target locally bounded on the real line, measured on the whole dilated interval [13 Sec. 7]. Theorem 2 instead treats a least norm under an error constraint, for a target 1/s1/s whose pole lies at the end of the gap [0,1)[0,1), which stays fixed under the scaling. Its limit Φ\Phi is also infinite below the threshold μ=L/2\mu=L/2 and finite at it. We did not find a limit theorem of this kind with a least norm under a constraint, a pole at the end of the gap, or such a threshold. The limiting class also has an exact dual description. Let σ=2μ\sigma=2\mu. Take the nodes s0=1s_0=1 and sj=1+vj2s_j=\sqrt{1+v_j^2}, where σvj+arctan⁡vj=jπ\sigma v_j+\arctan v_j=j\pi, and the weights w0=1/(σ+1)w_0=1/(\sigma+1) and wj=2/(σsj2+1)w_j=2/(\sigma s_j^2+1). Then every bounded odd entire ff of type at most σ\sigma satisfies

∑j≥0wj=1,∑j≥0(−1)jwjf(sj)=0,∑j≥0(−1)jwjsj=e−σ.(10)\sum_{j\ge0}w_j=1,\qquad\sum_{j\ge0}(-1)^jw_jf(s_j)=0,\qquad\sum_{j\ge0}\frac{(-1)^jw_j}{s_j}=e^{-\sigma}. \tag*{(10)}

The signed measure with mass (−1)jwj(-1)^jw_j at each sjs_j therefore certifies that no such ff approximates 1/s1/s on [1,∞)[1,\infty) with error below e−σe^{-\sigma}. The limit hσh_\sigma of the minimax polynomials attains that error. The identities (10) also yield a convergent hierarchy of finite linear programs for Φ\Phi. Their certified lower bounds and the explicit constructions of Section V and Sec. S7.1 enclose Φ\Phi at five bandwidths in intervals of relative width below 0.038 percent. Sec. S3 proves the identities and the convergence of the hierarchy. Sec. S7 lists the intervals.

The asymptotic frontier

Let D(η)=min⁡μ≥μu(μ/μu)Φ(μ,η)D(\eta)=\min_{\mu\ge\mu_u}(\mu/\mu_u)\Phi(\mu,\eta) be the optimized limiting cost relative to μu=L/2\mu_u=L/2. The limiting gain is then G∞(η)=ρ∞(L/2)/D(η)G_\infty(\eta)=\rho_\infty(L/2)/D(\eta). The behaviour of Φ\Phi along a fixed degree ratio λ=μ/μu\lambda=\mu/\mu_u is governed by the action

R(b)=∫b1x2−b21−x2 dx=E(1−b2)−b2K(1−b2),0<b<1,(11)R(b)=\int_b^1\sqrt{\frac{x^2-b^2}{1-x^2}}\,\mathrm{d}x=E(1-b^2)-b^2K(1-b^2),\qquad0<b<1, \tag*{(11)}

where KK and EE are the complete elliptic integrals of the first and second kind, with the parameter as argument. Since RR decreases strictly from 1 to 0, R(bλ)=1/λR(b_\lambda)=1/\lambda has a unique root bλb_\lambda for every λ>1\lambda>1.

Theorem 3 (Asymptotic frontier). For every fixed λ>1\lambda>1,

Ψ(λ)=lim⁡L→∞Φ(λL/2,e−L)=1bλ,λλ2−1<Ψ(λ)<λλ−1.(12)\Psi(\lambda)=\lim_{L\to\infty}\Phi(\lambda L/2,e^{-L})=\frac{1}{b_\lambda},\qquad\frac{\lambda}{\sqrt{\lambda^2-1}}<\Psi(\lambda)<\frac{\lambda}{\lambda-1}. \tag*{(12)}

Sec. S5 proves Theorem 3, with both strict inequalities, and Corollary 5 below. The lower bound lim⁡Φ≥1/bλ\lim\Phi\ge1/b_\lambda follows from an inequality that holds before any limit.

Proposition 4 (Finite lower bound). Let ff be odd entire of type at most σ\sigma with ∥f∥R=B\lVert f\rVert_{\mathbb R}=B and ∣f(s)−1/s∣≤e−L|f(s)-1/s|\le e^{-L} for s≥1s\ge1. For 0<b<s<10<b<s<1 with L≥σR(b)L\ge\sigma R(b), put Jb(s)=∫bs(x2−b2)/(1−x2) dxJ_b(s)=\int_b^s\sqrt{(x^2-b^2)/(1-x^2)}\,\mathrm{d}x and T=exp⁡[−σJb(s)+arcosh⁡(s/b)]T=\exp[-\sigma J_b(s)+\operatorname{arcosh}(s/b)]. Then

B≥1−Ts+bT.(13)B\ge\frac{1-T}{s+bT}. \tag*{(13)}

Appendix § 12 proves the bound with a harmonic majorant on the plane cut along ∣x∣≥1|x| \ge1 and ∣x∣≤b|x| \le b. With σ=λL\sigma=\lambda L and b=bλb=b_\lambda, the factor TT tends to zero for every fixed s>bλs>b_\lambda. Hence lim inf⁡Φ≥1/s\liminf\Phi\ge1/s. Letting s↓bλs \downarrow b_\lambda gives the lower bound. The bound also shows that, along any family of feasible functions with bounded norm, f(s)→1/sf(s) \to1/s on (bλ,1)(b_\lambda,1) as LL grows. The norm is set by continuing the reciprocal down to bλb_\lambda.

The matching upper bound uses a weighted sum of squared prolate spheroidal functions [20] as a kernel HH, with f=(1−H)/sf=(1-H)/s. The local density of HH follows from smooth semiclassical functional calculus on the sphere [21], arXiv v2, Theorem 4.5. The exterior decay of HH follows from an ordinary differential equation comparison. Appendix § 13 outlines the construction and states the cited theorem in the form used. This construction gives no quantitative onset in LL.

Harmonic majorants are a standard tool for extremal problems for entire functions [22]. Closely related two-interval constructions with elliptic periods appear in the best approximation of the sign function [6]. The configuration of two rays and a central segment and the resulting action (11) are specific to the present problem. We did not find the frontier of Theorem 3, or the extremal problem (8), in the sources on approximation by entire functions and on constrained polynomial approximation that we searched. The closest problem we found, described in [22], imposes different bounds on the two half-lines on functions of exponential type one. It is a different extremal problem.

Corollary 5 (Optimized constants). The asymptotic cost constant is lim⁡η→0D(η)=D∗=min⁡λ>1λΨ(λ)=2.949189861\lim_{\eta\to0}D(\eta)=D_*=\min_{\lambda>1}\lambda\Psi(\lambda)=2.949189861, attained at the unique b∗=0.5465094138b_*=0.5465094138 with E(1−b∗2)=2b∗2K(1−b∗2)E(1-b_*^2)=2b_*^2K(1-b_*^2), that is λ∗=1/R(b∗)=1.611760022\lambda_*=1/R(b_*)=1.611760022 and Ψ(λ∗)=1/b∗=1.829794647\Psi(\lambda_*)=1/b_*=1.829794647. Consequently

lim⁡η→0G∞(η)L=c02D∗=0.1530102351.(14)\lim_{\eta\to0}\frac{G_\infty(\eta)}{\sqrt{L}}=\frac{c_0}{\sqrt{2}D_*}=0.1530102351. \tag*{(14)}

Theorem 3 holds for each fixed λ\lambda. The limit of D(η)D(\eta) also needs the minimum over λ\lambda. Sec. S5 shows that the convergence is uniform on compact subintervals of (1,∞)(1,\infty). It also shows that near-minimizing λ\lambda stay in such a subinterval, which gives D(η)→D∗D(\eta)\to D_*. In finite terms the asymptotically optimal design uses about 0.806 κL0.806\,\kappa L odd terms and has M≈1.830 κM\approx1.830\,\kappa. The rescaled minimax polynomial uses κL/2\kappa L/2 odd terms and has M≈c0κL/2M\approx c_0\kappa\sqrt{L/2}. The two curves of Theorem 3 alone give the brackets [2,4][2,4] for D∗D_* and [0.1128,0.2257][0.1128,0.2257] for the coefficient (Sec. S5). The exact values lie inside them.

What the limit says at practical accuracies

Two limits appear in this paper. The first is κ→∞\kappa\to\infty at fixed η\eta (Theorem 2). It gives the limiting gain G∞(η)=ρ∞(L/2)/D(η)G_\infty(\eta)=\rho_\infty(L/2)/D(\eta). Sec. S2 shows that G(κ,ηκ)→G∞(η)G(\kappa,\eta\kappa)\to G_\infty(\eta) for L≥8L\ge8. Unlike GG in (6), G∞G_\infty is not at least one by definition, because Φ\Phi is a norm on all of R\mathbb{R} whereas ρ∞\rho_\infty is a maximum over the gap. It is at least one for L≥8L \ge8, which covers the criterion-A Table I, Table III and Table IV and Figure 2. The function hLh_L is feasible at μ=L/2\mu= L/2. For L≥8L \ge8 its norm on R\mathbb{R} equals ρ∞(L/2)\rho_\infty(L/2) (Sec. S2), so D(η)≤Φ(L/2,η)≤ρ∞(L/2)D(\eta) \le\Phi(L/2,\eta) \le\rho_\infty(L/2).

LLα\alpha best foundd/κd/\kappa best foundn/mun/m_u best foundGG best foundGG, rule
1731.490.7681.2161.01751.0165
2036.090.7641.1901.06691.0654
2442.030.7641.1651.11861.1167
2847.810.7661.1461.15931.1571
3253.870.7631.1311.19221.1898
3659.440.7671.1191.21951.2169
4065.580.7641.1101.24241.2398

Table IV. The two-term family at κ=105\kappa= 10^{5}, best found and rule.

Gain over the rescaled minimax polynomial as a function of $L=\ln(\kappa/\varepsilon)$

Figure 2. Gain over the rescaled minimax polynomial as a function of L=ln⁡(κ/ε)L=\ln(\kappa/\varepsilon). LP estimates of the bounded optima at κ=20\kappa=20 and 4040 (circles), certified near-optimal constructions at κ=104\kappa=10^4 with ε=10−6\varepsilon=10^{-6} and at κ=105\kappa=10^5 and 10610^6 with ε=10−10\varepsilon=10^{-10} (squares), the limiting gain G∞G_\infty as κ→∞\kappa\to\infty at fixed LL (black dashes, which are thicker than the certified brackets), the two-term family at κ=105\kappa=10^5 (solid, best found, and dashed, rule (16)) with the certified rule points at κ=104\kappa=10^4, 10510^5 and 10610^6 (triangles), and the leading term of Corollary 5 (dotted). The rule curve lies within 0.22 percent of the best values found and is nearly indistinguishable from the solid curve. The leading term lies below every finite curve in the practical range. The limiting gain itself is at least one there.

Explicit entire functions of the type used in § 5 bound G∞G_\infty from below (Sec. S7). Because Φ\Phi does not increase with the type, lower bounds on Φ\Phi at finitely many degree ratios give an upper bound on G∞G_\infty (Sec. S3.6). Sec. S3 derives from the dual identities (10) the explicit lower bound

Φ(σ/2,η)≥sup⁡0≤s≤1[hσ(s)−(η−e−σ)scosh⁡(σ1−s2)].\Phi(\sigma/2,\eta) \ge\sup_{0 \le s \le1}\left[h_\sigma(s)-(\eta-e^{-\sigma})s\cosh(\sigma\sqrt{1-s^2})\right].

We evaluate it on a mesh of degree ratios. Near the minimizing degree ratio it is loose, so there we add certified lower bounds from the finite linear programs of the dual hierarchy. The certified brackets are [1.0775,1.0781][1.0775,1.0781] at L=18.4L=18.4, [1.1102,1.1108][1.1102,1.1108] at L=20.7L=20.7, [1.1382,1.1387][1.1382,1.1387] at L=23.0L=23.0, [1.2723,1.2733][1.2723,1.2733] at L=34.5L=34.5 and [1.2962,1.2973][1.2962,1.2973] at L=36.8L=36.8 (Figure 2). The upper ends bound the saving of every bounded polynomial in this limit. At L=23.0L=23.0, 34.534.5 and 36.836.8, the accuracies of the three certified points of § 5, no bounded polynomial cuts the cost of the rescaled minimax polynomial by more than 12.2, 21.5 and 23.0 percent in this limit. The entire functions of that section cut it by at least 12.1, 21.4 and 22.8 percent. Each upper end exceeds its lower end by less than 0.1 percent. The gains of these functions are therefore within 0.1 percent of G∞G_\infty, the optimum over all degree ratios.

The second limit is L→∞L \to\infty (Theorem 3 and Corollary 5). It describes practical accuracies poorly. Its leading term 0.1530L0.1530\sqrt{L} exceeds one only for L>42.7L > 42.7, that is for η<2.9×10−19\eta< 2.9 \times10^{-19}. At L=34.5L=34.5 and 36.836.8 the leading term is 0.899 and 0.929. The certified gains of § 5 there are 1.2716 and 1.2961. The computed values in Figure 1 lie below the limit and approach it slowly. The circles lie at integer degrees, at λ=1.303\lambda=1.303 and 1.503 for L=23.0L=23.0 and at λ=2.003\lambda=2.003 for L=18.4L=18.4. At λ=1.3\lambda=1.3 the rigorous lower bound gives 1.856 at L=128L=128, and the limit is 2.474. The linear program gives 1.579 at L=23.0L=23.0 and λ=1.303\lambda=1.303. The deficit of the lower bound (13) decays only as O((ln⁡σ/σ)2/3)O((\ln\sigma/\sigma)^{2/3}). The limit theory therefore determines the scaling and the constants. Practical values must come from finite computation.

Figure 1. Asymptotic frontier of the scaled norm Φ(λL/2,e−L)\Phi(\lambda L/2,e^{-L}) as L→∞L \to\infty (solid), with the two bounding curves of Theorem 3. Squares are rigorous lower bounds from Proposition 4 at L=128L=128. Circles are linear-program values M/κM/\kappa at κ=40\kappa=40, at L=23.0L=23.0 and 18.418.4. The computed values lie below the limit and approach it slowly.

Finite condition number. At fixed interior (μ,η)(\mu,\eta), a negative correction to aM−ΦaM-\Phi is at most of order a2a^2. This bound holds along a=μ/ma=\mu/m with integer mm, where ma=μma=\mu exactly. A positive correction of order aa occurs at exact ma=μma=\mu in the following example. At μ=1/2\mu=1/2 and η=9/10\eta=9/10 the problem is solved exactly by the scaled Chebyshev polynomial, with Φ=1/(10sin⁡1)\Phi=1/(10\sin1) and a positive first-order correction cos⁡1/(10sin⁡21)\cos1/(10\sin^2 1) per unit of 1/κ1/\kappa. Our linear program reproduces this correction within 9×10−109\times10^{-10} relative at mm from 2 to 32. Rounding mm so that ma=μ+O(a)ma=\mu+O(a) can add a further term of order aa. Sec. S6 gives the proofs. Neither the sign nor the leading coefficient of the correction at small η\eta is established. The brackets of G∞G_\infty above therefore apply to the limiting gain, not to the gain at the three points of § 5. That section certifies lower bounds on the gain at these points.

Validation. We recomputed every constant of Theorem 3 and Corollary 5 independently in 50-digit arithmetic. We reproduced the rigorous table of Proposition 4 at L=128L=128 and 256, which Sec. S5 prints with the certified intervals of the constants. We also checked that (13) lies below all 19 linear-program values at κ=40\kappa=40 and below the five certified intervals of the dual hierarchy.

The residual-error limit remains open. The theory of this section is for A. The corresponding B problem is to minimize ∥f∥R\|f\|_{\mathbb{R}} over odd entire functions of exponential type at most σ\sigma, bounded on R\mathbb{R}, with ∣f(s)−1∣≤δ|f(s)-1|\le\delta for ∣s∣≥1|s|\ge1. The scaling limit of qRq_R is

fR,σ(s)=1−cosh⁡(σ1−s2)/cosh⁡σs.f_{R,\sigma}(s)=\frac{1-\cosh(\sigma\sqrt{1-s^2})/\cosh\sigma}{s}.

It is feasible exactly when cosh⁡σ≥1/δ\cosh\sigma\ge1/\delta. We do not prove convergence of the B frontier or an asymptotic cost constant. The B results of Sections III and § 5.D are finite LP estimates and certificates.

Polynomials at practical condition numbers

For criterion A at κ=104\kappa= 10^{4} to 10610^{6} the degree is 2.8×1052.8 \times10^{5} to 4.7×1074.7 \times10^{7}, beyond any direct linear program. We give two kinds of explicit polynomial and certify both.

Near-optimal constructions

An odd entire function of type σ\sigma is built from 321 coefficients,

F(s)=1−η[∑j=0160ajcos⁡(jΔv)+v∑j=1160bjsin⁡(jΔv)]s,v2=s2−1,Δ=σ/160,(15)F(s) = \frac{1-\eta\left[\sum_{j=0}^{160} a_j \cos(j\Delta v)+v\sum_{j=1}^{160} b_j\sin(j\Delta v)\right]}{s}, \qquad v^{2}=s^{2}-1,\qquad\Delta=\sigma/160, \tag*{(15)}

with a160a_{160} fixed analytically so that FF is entire. The coefficients were optimized numerically. The bandwidth was found by a numerical search. The optimized function has a certified exterior error of at most 1.0004η1.0004\eta. Mixing in hσh_{\sigma} with weight about 4×10−44\times10^{-4} gives a function ff with exterior error at most η\eta. The norm of ff lies within 0.038 percent of Φ\Phi at its bandwidth. Near-optimal refers to this property at the chosen bandwidth. The gain of ff is less than 0.1 percent below the limiting gain G∞G_{\infty}, which is the optimum over all bandwidths (Section IV.C). A second mixture with weight about 10−610^{-6} gives fˉ\bar{f} with exterior error at most (1−10−6)η(1-10^{-6})\eta, which reserves 10−6η10^{-6}\eta for the truncation. The polynomial is a−1a^{-1} times the truncation at odd degree 2m−12m-1 of the exact Chebyshev expansion of fˉ(x/a)\bar{f}(x/a). The Bernstein growth bound on an ellipse keeps the truncation error below the reserve. Table III lists the result.

We certified the exterior error and the norm with our own code built on the Arb library [23]. The exterior error is built from two functions of period 2π/Δ2\pi/\Delta in vv. We bounded it from 10610^{6} points of one period at which every angle is an exact rational multiple of π\pi, with every alias of each point bounded. We bounded the norm from 10510^{5} gap points under a Bernstein bound. At κ=104\kappa=10^{4} and ε=10−6\varepsilon=10^{-6} we used the function constructed for η=10−10\eta=10^{-10}. We chose the number of terms by the truncation rule of Sec. S7, minimized over its ellipse parameter. The certified gains are G≥1.13497G\geq1.13497 at κ=104\kappa=10^{4}, G≥1.27162G\geq1.27162 at κ=105\kappa=10^{5} and G≥1.29613G\geq1.29613 at κ=106\kappa=10^{6}. Sec. S7 gives the construction, both certificates and their results. The 321 coefficients per point are not printed. They are in the coefficient files on which those certificates operate.

Table III lists certified target polynomials under A at the three practical points, with error ε=10−6\varepsilon=10^{-6} at κ=104\kappa=10^{4} and ε=10−10\varepsilon=10^{-10} at κ=105\kappa=10^{5} and 10610^{6}. For each construction it gives the number of odd terms, the certified upper bound on M/κM/\kappa and the certified lower bound on the gain GG of (6). For the baseline, the rescaled minimax polynomial, the column M/κM/\kappa gives ρu\rho_u to five decimals. It enters GG through a certified lower bound on ρu\rho_u, which Sec. S7 lists with the other certificates. The CKS rows give the construction of the estimates in Section VII, the polynomial of Childs, Kothari and Somma [3] times a rectangle function. Its normalization 1/(2κ)1/(2\kappa) gives the entry 2 for M/κM/\kappa. The number of odd terms is for the CKS polynomial alone, with b=⌈κ2ln⁡(κ/ε)⌉b=\lceil\kappa^{2}\ln(\kappa/\varepsilon)\rceil, degree 2d+12d+1 and d=⌈bln⁡(b/ε)⌉d=\lceil\sqrt{b\ln(b/\varepsilon)}\rceil. This count leaves out the degree of the rectangle. The CKS cost and the CKS factors are therefore lower bounds. The CKS factor of a row is the CKS cost divided by the cost of the row, rounded down.

For the baseline the CKS factor is the factor of prior work [5], 2.27, 1.80 and 1.76 at the three points. For our constructions it is that factor times GG. Against the CKS construction the total factors are therefore at least 2.58, 2.29 and 2.29. Our constructions supply 13, 29 and 31 percent of the logarithm of the total.

A two-term closed-form family

The near-optimal constructions need 321 numerically determined coefficients per point. A simpler family uses only the closed form (5).

Proposition 6. For α≥0\alpha\geq0 and integers n,d≥1n,d\geq1, the polynomial q=(1+α)qn∗−αqn+d∗q=(1+\alpha)q_n^{*}-\alpha q_{n+d}^{*} has at most n+dn+d odd terms and satisfies ∥q−1/x∥[a,1]≤(κ+1)βn(1+α+αβd)\lVert q-1/x\rVert_{[a,1]}\leq(\kappa+1)\beta^{n}(1+\alpha+\alpha\beta^{d}).

Proof. For α=0\alpha=0, q=qn∗q=q_n^{*} has degree 2n−12n-1. For α>0\alpha>0, its degree is 2(n+d)−12(n+d)-1. On [a,1][a,1], q−1/x=(1+α)(qn∗−1/x)−α(qn+d∗−1/x)q-1/x=(1+\alpha)(q_n^{*}-1/x)-\alpha(q_{n+d}^{*}-1/x), so ∣q−1/x∣≤(1+α)En+αEn+d\lvert q-1/x\rvert\leq(1+\alpha)E_n+\alpha E_{n+d} by (5), and En=(κ+1)βnE_n=(\kappa+1)\beta^n (Sec. S1).

For given (α,d)(\alpha,d), Proposition 6 therefore gives an explicit formula for the least nn it certifies. Only MM needs numerical evaluation, as the maximum of an explicit function over the gap. Every family optimum reported below is the best value our search found over (α,d)(\alpha,d) with this nn. We optimized (α,d)(\alpha,d) at 47 points, at κ=105\kappa=10^5 for LL from 8 to 40, at κ=103\kappa=10^3, 10410^4 and 10610^6 for L∈{12,20,28,36}L \in\{12,20,28,36\}, and at the practical points (κ,ε)=(105,10−10)(\kappa,\varepsilon)=(10^5,10^{-10}) and (106,10−10)(10^6,10^{-10}). At fixed α\alpha the gain rises with dd up to an abrupt drop, where a second local maximum of ∣q∣|q| in the gap exceeds the first. At α=56\alpha=56 and κ=105\kappa=10^5, for example, GG falls from 1.209 at d/μ=0.045d/\mu=0.045 to 1.127 at 0.047. The optimum lies at the edge of this drop. We therefore located it by a nested golden-section search. At κ=105\kappa=10^5 and ε=10−10\varepsilon=10^{-10} it gives G=1.2101335G=1.2101335.

The optimal gain depends on LL alone to the precision we measured. At L=20L=20, 28 and 36 it agrees across κ\kappa from 10310^3 to 10610^6 within 6×10−56\times10^{-5}. The optimal parameters depend on κ\kappa more strongly. Our search covered 2≤α≤4002\leq\alpha\leq400 at every LL. In this range the family first gives a lower cost than the baseline between L=16L=16 and 17. At L=16L=16 the best member found has G=0.9984G=0.9984, below the baseline α=0\alpha=0. The optimal gain rises to 1.2424 at L=40L=40 (Table IV). Across all 35 points where the family costs less than the baseline, the optimal dd lies between 0.741κ0.741\kappa and 0.780κ0.780\kappa. At κ=105\kappa=10^5 the optimal α\alpha lies within 0.45 percent of the line 1.4767L+6.4631.4767L+6.463, its least-squares fit. At the other condition numbers it lies within 3.6 percent of this line. This gives the rule

d=round⁡(0.76κ),α=0.98(1.4767L+6.463),n=min⁡{n:(κ+1)βn(1+α+αβd)≤ε},(16)d=\operatorname{round}(0.76\kappa),\qquad\alpha=0.98\left(1.4767L+6.463\right),\qquad n=\min\{n:(\kappa+1)\beta^n(1+\alpha+\alpha\beta^d)\leq\varepsilon\}, \tag*{(16)}

for L≥17L\geq17, with α\alpha rounded to six decimals. The factor 0.98 is a 2 percent margin before the drop. With this margin the rule also keeps at least 2.6 percent in dd. Over the 35 points the rule loses at most 0.22 percent of GG against the best value found at each point. At κ=102\kappa=10^2, 10410^4 and 10710^7 and at half-integer LL from 17.5 to 39.5, outside the fitting set, it stays within 0.22 percent of the best values found, interpolated in LL between the fitting points. A parameter past the drop cannot make the polynomial infeasible, because nn and MM are computed for the chosen parameters. It only lowers GG. We tested margins around the rule with dd from 0.74κ0.74\kappa to 0.78κ0.78\kappa and α\alpha from 0.95 to 1.00 times the fitted line. On these margins the loss is at most 4.23 percent. Parameters further past the drop lose more, as the example at α=56\alpha=56 shows.

Table IV lists the best found values and the rule at κ=105\kappa=10^5. The optimizer evaluates the gap maximum on a uniform grid of 8001 points with golden-section refinement, which gives the columns α\alpha, d/κd/\kappa and n/μn/\mu. The column “GG, best found” is re-evaluated on 400001 gap points (Sec. S11). The column “GG, rule” is re-evaluated on 40001 points. All values in the table are measured. The two GG columns are rounded down. The parameter columns are rounded to the digits shown.

Procedure. For given κ\kappa and ε\varepsilon with L≥17L\geq17 the polynomial and its normalization follow in five steps.

  1. Allocate the polynomial error εpoly\varepsilon_{\mathrm{poly}} and use it as ε\varepsilon in the rule. Put a=1/κa=1/\kappa and β=(1−a)/(1+a)\beta=(1-a)/(1+a), and take dd, α\alpha and nn from (16).

  1. Form q=(1+α)qn∗−αqn+d∗q=(1+\alpha)q_n^*-\alpha q_{n+d}^* from (5). Proposition 6 gives ∣q−1/x∣≤ε|q-1/x|\leq\varepsilon on [a,1][a,1], so the error needs no check.

  1. Compute M=max⁡[0,1]∣q∣M=\max_{[0,1]}|q|. For the rule polynomials we certified, the maximum lies inside the gap near x=a/2x=a/2, where (5) is accurate in double precision. Lemma 7 gives a rigorous bound from values evaluated in ball arithmetic on a fine grid.

  1. Apply cqcq with c=1/(M(1+ξ))c=1/(M(1+\xi)). The margin ξ\xi, for example 10−310^{-3}, leaves the target below the norm bound one and divides GG by 1+ξ1+\xi. It is a normalization margin, not an error reserve. In unscaled reciprocal-error units, calculate εpoly+εphase+εsynthesis≤εtotal\varepsilon_{\mathrm{poly}}+\varepsilon_{\mathrm{phase}}+\varepsilon_{\mathrm{synthesis}}\leq\varepsilon_{\mathrm{total}}. The last two terms include the factor 1/c1/c that converts implementation errors to these units.

  1. For Chebyshev coefficients or pointwise values, use the evaluation forms of Sec. S1. Proposition S1.3 applies inside the gap. Outside it, the stated error bound controls the subtraction from one. The form (5) loses accuracy near x=0x=0.

Reserving part of ε\varepsilon for the phase factors and for gate synthesis raises the cost of the rule polynomial and of the rescaled baseline. Over the range of Table IV it also raises their ratio, the gain. Running (16) with half of ε\varepsilon raises LL by ln⁡2\ln2. By interpolation in that table the gain of the rule then rises by 0.3 to 1.1 percent.

At ε=10−10\varepsilon= 10^{-10} the rule gives α=56.317083\alpha= 56.317083, d=76000d = 76000 and n=1939103n = 1939103 at κ=105\kappa= 10^{5}. At κ=106\kappa= 10^{6} it gives α=59.649306\alpha= 59.649306, d=760000d = 760000 and n=20570651n = 20570651. A separate interval computation, run without knowledge of our floating-point values, certified G≥1.207619G \ge1.207619 and G≥1.222085G \ge1.222085 (Table III). It bounds the gap maximum from 10510^{5} exact rational points per function in 256-bit ball arithmetic [23] with the second-derivative bound of Appendix § 14, at a relative slack of about 2×10−82 \times10^{-8}. Our floating-point values agree to seven digits. At κ=104\kappa= 10^{4} and ε=10−6\varepsilon= 10^{-6} the rule gives α=39.655969\alpha= 39.655969, d=7600d = 7600 and n=134623n = 134623. We certified this point with a copy of the same code and obtained G≥1.105465G \ge1.105465. The copy first reproduced the certificate at κ=105\kappa= 10^{5} exactly. Sec. S7 lists the parameters and results of all three certificates. On a logarithmic scale the rule recovers 78.5 and 77.3 percent of the certified gain of the near-optimal constructions at κ=105\kappa= 10^{5} and 10610^{6}. The family optimum recovers 78 and 79 percent of the linear-program optimum at L=20.7L = 20.7 and 23.023.0.

Phase factors

QSVT applies a polynomial through a sequence of N+1N + 1 phase angles, where NN is the degree. Computing these angles is a separate numerical problem, which becomes harder with the degree and as max⁡∣p∣\max|p| approaches one. We computed them for the rule polynomials (16) at L=20L = 20 and κ∈{100,500,2000}\kappa\in\{100, 500, 2000\}, scaled to p=q/(M(1+ξ))p = q/(M(1 + \xi)) with a margin ξ\xi. We used Newton’s method for symmetric quantum signal processing [24] in the convention of [25], with an exact Jacobian and a dense linear solve on 8 threads, started from (π/4,0,…,0)(\pi/4,0,\ldots,0) and without continuation. Table V lists the results. Its error column is the largest difference between the polynomial realized by the angles and the target q/(M(1+ξ))q/(M(1 + \xi)) over the verification points, evaluated in double precision. Its last column is the largest value of ∣M(1+ξ)prealized−1/x∣/ε\lvert M(1+\xi)p_{\mathrm{realized}}-1/x\rvert/\varepsilon over the verification points in [a,1][a,1]. The realized polynomial was evaluated from the angles at 4N+24N+2 Chebyshev-angle points, 12000 points in the gap and 1201 points clustered at x=ax=a. Separately, we evaluated it from the phase files with our own code, against a target computed with the cancellation-free form of Sec. S1. The differences were at most 4.3×10−124.3\times10^{-12}. A 50-digit evaluation at 200 points of each run gives differences to the target of at most 2.5×10−122.5\times10^{-12}. In every case ∣p∣≤1\lvert p\rvert\le1 at all verification points. The rescaled polynomial M(1+ξ)pM(1+\xi)p meets the error ε\varepsilon at those of [a,1][a,1]. The margin divides GG by 1+ξ1+\xi. Sec. S11 gives the details.

κ\kappadegree NNξ\xiNewton iterations, timeerrorrealized error/ε\varepsilon
100253110−310^{-3}9, 3.9 s3.4×10−133.4\times10^{-13}0.99312
100253110−410^{-4}11, 4.6 s3.4×10−133.4\times10^{-13}0.99311
5001265310−310^{-3}10, 116 s1.7×10−121.7\times10^{-12}0.99794
5001265310−410^{-4}11, 128 s1.7×10−121.7\times10^{-12}0.99794
20005060910−310^{-3}10, 2298 s5.7×10−125.7\times10^{-12}0.99952

Table V. Phase factors of the rule polynomials at L=20L=20.

Phase factors computed for an inversion polynomial itself, rather than estimated by extrapolation, have been obtained up to κ=650\kappa=650 with the normalization fixed at 0.125/κ0.125/\kappa [26]. The same work extrapolates beyond this condition number. Ni and Ying demonstrated a fast phase-finding method on other polynomials at degrees of about 10510^5 [27]. Berntson and Sünderhauf computed complementary polynomials, the first step of such methods, up to degree 10710^7 [28]. Lapworth and Sünderhauf computed 14011 phase factors for an inversion polynomial at an effective condition number of 2500 and error 10−210^{-2} with the Remez method of QSPPACK [29]. They used them in an emulated solver. The Newton iteration used here solves a dense system of order about N/2N/2 in each step, which took about 230 s at N=50609N = 50609. The degrees of the certified points, 2.8×1052.8 \times10^{5} to 4.7×1074.7 \times10^{7}, therefore need one of those faster methods.

The certified point at κ=104\kappa= 10^{4}. We computed the phase factors of the rule polynomial of Table III at κ=104\kappa= 10^{4} and ε=10−6\varepsilon= 10^{-6}, of degree 284445, scaled by its certified MM with ξ=10−3\xi= 10^{-3}. We used the Weiss algorithm followed by the inverse nonlinear fast Fourier transform [27, 30]. We ran the code of Ni and Ying on 8 threads, which took 30 s. We checked the result with our own code. At this degree a double-precision evaluation of the realized polynomial itself erred by up to 1.7×10−111.7 \times10^{-11} at the points where we compared it with 50-digit values. The checks below therefore use 50 digits or 128 bits. At the points evaluated in this way, the realized polynomial differs from the target by at most 6.3×10−126.3 \times10^{-12} in the gap and by at most 1.8×10−131.8 \times10^{-13} on [a,1][a,1]. A scan at 20 points per oscillation found 15221 local maxima of the target error ratio ∣q−1/x∣/ε|q - 1/x|/\varepsilon on [a,1][a,1] above 0.99. We refined these locations and evaluated the realized polynomial there. The largest realized error ratio ∣M(1+ξ)p−1/x∣/ε|M(1 + \xi)p - 1/x|/\varepsilon at these points is below 0.999866. The largest target error ratio at these points is below 0.999868. The realized polynomial therefore meets the error ε\varepsilon at these points. At every point evaluated, ∣p∣<0.99901|p| < 0.99901. These evaluations use high-precision arithmetic at selected points. They are not interval enclosures, because enclosures widen beyond use over a product of this length. This run allocated εpoly=ε\varepsilon_{\mathrm{poly}} = \varepsilon with no phase reserve. The realized-error evidence is the direct check at the refined points. By the triangle inequality, the sampled discrepancy 1.8×10−131.8 \times10^{-13} corresponds to about 0.0029ε0.0029\varepsilon after multiplication by M(1+ξ)M(1 + \xi), about 22 times the unused target error 1.33×10−4ε1.33 \times10^{-4}\varepsilon. A design with εpoly=ε/2\varepsilon_{\mathrm{poly}} = \varepsilon/2 would leave a reserve about 170 times this sampled discrepancy at the same phase accuracy. This comparison does not certify an error between sampled points. Sec. S11 gives the details.

Under criterion A, at κ=105\kappa= 10^{5} and 10610^{6} with ε=10−10\varepsilon= 10^{-10}, the polynomial divided by its maximum MM must be realized to an absolute error below η\eta, that is below 10−1510^{-15} and 10−1610^{-16}, because MM exceeds κ\kappa. This is beneath the double-precision rounding error accumulated over the 3.4×1063.4 \times10^{6} to 4.7×1074.7 \times10^{7} factors of these polynomials. We therefore expect phase finding there to need extended-precision arithmetic, for the rescaled minimax polynomial as well. We have not computed phase factors at these two points. The rescaled minimax polynomial needs phase finding at comparable degrees, 230259 at κ=104\kappa= 10^{4} and 3.7×1073.7 \times10^{7} at κ=106\kappa= 10^{6}. The certified constructions have 1.15 to 1.29 times its degree.

Finite construction under residual error

For criterion B we solve a finite problem directly at the target condition number KK. With a=1/Ka = 1/K, even ϖ\varpi and m=Jϖm = J\varpi, put

w(t)=∑j=0JcjTjϖ(t),wξB(t)=(1−ξB)w(t)+ξBTJϖ(t)TJϖ(t(0)),ξB=31000000.w(t) = \sum_{j=0}^{J} c_j T_{j\varpi}(t), \qquad w_{\xi_{\mathrm{B}}}(t) = (1 - \xi_{\mathrm{B}})w(t) + \xi_{\mathrm{B}}\frac{T_{J\varpi}(t)}{T_{J\varpi}(t(0))}, \qquad\xi_{\mathrm{B}} = \frac{3}{1000000}.

and q(x)=(1−wξB(t(x2)))/xq(x) = (1 - w_{\xi_{\mathrm{B}}}(t(x^2)))/x. The last coefficient of ww enforces w(t(0))=1w(t(0)) = 1 exactly, so qq is an odd polynomial. On t=cos⁡θt = \cos\theta the fit is a cosine polynomial of degree JJ in ϖθ\varpi\theta. In the gap it is ∑jcjcosh⁡(ju)\sum_j c_j \cosh(j u), where u=ϖarcosh⁡(−t)u = \varpi\operatorname{arcosh}(-t). We optimize the coefficients at finite KK with J=160J = 160. There is no limit approximation or truncation. The common repair weight above is part of the definition of every published polynomial.

Two separately written Arb programs certify all six published instances at that weight. One bounds the fit on a uniform phase grid, and the other uses adaptive Taylor intervals and derivative signs. Each bounds the gap independently by Lemma 7. Table VI prints the weaker bounds, rounded outward. These target polynomials have degree 2m−12m - 1. The gain is relative to the known residual-minimax polynomial at mRm_R. The error targets differ from those of Table III. No phase factors are claimed for the polynomials in Table VI. Sec. S12 defines the coefficients and gives the fit repair, both certificates and the three benchmark instances. The coefficient values are in the coefficient file anc/verification_set/criterion_b/coefficients.json. The savings are at least 8.7 percent at K=104K = 10^{4} with normalized-state error at most 10−810^{-8}, and 13.1 percent at K=105,106K = 10^{5},10^{6} with error at most 10−1010^{-10}, all in the 2-norm. The first gain lies between the small-κ\kappa LP values at δ=10−8\delta= 10^{-8} and 3×10−93 \times10^{-9}. This is consistent with a scaling picture but does not prove one.

KKδ\deltammM/KM/K, upperGBG_B, lower
10410^{4}5×10−95 \times10^{-9}1225601.5054541.095883
10510^{5}5×10−115 \times10^{-11}14646401.6350121.151636
10610^{6}5×10−115 \times10^{-11}146352001.6361571.151710

Table VI. Certified target polynomials under criterion B.

Windowing

Sünderhauf et al. name multiplication by a window polynomial as an alternative to rescaling [5]. In this section criterion A applies. A window multiplies a minimax polynomial that already meets the error. Hence n≥mun \ge m_u throughout. For a fixed qn∗q_n^* and an even window WW with k+1k+1 Chebyshev terms, the product qn∗Wq_n^*W is linear in WW. We can therefore find the best window for given (n,k)(n,k) by a linear program. The window is restricted only by its number of terms. At κ=20\kappa= 20 and η∈{10−8,10−9,10−10}\eta\in\{10^{-8}, 10^{-9}, 10^{-10}\}, over n/mun/m_u from 1 to 1.1 and k/muk/m_u from 0.02 to 0.3 (120 cases, all feasible and converged), the windowed cost (n+k)max⁡∣qn∗W∣(n+k)\max|q_n^*W| never fell below the rescaled cost. Every cost ratio in this section is the windowed cost divided by the rescaled cost. In these cases it was at least 1.019. A window lowers MM appreciably only once kk exceeds mum_u. At n=mun=m_u, η=10−8\eta=10^{-8} and k/mu=1.5k/m_u=1.5, M/κM/\kappa falls from 2.0 to 1.30. The cost ratio is then 1.63. The reason is that the window must stay within about ϵx\epsilon x of one at each xx of [a,1][a,1], while dropping inside the gap. Near the gap edge this tolerance is about η\eta. This is a high-accuracy step approximation with a degree of the same order as the inverse itself.

This null result does not extend to a general statement that windowing never lowers the cost. When ϵ\epsilon exceeds EmuE_{m_u}, a constant window below one already lowers MM at no degree cost. Without that slack there is a counterexample at κ=2\kappa=2 and ϵ=31−65536\epsilon=3^{1-65536}, with cost ratio below 0.76. As η→0\eta\to0, the best windowed cost over the rescaled cost tends to zero like L−1/2L^{-1/2}. In the iterated limit, κ→∞\kappa\to\infty first and η→0\eta\to0 afterwards, L\sqrt{L} times this ratio lies between 6.5355 and 10.2601. The lower coefficient is that of the unrestricted bounded optimum, because a windowed product is itself a feasible polynomial. For the specific Chebyshev window family xqR,ℓ(x)=1−Tℓ(t(x2))/Tℓ(t(0))xq_{R,\ell}(x)=1-T_\ell(t(x^2))/T_\ell(t(0)) the cost tends to 1.673 times the rescaled cost. These limits give no bound at a finite LL, so the null result at the tested accuracies rests on the 120 cases above. At the points κ=104\kappa=10^{4} to 10610^{6} of Table III we have no measurement of the best window. At κ=105\kappa=10^{5} and 10610^{6}, every member of the Chebyshev window family above costs more than 1.70 times the rescaled minimax polynomial. This bounds one family and not the best window. In the limit the best window costs at most 10.2601/6.5355≤1.57010.2601/6.5355 \le1.570 times the bounded optimum. Sec. S8 gives the proofs and the measurements.

Where the normalization matters

For a normalized solve with amplitude amplification, the relevant gain is GBG_B of § 5.D. The criterion-A gain (6) applies where absolute inverse operator accuracy is required. When a block-encoding of A−1A^{-1} or of a resolvent is a factor inside a larger algorithm, 1/c1/c enters the total cost differently. Table VII separates these uses at κ=106\kappa=10^{6}. The two solve rows use criterion B. They compare the sparse construction with qR,mRq_{R,m_R} at δ=5×10−11\delta=5 \times10^{-11}. Their normalized-state 2-norm error is at most 10−1010^{-10}. The other rows use criterion A. They compare the near-optimal construction and the two-term rule with the rescaled minimax polynomial. Under A the absolute operator-error bound is ϵ=10−10\epsilon=10^{-10} per inverse factor. Paired factors are near-optimal / rule. The factors are certified lower bounds in this model from Table III and Table VI. Under A, the near-optimal construction raises cc by the factor ρκ/M=1.649\rho_\kappa/M=1.649 at 1.2724 times the degree. A cost proportional to c−pc^{-p} therefore falls by the factor 1.649p/1.27241.649^p/1.2724.

usedependence on 1/c1/csaving factor
single solve with amplitude amplificationlinear1.15
observable estimation, e.g. Green’s functions [14, 31]linear, through amplitude estimation1.29 / 1.22
solve without amplitude amplification (repeat until success)quadratic1.59
amplified product of two inverse block-encodingsquadratic2.13 / 1.72
chain of kk non-unitary stepspower that grows with kkgrows with the chain

Table VII. Saving factors in the stated cost model.

Without amplitude amplification a solve succeeds with probability proportional to c2c^2. The expected number of repetitions and the cost then scale as c−2c^{-2}. This route matters where amplification is unavailable, since for a single solve it costs more than the amplified one. Under B its saving factor is GB2m/mRG_B^2m/m_R. For the K=106K = 10^6 polynomial of Table VI, this factor is at least 1.59 against qRq_R at mRm_R of § 2. A product of two inverse block-encodings has the product of their normalizations. Its cost scales as c−2c^{-2} under the amplified-product model used here. If ∥Qi−Ai−1∥≤ε\lVert Q_i-A_i^{-1}\rVert\le\varepsilon and ∥Ai−1∥≤κ\lVert A_i^{-1}\rVert\le\kappa, the product error is at most 2κε+ε22\kappa\varepsilon+\varepsilon^2, so the per-factor error is not the product error. At κ=106\kappa=10^6 and ε=10−10\varepsilon=10^{-10}, this bound is approximately 2×10−42\times10^{-4}. A chain of kk non-unitary steps carries the kk-th power of the normalization. Amplifying each step does not remove this power in general, because every round of amplification reflects about the input of that step, which the earlier steps must prepare again. The criterion-A construction was optimized for a cost linear in 1/c1/c. For the amplified product its factor 1.64922/1.27241.6492^2/1.2724, at least 2.13, is achievable. The best factor for this cost is at least as large. The two-term rule gives 1.22 for the linear and 1.72 for the quadratic uses under A. The factors are our arithmetic, not values reported by the cited works.

Uniform singular value amplification can increase the normalization after the polynomial has been chosen. It costs O((γ/θ)log⁡(γ/ε))O((\gamma/\theta)\log(\gamma/\varepsilon)) queries for an amplification factor γ\gamma and a margin θ\theta below the norm [1]. For a product of two block-encodings, Lapworth and Sünderhauf give conditions under which amplifying the factors before the multiplication is cheaper [29]. For two equal factors these conditions reduce to γ>(3/θ)log⁡(γ/ε)\gamma>(3/\theta)\log(\gamma/\varepsilon). At γ≈1.6\gamma\approx1.6 and ε=10−10\varepsilon=10^{-10} this condition fails for every θ≤1\theta\le1. Within this cited construction and its approximate cost model, a better normalization is therefore cheaper than this amplification at these parameters.

A scenario based on one published estimate. Nelson and Baczewski estimate the T-gate cost of Green’s functions at 1 percent accuracy [31]. Their inverse is the Childs–Kothari–Somma polynomial times a rectangle function, with normalization 1/(2κ)1/(2\kappa). In their cost model the cost per evaluation is proportional to degree divided by normalization, as in (4). The text of that work states the degree as d+nd+n. Its Eq. (D3) runs to T2d+1T_{2d+1}. We use this second reading unless we state otherwise. We compared the costs per evaluation at κ∈{10,100,1000}\kappa\in\{10,100,1000\}. We left out the rectangle’s degree, so the baseline is a lower bound on their cost. We take 1 percent accuracy to require a polynomial error between 10−210^{-2} and 10−410^{-4} of the largest value κ\kappa of 1/x1/x, that is η\eta from 10−210^{-2} to 10−410^{-4}. This range is our assumed polynomial-error budget. Their work does not state the polynomial error it assumes.

The gain GG comes from our linear programs, which reach κ=40\kappa=40. At η\eta from 10−210^{-2} to 10−610^{-6}, G−1G-1 falls by a factor of 5.5 to 12 from κ=10\kappa=10 to 40. We therefore use the gains at κ=40\kappa=40 for all three condition numbers of the scenario. At κ=100\kappa=100 and 1000 they may overstate the gain. They are G=1.0016G=1.0016, 1.0012 and 1.0008 at η=10−2\eta=10^{-2}, 10−310^{-3} and 10−410^{-4}. The value at 10−310^{-3} is the mean of the values at 10−210^{-2} and 10−410^{-4}. At η=10−8\eta=10^{-8} and 10−1010^{-10} the gains are those of Table I. The log recost.nb.log lists the gains at κ=10\kappa=10, 20 and 40 with the factors and shares of both readings.

Replacing their inverse by the rescaled minimax polynomial lowers the cost by a factor of 3.5 to 6.4 at 1 percent accuracy. This factor comes from the minimax polynomial, which is prior work [5]. Under the assumed gains above, the further cost reduction is 1−1/G=0.081 - 1/G = 0.08 to 0.16 percent. The estimated total saving factor is the factor above times GG. We measure the contribution of the assumed gain as its share of the logarithm of this total, that is ln⁡G\ln G divided by the logarithm of the total. This share is 0.06 to 0.10 percent at 1 percent accuracy, 6.8 to 7.4 percent at η=10−8\eta= 10^{-8} and 14.0 to 15.2 percent at η=10−10\eta= 10^{-10}. Under the reading d+nd + n the factors from the minimax polynomial halve. The share of the assumed gain then rises to 0.11 to 0.17 percent at 1 percent accuracy, 22 to 31 percent at η=10−8\eta= 10^{-8} and 57 to 84 percent at η=10−10\eta= 10^{-10}.

Matched evaluations of a published query model. Lefterovici et al. report QSVT query counts for Poisson matrices at normalized-state 2-norm error 10−810^{-8} [16]. Their implementation assumes unit solution norm. It applies its inverse polynomial to A/dA/d, so its effective condition number is K=dκK = d\kappa. Their Fig. 3 plots d−1d - 1, whereas their count uses dd. Every matched evaluation uses the stored sparsity.

Our independent implementation reproduces 77 of the 90 stored Poisson counts to 10−910^{-9} relative. Two rows at κ=1\kappa= 1 differ by 9.4×10−49.4 \times10^{-4}. For the last 11 rows, the implemented model gives counts 9.4 to about 14600 times the stored values. We do not infer the cause. Exactly two cells with K≥104K \ge10^{4} have all their instances reproduced. They are 80≤κ<10080 \le\kappa< 100, d=125d = 125, with K=11264.275K = 11264.275 and 11345.4625, and 1500≤κ<15201500 \le\kappa< 1520, d=7d = 7, with K=10632.44K = 10632.44.

With only the polynomial replaced and δ=5×10−9\delta= 5 \times10^{-9}, evaluations of the published model as implemented give reductions of 71.67 to 71.69 and 78.37 from qRq_R, which is prior work. The common-weight polynomials of § 5.D give further factors of 1.146 to 1.147 and 1.101, for totals of about 82.2 and 86.3. Their certified lower bounds on GBG_B are 1.0960 to 1.0964 (Sec. S12). The model ratios differ because the implemented amplification formula is not proportional to the inverse square root of the success probability. These are evaluations of that model as implemented, not measured circuit costs or certified end-to-end costs. Appendix § 15 specifies the source and summation conventions, and Sec. S12 lists the counts.

Limitations

The cost model counts degree divided by normalization for a solve with amplitude amplification. It does not include the classical computation of phase factors. We computed phase factors only for the two-term family, up to κ=104\kappa= 10^{4} (§ 5.C). For a single linear solve, solvers whose query count is linear in κ\kappa are known [11, 15]. The gain therefore matters most where the inverse block-encoding is a subroutine.

The criterion-A linear programs stop at η=10−10\eta= 10^{-10} and κ=40\kappa= 40 because of double precision (Section III). Between L=23L = 23 and 34.5 our finite bounds on the least cost come only from constructions, which give lower bounds on GG. The certified gains at the practical points are lower bounds on the optimal gain. The upper bounds of Section IV.C apply to the limiting gain, not to the gain at the practical points. The rule (16) is measured for LL from 17 to 40 and κ\kappa from 10210^{2} to 10710^{7}, and certified at three points. On our integer grid up to L=16L = 16, no row with 2≤α≤4002 \le\alpha\le400 costs less than the plain minimax polynomial. The crossover lies between L=16L = 16 and 17.

The upper bound of Theorem 3 rests on a theorem of semiclassical functional calculus [21, arXiv v2, Theorem 4.5, which Appendix § 13 states. This upper bound gives no quantitative onset in LL (Section IV). The sign of the finite-κ\kappa correction at small η\eta is open (Section IV.C). The saving factors of Table VII come from our cost model. The criterion-B theory remains open, and Table II contains LP estimates. The matched model evaluations cover two clean cells of one benchmark, whose other rows include 13 discrepancies between the stored counts and the implemented model.

Conclusion

Choosing the degree and the normalization of a QSVT inverse together, instead of rescaling the least-degree minimax polynomial for the same error criterion, lowers the amplified query cost by an amount that depends on the accuracy and on the error criterion. Under absolute reciprocal error, an entire-function extremal problem gives the optimal gain in the limit where the condition number grows with the error held fixed relative to it (Section IV). At high accuracy this gain has the leading term 0.1530ln⁡(κ/ε)0.1530\sqrt{\ln(\kappa/\varepsilon)}, which exceeds one only beyond ln⁡(κ/ε)=42.7\ln(\kappa/\varepsilon)=42.7. At practical accuracies the limiting gain is therefore known from certified two-sided bounds rather than from this leading term. At finite condition numbers the certificates of § 5 give lower bounds on the gain itself. At condition numbers 10510^5 and 10610^6 with absolute reciprocal error 10−1010^{-10}, the near-optimal constructions save at least 21 percent of the query cost (Table III). Under residual error, the sparse Chebyshev construction saves at least 13 percent at the same condition numbers with normalized-state error at most 10−1010^{-10} (Table VI).

The error criterion is therefore part of every cost estimate. A normalized solve gains the residual-error saving, whereas uses that need inverse-operator accuracy gain the absolute-error saving. Under the amplified-product cost model of Section VII, a product of two inverses gains more than a single inverse, because its cost scales with the square of the inverse normalization. Each factor of such a product needs its own error budget. Realizing these target polynomials in a circuit needs phase factors within an allocated phase and synthesis error (§ 5.C). Under criterion A at condition numbers 10510^5 and 10610^6 we expect phase finding to need extended-precision arithmetic. Computing those phase factors is the next step.

Acknowledgments

The author formulated the research question and directed the research and manuscript preparation. The author used AI tools to assist with literature research, mathematical analysis, code development, and manuscript preparation. The author takes full responsibility for the content of the paper and the Supplemental Material.

Proof of Proposition 1

Let p∗p^* be the unbounded minimax polynomial. Odd polynomials with mm odd terms form a Haar space of dimension mm on [ϑ,1][\vartheta,1], so p∗−1p^*-1 attains ±Λ\pm\Lambda with alternating signs at m+1m+1 points of [ϑ,1][\vartheta,1]. Every interior alternation point is a local extremum of p∗p^* and hence a zero of (p∗)′(p^*)'. The derivative is an even polynomial of degree 2m−22m-2, so it has at most m−1m-1 positive zeros. If ϑ\vartheta or 11 were not an alternation point, at least mm alternation points would be interior, which is too many. Hence both endpoints are alternation points, the m−1m-1 interior alternation points are all the positive zeros of (p∗)′(p^*)', and (p∗)′(p^*)' has no zero in (0,ϑ)(0,\vartheta). Then p∗p^* is monotone on [0,ϑ][0,\vartheta] with p∗(0)=0p^*(0)=0, so ∣p∗∣≤1+Λ|p^*|\le1+\Lambda on [0,ϑ][0,\vartheta], and by oddness on [−1,1][-1,1]. The polynomial p∗/(1+Λ)p^*/(1+\Lambda) is bounded by one and takes values in [(1−Λ)/(1+Λ),1][(1-\Lambda)/(1+\Lambda),1] on [ϑ,1][\vartheta,1], so its error is 2Λ/(1+Λ)2\Lambda/(1+\Lambda).

Conversely, let pp be bounded by one with error EE on [ϑ,1][\vartheta,1]. Then p∈[1−E,1]p\in[1-E,1] there, and p/(1−E/2)p/(1-E/2) approximates 11 on [ϑ,1][\vartheta,1] with error (E/2)/(1−E/2)(E/2)/(1-E/2). Hence Λ≤(E/2)/(1−E/2)\Lambda\le(E/2)/(1-E/2), which is E≥2Λ/(1+Λ)E\ge2\Lambda/(1+\Lambda).

Proof of Proposition 4

Put h(z)=1−zf(z)h(z)=1-zf(z). Since ff has type at most σ\sigma and ∣f∣≤B|f|\le B on R\mathbb{R}, log⁡∣h(z)∣≤σ∣Im⁡z∣+log⁡(1+B∣z∣)\log|h(z)|\le\sigma|\operatorname{Im}z|+\log(1+B|z|). Let Ωb=C∖((−∞,−1]∪[−b,b]∪[1,∞))\Omega_b=\mathbb{C}\setminus((-\infty,-1]\cup[-b,b]\cup[1,\infty)). In the upper half-plane define

Hb(z)=Re⁡[−i∫bzζ2−b2ζ2−1 dζ],(17)H_b(z)=\operatorname{Re}\left[-i\int_b^z\sqrt{\frac{\zeta^2-b^2}{\zeta^2-1}}\,\mathrm{d}\zeta\right], \tag*{(17)}

with the root tending to one at infinity, and extend HbH_b evenly to the lower half-plane. On the gaps b<∣x∣<1b<|x|<1 the integrand is imaginary, so the normal derivative of HbH_b vanishes and the reflection is harmonic in Ωb\Omega_b. Its boundary values are Hb=0H_b=0 on [−b,b][-b,b] and Hb=−R(b)H_b=-R(b) on ∣x∣≥1|x|\ge1, it equals −Jb(s)-J_b(s) at b<s<1b<s<1, and Hb(z)=∣Im⁡z∣−R(b)+O(∣z∣−1)H_b(z)=|\operatorname{Im}z|-R(b)+O(|z|^{-1}) at infinity. Let gb(z)=log⁡∣z/b+z2/b2−1∣g_b(z)=\log|z/b+\sqrt{z^2/b^2-1}| be the Green function of [−b,b][-b,b] with pole at infinity, so gb=0g_b=0 on [−b,b][-b,b], gb(x)=arcosh⁡(∣x∣/b)≥log⁡∣x∣g_b(x)=\operatorname{arcosh}(|x|/b)\ge\log|x| for ∣x∣≥1|x|\ge1, and gb(z)=log⁡∣z∣+log⁡(2/b)+o(1)g_b(z)=\log|z|+\log(2/b)+o(1). Define S=σHb+log⁡(1+Bb)+gbS=\sigma H_b+\log(1+B b)+g_b. On [−b,b][-b,b], log⁡∣h∣≤log⁡(1+B∣x∣)≤S\log|h| \le\log(1+B|x|) \le S. On ∣x∣≥1|x| \ge1, feasibility gives ∣h(x)∣=∣x∣∣1/x−f(x)∣≤∣x∣e−L|h(x)|=|x||1/x-f(x)| \le|x|e^{-L}, and L≥σR(b)L \ge\sigma R(b) gives log⁡∣h∣≤−σR(b)+log⁡∣x∣≤S\log|h| \le-\sigma R(b)+\log|x| \le S. At infinity both the linear and the logarithmic growth of log⁡∣h∣\log|h| are matched by SS, so log⁡∣h∣−S\log|h|-S is subharmonic in Ωb\Omega_b and bounded above. We subtract ϵgb\epsilon g_b and apply the maximum principle on truncated domains. We first let the truncation radius tend to infinity with ϵ>0\epsilon>0 fixed, and then take ϵ→0\epsilon\to0, which gives log⁡∣h∣≤S\log|h| \le S in Ωb\Omega_b. At z=sz=s this reads ∣1−sf(s)∣≤(1+Bb)T|1-sf(s)| \le(1+Bb)T. If Bs<1Bs<1, then 1−Bs≤1−sf(s)≤(1+Bb)T1-Bs \le1-sf(s) \le(1+Bb)T, which rearranges to (13). If Bs≥1Bs \ge1, the right side of (13) is at most 1/s≤B1/s \le B.

Outline of the upper bound in Theorem 3

Fix λ>1\lambda>1 and 0<b−<b+<bλ0<b_-<b_+<b_\lambda, and put c=λL/2c=\lambda L/2. In this appendix cc is the bandwidth of the prolate functions, not the normalization of § 2. The construction gives, for all large LL, an odd entire function fcf_c of type at most λL\lambda L with ∣fc(s)−1/s∣≤e−L|f_c(s)-1/s|\le e^{-L} for s≥1s\ge1 and ∥fc∥R≤1/b−+o(1)\|f_c\|_{\mathbb{R}}\le1/b_-+o(1). Letting b−↑bλb_-\uparrow b_\lambda then gives lim sup⁡L→∞Φ(λL/2,e−L)≤1/bλ\limsup_{L\to\infty}\Phi(\lambda L/2,e^{-L})\le1/b_\lambda, the upper half of Theorem 3. Sec. S5.2 gives the proof in five steps.

Prolate basis (Sec. S5.2.1). Let ψj,c\psi_{j,c} be the regular eigenfunctions, orthonormal on (−1,1)(-1,1), of

Pcψ=−((1−x2)ψ′)′+c2x2ψ=χj,cψ.\mathcal{P}_c\psi=-((1-x^2)\psi')'+c^2x^2\psi=\chi_{j,c}\psi.

Each extends to a real entire function of exponential type at most cc, because it is an eigenfunction of the finite Fourier transform u↦∫−11eicztu(t) dtu\mapsto\int_{-1}^{1}e^{\mathrm{i}czt}u(t)\,\mathrm{d}t, which commutes with Pc\mathcal{P}_c.

Kernel (Sec. S5.2.3). Choose a nonnegative φ∈Cc∞((b−2,b+2))\varphi\in C^\infty_c((b_-^2,b_+^2)) with integral one and put ω(Z)=∫φ(θ)1Z≤θ dθ\omega(Z)=\int\varphi(\theta)\mathbf{1}_{Z\le\theta}\,\mathrm{d}\theta for Z≥0Z\ge0. Extend ω\omega smoothly with compact support to Z<0Z<0, where the spectrum has no points, and define

Kc(x)=∑j≥0ω(χj,c/c2)ψj,c(x)2,Hc=Kc/Kc(0),fc(z)=1−Hc(z)z.(18)K_c(x)=\sum_{j\ge0}\omega(\chi_{j,c}/c^2)\psi_{j,c}(x)^2,\qquad H_c=K_c/K_c(0),\qquad f_c(z)=\frac{1-H_c(z)}{z}. \tag*{(18)}

The sum is finite, Kc(0)>0K_c(0)>0 for large cc, and HcH_c is even, nonnegative on R\mathbb{R} and entire of type at most 2c=λL2c=\lambda L with Hc(0)=1H_c(0)=1. So fcf_c is odd and entire of the permitted type.

Interior density (Sec. S5.2.2, Lemma S5.2). For every fixed r<1r<1 and integer ℓ≥0\ell\ge0,

Kc(x)=c2π∫Rω((1−x2)y2+x2) dy+O(1)in Cℓ([−r,r]).(19)K_c(x)=\frac{c}{2\pi}\int_{\mathbb{R}}\omega((1-x^2)y^2+x^2)\,\mathrm{d}y+O(1)\quad\text{in }C^\ell([-r,r]). \tag*{(19)}

The proof writes KcK_c as the integral, over the rotation orbits, of the kernel of ω(Aℏ)\omega(A_{\hbar}) for the operator Aℏ=−ℏ2∇S22+x2A_{\hbar}=-\hbar^2\nabla^2_{\mathbb{S}^2}+x^2 on the unit sphere, with ℏ=1/c\hbar=1/c. On rotation-invariant functions AℏA_{\hbar} acts as c−2Pcc^{-2}\mathcal{P}_c. The external input is Theorem 4.5 of Küster [21 arXiv v2], which we use with his symbol-class parameter equal to zero, his operator BB equal to the identity and his function family equal to ω\omega. For a closed manifold and a smooth real potential VV, it writes ω(−ℏ2∇2+V)\omega(-\hbar^2\nabla^2+V) as a sum of localized Weyl quantizations of ω\omega composed with the classical Hamiltonian ∣ξ∣2+V|\xi|^2+V, plus terms whose symbols are O(ℏ)O(\hbar) with all derivatives and an operator of trace O(ℏk)O(\hbar^k) for every fixed kk. The remainder enters only through its operator norm. Step 7 of Lemma S5.2 combines it with a priori Sobolev bounds on the eigenfunctions to obtain a pointwise CℓC^\ell bound on the kernel. The sphere is closed and x2x^2 is smooth on it, so the theorem applies as stated. The leading term gives Hc→HωH_c\to H_\omega in CℓC^\ell on [−r,r][-r,r], where HωH_\omega is a convex mixture of the functions (θ−x2)/(θ(1−x2))\sqrt{(\theta-x^2)/(\theta(1-x^2))} over θ∈(b−2,b+2)\theta\in(b_-^2,b_+^2). Hence ∣fc∣≤1/b−+O(1/c)|f_c|\le1/b_-+O(1/c) on [0,r][0,r].

Forbidden region (Subsection S5.2.4 and Lemma S5.4). Choose r∈(b+,1)r\in(b_+,1). Eigenfunctions with χj,c≤c2b+2\chi_{j,c}\le c^2b_+^2 have no zeros in (b+,1)(b_+,1) and decrease there, so 0≤Hc≤O(1/c)0\le H_c\le O(1/c) on [r,1][r,1]. An elementary barrier and Sonin estimate (Lemma S5.4) gives sup⁡x≥1∣ψj,c(x)∣≤Πce−cτ\sup_{x\ge1}|\psi_{j,c}(x)|\le\Pi_c e^{-c\tau} for every fixed τ<R(b+)\tau<R(b_+), with a prefactor Πc\Pi_c polynomial in cc. Its constants are independent of jj for all χj,c≤c2b+2\chi_{j,c}\le c^2b_+^2. At most cb++1cb_++1 modes enter, and Kc(0)K_c(0) is of order cc. After division by Kc(0)K_c(0), Hc(x)H_c(x) is at most a constant times (1+c)2e−2cτ(1+c)^2e^{-2c\tau} on [1,∞)[1,\infty), and ∥fc∥R≤1/b−+o(1)\|f_c\|_{\mathbb{R}}\le1/b_-+o(1).

Feasibility (Sec. S5.2.5). Because b+<bλb_+<b_\lambda, R(b+)>1/λR(b_+)>1/\lambda. With τ\tau strictly between the two, ∣fc(s)−1/s∣=Hc(s)/s≤e−L|f_c(s)-1/s|=H_c(s)/s\le e^{-L} for s≥1s\ge1 and all large LL.

Küster’s theorem is the only external theorem in the interior-density step. Step 3 of the proof of Lemma S5.2 checks its hypotheses. The same proof computes the reduction along the rotation orbits explicitly.

Certifying the gap maximum

Lemma 7. Let qq be an odd polynomial of degree NN, B=amax⁡[−1,1]∣q∣B=a\max_{[-1,1]}|q| and F(s)=aq(as)F(s)=aq(as). Then for 0≤s≤10\le s\le1,

∣F′′(s)∣≤CDB,CD=a2[N21−a2+aN(1−a2)3/2].(20)|F^{\prime\prime}(s)|\le C_D B,\qquad C_D=a^2\left[\frac{N^2}{1-a^2}+\frac{aN}{(1-a^2)^{3/2}}\right]. \tag*{(20)}

If CD<8K2C_D<8K^2, the maxima of ∣F∣|F| on a grid of spacing 1/K1/K in [0,1][0,1] are at most gg, and ∣F∣≤1+η|F|\le1+\eta on [1,κ][1,\kappa], then B≤max⁡{1+η,g/(1−CD/(8K2))}B\le\max\{1+\eta,g/(1-C_D/(8K^2))\}.

Proof. Put x=sin⁡θx=\sin\theta and u(θ)=q(sin⁡θ)u(\theta)=q(\sin\theta), a trigonometric polynomial of degree NN. Bernstein’s inequality gives ∣u′∣≤N∥q∥|u^\prime|\le N\|q\| and ∣u′′∣≤N2∥q∥|u^{\prime\prime}|\le N^2\|q\|, and q′′(x)=[u′′(θ)cos⁡θ+u′(θ)sin⁡θ]/cos⁡3θq^{\prime\prime}(x)=[u^{\prime\prime}(\theta)\cos\theta+u^\prime(\theta)\sin\theta]/\cos^3\theta, so ∣q′′(x)∣≤[N2/(1−x2)+N∣x∣/(1−x2)3/2]∥q∥|q^{\prime\prime}(x)|\le[N^2/(1-x^2)+N|x|/(1-x^2)^{3/2}]\|q\|. With F′′(s)=a3q′′(as)F^{\prime\prime}(s)=a^3q^{\prime\prime}(as) and as≤aas\le a this gives the first bound. Between two grid points, ±F\pm F lies below its linear interpolant plus CDB/(8K2)C_DB/(8K^2), so the maximum of ∣F∣|F| on [0,1][0,1] is at most g+CDB/(8K2)g+C_DB/(8K^2). If BB is attained on [0,1][0,1] this gives B≤g+CDB/(8K2)B\le g+C_DB/(8K^2), hence B≤g/(1−CD/(8K2))B\le g/(1-C_D/(8K^2)) because CD<8K2C_D<8K^2, and otherwise B≤1+ηB\le1+\eta.

For the rule polynomials at κ=105\kappa=10^5 and 10610^6, NN is about 4×1064\times10^6 and 4×1074\times10^7 and aNaN is about 40. The grid spacing 1/K1/K with K=105K=10^5 then gives CD/(8K2)≈2×10−8C_D/(8K^2)\approx2\times10^{-8}. At κ=104\kappa=10^4, N=284445N=284445, aN≈28aN\approx28 and CD/(8K2)≈1.0×10−8C_D/(8K^2)\approx1.0\times10^{-8}. The grid values are evaluated at exact rational points in ball arithmetic.

Reproducibility

The computations used Python 3.12.13, NumPy 2.5.2, SciPy 1.18.0, mpmath 1.3.0, python-flint 0.9.0 and HiGHS 1.15.1, with MATLAB for the large phase calculation. The public set in anc/verification_set/ contains the inputs, programs and expected outputs of every certified result. Its guide is anc/verification_set/README.txt. Its checksums and licences are in anc/verification_set/SHA256SUMS.txt and anc/verification_set/LICENSE.txt. The other records are available from the author on request. They contain the programs, inputs and logs behind measured results. Third-party code and files are excluded. These exclusions cover the phase solver of Ni and Ying and the source files of the matched comparison. The records include the solver’s output phases and our checks.

claimcertificate and expected output
A finite targets, Table IIIanc/verification_set/verify.py a_targets, norm upper and gain lower bounds of Sec. S7.3
limiting frontier and gainanc/verification_set/verify.py limiting, the two-sided intervals in the supplement’s certificate index
elliptic constantsanc/verification_set/verify.py constants_windows, the intervals of Corollary 5
B finite targets, Table VIanc/verification_set/verify.py b_targets, fit ratios below one and norm/gain bounds of the six-row certificate table of Sec. S12

Table 3.

The matched source is https://gitlab.ibr.cs.tu-bs.de/alg/qls-comparison, commit e12600d5. The SHA-256 hashes of evaluation/query_costs.py and the extracted results .txt, respectively, are

757b9e4b234090f8b32fa0590484c34a441c0f8b4e7d1b161f131c5c9c5c3eb7 2ef7a7f1f11436c8b90f4265a7f09609fd99e8992828a9128fe460796b2adfa7

Our independent model implementation follows the source in skipping the k=1k=1 term and dropping the final dyadic block when its sum is below 0.1. The README.txt of the records available on request gives recount commands with these hashed inputs. Their files are not redistributed or executed.

References

  1. [1]András Gilyé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 (STOC 2019). Pages 193–204. (2019). arXiv:1806.01838.DOI
  2. [2]John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. “Grand unification of quantum algorithms”. PRX Quantum 2, 040203 (2021). arXiv:2105.02859.DOI
  3. [3]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, 1920–1950 (2017). arXiv:1511.02306.DOI
  4. [4]Bjorn K. Berntson and Christoph Sünd er hauf. “Two exact quantum signal processing results”. In 2024 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). Pages 625–626. Knoxville, TN, USA (2024). arXiv:2505.10710.DOI
  5. [5]Christoph Sünderhauf, Zalán Németh, Adnaan Walayat, Andrew Patterson, and Bjorn K. Berntson. “Matrix inversion polynomials for the quantum singular value transformation” (2025). arXiv:2507.15537.arxiv.org/abs/2507.15537
  6. [6]Alexandre Eremenko and Peter Yuditskii. “Polynomials of the best uniform approximation to sgn(x) on two intervals”. J. d’Analyse Math. 114, 285–315 (2011). arXiv:1008.3765.arxiv.org/abs/1008.3765
  7. [7]Yulong Dong, James B. Larsen, Lin Lin, and Rahul Sarkar. “Constrained minimax approximation for quantum signal processing” (2026). arXiv:2608.30937.arxiv.org/abs/2608.30937
  8. [8]Matthias Deiml and Daniel Peterseim. “Constrained optimal polynomials for quantum linear system solvers” (2026). arXiv:2604.20513.arxiv.org/abs/2604.20513
  9. [9]Kiran Adhikari. “Krylov polynomials and quantum query complexity” (2025). arXiv:2510.11786.arxiv.org/abs/2510.11786
  10. [10]David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yiğit Subaşı. “Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs”. PRX Quantum 6, 040373 (2025). arXiv:2305.11352.DOI
  11. [11]Alexander M. Dalzell. “A shortcut to an optimal quantum linear system solver” (2024). arXiv:2406.12086.arxiv.org/abs/2406.12086
  12. [12]M. I. Ganzburg. “Limit theorems in approximation theory”. Anal. Math. 18, 37–57 (1992).DOI
  13. [13]M. I. Ganzburg. “Sharp constants of approximation theory. IV. Asymptotic relations in general settings”. Anal. Math. 49, 79–136 (2023). arXiv:2002.10512.arxiv.org/abs/2002.10512
  14. [14]Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. “Fast inversion, preconditioned quantum linear system solvers, fast Green’s-function computation, and fast evaluation of matrix functions”. Physical Review A 104, 032422 (2021). arXiv:2008.13295.DOI
  15. [15]Pedro C. S. Costa, Dong An, Ryan Babbush, and Dominic Berry. “The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver”. Quantum 9, 1887 (2025). arXiv:2312.07690.DOI
  16. [16]Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti, Antonio F. Rotundo, Shawn E. Skelton, and Martin Steinbach. “Beyond asymptotic scaling: comparing functional quantum linear solvers”. IEEE Transactions on Quantum Engineering 7, 1–26 (2026). arXiv:2503.21420.arxiv.org/abs/2503.21420
  17. [17]Q. Huangfu and J. A. J. Hall. “Parallelizing the dual revised simplex method”. Mathematical Programming Computation 10, 119–142 (2018).arxiv.org/abs/1503.01889
  18. [18]H. Ehlich and K. Zeller. “Schwankung von Polynomen zwischen Gitterpunkten”. Mathematische Zeitschrift 86, 41–44 (1964).DOI
  19. [19]D. S. Lubinsky. “On the Bernstein constants of polynomial approximation”. Constr. Approx. 25, 303–366 (2007).DOI
  20. [20]D. Slepian and H. O. Pollak. “Prolate spheroidal wave functions, Fourier analysis and uncertainty – I”. The Bell System Technical Journal 40, 43–63 (1961).DOI
  21. [21]Benjamin Küster. “On the semiclassical functional calculus for h-dependent functions”. Annals of Global Analysis and Geometry 52, 57–97 (2017). arXiv:1507.06214.
  22. [22]Alexandre Eremenko and Peter Yuditskii. “Comb functions”. Contemp. Math. 578, 99–118 (2012). arXiv:1109.1464.arxiv.org/abs/1109.1464
  23. [23]Fredrik Johansson. “Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic”. IEEE Transactions on Computers 66, 1281–1292 (2017).arxiv.org/abs/1611.02831
  24. [24]Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang. “Robust iterative method for symmetric quantum signal processing in all parameter regimes” (2023). arXiv:2307.12468.arxiv.org/abs/2307.12468
  25. [25]Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. “Efficient phase-factor evaluation in quantum signal processing”. Phys. Rev. A 103, 042419 (2021). arXiv:2002.11649.DOI
  26. [26]I. Novikau and I. Joseph. “Estimating QSVT angles for matrix inversion with large condition numbers”. Journal of Computational Physics 525, 113767 (2025). arXiv:2408.15453.DOI
  27. [27]Hongkang Ni and Lexing Ying. “Fast phase factor finding for quantum signal processing” (2024). arXiv:2410.06409.arxiv.org/abs/2410.06409
  28. [28]Bjorn K. Berntson and Christoph Sünd er hauf. “Complementary polynomials in quantum signal processing”. Commun. Math. Phys. 406, 161 (2025). arXiv:2406.04246.DOI
  29. [29]Leigh Lapworth and Christoph Sünd er hauf. “Preconditioned block encodings for quantum linear systems”. Quantum Science and Technology10 (2025). arXiv:2502.20908.DOI
  30. [30]Hongkang Ni, Rahul Sarkar, Lexing Ying, and Lin Lin. “Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing” (2025). arXiv:2505.12615.arxiv.org/abs/2505.12615
  31. [31]Jacob S. Nelson and Andrew B. Baczewski. “Estimating Green’s functions with a robust quantum Arnoldi method” (2026). arXiv:2605.22920.arxiv.org/abs/2605.22920

Paper details

vlnc:W_sjw3z9ta
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

AI tools

View statement
Looking for related papers…
Contents