Truncated Chebyshev expansion

What it fills

• Polynomial approximation

  Given a target function, a domain and an error $\varepsilon$, return a polynomial of definite parity, bounded on $[-1,1]$, that is $\varepsilon$-close to the target on that domain, with an explicit degree.

When it applies

For the $1/x$ construction with $b = ⌈\kappa² \log(\kappa/\varepsilon)⌉$, accuracy is claimed only on $[−1,1]$ \ $(−1/\kappa, 1/\kappa)$ — a gap of width $1/\kappa$ around the origin, which is where the condition-number assumption enters — and requires $\kappa > 1$ and $\varepsilon ∈ (0, ½)$. The polynomial must be rescaled to satisfy $|P| \leq 1$ before QSVT will accept it, and that rescaling is what makes amplification mandatory downstream. On attribution: this polynomial is Childs, Kothari and Somma's Lemmas 17-19; Gilyén, Su, Low and Wiebe reuse it as their Lemma 40 after adjustments, and the form quoted here is that restatement.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  the target function and an error budget e
       for 1/x also the condition number k > 1,  with e in (0, 1/2)

choose the function actually expanded:
    for 1/x       :  f(x) = (1 - (1 - x^2)^b) / x   with  b = ceil(k^2 log(k/e))
                     # odd, and accurate only on [-1,1] minus (-1/k, 1/k) --
                     # a gap of width 1/k around the origin, which is where
                     # the condition-number assumption enters
    for e^{-ixt}  :  the Jacobi-Anger identity, whose Bessel coefficients
                     decay super-exponentially once the order passes about t

expand in Chebyshev polynomials and truncate:
    keep the terms whose coefficients have not yet fallen below e

rescale so that |P(x)| <= 1 on the interval
    # QSVT will not accept the polynomial otherwise, and this rescaling is
    # what makes amplification mandatory downstream

return the truncated, rescaled polynomial

Cost, as the source states it

Degree $O(\kappa \log(\kappa/\varepsilon))$ for the odd real polynomial, with $|P(x)| = O(\kappa \log(\kappa/\varepsilon))$ on the interval before rescaling. For Hamiltonian simulation, Low and Chuang give the resulting query complexity as $O(t d ‖Ĥ‖_max + \log(1/\varepsilon)/\log \log(1/\varepsilon))$ for a $d$-sparse Hamiltonian ($d$ here is the sparsity, not the polynomial degree above), matching lower bounds in all parameters.

Implementations

• pyqsp's Chebyshev-truncated target-polynomial generators

  • Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
  • Optimal Hamiltonian Simulation by Quantum Signal Processing

  pyqsp (github.com/ichuang/pyqsp, 140 stars, actively maintained) is a Python package for quantum signal processing and QSVT. Its `pyqsp/poly.py` module holds the `PolyGenerator` subclasses that build the classical target polynomial a QSP phase-finding routine consumes before any circuit is generated; three of those subclasses expand a target in Chebyshev polynomials, matching this method's own description of the first step, and two of the three (`PolyCosineTX`, `PolySineTX`) then cut that series at a computed truncation order, matching the second step — the third (`PolyOneOverX`) instead runs a closed-form regularization in its executed code path, with the truncated-sum form present only as dead code (see `methods`).

  `PolyOneOverX.generate(kappa, epsilon)` sets $b = \lfloor \kappa^{2}\log(\kappa/\varepsilon)\rfloor$ and $j_{0} = \lfloor\sqrt{b\log(4b/\varepsilon)}\rfloor$, its own comment citing this as "following analytic form of Lemma 18" of the Childs-Kothari-Somma paper (arXiv id given as 1511.02306v2); $j_{0}$ is computed and printed but the branch that actually runs does not cap the sum there — it builds $f(x) = (1-(1-x^{2})^{b})/x$ directly, by repeated Chebyshev-basis multiplication by $(1-x^{2})$ (written `Chebyshev([0.5, 0, -0.5])`) followed by a `chebdiv` against $x$, so the executed polynomial has degree $2b-1$ and is not truncated at all; a degree-$j_{0}$ truncated sum exists in the file only inside a triple-quoted, non-executed block. The result is then rescaled by $0.9/|g(p_{\min})|$, found by `scipy.optimize.minimize`, so that $|P|\le 1$ on the fitted interval. `PolyCosineTX.generate(tau, epsilon)` and `PolySineTX.generate(tau, epsilon)`, both citing Low and Chuang's paper by name and URL in their docstrings, instead solve $r$ from $(e|\tau|/2r)^{r} = (5/4)\varepsilon$ via `scipy.optimize.fsolve`, set the truncation order $R = \lfloor r/2\rfloor$, and build the series from $R+1$ Bessel-weighted Chebyshev terms — cosine sums an initial term from `scipy.special.jv(0, tau)` plus $k=1,\ldots,R$ from `scipy.special.jv(2k, tau)`, reaching degree $2R$; sine sums $k=0,\ldots,R$ from `scipy.special.jv(2k+1, tau)`, reaching degree $2R+1$ — here the loop bound really is the computed truncation order, unlike `PolyOneOverX` above.

  `pyqsp/poly.py` on the `master` branch of github.com/ichuang/pyqsp (HEAD pushed 2026-05-22): `class PolyOneOverX(PolyGenerator)` at line 194, `generate` at line 199, the executed construction at lines 238-252, rescaling at lines 254-263; `class PolyCosineTX(PolyGenerator)` at line 82 and `class PolySineTX(PolyGenerator)` at line 138, each with its Bessel-coefficient loop at lines 111-116 and 167-172 respectively.

• NumPy's `numpy.polynomial.chebyshev` expansion and trimming primitives

  `numpy.polynomial.chebyshev` is NumPy's general-purpose, non-quantum submodule for Chebyshev series. It supplies the two primitives this method composes — computing a target's Chebyshev expansion, then cutting the resulting series by coefficient size — as separate, independently documented public functions rather than one combined routine, and needs no quantum-specific package to run.

  `Chebyshev.interpolate(func, deg, domain)` returns the degree-`deg` Chebyshev series that interpolates `func` at the Chebyshev points of the first kind on `domain`; its own docstring states the result "tends to a minmax approximation of `func`" when `func` is continuous on `domain`. `chebfit(x, y, deg)` is the least-squares alternative when only sampled data, not a callable target function, are available. Neither function truncates by itself: truncation is a separate call, `chebtrim(c, tol)` — a public module-level alias for `numpy.polynomial.polyutils.trimcoef` — which removes an already-computed series' trailing (highest-order) coefficients whose absolute value is at or below `tol`, i.e. it trims by coefficient magnitude and states no accuracy guarantee of its own.

  `numpy/polynomial/chebyshev.py` on the `main` branch of github.com/numpy/numpy (read 2026-08-26): `chebfit` at line 1554, `class Chebyshev(ABCPolyBase)` at line 1970 with `interpolate` at line 2011, and the module-level alias `chebtrim = pu.trimcoef` at line 125 (listed in `__all__` at line 120, and in the module docstring's function index at line 77).

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Remez exchange for a minimax polynomial

  Rather than truncating a Chebyshev series, which is only near-optimal, run the Remez exchange algorithm to obtain the genuine minimax polynomial of a given degree. In the QSP setting it is the alternative front end, handing a tighter polynomial of the same degree to the phase-factor stage.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision↗Andrew M. Childs, Robin Kothari, Rolando D. Somma · 2015theory yes · simulation no · hardware no
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics↗András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe · 2018theory yes · simulation no · hardware no
• Optimal Hamiltonian Simulation by Quantum Signal Processing↗Guang Hao Low, Isaac L. Chuang · 2016theory yes · simulation ? · hardware no