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:2410.06409 · SIAM Journal on Scientific Computing

Fast Phase Factor Finding for Quantum Signal Processing

Hongkang Ni, Lexing Ying B

Published Jul 30, 2026• 1 citation
arXivHTMLPDF

Abstract

Abstract. This paper presents two efficient and stable algorithms for recovering phase factors in quantum signal processing (QSP), a crucial component of many quantum information processing applications. The first algorithm, the Half Cholesky (HC) method, which is based on nonlinear Fourier analysis and fast solvers for structured matrices, demonstrates robust performance across all regimes. The second algorithm, Fast Fixed Point Iteration (FFPI), offers even greater efficiency in the non–fully coherent regime. Both theoretical analysis and numerical experiments demonstrate the significant advantages of these new methods over all existing approaches. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/HongkangNi/Fast-Phase-Factor-Finding-for-QSP and in the supplementary materials ( Fast-Phase-Factor-Finding-for-QSP-main.zip [135KB]). [Formula: see text]

DOI
10.1137/24m1705214

Related papers

Mathematical and Numerical Analysis of Quantum Signal Processing

Lin Lin

Quantum signal processing (QSP) provides a representation of scalar polynomials of degree $d$ as products of matrices in $\mathrm{SU}(2)$, parameterized by $(d+1)$ real numbers known as phase factors. QSP is the mathematical foundation of quantum singular value transformation (QSVT), which is often regarded as one of the most important quantum algorithms of the past decade, with a wide range of applications in scientific computing, from Hamiltonian simulation to solving linear systems of equations and eigenvalue problems. In this article we survey recent advances in the mathematical and numerical analysis of QSP. In particular, we focus on its generalization beyond polynomials, the computational complexity of algorithms for phase factor evaluation, and the numerical stability of such algorithms. The resolution to some of these problems relies on an unexpected interplay between QSP, nonlinear Fourier analysis on $\mathrm{SU}(2)$, fast polynomial multiplications, and Gaussian elimination for matrices with displacement structure.

arXiv:2510.00443•Jul 1, 2026•0 citations

Robust Iterative Method for Symmetric Quantum Signal Processing in All Parameter Regimes

Yulong Dong, Lin Lin, Hongkang Ni +1 more

Abstract. This paper addresses the problem of solving nonlinear systems in the context of symmetric quantum signal processing (QSP), a powerful technique for implementing matrix functions on quantum computers. Symmetric QSP focuses on representing target polynomials as products of matrices in SU(2) that possess symmetry properties. We present a novel Newton’s method tailored for efficiently solving the nonlinear system involved in determining the phase factors within the symmetric QSP framework. Our method demonstrates rapid and robust convergence in all parameter regimes, including the challenging scenario with ill-conditioned Jacobian matrices, using standard double precision arithmetic operations. For instance, solving symmetric QSP for a highly oscillatory target function [Formula: see text] (polynomial degree [Formula: see text]) takes 6 iterations to converge to machine precision when [Formula: see text], and the number of iterations only increases to 18 iterations when [Formula: see text] with a highly ill-conditioned Jacobian matrix. Leveraging the matrix product state structure of symmetric QSP, the computation of the Jacobian matrix incurs a computational cost comparable to a single function evaluation. Moreover, we introduce a reformulation of symmetric QSP using real-number arithmetics, further enhancing the method’s efficiency. Extensive numerical tests validate the effectiveness and robustness of our approach, which has been implemented in the QSPPACK software package.

arXiv:2307.12468•SIAM Journal on Scientific Computing•Sep 13, 2024•12 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

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

Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing

Hongkang Ni, Rahul Sarkar, Lexing Ying B +1 more

The nonlinear Fourier transform (NLFT) extends the classical Fourier transform by replacing addition with matrix multiplication. While the NLFT on $\mathrm{SU}(1,1)$ has been widely studied, its $\mathrm{SU}(2)$ variant has only recently attracted attention due to emerging applications in quantum signal processing (QSP) and quantum singular value transformation (QSVT). In this paper, we investigate the inverse NLFT on $\mathrm{SU}(2)$ and establish the numerical stability of the layer stripping algorithm for the first time under suitable conditions. Furthermore, we develop a fast and numerically stable algorithm, called inverse nonlinear fast Fourier transform, for performing inverse NLFT with near-linear complexity. This algorithm is applicable to computing phase factors for both QSP and the generalized QSP (GQSP).

arXiv:2505.12615•May 19, 2025•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
Abstract. This paper presents two efficient and stable algorithms for recovering phase factors in quantum signal processing (QSP), a crucial component of many quantum information processing applications. The first algorithm, the Half Cholesky (HC) method, which is based on nonlinear Fourier analysis and fast solvers for structured matrices, demonstrates robust performance across all regimes. The second algorithm, Fast Fixed Point Iteration (FFPI), offers even greater efficiency in the non–fully coherent regime. Both theoretical analysis and numerical experiments demonstrate the significant advantages of these new methods over all existing approaches. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/HongkangNi/Fast-Phase-Factor-Finding-for-QSP and in the supplementary materials ( Fast-Phase-Factor-Finding-for-QSP-main.zip [135KB]). [Formula: see text]
Quantum signal processing (QSP) provides a representation of scalar polynomials of degree ddd as products of matrices in SU(2)\mathrm{SU}(2)SU(2), parameterized by (d+1)(d+1)(d+1) real numbers known as phase factors. QSP is the mathematical foundation of quantum singular value transformation (QSVT), which is often regarded as one of the most important quantum algorithms of the past decade, with a wide range of applications in scientific computing, from Hamiltonian simulation to solving linear systems of equations and eigenvalue problems. In this article we survey recent advances in the mathematical and numerical analysis of QSP. In particular, we focus on its generalization beyond polynomials, the computational complexity of algorithms for phase factor evaluation, and the numerical stability of such algorithms. The resolution to some of these problems relies on an unexpected interplay between QSP, nonlinear Fourier analysis on SU(2)\mathrm{SU}(2)SU(2), fast polynomial multiplications, and Gaussian elimination for matrices with displacement structure.
Abstract. This paper addresses the problem of solving nonlinear systems in the context of symmetric quantum signal processing (QSP), a powerful technique for implementing matrix functions on quantum computers. Symmetric QSP focuses on representing target polynomials as products of matrices in SU(2) that possess symmetry properties. We present a novel Newton’s method tailored for efficiently solving the nonlinear system involved in determining the phase factors within the symmetric QSP framework. Our method demonstrates rapid and robust convergence in all parameter regimes, including the challenging scenario with ill-conditioned Jacobian matrices, using standard double precision arithmetic operations. For instance, solving symmetric QSP for a highly oscillatory target function [Formula: see text] (polynomial degree [Formula: see text]) takes 6 iterations to converge to machine precision when [Formula: see text], and the number of iterations only increases to 18 iterations when [Formula: see text] with a highly ill-conditioned Jacobian matrix. Leveraging the matrix product state structure of symmetric QSP, the computation of the Jacobian matrix incurs a computational cost comparable to a single function evaluation. Moreover, we introduce a reformulation of symmetric QSP using real-number arithmetics, further enhancing the method’s efficiency. Extensive numerical tests validate the effectiveness and robustness of our approach, which has been implemented in the QSPPACK software package.
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) 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}$.
The nonlinear Fourier transform (NLFT) extends the classical Fourier transform by replacing addition with matrix multiplication. While the NLFT on SU(1,1)\mathrm{SU}(1,1)SU(1,1) has been widely studied, its SU(2)\mathrm{SU}(2)SU(2) variant has only recently attracted attention due to emerging applications in quantum signal processing (QSP) and quantum singular value transformation (QSVT). In this paper, we investigate the inverse NLFT on SU(2)\mathrm{SU}(2)SU(2) and establish the numerical stability of the layer stripping algorithm for the first time under suitable conditions. Furthermore, we develop a fast and numerically stable algorithm, called inverse nonlinear fast Fourier transform, for performing inverse NLFT with near-linear complexity. This algorithm is applicable to computing phase factors for both QSP and the generalized QSP (GQSP).
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.