MethodLayer 2

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.

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.

Same contract as the slot it fills.

From Polynomial approximation to QSP phase sequence

A circle is an object you are holding. This method is drawn heavier, opened into its own steps; the other lines between the same two ends are the alternatives recorded for the same slot. 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

What it fills

QSP phase factors
Given an admissible polynomial, compute the phase sequence $Φ$ that makes the quantum-signal-processing product reproduce it to accuracy $\varepsilon$ in classical finite-precision arithmetic.

When it applies

Converges rapidly and robustly in all parameter regimes, including the case of an ill-conditioned Jacobian, using standard double precision arithmetic. The reported example is the highly oscillatory target $α cos(1000x)$ at polynomial degree $≈ 1433$ : 6 iterations to machine precision at $α = 0.9$ , rising only to 18 iterations at $α = 1 − 10^{-9}$ , where the Jacobian is highly ill-conditioned. The authors also give a reformulation of symmetric QSP in real arithmetic, and the method is implemented in the QSPPACK package.

Requires

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

Example

given  phase-factor finding written as a nonlinear system,
       not as a minimization

repeat:
    compute the Jacobian
        # the matrix-product-state structure of symmetric QSP makes
        # computing the Jacobian cost about the same as a single
        # function evaluation
    take a Newton step
until converged

return the phase factors

# how the Newton step is taken, and what the convergence test is, are
#   not on this record. The per-iteration characterization in
#   circulation -- a cost dominated by one linear solve -- is Ni and
#   Ying's, not this paper's, which claims no complexity for the
#   iteration at all

# what the paper does state is where it converges and how fast:
#   rapidly and robustly in all parameter regimes, including the case of
#   an ill-conditioned Jacobian, using standard double precision
#   arithmetic
#
#   reported example -- the highly oscillatory target alpha cos(1000x)
#   at polynomial degree about 1433:
#       alpha = 0.9        ->  6 iterations to machine precision
#       alpha = 1 - 10^-9  -> 18 iterations, Jacobian highly
#                             ill-conditioned

# the authors also give a reformulation of symmetric QSP in real
#   arithmetic, and the method is implemented in the QSPPACK package

# the robustness claim above is the paper's own and stands; the
#   efficiency ranking has since moved -- Ni and Ying present a
#   structured-matrix method they describe as the fastest applicable
#   across all regimes

Cost, as the source states it

The paper claims no complexity for the iteration — checked against the full text, whose quantitative content is the convergence record already in conditions. The per-iteration characterization in circulation, a cost dominated by one linear solve, is Ni and Ying's, not this paper's (see contested).

Implementations

Newton's method through an ill-conditioned Jacobian
- Robust iterative method for symmetric quantum signal processing in all parameter regimes
The measurement behind this record's "all parameter regimes" claim. The paper's stated target is the case its siblings struggle with — "the challenging scenario with ill-conditioned Jacobian matrices" — using standard double precision arithmetic.
A Newton's method for the nonlinear system that determines the phase factors, with the Jacobian computed at a cost comparable to a single function evaluation by using the matrix-product-state structure of symmetric QSP, plus a reformulation in real-number arithmetic.
Implemented in the QSPPACK software package. The abstract names the package but gives no link or availability statement, so this is a lead to follow rather than an artefact this record can point at.
For the highly oscillatory target $\alpha \cos(1000 x)$ at polynomial degree $\approx 1433$ : $6$ iterations to machine precision at $\alpha = 0.9$ , rising only to $18$ iterations at $\alpha = 1 - 10^{-9}$ , where the Jacobian is highly ill-conditioned. That near-flat iteration count across nine orders of conditioning is the robustness claim, stated as a measurement.

Where the claim is contested

The robustness claim is the paper's own and stands; the efficiency ranking has since moved. Ni and Ying present a structured-matrix method they describe as the fastest applicable across all regimes, and characterise this Newton iteration's per-iteration cost as dominated by a linear solve — a figure that is theirs, not this paper's, which claims no complexity.

What it needs

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Other ways to fill the same slot

Different approaches

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

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

Robust iterative method for symmetric quantum signal processing in all parameter regimes ↗Yulong Dong, Lin Lin, Hongkang Ni, Jiasu Wang · 2023theory yes · simulation yes · hardware no

This one, drawn