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.

A target function $f$ ($1/x$, sign, $e^{-ixt}$ and so on); a domain such as $[-1,1] \setminus (-1/\kappa, 1/\kappa)$; an error $\varepsilon$; the required parity.

1. Target function → Polynomial approximationregularise 1/x, then cut the series

   $1/x$ is not expanded directly. For Hermitian $H = A/d$ with spectrum in $D_{\kappa d} := [-1, -1/(\kappa d)] \cup [1/(\kappa d), 1]$ assumption: $H$ is Hermitian and its eigenvalues are bounded away from $0$ by a known $1/(\kappa d)$ — a condition-number bound $\kappa$ on the $d$-sparse $A$, the target is regularised as $f(x) := \frac{1 - (1 - x^{2})^{b}}{x}$, which is $\varepsilon$-close to $1/x$ on that domain for any integer $b \ge (\kappa d)^{2}\log(\kappa d/\varepsilon)$, and which on $[-1, 1]$ is exactly the Chebyshev sum $f(x) = 4\sum_{j=0}^{b-1}(-1)^{j}\left[\frac{\sum_{i=j+1}^{b}\binom{2b}{b+i}}{2^{2b}}\right]\mathcal{T}_{2j+1}(x)$ — each bracketed weight "the probability of seeing more than $b+j$ heads on flipping $2b$ fair coins". approximation: that sum is truncated at $j_{0} = \sqrt{b\log(4b/\varepsilon)}$, an order $O(\sqrt{b\log(b/\varepsilon)})$ polynomial, and a Chernoff bound on the discarded tail gives $4be^{-j_{0}^{2}/b} = \varepsilon$. The record's `conditions` quotes the later restatement in terms of a bare $\kappa$; the form here is the original, in $\kappa d$.

   approximationassumption

Chebyshev coefficients of the polynomial and its degree $d$, plus the bound on $|P|$ over $[-1,1]$ before any rescaling.

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

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.

• pyqsp's Chebyshev-truncated target-polynomial generators

  • Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Andrew M. Childs, Robin Kothari, Rolando D. Somma · 2015

  • Optimal Hamiltonian Simulation by Quantum Signal Processing

    Guang Hao Low, Isaac L. Chuang · 2016

  About

  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`).

  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.

  Data

  None found yet.

  Code

  `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.

  Results

  None found yet.

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

  About

  `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.

  Methods

  `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.

  Data

  None found yet.

  Code

  `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).

  Results

  None found yet.