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 . If approximates on for condition number , QSVT implements a scaled polynomial , where the normalization cannot exceed the reciprocal of the maximum of on . With amplitude amplification, the query cost depends on both the polynomial degree and the inverse norm . 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]. 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 [5]. However, inside the spectral gap it exceeds 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 [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 error, at condition numbers 3 and 5 and degrees up to 16 [8]. Adhikari formulates an 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 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:
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.
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.
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.
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 with error , and at least 22.8 percent at with error . The sparse Chebyshev construction under criterion B has certified savings over the residual-minimax baseline of at least 8.7 percent at condition number with normalized-state error at most , and at least 13.1 percent at and with error at most .
The study map below summarizes the three questions these results address, with the corresponding analyses and evidence.
| Question | Analysis and section | Evidence 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 . We consider odd polynomials in the span of the first odd Chebyshev terms,
whose degree is at most . Under criterion A, such a is feasible for absolute reciprocal error when
The error bounds itself, not its ratio to . For a matrix with and , the inversion algorithm applies to the singular values of , which lie in . For , QSVT applied to a block-encoding of gives , which approximates . The computed vector therefore differs from by at most . Hence bounds the relative error of the solution vector. In a solve we take , so the computed vector is nonzero. Since the circuit applies and the solution state is normalized, the error of the normalized solution state does not depend on the normalization. This error is at most . The bounded frontier is
Because is odd, its maximum over equals its maximum over . QSVT can therefore implement with .
Cost model. In a linear solve with amplitude amplification and a unit vector , the QSVT circuit prepares the solution state with an amplitude equal to times the norm of the computed vector. By the bound above, this norm lies within a factor of , which is common to all polynomials. The amplitude is therefore proportional to up to this factor. The number of amplification rounds is proportional to . Each round uses a transformation of degree at most . We count its query budget as , so the amplified query budget is proportional to . We use
as the cost. We assume that the block-encoding of is exact and count each query to it at the same cost. The certified savings do not cover errors in 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 and its reciprocal. At the certified points of § 5 this factor differs from one by less than . Section VII discusses uses of the inverse in which the cost depends on differently.
Baseline. The minimax polynomial without the bound is known in closed form [5]. Sec. S1 proves the value of its error. With , and ,
Let be the least with . Let be the overshoot of this polynomial in units of . The rescaled minimax polynomial is realizable and costs . In the gap grows pointwise with (Corollary S1.4). At every criterion-A parameter point where this paper reports a gain, ball arithmetic gives (program overshoot-scan.py). The right-hand side bounds over . The maximum therefore lies in the gap. Every with then has norm at least and a larger rescaled cost. Hence is also the best degree for rescaling. We report the gain
A gain is a cost reduction by the fraction . Using instead of (4) lowers every criterion-A gain below by a relative amount of at most over the degrees we compare, . This amount is about in Table I, below at and below at and .
| , | , | cost reduction | |||||
| 16.12 | 8.07 | 1.040 | 1.035 | 1.27 | 1.32 | 3.4–3.9% | |
| 18.42 | 9.22 | 1.077 | 1.069 | 1.24 | 1.33–1.34 | 6.5–7.2% | |
| 19.62 | 9.82 | 1.092 | 1.093 | 1.24 | 1.36 | 8.4–8.5% | |
| 20.72 | 10.38 | 1.101 | 1.099 | 1.24 | 1.36–1.37 | 9.0–9.1% | |
| 21.93 | 10.97 | 1.126 | 1.117 | 1.21 | 1.35–1.37 | 10.5–11.2% | |
| 23.03 | 11.53 | 1.137 | 1.137 | 1.21 | 1.38 | 12.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 on , with . If , then
Thus , the normalized-state error is at most in the 2-norm, and . The cost model above applies with in place of .
Matrix functions, absolute-error matrix elements and products of inverse block-encodings need the operator guarantee of [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 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)]
Its least feasible number of odd terms is . Write . For a feasible degree- polynomial of norm at most , we report . The Chebyshev window of Section VI is .
The choice of error criterion changes the comparison. At the three criterion-A points of Table III, equal state guarantees mean . Then 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, , our A construction is 1.17 to 1.32 times cheaper than . These are numerical evaluations of the stated cost model. We use no other pairing for a comparison of costs across the criteria.
| construction | odd terms | , upper | , lower | CKS factor | |
| CKS times rectangle, | 290 933 | 2 | – | 1 | |
| rescaled minimax (baseline) | 1 | 2.27 | |||
| near-optimal, 321 coefficients | 139 671 | 1.611930 | 1.13497 | 2.58 | |
| two-term family, rule (16) | 142 223 | 1.625258 | 1.10546 | 2.51 | |
| CKS times rectangle, | 4 196 178 | 2 | – | 1 | |
| rescaled minimax (baseline) | 1 | 1.80 | |||
| near-optimal, 321 coefficients | 2 224 248 | 1.646030 | 1.27162 | 2.29 | |
| two-term family, rule (16) | 2 015 103 | 1.913170 | 1.20761 | 2.17 | |
| CKS times rectangle, | 45 279 290 | 2 | – | 1 | |
| rescaled minimax (baseline) | 1 | 1.76 | |||
| near-optimal, 321 coefficients | 23 437 824 | 1.686593 | 1.29613 | 2.29 | |
| two-term family, rule (16) | 21 330 651 | 1.965489 | 1.22208 | 2.16 |
Table III. Certified target polynomials under criterion A.
Scaling variables. We write , and . We call the scaled error because it compares with the largest value of on . Because for small , the minimal unbounded degree satisfies . We write . At with , and . At with , and . The degree is then . In the same limit the overshoot of the minimax polynomial tends to
where is the scaled gap coordinate. For large , with and (Sec. S4). At finite we evaluate from (5). It equals 2.69590 at and 2.78144 at .
Measured trade-off
Method. This section measures the gain (6) directly, by linear programs at condition numbers up to 40. For given we solve (3) as a linear program in the coefficients and the bound . The error constraint is imposed on a finite set of points of . The bound constraint is imposed on a finite set of points of . 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 and clustered at . The clustering is needed because the error of the extremal oscillates near on a scale far below the node spacing of . The large local maxima of the error and of 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 . The reported is the Ehlich–Zeller upper bound computed from the values at Chebyshev nodes [18]. It exceeds the attained maximum by at most relative. We compute with the same bound. This factor therefore cancels in to about . Accepted solutions satisfy (2) on the verification grid to within relative plus a floor of . At the floor amounts to relative. As a control, the program reproduces the exact error of (5) within relative in all 9 tested cases, at and 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 . Sec. S10 gives the details.
Result. Table I reports the gain at and 40. Its column is the scaled minimal unbounded number of terms at . The column is the degree ratio at the minimum cost on the grid. The column is the increase of the normalization at that degree. In the table, and the cost reduction are computed from the unrounded gains and rounded down. At and , 9 of the 12 grid points converged. For each the minimum over is taken on a grid of twelve values of from 1 to 1.5. A minimum over a grid can only overestimate the least cost. Up to the stated tolerances, each reported 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 . The gains at the two condition numbers agree within 0.009 in . In four of the six rows is slightly lower at .
The certified point with of § 5 has , as in the last row of the table. Two condition numbers do not fix the gain at . As grows at fixed , the gain converges to the limiting gain of Section IV. At this the limiting gain lies between 1.1382 and 1.1387. Table III gives certified values at for a near-optimal construction and for the two-term rule.
Mechanism. At the minimal degree itself, the LP estimate improves on the overshoot 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 and in return raises the normalization by 31 to 38 percent. Below the gain is at most 1.01, because the overshoot is itself small.
| 1.0467 | 1.0511 | 1.27 | |
| 1.0842 | 1.0893 | 1.24 | |
| 1.1071 | 1.1050 | 1.23 | |
| 1.1155 | 1.1191 | 1.22 | |
| 1.1352 | 1.1333 | 1.21 | |
| 1.1425 | 1.1440 | 1.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 near the gap account for the gain above. It does not compare costs across degrees.
Proposition 1. For , let be the least uniform error on of an odd polynomial with odd terms approximating the constant 1, and assume . Among such polynomials that are also bounded by one in magnitude on , the least error on is exactly . It is attained by the unbounded minimax polynomial divided by .
The proof is in Appendix § 11. Linear programs at agree with within relative in 46 of 48 cases. The other two lie at the double-precision floor (Sec. S10). The bound costs about additional odd terms. At this is 17 percent of the degree at error and 4 percent at 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 , far above its values on .
Residual-error frontier. Table II gives the counterpart under B. The LP uses as its variable, so it constrains the residual directly. A formulation in loses accuracy when coefficients of order cancel to a residual of order , and fails at . 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 by up to 0.031 percent. At the estimated gains are 1.0042 and 1.0083, and at and the estimates agree with the baseline within 0.0020. With from downwards, the B gains exceed those of Table I by 0.005 to 0.020. This pairing equates the tolerances at the gap edge . In scaled coordinates the constraints are under A and under B for . 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 , far below the condition numbers of resource estimates. We therefore study criterion A as at fixed scaled error. In this limit tends to infinity, so this is an approximately theoretical scaling limit and not a family of increasingly accurate solves. For and , let
Here . The substitution maps a feasible polynomial with odd terms to an odd function that approximates on with error . Its Bernstein–Walsh growth tends to exponential type as .
Theorem 2 (Scaling limit). Fix , and let and . If , then . If , the same holds along every sequence of feasible finite
problems, that is, with for , and along some sequences with the finite problems are eventually all infeasible. If , the finite problems are eventually infeasible. For the infimum in (8) is attained.
The threshold case uses the uniqueness of as a feasible function at , proved in Proposition S2.4 with the dual identities (10).
Sec. S2 proves Theorem 2. Fix constants and . For margins and types , explicit transfer bounds give
where the implied constant depends on and . 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 , 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 whose pole lies at the end of the gap , which stays fixed under the scaling. Its limit is also infinite below the threshold 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 . Take the nodes and , where , and the weights and . Then every bounded odd entire of type at most satisfies
The signed measure with mass at each therefore certifies that no such approximates on with error below . The limit of the minimax polynomials attains that error. The identities (10) also yield a convergent hierarchy of finite linear programs for . Their certified lower bounds and the explicit constructions of Section V and Sec. S7.1 enclose 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 be the optimized limiting cost relative to . The limiting gain is then . The behaviour of along a fixed degree ratio is governed by the action
where and are the complete elliptic integrals of the first and second kind, with the parameter as argument. Since decreases strictly from 1 to 0, has a unique root for every .
Theorem 3 (Asymptotic frontier). For every fixed ,
Sec. S5 proves Theorem 3, with both strict inequalities, and Corollary 5 below. The lower bound follows from an inequality that holds before any limit.
Proposition 4 (Finite lower bound). Let be odd entire of type at most with and for . For with , put and . Then
Appendix § 12 proves the bound with a harmonic majorant on the plane cut along and . With and , the factor tends to zero for every fixed . Hence . Letting gives the lower bound. The bound also shows that, along any family of feasible functions with bounded norm, on as grows. The norm is set by continuing the reciprocal down to .
The matching upper bound uses a weighted sum of squared prolate spheroidal functions [20] as a kernel , with . The local density of follows from smooth semiclassical functional calculus on the sphere [21], arXiv v2, Theorem 4.5. The exterior decay of 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 .
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 , attained at the unique with , that is and . Consequently
Theorem 3 holds for each fixed . The limit of also needs the minimum over . Sec. S5 shows that the convergence is uniform on compact subintervals of . It also shows that near-minimizing stay in such a subinterval, which gives . In finite terms the asymptotically optimal design uses about odd terms and has . The rescaled minimax polynomial uses odd terms and has . The two curves of Theorem 3 alone give the brackets for and 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 at fixed (Theorem 2). It gives the limiting gain . Sec. S2 shows that for . Unlike in (6), is not at least one by definition, because is a norm on all of whereas is a maximum over the gap. It is at least one for , which covers the criterion-A Table I, Table III and Table IV and Figure 2. The function is feasible at . For its norm on equals (Sec. S2), so .
| best found | best found | best found | best found | , rule | |
| 17 | 31.49 | 0.768 | 1.216 | 1.0175 | 1.0165 |
| 20 | 36.09 | 0.764 | 1.190 | 1.0669 | 1.0654 |
| 24 | 42.03 | 0.764 | 1.165 | 1.1186 | 1.1167 |
| 28 | 47.81 | 0.766 | 1.146 | 1.1593 | 1.1571 |
| 32 | 53.87 | 0.763 | 1.131 | 1.1922 | 1.1898 |
| 36 | 59.44 | 0.767 | 1.119 | 1.2195 | 1.2169 |
| 40 | 65.58 | 0.764 | 1.110 | 1.2424 | 1.2398 |
Table IV. The two-term family at , best found and rule.

Figure 2. Gain over the rescaled minimax polynomial as a function of . LP estimates of the bounded optima at and (circles), certified near-optimal constructions at with and at and with (squares), the limiting gain as at fixed (black dashes, which are thicker than the certified brackets), the two-term family at (solid, best found, and dashed, rule (16)) with the certified rule points at , and (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 from below (Sec. S7). Because does not increase with the type, lower bounds on at finitely many degree ratios give an upper bound on (Sec. S3.6). Sec. S3 derives from the dual identities (10) the explicit lower bound
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 at , at , at , at and at (Figure 2). The upper ends bound the saving of every bounded polynomial in this limit. At , and , 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 , the optimum over all degree ratios.
The second limit is (Theorem 3 and Corollary 5). It describes practical accuracies poorly. Its leading term exceeds one only for , that is for . At and 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 and 1.503 for and at for . At the rigorous lower bound gives 1.856 at , and the limit is 2.474. The linear program gives 1.579 at and . The deficit of the lower bound (13) decays only as . 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 as (solid), with the two bounding curves of Theorem 3. Squares are rigorous lower bounds from Proposition 4 at . Circles are linear-program values at , at and . The computed values lie below the limit and approach it slowly.
Finite condition number. At fixed interior , a negative correction to is at most of order . This bound holds along with integer , where exactly. A positive correction of order occurs at exact in the following example. At and the problem is solved exactly by the scaled Chebyshev polynomial, with and a positive first-order correction per unit of . Our linear program reproduces this correction within relative at from 2 to 32. Rounding so that can add a further term of order . Sec. S6 gives the proofs. Neither the sign nor the leading coefficient of the correction at small is established. The brackets of 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 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 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 over odd entire functions of exponential type at most , bounded on , with for . The scaling limit of is
It is feasible exactly when . 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 to the degree is to , beyond any direct linear program. We give two kinds of explicit polynomial and certify both.
Near-optimal constructions
An odd entire function of type is built from 321 coefficients,
with fixed analytically so that 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 . Mixing in with weight about gives a function with exterior error at most . The norm of lies within 0.038 percent of at its bandwidth. Near-optimal refers to this property at the chosen bandwidth. The gain of is less than 0.1 percent below the limiting gain , which is the optimum over all bandwidths (Section IV.C). A second mixture with weight about gives with exterior error at most , which reserves for the truncation. The polynomial is times the truncation at odd degree of the exact Chebyshev expansion of . 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 in . We bounded it from points of one period at which every angle is an exact rational multiple of , with every alias of each point bounded. We bounded the norm from gap points under a Bernstein bound. At and we used the function constructed for . We chose the number of terms by the truncation rule of Sec. S7, minimized over its ellipse parameter. The certified gains are at , at and at . 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 at and at and . For each construction it gives the number of odd terms, the certified upper bound on and the certified lower bound on the gain of (6). For the baseline, the rescaled minimax polynomial, the column gives to five decimals. It enters through a certified lower bound on , 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 gives the entry 2 for . The number of odd terms is for the CKS polynomial alone, with , degree and . 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 . 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 and integers , the polynomial has at most odd terms and satisfies .
Proof. For , has degree . For , its degree is . On , , so by (5), and (Sec. S1).
For given , Proposition 6 therefore gives an explicit formula for the least it certifies. Only 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 with this . We optimized at 47 points, at for from 8 to 40, at , and for , and at the practical points and . At fixed the gain rises with up to an abrupt drop, where a second local maximum of in the gap exceeds the first. At and , for example, falls from 1.209 at 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 and it gives .
The optimal gain depends on alone to the precision we measured. At , 28 and 36 it agrees across from to within . The optimal parameters depend on more strongly. Our search covered at every . In this range the family first gives a lower cost than the baseline between and 17. At the best member found has , below the baseline . The optimal gain rises to 1.2424 at (Table IV). Across all 35 points where the family costs less than the baseline, the optimal lies between and . At the optimal lies within 0.45 percent of the line , its least-squares fit. At the other condition numbers it lies within 3.6 percent of this line. This gives the rule
for , with 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 . Over the 35 points the rule loses at most 0.22 percent of against the best value found at each point. At , and and at half-integer from 17.5 to 39.5, outside the fitting set, it stays within 0.22 percent of the best values found, interpolated in between the fitting points. A parameter past the drop cannot make the polynomial infeasible, because and are computed for the chosen parameters. It only lowers . We tested margins around the rule with from to and 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 shows.
Table IV lists the best found values and the rule at . The optimizer evaluates the gap maximum on a uniform grid of 8001 points with golden-section refinement, which gives the columns , and . The column “, best found” is re-evaluated on 400001 gap points (Sec. S11). The column “, rule” is re-evaluated on 40001 points. All values in the table are measured. The two columns are rounded down. The parameter columns are rounded to the digits shown.
Procedure. For given and with the polynomial and its normalization follow in five steps.
Allocate the polynomial error and use it as in the rule. Put and , and take , and from (16).
Form from (5). Proposition 6 gives on , so the error needs no check.
Compute . For the rule polynomials we certified, the maximum lies inside the gap near , where (5) is accurate in double precision. Lemma 7 gives a rigorous bound from values evaluated in ball arithmetic on a fine grid.
Apply with . The margin , for example , leaves the target below the norm bound one and divides by . It is a normalization margin, not an error reserve. In unscaled reciprocal-error units, calculate . The last two terms include the factor that converts implementation errors to these units.
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 .
Reserving part of 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 raises by . By interpolation in that table the gain of the rule then rises by 0.3 to 1.1 percent.
At the rule gives , and at . At it gives , and . A separate interval computation, run without knowledge of our floating-point values, certified and (Table III). It bounds the gap maximum from 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 . Our floating-point values agree to seven digits. At and the rule gives , and . We certified this point with a copy of the same code and obtained . The copy first reproduced the certificate at 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 and . The family optimum recovers 78 and 79 percent of the linear-program optimum at and .
Phase factors
QSVT applies a polynomial through a sequence of phase angles, where is the degree. Computing these angles is a separate numerical problem, which becomes harder with the degree and as approaches one. We computed them for the rule polynomials (16) at and , scaled to with a margin . 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 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 over the verification points, evaluated in double precision. Its last column is the largest value of over the verification points in . The realized polynomial was evaluated from the angles at Chebyshev-angle points, 12000 points in the gap and 1201 points clustered at . 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 . A 50-digit evaluation at 200 points of each run gives differences to the target of at most . In every case at all verification points. The rescaled polynomial meets the error at those of . The margin divides by . Sec. S11 gives the details.
| degree | Newton iterations, time | error | realized error/ | ||
| 100 | 2531 | 9, 3.9 s | 0.99312 | ||
| 100 | 2531 | 11, 4.6 s | 0.99311 | ||
| 500 | 12653 | 10, 116 s | 0.99794 | ||
| 500 | 12653 | 11, 128 s | 0.99794 | ||
| 2000 | 50609 | 10, 2298 s | 0.99952 |
Table V. Phase factors of the rule polynomials at .
Phase factors computed for an inversion polynomial itself, rather than estimated by extrapolation, have been obtained up to with the normalization fixed at [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 [27]. Berntson and Sünderhauf computed complementary polynomials, the first step of such methods, up to degree [28]. Lapworth and Sünderhauf computed 14011 phase factors for an inversion polynomial at an effective condition number of 2500 and error 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 in each step, which took about 230 s at . The degrees of the certified points, to , therefore need one of those faster methods.
The certified point at . We computed the phase factors of the rule polynomial of Table III at and , of degree 284445, scaled by its certified with . 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 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 in the gap and by at most on . A scan at 20 points per oscillation found 15221 local maxima of the target error ratio on above 0.99. We refined these locations and evaluated the realized polynomial there. The largest realized error ratio 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 at these points. At every point evaluated, . 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 with no phase reserve. The realized-error evidence is the direct check at the refined points. By the triangle inequality, the sampled discrepancy corresponds to about after multiplication by , about 22 times the unused target error . A design with 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 and with , the polynomial divided by its maximum must be realized to an absolute error below , that is below and , because exceeds . This is beneath the double-precision rounding error accumulated over the to 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 and at . 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 . With , even and , put
and . The last coefficient of enforces exactly, so is an odd polynomial. On the fit is a cosine polynomial of degree in . In the gap it is , where . We optimize the coefficients at finite with . 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 . The gain is relative to the known residual-minimax polynomial at . 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 with normalized-state error at most , and 13.1 percent at with error at most , all in the 2-norm. The first gain lies between the small- LP values at and . This is consistent with a scaling picture but does not prove one.
| , upper | , lower | |||
| 122560 | 1.505454 | 1.095883 | ||
| 1464640 | 1.635012 | 1.151636 | ||
| 14635200 | 1.636157 | 1.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 throughout. For a fixed and an even window with Chebyshev terms, the product is linear in . We can therefore find the best window for given by a linear program. The window is restricted only by its number of terms. At and , over from 1 to 1.1 and from 0.02 to 0.3 (120 cases, all feasible and converged), the windowed cost 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 appreciably only once exceeds . At , and , falls from 2.0 to 1.30. The cost ratio is then 1.63. The reason is that the window must stay within about of one at each of , while dropping inside the gap. Near the gap edge this tolerance is about . 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 exceeds , a constant window below one already lowers at no degree cost. Without that slack there is a counterexample at and , with cost ratio below 0.76. As , the best windowed cost over the rescaled cost tends to zero like . In the iterated limit, first and afterwards, 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 the cost tends to 1.673 times the rescaled cost. These limits give no bound at a finite , so the null result at the tested accuracies rests on the 120 cases above. At the points to of Table III we have no measurement of the best window. At and , 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 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 of § 5.D. The criterion-A gain (6) applies where absolute inverse operator accuracy is required. When a block-encoding of or of a resolvent is a factor inside a larger algorithm, enters the total cost differently. Table VII separates these uses at . The two solve rows use criterion B. They compare the sparse construction with at . Their normalized-state 2-norm error is at most . 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 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 by the factor at 1.2724 times the degree. A cost proportional to therefore falls by the factor .
| use | dependence on | saving factor |
| single solve with amplitude amplification | linear | 1.15 |
| observable estimation, e.g. Green’s functions [14, 31] | linear, through amplitude estimation | 1.29 / 1.22 |
| solve without amplitude amplification (repeat until success) | quadratic | 1.59 |
| amplified product of two inverse block-encodings | quadratic | 2.13 / 1.72 |
| chain of non-unitary steps | power that grows with | grows with the chain |
Table VII. Saving factors in the stated cost model.
Without amplitude amplification a solve succeeds with probability proportional to . The expected number of repetitions and the cost then scale as . 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 . For the polynomial of Table VI, this factor is at least 1.59 against at of § 2. A product of two inverse block-encodings has the product of their normalizations. Its cost scales as under the amplified-product model used here. If and , the product error is at most , so the per-factor error is not the product error. At and , this bound is approximately . A chain of non-unitary steps carries the -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 . For the amplified product its factor , 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 queries for an amplification factor and a margin 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 . At and this condition fails for every . 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 . 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 . Its Eq. (D3) runs to . We use this second reading unless we state otherwise. We compared the costs per evaluation at . 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 and of the largest value of , that is from to . This range is our assumed polynomial-error budget. Their work does not state the polynomial error it assumes.
The gain comes from our linear programs, which reach . At from to , falls by a factor of 5.5 to 12 from to 40. We therefore use the gains at for all three condition numbers of the scenario. At and 1000 they may overstate the gain. They are , 1.0012 and 1.0008 at , and . The value at is the mean of the values at and . At and the gains are those of Table I. The log recost.nb.log lists the gains at , 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 to 0.16 percent. The estimated total saving factor is the factor above times . We measure the contribution of the assumed gain as its share of the logarithm of this total, that is 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 and 14.0 to 15.2 percent at . Under the reading 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 and 57 to 84 percent at .
Matched evaluations of a published query model. Lefterovici et al. report QSVT query counts for Poisson matrices at normalized-state 2-norm error [16]. Their implementation assumes unit solution norm. It applies its inverse polynomial to , so its effective condition number is . Their Fig. 3 plots , whereas their count uses . Every matched evaluation uses the stored sparsity.
Our independent implementation reproduces 77 of the 90 stored Poisson counts to relative. Two rows at differ by . 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 have all their instances reproduced. They are , , with and 11345.4625, and , , with .
With only the polynomial replaced and , evaluations of the published model as implemented give reductions of 71.67 to 71.69 and 78.37 from , 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 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 (§ 5.C). For a single linear solve, solvers whose query count is linear in are known [11, 15]. The gain therefore matters most where the inverse block-encoding is a subroutine.
The criterion-A linear programs stop at and because of double precision (Section III). Between and 34.5 our finite bounds on the least cost come only from constructions, which give lower bounds on . 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 from 17 to 40 and from to , and certified at three points. On our integer grid up to , no row with costs less than the plain minimax polynomial. The crossover lies between 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 (Section IV). The sign of the finite- correction at small 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 , which exceeds one only beyond . 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 and with absolute reciprocal error , 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 (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 and 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 be the unbounded minimax polynomial. Odd polynomials with odd terms form a Haar space of dimension on , so attains with alternating signs at points of . Every interior alternation point is a local extremum of and hence a zero of . The derivative is an even polynomial of degree , so it has at most positive zeros. If or were not an alternation point, at least alternation points would be interior, which is too many. Hence both endpoints are alternation points, the interior alternation points are all the positive zeros of , and has no zero in . Then is monotone on with , so on , and by oddness on . The polynomial is bounded by one and takes values in on , so its error is .
Conversely, let be bounded by one with error on . Then there, and approximates on with error . Hence , which is .
Proof of Proposition 4
Put . Since has type at most and on , . Let . In the upper half-plane define
with the root tending to one at infinity, and extend evenly to the lower half-plane. On the gaps the integrand is imaginary, so the normal derivative of vanishes and the reflection is harmonic in . Its boundary values are on and on , it equals at , and at infinity. Let be the Green function of with pole at infinity, so on , for , and . Define . On , . On , feasibility gives , and gives . At infinity both the linear and the logarithmic growth of are matched by , so is subharmonic in and bounded above. We subtract and apply the maximum principle on truncated domains. We first let the truncation radius tend to infinity with fixed, and then take , which gives in . At this reads . If , then , which rearranges to (13). If , the right side of (13) is at most .
Outline of the upper bound in Theorem 3
Fix and , and put . In this appendix is the bandwidth of the prolate functions, not the normalization of § 2. The construction gives, for all large , an odd entire function of type at most with for and . Letting then gives , the upper half of Theorem 3. Sec. S5.2 gives the proof in five steps.
Prolate basis (Sec. S5.2.1). Let be the regular eigenfunctions, orthonormal on , of
Each extends to a real entire function of exponential type at most , because it is an eigenfunction of the finite Fourier transform , which commutes with .
Kernel (Sec. S5.2.3). Choose a nonnegative with integral one and put for . Extend smoothly with compact support to , where the spectrum has no points, and define
The sum is finite, for large , and is even, nonnegative on and entire of type at most with . So is odd and entire of the permitted type.
Interior density (Sec. S5.2.2, Lemma S5.2). For every fixed and integer ,
The proof writes as the integral, over the rotation orbits, of the kernel of for the operator on the unit sphere, with . On rotation-invariant functions acts as . 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 equal to the identity and his function family equal to . For a closed manifold and a smooth real potential , it writes as a sum of localized Weyl quantizations of composed with the classical Hamiltonian , plus terms whose symbols are with all derivatives and an operator of trace for every fixed . 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 bound on the kernel. The sphere is closed and is smooth on it, so the theorem applies as stated. The leading term gives in on , where is a convex mixture of the functions over . Hence on .
Forbidden region (Subsection S5.2.4 and Lemma S5.4). Choose . Eigenfunctions with have no zeros in and decrease there, so on . An elementary barrier and Sonin estimate (Lemma S5.4) gives for every fixed , with a prefactor polynomial in . Its constants are independent of for all . At most modes enter, and is of order . After division by , is at most a constant times on , and .
Feasibility (Sec. S5.2.5). Because , . With strictly between the two, for and all large .
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 be an odd polynomial of degree , and . Then for ,
If , the maxima of on a grid of spacing in are at most , and on , then .
Proof. Put and , a trigonometric polynomial of degree . Bernstein’s inequality gives and , and , so . With and this gives the first bound. Between two grid points, lies below its linear interpolant plus , so the maximum of on is at most . If is attained on this gives , hence because , and otherwise .
For the rule polynomials at and , is about and and is about 40. The grid spacing with then gives . At , , and . 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.
| claim | certificate and expected output |
| A finite targets, Table III | anc/verification_set/verify.py a_targets, norm upper and gain lower bounds of Sec. S7.3 |
| limiting frontier and gain | anc/verification_set/verify.py limiting, the two-sided intervals in the supplement’s certificate index |
| elliptic constants | anc/verification_set/verify.py constants_windows, the intervals of Corollary 5 |
| B finite targets, Table VI | anc/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 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]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]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]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]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]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]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]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]Matthias Deiml and Daniel Peterseim. “Constrained optimal polynomials for quantum linear system solvers” (2026). arXiv:2604.20513.arxiv.org/abs/2604.20513
- [9]Kiran Adhikari. “Krylov polynomials and quantum query complexity” (2025). arXiv:2510.11786.arxiv.org/abs/2510.11786
- [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]Alexander M. Dalzell. “A shortcut to an optimal quantum linear system solver” (2024). arXiv:2406.12086.arxiv.org/abs/2406.12086
- [12]M. I. Ganzburg. “Limit theorems in approximation theory”. Anal. Math. 18, 37–57 (1992).DOI
- [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]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]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]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]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]H. Ehlich and K. Zeller. “Schwankung von Polynomen zwischen Gitterpunkten”. Mathematische Zeitschrift 86, 41–44 (1964).DOI
- [19]D. S. Lubinsky. “On the Bernstein constants of polynomial approximation”. Constr. Approx. 25, 303–366 (2007).DOI
- [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]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]Alexandre Eremenko and Peter Yuditskii. “Comb functions”. Contemp. Math. 578, 99–118 (2012). arXiv:1109.1464.arxiv.org/abs/1109.1464
- [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]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]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]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]Hongkang Ni and Lexing Ying. “Fast phase factor finding for quantum signal processing” (2024). arXiv:2410.06409.arxiv.org/abs/2410.06409
- [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]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]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]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
