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

Quantum Signal Processing, Phase Extraction, and Proportional Sampling

Lorenzo Laneve

Published Mar 20, 2023• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2303.11077

Related papers

On multivariate polynomials achievable with quantum signal processing

Lorenzo Laneve, Stefan Wolf

Quantum signal processing (QSP) is a framework which was proven to unify and simplify a large number of known quantum algorithms, as well as discovering new ones. QSP allows one to transform a signal embedded in a given unitary using polynomials. Characterizing which polynomials can be achieved with QSP protocols is an important part of the power of this technique, and while such a characterization is well-understood in the case of univariate signals, it is unclear which multivariate polynomials can be constructed when the signal is a vector, rather than a scalar. This work uses a slightly different formalism than what is found in the literature, and uses it to find simpler necessary conditions for decomposability, as well as a sufficient condition – the first, to the best of our knowledge, proven for a (generally inhomogeneous) multivariate polynomial in the context of quantum signal processing.

arXiv:2407.20823•Quantum•Feb 20, 2025•5 citations

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

Parallel Quantum Signal Processing Via Polynomial Factorization

John M. Martyn, Zane M. Rossi, Kevin Z. Cheng +2 more

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.

arXiv:2409.19043•Quantum•Aug 27, 2025•2 citations

Halving the cost of quantum algorithms with randomization

John M. Martyn, Patrick Rall

Abstract Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling , a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., ϵ → O ( ϵ 2 )) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing . Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as $$O(\log (1/\epsilon ))$$ O ( log ( 1 / ϵ ) ) —stemming from a result in functional analysis—this error suppression reduces their query complexity by a factor that asymptotically approaches 1/2. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.

arXiv:2409.03744•npj Quantum Information•Mar 15, 2025•8 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
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 framework which was proven to unify and simplify a large number of known quantum algorithms, as well as discovering new ones. QSP allows one to transform a signal embedded in a given unitary using polynomials. Characterizing which polynomials can be achieved with QSP protocols is an important part of the power of this technique, and while such a characterization is well-understood in the case of univariate signals, it is unclear which multivariate polynomials can be constructed when the signal is a vector, rather than a scalar. This work uses a slightly different formalism than what is found in the literature, and uses it to find simpler necessary conditions for decomposability, as well as a sufficient condition – the first, to the best of our knowledge, proven for a (generally inhomogeneous) multivariate polynomial in the context of 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
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.
Abstract Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling , a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., ϵ → O ( ϵ 2 )) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing . Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as O(log⁡(1/ϵ))O(\log (1/\epsilon ))O(log(1/ϵ)) O ( log ( 1 / ϵ ) ) —stemming from a result in functional analysis—this error suppression reduces their query complexity by a factor that asymptotically approaches 1/2. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.
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.