Takes

Chebyshev coefficients of a real polynomial $P$ of degree $d$ with definite parity and $|P(x)| \le 1$ on $[-1,1]$, plus a target accuracy $\varepsilon$.

Returns

A phase sequence $\Phi \in R^{d+1}$, often symmetric ($\phi_j = \phi_{d-j}$), together with the classical running time and the arithmetic precision the method requires.

This is a classical numerical-analysis problem sitting inside a quantum algorithm: the existence of the phases was established non-constructively, and computing them stably is separate work. The methods differ on a measurable axis — behaviour as ‖f‖_∞ → 1, the fully-coherent regime — not on taste. The root-finding family is analysed as needing $O(d \mathrm{polylog}(d/\varepsilon))$ bits rather than double precision; the optimization and Prony families run in standard double precision but are understood to degrade as ‖f‖_∞ → 1; the Newton formulation is reported to hold up in that regime.

• Direct method: root finding, then layer stripping

  Compute the complementary polynomial by finding the roots of a high-degree polynomial, then strip off one phase factor at a time from the assembled $SU(2)$-valued product. Haah's product decomposition is the version of this route that comes with a full arithmetic-model analysis.

• Least-squares optimization of the phase factors

  Instead of constructing the complementary polynomial, minimise the mean squared difference between the QSP response $Re[\langle0|U_Φ(x_j)|0\rangle]$ and the target $f$, evaluated at the positive roots of the Chebyshev polynomial $T_{2d̃}$, over symmetric phase sequences. Gradients come from $SU(2)$ matrix products, so root finding is avoided entirely and the method runs in standard double precision — but it degrades as $‖f‖_\infty$ approaches 1.

• Newton's method for symmetric QSP

  Treat phase-factor finding as a nonlinear system rather than a minimization, and solve it with a Newton iteration built for symmetric QSP. The matrix-product-state structure of symmetric QSP makes computing the Jacobian cost about the same as a single function evaluation.

• Stable factorization via Prony's method

  Build the complementary polynomial directly, with Prony's method as the key step, then obtain the phase factors by factorization. This avoids root finding of high-degree polynomials, which is the step that forces variable-precision arithmetic elsewhere in the direct family.

• HHL: eigenvalue inversion by phase estimation

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

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

• Quantum signal processing

  A single-qubit rotation sequence that transforms an encoded signal into a polynomial response.