Stable factorization via Prony's method

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

Reported numerically stable in double precision arithmetic, with experiments on Hamiltonian simulation, eigenstate filtering, matrix inversion and evaluation of the Fermi-Dirac operator.

Requires

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

Example

given  a polynomial of degree d      # d is the polynomial degree

build the complementary polynomial directly,
    with Prony's method as the key step
    # this avoids root finding of high-degree polynomials, which is the
    # step that forces variable-precision arithmetic elsewhere in the
    # direct family

obtain the phase factors by factorization

return the phase factors

# Ying's own accounting: computing the vector m costs an empirical
#   O(d^2), and extracting the phase factors costs O(d^2 log d) via the
#   FFT and dominates, so the overall cost is O(d^2 log d) -- classical
#   preprocessing. Stated in the full text; the abstract carries no bound

# how Prony's method builds the complementary polynomial, what the vector
#   m is, and how the factorization proceeds are not stated here

# reported numerically stable in double precision arithmetic, with
#   experiments on Hamiltonian simulation, eigenstate filtering, matrix
#   inversion and evaluation of the Fermi-Dirac operator

# the record carries a second figure beside that accounting and does not
#   join the two -- the paper's headline comparison is the same O(d^2)
#   computational cost as the optimization-based method of Dong, Meng,
#   Whaley and Lin at comparable accuracy (about 10^-12), with sequences
#   beyond 50,000 phase factors demonstrated

# what is claimed is stability in double precision, not an improved
#   asymptotic: no sharp worst-case complexity separating this from the
#   root-finding family is given, and Ni and Ying add that the stability
#   of the layer-stripping process most direct methods rely on -- this
#   one included -- remains an open question

Cost, as the source states it

Ying's own accounting: computing the vector $m$ costs an empirical $O(d^2)$, and extracting the phase factors costs $O(d^2 \log d)$ via the FFT and dominates, so the overall cost is $O(d^2 \log d)$. The paper's headline comparison is the same $O(d^2)$ computational cost as the optimization-based method of Dong, Meng, Whaley and Lin at comparable accuracy ($\sim 10^{-12}$), with sequences beyond 50,000 phase factors demonstrated. $d$ is the polynomial degree, and the cost is classical preprocessing. Stated in the full text; the abstract carries no bound.

Implementations

• The four reported applications

  • Stable factorization for phase factors of quantum signal processing

  The experiments accompanying the factorization algorithm this record describes. Published as Quantum 6, 842 (2022).

  Experimental results are reported for Hamiltonian simulation, eigenstate filtering, matrix inversion, and the Fermi-Dirac operator, with the algorithm stated to be numerically stable in double precision arithmetic.

  The abstract states that these experiments were run and gives no degree, precision or timing — so nothing is transcribed here from it. The figures for this paper are already on this card, one field up: `cost` carries the $\sim 10^{-12}$ accuracy and the sequences beyond 50,000 phase factors, read from the full text by an earlier pass that recorded, in the same breath, that "the abstract carries no bound". This entry does not restate them, because they are a comparison of cost rather than a report of this run, and duplicating them here would make the card look like two independent measurements of one experiment.

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.

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

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

• Stable factorization for phase factors of quantum signal processing↗Lexing Ying · 2022theory yes · simulation yes · hardware no
• Fast Phase Factor Finding for Quantum Signal Processing↗Hongkang Ni, Lexing Ying · 2024theory yes · simulation yes · hardware no