Sign outOpen workspaceSign in

MethodLayer 2

Least-squares optimization of the phase factors

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

Takes

Chebyshev coefficients of a real polynomial PP of degree dd with definite parity and ∣P(x)∣≤1|P(x)| \le 1 on [−1,1][-1,1], plus a target accuracy ε\varepsilon.

Returns

A phase sequence Φ∈Rd+1\Phi \in R^{d+1}, often symmetric (ϕj=ϕd−j\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.

This one, drawn

Least-squares optimization of the phase factorsDirect method: root finding, then layer strippingLeast-squares optimization of the phase factorsNewton's method for symmetric QSPStable factorization via Prony's methodDirect method: root finding, then layer stripping — click the name to read about itDirect root findingLeast-squares optimization of the phase factors — click the name to read about itLeast-squares optimizationNewton's method for symmetric QSP — click the name to read about itNewton's method for symmetric QSPStable factorization via Prony's method — click the name to read about itStable factorization via Prony's methodPolynomial approximation — you start hereQSP phase sequence — 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 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

The objective is L(Φ^)=(1/d~)Σj=1d~∣Re[⟨0∣UΦ(xj)∣0⟩]−f(xj)∣2L(Φ̂) = (1/d̃) \Sigma_{j=1}^{d̃} |Re[\langle0|U_Φ(x_j)|0\rangle] − f(x_j)|² at xj=cos⁡((2j−1)π/(4d~))x_j = \cos((2j−1)\pi/(4d̃)) with d~=⌈(d+1)/2⌉d̃ = ⌈(d+1)/2⌉, minimised with L-BFGS over symmetric phase factors. The target must already be an admissible polynomial: feed in a non-polynomial f and L(Φ)=0L(Φ) = 0 generally has no solution, leaving the optimizer stuck among many local minima. The initial guess Φ0=(π/4,0,…,0,π/4)Φ⁰ = (\pi/4, 0, \ldots, 0, \pi/4) is load-bearing — the seemingly natural Φ=(0,…,0)Φ = (0, \ldots, 0) is a stationary point whose loss is non-zero. Wang, Dong and Lin later proved that one global minimum lies in a neighbourhood of Φ⁰ on which the cost function is strongly convex, under ‖f‖∞=O(d−1)‖f‖_∞ = O(d^{-1}) with d=deg⁡(f)d = \deg(f).

Requires

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

Example

given  an admissible polynomial target f of degree d
       # the target must already be an admissible polynomial: feed in a
       # non-polynomial f and L(Phi) = 0 generally has no solution,
       # leaving the optimizer stuck among many local minima

# instead of constructing the complementary polynomial, minimise the mean
# squared difference between the QSP response and the target f

set  d~ = ceil((d + 1) / 2)
set  x_j = cos((2j - 1) pi / (4 d~))    for j = 1 .. d~
     # the positive roots of the Chebyshev polynomial T_{2 d~}

define  L(Phi) = (1/d~) sum over j = 1 .. d~ of
            |Re[<0|U_Phi(x_j)|0>] - f(x_j)|^2

start from  Phi_0 = (pi/4, 0, ..., 0, pi/4)
# load-bearing: the seemingly natural Phi = (0, ..., 0) is a stationary
# point whose loss is non-zero

minimise L over symmetric phase sequences with L-BFGS
    # gradients come from SU(2) matrix products, so root finding is
    # avoided entirely and the method runs in standard double precision

return the symmetric phase factors

# why Phi_0 and not any starting point: Wang, Dong and Lin later proved
#   that one global minimum lies in a neighbourhood of Phi_0 on which the
#   cost function is strongly convex, under ||f||_inf = O(d^-1) with
#   d = deg(f)

# no asymptotic bound is claimed. What the paper reports is empirical:
#   phase factors accurately approximating polynomials of degree larger
#   than 10,000 with error below 10^-12, using standard double precision
#   arithmetic operations

# where it stops working: the method degrades as ||f||_inf approaches 1,
#   the fully-coherent regime, which the strong-convexity guarantee above
#   does not reach. The Newton method for symmetric QSP and the
#   nonlinear-Fourier-transform route were developed for that regime
#   specifically

Cost, as the source states it

No asymptotic bound is claimed. The paper reports that the optimization finds phase factors accurately approximating polynomials of degree larger than 10,000 with error below 10−1210^{-12}, using standard double precision arithmetic operations.

Implementations

  • Phase factors past degree 10,000 in double precision

    The run that made this stage practical. The paper states the problem it is answering in its own words: "there is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits", and existing methods "require the usage of variable precision arithmetic and can only be applied to polynomials of relatively low degree". Published as Phys. Rev. A 103, 042419 (2021).

    An optimization-based method computing the phase factors using standard double precision arithmetic operations, demonstrated on Hamiltonian simulation, eigenvalue filtering, and the quantum linear system problem.

    Phase factors accurately approximating polynomials of degree larger than 10,00010{,}000, with error below 10−1210^{-12}.

Where the claim is contested

This family is efficient and stable in double precision but is understood to degrade in the fully-coherent regime, where ‖f‖_∞ → 1. The Newton method for symmetric QSP and the nonlinear-Fourier-transform route were developed for that regime specifically, and the strong-convexity guarantee that justifies the standard initial guess is proved only under ‖f‖_∞ = O(d^{-1}), which does not reach it.

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)SU(2)-valued product. Haah's product decomposition is the version of this route that comes with a full arithmetic-model analysis.

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

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