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:2409.19043 · Quantum

Parallel Quantum Signal Processing Via Polynomial Factorization

John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, Isaac L. Chuang

Published Aug 27, 2025• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2025-08-27-1834

Related papers

Quantum Signal Processing and Quantum Singular Value Transformation on U ( N )

Xi Lu, Yuan Liu, Hongwei Lin

Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on U ( N ) , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on U ( 2 ) in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate N -interval decision achieving O ( d ) query complexity with a log 2 ⁡ N improvement over iterative U ( 2 ) -QSP requiring O ( d log 2 ⁡ N ) queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.

arXiv:2408.01439•Quantum•Mar 27, 2026•1 citation

Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations

Kevin J. Joven, Elin Ranjan Das, Joel Bierman +3 more

Significant developments made in quantum hardware and error correction recently have been driving quantum computing towards practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this Perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented including construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this Perspective serves as a gentle introduction of state-of-the-art quantum algorithms to the computational science community, and inspires future development on scalable quantum computational science methodologies that bridge theory and practice.

quant-pharXiv:2511.16738•APL Computational Physics•Nov 24, 2025•2 citations

Quantum Signal Processing, Phase Extraction, and Proportional Sampling

Lorenzo Laneve

Quantum Signal Processing (QSP) is a technique that can be used to implement a polynomial transformation $P(x)$ applied to the eigenvalues of a unitary $U$, essentially implementing the operation $P(U)$, provided that $P$ satisfies some conditions that are easy to satisfy. A rich class of previously known quantum algorithms were shown to be derived or reduced to this technique or one of its extensions. In this work, we show that QSP can be used to tackle a new problem, which we call phase extraction, and that this can be used to provide quantum speed-up for proportional sampling, a problem of interest in machine-learning applications and quantum state preparation. We show that, for certain sampling distributions, our algorithm provides an almost-quadratic speed-up over classical sampling procedures. Then we extend the result by constructing a sequence of algorithms that increasingly relax the dependence on the space of elements to sample.

arXiv:2303.11077•Mar 20, 2023•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

From Block-encoding to Generalized Quantum Signal Processing: Principles, Algorithms and Applications

Tal Gurfinkel, Kaushika De Silva, Anuradha Mahasinghe +9 more

Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations. A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.

quant-pharXiv:2609.09977•Sep 10, 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•21 citations
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.
Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on U ( N ) , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on U ( 2 ) in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate N -interval decision achieving O ( d ) query complexity with a log 2 ⁡ N improvement over iterative U ( 2 ) -QSP requiring O ( d log 2 ⁡ N ) queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.
Significant developments made in quantum hardware and error correction recently have been driving quantum computing towards practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this Perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented including construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this Perspective serves as a gentle introduction of state-of-the-art quantum algorithms to the computational science community, and inspires future development on scalable quantum computational science methodologies that bridge theory and practice.
Quantum Signal Processing (QSP) is a technique that can be used to implement a polynomial transformation P(x)P(x)P(x) applied to the eigenvalues of a unitary UUU, essentially implementing the operation P(U)P(U)P(U), provided that PPP satisfies some conditions that are easy to satisfy. A rich class of previously known quantum algorithms were shown to be derived or reduced to this technique or one of its extensions. In this work, we show that QSP can be used to tackle a new problem, which we call phase extraction, and that this can be used to provide quantum speed-up for proportional sampling, a problem of interest in machine-learning applications and quantum state preparation. We show that, for certain sampling distributions, our algorithm provides an almost-quadratic speed-up over classical sampling procedures. Then we extend the result by constructing a sequence of algorithms that increasingly relax the dependence on the space of elements to sample.
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}$.
Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations. A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.
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 → ∞ .