Parallel Quantum Signal Processing Via Polynomial Factorization
John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, Isaac L. Chuang · Quantum · 2025
Quantum signal processing (QSP) is a methodology for constructing polynomial transformations of a linear operator encoded in a unitary. Applied to an encoding of a state ρ , QSP enables the evaluation of nonlinear functions of the form tr(P(ρ)) for a polynomial P(x) , which encompasses relevant properties like entropies and fidelity. However, QSP is a sequential algorithm: implementing a degree- d polynomial necessitates d queries to the encoding, equating to a query depth d . Here, we reduce the depth of these property estimation algorithms by developing Parallel Quantum Signal Processing. Our algorithm parallelizes the computation of tr(P(ρ)) over k systems and reduces the query depth to d/k , thus enabling a family of time-space tradeoffs for QSP. This furnishes a property estimation algorithm suitable for distributed quantum computers, and is realized at the expense of increasing the number of measurements by a factor O(poly(d)2O(k)) . We achieve this result by factorizing P(x) into a product of k smaller polynomials of degree O(d/k) , which are each implemented in parallel with QSP, and subsequently multiplied together with a swap test to reconstruct P(x) . We characterize the achievable class of polynomials by appealing to the fundamental theorem of algebra, and demonstrate application to canonical problems including entropy estimation and partition function evaluation.