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• 1 citation
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•15 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•149 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•14 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•18 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

Quantum signal processing over SU(N)

Lorenzo Laneve

Quantum signal processing (QSP) and the quantum singular value transformation (QSVT) are pivotal tools for simplifying the development of quantum algorithms. These techniques leverage polynomial transformations on the eigenvalues or singular values of block-encoded matrices, achieved with the use of just one control qubit. In contexts where the control qubit is used to extract information about the eigenvalues or singular values, the amount of extractable information is limited to one bit per protocol. In this work, we extend the original QSP ansatz by introducing multiple control qubits. We show that, much like in the single-qubit case, nearly any vector of polynomials can be implemented with a multi-qubit QSP ansatz, and the gate complexity scales polynomially with the dimension of such states. Moreover, assuming that powers of the matrix to transform are easily implementable - as in Shor's algorithm - we can achieve polynomial transformations with degrees that scale exponentially with the number of control qubits. This work aims to provide a partial characterization of the polynomials that can be implemented using this approach, with phase estimation schemes and discrete logarithm serving as illustrative examples.

arXiv:2311.03949•Nov 7, 2023•16 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}$.
Quantum signal processing (QSP) and the quantum singular value transformation (QSVT) are pivotal tools for simplifying the development of quantum algorithms. These techniques leverage polynomial transformations on the eigenvalues or singular values of block-encoded matrices, achieved with the use of just one control qubit. In contexts where the control qubit is used to extract information about the eigenvalues or singular values, the amount of extractable information is limited to one bit per protocol. In this work, we extend the original QSP ansatz by introducing multiple control qubits. We show that, much like in the single-qubit case, nearly any vector of polynomials can be implemented with a multi-qubit QSP ansatz, and the gate complexity scales polynomially with the dimension of such states. Moreover, assuming that powers of the matrix to transform are easily implementable - as in Shor's algorithm - we can achieve polynomial transformations with degrees that scale exponentially with the number of control qubits. This work aims to provide a partial characterization of the polynomials that can be implemented using this approach, with phase estimation schemes and discrete logarithm serving as illustrative examples.