Sign outOpen workspaceSign in

SlotLayer 3

Polynomial approximation

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

Takes

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

Returns

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

This one, drawn

Polynomial approximationTruncated Chebyshev expansionRemez exchange for a minimax polynomialTruncated Chebyshev expansion — click the name to read about itTruncated Chebyshev expansionRemez exchange for a minimax polynomial — click the name to read about itRemez exchange for a minimax polynomialTarget function — you start herePolynomial approximation — you finish here

Drag to pan. Pinch, or hold ctrl and scroll, to zoom. Arrow keys pan, plus and minus zoom, zero resets the view.

From Target function to Polynomial approximation

A circle is an object you are holding. Each line between the two ends is one recorded way through this slot; where a way is built from smaller slots, those are its own lines. Circles are named on hover, and each one is a link.

Nothing drawn here has a recorded way through it that this figure leaves shut. See it on the map

Why this is a layer

The degree returned here becomes the query complexity of the circuit above it, so the cost of the quantum algorithm is settled by classical approximation theory rather than by anything quantum. Routes to the same target differ in their constants and sometimes in their asymptotics, and the bound on ∣P∣|P| before rescaling determines how much amplification the caller must pay for afterwards.

Ways to do this

2 methods recorded

  • Truncated Chebyshev expansion

    Expand the target in Chebyshev polynomials and truncate once the coefficients have fallen below the error budget. For 1/x1/x the expansion is taken of the odd function f(x)=(1−(1−x2)b)/xf(x) = (1 − (1 − x²)^b)/x; for e−ixte^{-ixt} the Jacobi-Anger identity supplies Bessel coefficients that decay super-exponentially once the order passes about tt.

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

Routes that skip this layer

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

  • HHL: eigenvalue inversion by phase estimation

    Prepare ∣b>|b>, run phase estimation against e−iAte^{-iAt} to write eigenvalue estimates into an ancilla register, apply a controlled rotation with amplitude proportional to 1/λ~1/λ̃, uncompute the estimation and post-select on the rotation ancilla. The success amplitude is about 1/κ1/κ, so the procedure is amplified O(κ)O(κ) times.

This is a step inside

  • Quantum singular value transformation

    Interleave the block-encoding UU, its inverse, and projector-controlled phase shifts eiφ(2Π−I)e^{iφ(2Π-I)} so that the designated block becomes PP applied to the singular values of AA. The phase sequence is the compiled form of the polynomial, and a single ancilla qubit carries the phase shifts.

  • Chebyshev series by linear combination of unitaries

    Write the target function as a Chebyshev series, then implement that series as a linear combination of walk-operator powers using a PREPARE/SELECT pair on an ancilla register, and post-select. No phase factors are computed — the polynomial enters through the coefficients of the combination instead.

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.