QSP phase factors

Why this is a layer

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.

Ways to do this

4 methods recorded

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

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

This is a step inside

• Quantum singular value transformation

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

• Qubitization walk simulation

  From a block-encoding pair $(U, |G⟩)$ with $H = (⟨G|⊗I)U(|G⟩⊗I)$, build a walk operator $W$ that splits the Hilbert space into invariant two-dimensional $SU(2)$ subspaces, one per eigenvalue of $H$, with eigenvalues $e^{±i·arccos(H/α)}$. Quantum signal processing phases applied to $W$ then produce $e^{-iHt}$.

In the Atlas

• Quantum signal processing

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