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• 7 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•3 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•197 citations

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

Infinite quantum signal processing

Yulong Dong, Lin Lin, Hongkang Ni +1 more

Quantum signal processing (QSP) represents a real scalar polynomial of degree d using a product of unitary matrices of size 2 × 2 , parameterized by ( d + 1 ) real numbers called the phase factors. This innovative representation of polynomials has a wide range of applications in quantum computation. When the polynomial of interest is obtained by truncating an infinite polynomial series, a natural question is whether the phase factors have a well defined limit as the degree d → ∞ . While the phase factors are generally not unique, we find that there exists a consistent choice of parameterization so that the limit is well defined in the ℓ 1 space. This generalization of QSP, called the infinite quantum signal processing, can be used to represent a large class of non-polynomial functions. Our analysis reveals a surprising connection between the regularity of the target function and the decay properties of the phase factors. Our analysis also inspires a very simple and efficient algorithm to approximately compute the phase factors in the ℓ 1 space. The algorithm uses only double precision arithmetic operations, and provably converges when the ℓ 1 norm of the Chebyshev coefficients of the target function is upper bounded by a constant that is independent of d . This is also the first numerically stable algorithm for finding phase factors with provable performance guarantees in the limit d → ∞ .

arXiv:2209.10162•Quantum•Dec 10, 2024•47 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•2 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) 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) 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 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) represents a real scalar polynomial of degree d using a product of unitary matrices of size 2 × 2 , parameterized by ( d + 1 ) real numbers called the phase factors. This innovative representation of polynomials has a wide range of applications in quantum computation. When the polynomial of interest is obtained by truncating an infinite polynomial series, a natural question is whether the phase factors have a well defined limit as the degree d → ∞ . While the phase factors are generally not unique, we find that there exists a consistent choice of parameterization so that the limit is well defined in the ℓ 1 space. This generalization of QSP, called the infinite quantum signal processing, can be used to represent a large class of non-polynomial functions. Our analysis reveals a surprising connection between the regularity of the target function and the decay properties of the phase factors. Our analysis also inspires a very simple and efficient algorithm to approximately compute the phase factors in the ℓ 1 space. The algorithm uses only double precision arithmetic operations, and provably converges when the ℓ 1 norm of the Chebyshev coefficients of the target function is upper bounded by a constant that is independent of d . This is also the first numerically stable algorithm for finding phase factors with provable performance guarantees in the limit d → ∞ .
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.