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:2505.12615

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

Hongkang Ni, Rahul Sarkar, Lexing Ying B, Lin Lin

Published May 19, 2025• 0 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.2505.12615

Related papers

Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent

Lorenzo Laneve

Quantum signal processing (QSP) and quantum singular value transformation (QSVT) are powerful techniques for the development of quantum procedures. They allow to derive circuits preparing desired polynomial transformations. Recent research [Alexis et al. 2024] showed that Non-Linear Fourier Analysis (NLFA) can be employed to numerically compute a QSP protocol, with provable stability. In this work we extend their result, showing that GQSP and the Non-Linear Fourier Transform over $SU(2)$ are the same object. This statement - proven by a simple argument - has a bunch of consequences: first, the Riemann-Hilbert-Weiss algorithm can be turned, with little modifications and no penalty in complexity, into a unified, provably stable algorithm for the computation of phase factors in any QSP variant, including GQSP. Secondly, we derive a uniqueness result for the existence of GQSP phase factors based on the bijectivity of the Non-Linear Fourier Transform. Furthermore, NLFA provides a complete theory of infinite generalized quantum signal processing, which characterizes the class of functions approximable by GQSP protocols.

arXiv:2503.03026•Mar 4, 2025•0 citations

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

On the Fast Fourier Transform on SU(2)

Julio Delgado, Alejandro Umaña

The special unitary group SU(2) plays a fundamental role in the description of symmetries in quantum mechanics, theoretical physics, and spherical signal processing. In this paper, we address the computational challenges of performing spectral analysis on this non-abelian compact Lie group. We present the Fourier Transform (FT) on SU(2) and develop a Fast Fourier Transform (FFT) algorithm inspired by the classical Cooley-Tukey divide-and-conquer scheme. Our approach efficiently discretizes the group using Euler angles, applying a two-dimensional FFT on the angular variables and exploiting the recursive properties of Jacobi polynomials. We provide an analysis of the computational complexity, demonstrating that our FFT-based method significantly outperforms the direct computation of the FT. This algorithm serves as a foundational tool for understanding the implementation of the FFT on SU(2), a key component in numerical simulations and advanced data analysis for high-performance computing applications on curved manifolds and quantum systems.

physics.comp-phCross-listedarXiv:2605.23923•Apr 21, 2026

Fast Phase Factor Finding for Quantum Signal Processing

Hongkang Ni, Lexing Ying B

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]

arXiv:2410.06409•SIAM Journal on Scientific Computing•Jul 30, 2026•1 citation

An SU(2n)-valued nonlinear Fourier transform

Michel Alexis, Lars Becker, Diogo Oliveira e Silva +1 more

We define a nonlinear Fourier transform which maps sequences of contractive $n \times n$ matrices to $SU(2n)$-valued functions on the circle $\mathbb{T}$. We characterize the image of finitely supported sequences and square-summable sequences on the half-line, and construct an inverse for $SU(2n)$-valued functions whose diagonal $n \times n$ blocks are outer matrix functions. As an application, we relate this nonlinear Fourier transform with quantum signal processing over $U(2n)$ and multivariate quantum signal processing.

math.CACross-listedarXiv:2601.03987•Jan 8, 2026

Generalized Quantum Signal Processing

Danial Motlagh, Nathan Wiebe

Quantum signal processing (QSP) and quantum singular value transformation (QSVT) currently stand as the most efficient techniques for implementing functions of block-encoded matrices, a central task that lies at the heart of most prominent quantum algorithms. However, current QSP approaches face several challenges, such as the restrictions imposed on the family of achievable polynomials and the difficulty of calculating the required phase angles for specific transformations. In this paper, we present a generalized quantum signal processing (GQSP) approach, employing general SU(2) rotations as our signal-processing operators, rather than relying solely on rotations in a single basis. Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that |P|≤1 , a restriction necessary due to the unitary nature of quantum computation. Furthermore, GQSP provides a straightforward recursive formula for determining the rotation angles needed to construct the polynomials in cases where P and Q are known. In cases where only P is known, we provide an efficient optimization algorithm capable of identifying in under a minute of GPU time, a corresponding Q for polynomials of degree on the order of 107 . We further illustrate GQSP simplifies QSP-based strategies for Hamiltonian simulation, offer an optimal solution to the ϵ -approximate fractional query problem that requires O((1/δ)+log(1/ϵ)) queries to perform where O(1/δ) is a proved lower bound, and introduces novel approaches for implementing bosonic operators. Moreover, we propose a novel framework for the implementation of normal matrices, demonstrating its applicability through synthesis of diagonal matrices, as well as the development of a new algorithm for convolution through synthesis of circulant matrices using only O(dlogN+log2N) 1 and 2-qubit gates for a filter of lengths d . Published by the American Physical Society 2024

arXiv:2308.01501•PRX Quantum•Jun 28, 2024•74 citations
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) and quantum singular value transformation (QSVT) are powerful techniques for the development of quantum procedures. They allow to derive circuits preparing desired polynomial transformations. Recent research [Alexis et al. 2024] showed that Non-Linear Fourier Analysis (NLFA) can be employed to numerically compute a QSP protocol, with provable stability. In this work we extend their result, showing that GQSP and the Non-Linear Fourier Transform over SU(2)SU(2)SU(2) are the same object. This statement - proven by a simple argument - has a bunch of consequences: first, the Riemann-Hilbert-Weiss algorithm can be turned, with little modifications and no penalty in complexity, into a unified, provably stable algorithm for the computation of phase factors in any QSP variant, including GQSP. Secondly, we derive a uniqueness result for the existence of GQSP phase factors based on the bijectivity of the Non-Linear Fourier Transform. Furthermore, NLFA provides a complete theory of infinite generalized quantum signal processing, which characterizes the class of functions approximable by GQSP protocols.
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.
The special unitary group SU(2) plays a fundamental role in the description of symmetries in quantum mechanics, theoretical physics, and spherical signal processing. In this paper, we address the computational challenges of performing spectral analysis on this non-abelian compact Lie group. We present the Fourier Transform (FT) on SU(2) and develop a Fast Fourier Transform (FFT) algorithm inspired by the classical Cooley-Tukey divide-and-conquer scheme. Our approach efficiently discretizes the group using Euler angles, applying a two-dimensional FFT on the angular variables and exploiting the recursive properties of Jacobi polynomials. We provide an analysis of the computational complexity, demonstrating that our FFT-based method significantly outperforms the direct computation of the FT. This algorithm serves as a foundational tool for understanding the implementation of the FFT on SU(2), a key component in numerical simulations and advanced data analysis for high-performance computing applications on curved manifolds and quantum systems.
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]
We define a nonlinear Fourier transform which maps sequences of contractive n×nn \times nn×n matrices to SU(2n)SU(2n)SU(2n)-valued functions on the circle T\mathbb{T}T. We characterize the image of finitely supported sequences and square-summable sequences on the half-line, and construct an inverse for SU(2n)SU(2n)SU(2n)-valued functions whose diagonal n×nn \times nn×n blocks are outer matrix functions. As an application, we relate this nonlinear Fourier transform with quantum signal processing over U(2n)U(2n)U(2n) and multivariate quantum signal processing.
Quantum signal processing (QSP) and quantum singular value transformation (QSVT) currently stand as the most efficient techniques for implementing functions of block-encoded matrices, a central task that lies at the heart of most prominent quantum algorithms. However, current QSP approaches face several challenges, such as the restrictions imposed on the family of achievable polynomials and the difficulty of calculating the required phase angles for specific transformations. In this paper, we present a generalized quantum signal processing (GQSP) approach, employing general SU(2) rotations as our signal-processing operators, rather than relying solely on rotations in a single basis. Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that |P|≤1 , a restriction necessary due to the unitary nature of quantum computation. Furthermore, GQSP provides a straightforward recursive formula for determining the rotation angles needed to construct the polynomials in cases where P and Q are known. In cases where only P is known, we provide an efficient optimization algorithm capable of identifying in under a minute of GPU time, a corresponding Q for polynomials of degree on the order of 107 . We further illustrate GQSP simplifies QSP-based strategies for Hamiltonian simulation, offer an optimal solution to the ϵ -approximate fractional query problem that requires O((1/δ)+log(1/ϵ)) queries to perform where O(1/δ) is a proved lower bound, and introduces novel approaches for implementing bosonic operators. Moreover, we propose a novel framework for the implementation of normal matrices, demonstrating its applicability through synthesis of diagonal matrices, as well as the development of a new algorithm for convolution through synthesis of circulant matrices using only O(dlogN+log2N) 1 and 2-qubit gates for a filter of lengths d . Published by the American Physical Society 2024