Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2501.05977

The Hitchhiker's Guide to QSP pre-processing

Skelton, S. E.

Published Jan 10, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum signal processing (QSP) relies on a historically costly pre-processing step, "QSP-processing/phase-factor finding." QSP-processing is now a developed topic within quantum algorithms literature, and a beginner accessible review of QSP-processing is overdue. This work provides a whirlwind tour through QSP conventions and pre-processing methods, beginning from a pedagogically accessible QSP convention. We then review QSP conventions associated with three common polynomial types: real polynomials with definite parity, sums of reciprocal/anti-reciprocal Chebyshev polynomials, and complex polynomials. We demonstrate how the conventions perform with respect to three criteria: circuit length, polynomial conditions, and pre-processing methods. We then review the recently introduced Wilson method for QSP-processing and give conditions where it can succeed with bound error. Although the resulting bound is not computationally efficient, we demonstrate that the method succeeds with linear error propagation for relevant target polynomials and precision regimes, including the Jacobi-Anger expansion used in Hamiltonian simulation algorithms. We then apply our benchmarks to three QSP-processing methods for QSP circuits and show that a method introduced by Berntson and Sünderhauf outperforms both the Wilson method and the standard optimization strategy for complex polynomials.

DOI
10.48550/arxiv.2501.05977

Related papers

Mostly Harmless Methods for QSP-Processing with Laurent Polynomials

S. E. Skelton

Quantum signal processing (QSP) and its extensions are increasingly popular frameworks for developing quantum algorithms. Yet QSP implementations still struggle to complete a classical pre-processing step (‘QSP-processing’) that determines the set of SU (2) rotation matrices defining the QSP circuit. We introduce a method of QSP-processing for complex polynomials that identifies a solution without optimization or root-finding and verify the success of our methods with polynomials characterized by floating point precision coefficients. We demonstrate the success of our technique for relevant target polynomials and precision regimes, including the Jacobi-Anger expansion used in QSP Hamiltonian Simulation. For popular choices of sign and inverse function approximations, we characterize regimes where all known QSP-processing methods should be expected to struggle without arbitrary precision arithmetic.

arXiv:2408.04321•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Improved constant factors for qubitized Hamiltonian simulation

Matthew Pocrnic, Danial Motlagh

Quantum signal processing (QSP) serves as the asymptotically optimal technique for Hamiltonian simulation on a quantum computer. By approximating the time evolution operator via the Jacobi-Anger expansion, the Hamiltonian simulation problem reduces to a problem in polynomial approximation theory: find a sufficient degree-$d$ polynomial series to approximate $e^{-iτx}$ on $[-1,1]$ within error $ε$. While $d\in\tilde{\mathcal{O}}(τ)$ is known to be asymptotically optimal, there exists a gap between state-of-the-art bounds and the optimal constant multiplicative factor, which is approximately equal to 1. Here, we close this gap almost entirely, to the point where possible future improvements will not be of practical significance. Our improvement resides in a careful treatment of the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities, thereby reducing the overhead estimates for all Hamiltonian simulation tasks on quantum computers by a factor of $\approx e/2$.

quant-pharXiv:2608.02734•Aug 5, 2026•0 citations

Efficient phase-factor evaluation in quantum signal processing

Yulong Dong, Xiang Meng, K. Birgitta Whaley +1 more

Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrix polynomials on quantum computers. Asymptotic analysis of quantum algorithms based on QSP has shown that asymptotically optimal results can in principle be obtained for a range of tasks, such as Hamiltonian simulation and the quantum linear system problem. A further benefit of QSP is that it uses a minimal number of ancilla qubits, which facilitates its implementation on near-to-intermediate term quantum architectures. However, there is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits. Existing methods require the use of variable precision arithmetic and can only be applied to polynomials of a relatively low degree. We present here an optimization-based method that can accurately compute the phase factors using standard double precision arithmetic operations. We demonstrate the performance of this approach with applications to Hamiltonian simulation, eigenvalue filtering, and quantum linear system problems. Our numerical results show that the optimization algorithm can find phase factors to accurately approximate polynomials of a degree larger than $10\phantom{\rule{0.16em}{0ex}}000$ with errors below ${10}^{\ensuremath{-}12}$.

arXiv:2002.11649•Physical Review A•Apr 22, 2021•140 citations

Much Ado about Quantum Signal Processing: Phase-Finding, Application, and Interpretation

Skelton, Shawna Erica Sullivan

Quantum signal processing (QSP) is a template for designing algorithms in the quantum circuit model. We consider three facets of this template. First, how to compute the exact circuit for a given algorithm and problem parameters. QSP requires two interrelated pre-processing steps. We give an algorithm for the first step, and compare its performance to recent alternatives. We find that our algorithm, using the Wilson method, is competitive for sparse polynomials away from the near-coherent regime. Next, we give an algorithm for quantum phase or energy estimation (QPE and QEE), designed with QSP. QEE replaces the common oracle access model in QPE with a block-encoding. We use von Neumann's measurement protocol and Hamiltonian simulation with QSP to show that QEE can be solved efficiently. We then show that when the standard QPE oracle is block-encoded, QPE algorithm with logarithmic overhead. We also show that whenever the system of interest is described by a linear combination of Pauli terms, the gate complexity of the entire algorithm is efficient in Clifford and T gates. We then consider how QSP relates to time-evolution. We show that QSP circuits can be understood as the circuits generated by a piecewise continuous time-evolution. Specifically, this evolution fits the bilinear control model, a common model in quantum control theory. Finally, we engineer a continuous time-dependent system for which the quantum adiabatic theorem will hold, which syntactically resembles QSP. We show that in the high-degree and small-signal limit, when the adiabatic schedule is Lipschitz continuous, the quantum adiabatic evolution of an eigenstate of H(0) is close to a QSP circuit applied to the same eigenstate. Crucially, our formalism establishes a direct functional relationship between the adiabatic schedule and the set of phase factors that determine the QSP circuit.

•Jan 1, 2026•0 citations

Quantum Signal Processing Phase Factorization via Logarithmic Derivatives

Christopher Peng

Quantum signal processing (QSP) requires the efficient computation of phase factors associated with a polynomial transformation. One existing stable factorization method avoids direct root finding but relies on Prony's method to recover a polynomial from weighted power sums of its roots (arXiv:2202.02671). We present a modification of this approach that eliminates Prony's method by using the logarithmic derivative of an associated polynomial. Because the logarithmic derivative has the same residue at every root after accounting for multiplicity, its Fourier coefficients directly yield the unweighted power sums of the roots inside the unit disk. The Newton--Girard identities then recover the coefficients of the corresponding polynomial without computing its roots. The resulting algorithm has $O(d\log^2 d)$ computational complexity and simplifies the factorization procedure of the original method. In numerical experiments on Hamiltonian simulation, eigenstate filtering, matrix inversion, and the Fermi--Dirac operator, our implementation computes phase factors in seconds with maximum errors on the order of $10^{-12}$.

quant-pharXiv:2610.14259•Oct 13, 2026•0 citations

Constrained minimax approximation for quantum signal processing

Yulong Dong, James B. Larsen, Lin Lin +1 more

Quantum signal processing (QSP) provides a simple and efficient framework for implementing polynomial transformations using quantum circuits. Its classical design stage leads to a constrained minimax approximation problem: find a polynomial of prescribed parity that approximates a target function uniformly on a fitting set while remaining bounded in magnitude by one on the domain $[0,1]$, which can be viewed as a semi-infinite constraint. Discretization converts the problem into a linear program, but feasibility at a set of finitely many sampled points does not ensure feasibility on the whole domain, especially when an optimal approximant reaches the boundary of the feasible set. We investigate two approaches to address this difficulty. A Remez exchange method combined with active-set constraint enforcement is efficient on many tested instances, but its stability depends on the target and problem geometry. We then introduce nonlinear Fourier retraction, which uses QSP completion and phase synthesis to turn a nearly feasible polynomial into phase factors for a feasible QSP polynomial without increasing the degree. Across representative problems, retraction largely preserves approximation accuracy and remains effective on instances where the Remez heuristic is unstable. The resulting workflow connects classical minimax approximation and semi-infinite optimization with nonlinear Fourier analysis, and is implemented in the qsppack software package.

quant-pharXiv:2608.30937•Sep 1, 2026•0 citations
Quantum signal processing (QSP) relies on a historically costly pre-processing step, "QSP-processing/phase-factor finding." QSP-processing is now a developed topic within quantum algorithms literature, and a beginner accessible review of QSP-processing is overdue. This work provides a whirlwind tour through QSP conventions and pre-processing methods, beginning from a pedagogically accessible QSP convention. We then review QSP conventions associated with three common polynomial types: real polynomials with definite parity, sums of reciprocal/anti-reciprocal Chebyshev polynomials, and complex polynomials. We demonstrate how the conventions perform with respect to three criteria: circuit length, polynomial conditions, and pre-processing methods. We then review the recently introduced Wilson method for QSP-processing and give conditions where it can succeed with bound error. Although the resulting bound is not computationally efficient, we demonstrate that the method succeeds with linear error propagation for relevant target polynomials and precision regimes, including the Jacobi-Anger expansion used in Hamiltonian simulation algorithms. We then apply our benchmarks to three QSP-processing methods for QSP circuits and show that a method introduced by Berntson and Sünderhauf outperforms both the Wilson method and the standard optimization strategy for complex polynomials.
Quantum signal processing (QSP) and its extensions are increasingly popular frameworks for developing quantum algorithms. Yet QSP implementations still struggle to complete a classical pre-processing step (‘QSP-processing’) that determines the set of SU (2) rotation matrices defining the QSP circuit. We introduce a method of QSP-processing for complex polynomials that identifies a solution without optimization or root-finding and verify the success of our methods with polynomials characterized by floating point precision coefficients. We demonstrate the success of our technique for relevant target polynomials and precision regimes, including the Jacobi-Anger expansion used in QSP Hamiltonian Simulation. For popular choices of sign and inverse function approximations, we characterize regimes where all known QSP-processing methods should be expected to struggle without arbitrary precision arithmetic.
Quantum signal processing (QSP) serves as the asymptotically optimal technique for Hamiltonian simulation on a quantum computer. By approximating the time evolution operator via the Jacobi-Anger expansion, the Hamiltonian simulation problem reduces to a problem in polynomial approximation theory: find a sufficient degree-ddd polynomial series to approximate e−iτxe^{-iτx}e−iτx on [−1,1][-1,1][−1,1] within error εεε. While d∈O~(τ)d\in\tilde{\mathcal{O}}(τ)d∈O~(τ) is known to be asymptotically optimal, there exists a gap between state-of-the-art bounds and the optimal constant multiplicative factor, which is approximately equal to 1. Here, we close this gap almost entirely, to the point where possible future improvements will not be of practical significance. Our improvement resides in a careful treatment of the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities, thereby reducing the overhead estimates for all Hamiltonian simulation tasks on quantum computers by a factor of ≈e/2\approx e/2≈e/2.
Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrix polynomials on quantum computers. Asymptotic analysis of quantum algorithms based on QSP has shown that asymptotically optimal results can in principle be obtained for a range of tasks, such as Hamiltonian simulation and the quantum linear system problem. A further benefit of QSP is that it uses a minimal number of ancilla qubits, which facilitates its implementation on near-to-intermediate term quantum architectures. However, there is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits. Existing methods require the use of variable precision arithmetic and can only be applied to polynomials of a relatively low degree. We present here an optimization-based method that can accurately compute the phase factors using standard double precision arithmetic operations. We demonstrate the performance of this approach with applications to Hamiltonian simulation, eigenvalue filtering, and quantum linear system problems. Our numerical results show that the optimization algorithm can find phase factors to accurately approximate polynomials of a degree larger than 1000010\phantom{\rule{0.16em}{0ex}}00010000 with errors below ${10}^{\ensuremath{-}12}$.
Quantum signal processing (QSP) is a template for designing algorithms in the quantum circuit model. We consider three facets of this template. First, how to compute the exact circuit for a given algorithm and problem parameters. QSP requires two interrelated pre-processing steps. We give an algorithm for the first step, and compare its performance to recent alternatives. We find that our algorithm, using the Wilson method, is competitive for sparse polynomials away from the near-coherent regime. Next, we give an algorithm for quantum phase or energy estimation (QPE and QEE), designed with QSP. QEE replaces the common oracle access model in QPE with a block-encoding. We use von Neumann's measurement protocol and Hamiltonian simulation with QSP to show that QEE can be solved efficiently. We then show that when the standard QPE oracle is block-encoded, QPE algorithm with logarithmic overhead. We also show that whenever the system of interest is described by a linear combination of Pauli terms, the gate complexity of the entire algorithm is efficient in Clifford and T gates. We then consider how QSP relates to time-evolution. We show that QSP circuits can be understood as the circuits generated by a piecewise continuous time-evolution. Specifically, this evolution fits the bilinear control model, a common model in quantum control theory. Finally, we engineer a continuous time-dependent system for which the quantum adiabatic theorem will hold, which syntactically resembles QSP. We show that in the high-degree and small-signal limit, when the adiabatic schedule is Lipschitz continuous, the quantum adiabatic evolution of an eigenstate of H(0) is close to a QSP circuit applied to the same eigenstate. Crucially, our formalism establishes a direct functional relationship between the adiabatic schedule and the set of phase factors that determine the QSP circuit.
Quantum signal processing (QSP) requires the efficient computation of phase factors associated with a polynomial transformation. One existing stable factorization method avoids direct root finding but relies on Prony's method to recover a polynomial from weighted power sums of its roots (arXiv:2202.02671). We present a modification of this approach that eliminates Prony's method by using the logarithmic derivative of an associated polynomial. Because the logarithmic derivative has the same residue at every root after accounting for multiplicity, its Fourier coefficients directly yield the unweighted power sums of the roots inside the unit disk. The Newton--Girard identities then recover the coefficients of the corresponding polynomial without computing its roots. The resulting algorithm has O(dlog⁡2d)O(d\log^2 d)O(dlog2d) computational complexity and simplifies the factorization procedure of the original method. In numerical experiments on Hamiltonian simulation, eigenstate filtering, matrix inversion, and the Fermi--Dirac operator, our implementation computes phase factors in seconds with maximum errors on the order of 10−1210^{-12}10−12.
Quantum signal processing (QSP) provides a simple and efficient framework for implementing polynomial transformations using quantum circuits. Its classical design stage leads to a constrained minimax approximation problem: find a polynomial of prescribed parity that approximates a target function uniformly on a fitting set while remaining bounded in magnitude by one on the domain [0,1][0,1][0,1], which can be viewed as a semi-infinite constraint. Discretization converts the problem into a linear program, but feasibility at a set of finitely many sampled points does not ensure feasibility on the whole domain, especially when an optimal approximant reaches the boundary of the feasible set. We investigate two approaches to address this difficulty. A Remez exchange method combined with active-set constraint enforcement is efficient on many tested instances, but its stability depends on the target and problem geometry. We then introduce nonlinear Fourier retraction, which uses QSP completion and phase synthesis to turn a nearly feasible polynomial into phase factors for a feasible QSP polynomial without increasing the degree. Across representative problems, retraction largely preserves approximation accuracy and remains effective on instances where the Remez heuristic is unstable. The resulting workflow connects classical minimax approximation and semi-infinite optimization with nonlinear Fourier analysis, and is implemented in the qsppack software package.