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

Improved Quantum Power Method and Numerical Integration Using Quantum Singular Value Transformation

Nhat A. Nghiem, Hiroki Sukeno, Zhang, Shuyu, Tzu-Chieh Wei

Published Jul 16, 2024• 0 citations
arXivHTMLPDF

Abstract

Quantum singular value transformation (QSVT) is a framework that has been shown to unify many primitives in quantum algorithms. In this work, we leverage the QSVT framework in two directions. We first show that the QSVT framework can accelerate one recently introduced quantum power method, which substantially improves its running time. Additionally, we incorporate several elementary numerical integration techniques, such as the rectangular method, Monte Carlo method, and quadrature method, into the QSVT framework, which results in polynomial speedup with respect to the size or the number of points of the grid. Our results thus provide further examples to demonstrate the potential of the QSVT and how it may enhance quantum algorithmic tasks.

DOI
10.48550/arxiv.2407.11744

Related papers

Improved quantum power method and numerical integration using a quantum singular-value transformation

Nhat A. Nghiem, Hiroki Sukeno, Shuyu Zhang +1 more

Quantum singular-value transformation (QSVT) is a framework that has been shown to unify many primitives in quantum algorithms. In this work we leverage the QSVT framework in two directions. We first show that the QSVT framework can accelerate one recently introduced quantum power method, which substantially improves its running time. Additionally, we incorporate several elementary numerical integration techniques, such as the rectangular method, Monte Carlo method, and quadrature method, into the QSVT framework, which results in polynomial speedup with respect to the size or the number of points of the grid. Our results thus provide further examples to demonstrate the potential of the QSVT and how it may enhance quantum algorithmic tasks.

Physical Review A•Jan 21, 2025•3 citations

Improved Performance of Quantum Search via Quantum Singular Value Transformation

Zheng Zhang, Minzhong Luo

Quantum singular value transformation (QSVT) is a powerful framework that unifies many quantum algorithms, including Grover’s search, by enabling polynomial transformations of the singular values of linear operators embedded in unitary matrices. We present an improved quantum search algorithm within this framework. Instead of amplifying the target state amplitude, our method suppresses the non-target amplitude using a modified Chebyshev polynomial. This approach achieves the optimal \(\mathcal {O}(\sqrt {N}\log (1/\delta))\) query complexity while requiring lower-degree polynomials. For N = 512, our method reduces the polynomial degree from 71 to 43 compared to prior QSVT-based fixed-point search. We also demonstrate how QSVT enables exact search construction.

International Conference on Computer Information and Big Data Applications (CIBDA)•Mar 20, 2026•0 citations

An Improved Classical Singular Value Transformation for Quantum Machine Learning

Ainesh Bakshi, Ewin Tang

The field of quantum machine learning (QML) produces many proposals for attaining quantum speedups for tasks in machine learning and data analysis. Such speedups can only manifest if classical algorithms for these tasks perform significantly slower than quantum ones. We study quantum-classical gaps in QML through the quantum singular value transformation (QSVT) framework. QSVT, introduced by Gilyén, Su, Low and Wiebe [GSLW19], unifies all major types of quantum speedup [MRTC21]; in particular, a wide variety of QML proposals are applications of QSVT on low-rank classical data. We challenge these proposals by providing a classical algorithm that matches the performance of QSVT in this regime up to a small polynomial overhead.

arXiv:2303.01492•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•14 citations

Randomized Quantum Singular Value Transformation

Xinzhao Wang, Yuxin Zhang, Hazra, Soumyabrata +3 more

We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.

arXiv:2510.06851•Oct 8, 2025•0 citations

Feedforward Quantum Singular Value Transformation

Yulong Dong, Dong Un An, Murphy Yuezhen Niu

In this paper, we introduce a major advancement in Quantum Singular Value Transformation (QSVT) through the development of Feedforward QSVT (FQSVT), a framework that significantly enhances the efficiency and robustness of quantum algorithm design. By leveraging intermediate measurements and feedforward operations, FQSVTs reclaim quantum information typically discarded in conventional QSVT, enabling more efficient transformations. Our results show that FQSVTs can exponentially accelerate the projection of quantum states onto energy subspaces, outperforming probabilistic projection and adiabatic algorithms with superior efficiency and a drastic reduction in query complexity. In the context of superconducting qubits, FQSVTs offer a powerful tool for managing energy subspaces, improving efficiency for state preparation and leakage detection.

arXiv:2408.07803•Aug 14, 2024•0 citations

A CS guide to the quantum singular value transformation

Ewin Tang, Kevin Tian

We present a simplified exposition of some pieces of [GSLW19], which introduces a quantum singular value transformation (QSVT) framework for applying polynomial functions to block-encoded matrices. The QSVT framework has garnered substantial recent interest from the quantum algorithms community, as it was demonstrated by [GSLW19] to encapsulate many existing algorithms naturally phrased as an application of a matrix function. First, we posit that the lifting of quantum singular processing (QSP) to QSVT is better viewed not through Jordan's lemma [Jor75; Reg06] (as was suggested by [GSLW19]) but as an application of the cosine-sine decomposition, which can be thought of as a more explicit and stronger version of Jordan's lemma. Second, we demonstrate that the constructions of bounded polynomial approximations given in [GSLW19], which use a variety of ad hoc approaches drawing from Fourier analysis, Chebyshev series, and Taylor series, can be unified under the framework of truncation of Chebyshev series, and indeed, can in large part be matched via a bounded variant of a standard meta-theorem from [Tre19]. We hope this work finds use to the community as a companion guide for understanding and applying the powerful framework of [GSLW19].

arXiv:2302.14324•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•13 citations
Quantum singular value transformation (QSVT) is a framework that has been shown to unify many primitives in quantum algorithms. In this work, we leverage the QSVT framework in two directions. We first show that the QSVT framework can accelerate one recently introduced quantum power method, which substantially improves its running time. Additionally, we incorporate several elementary numerical integration techniques, such as the rectangular method, Monte Carlo method, and quadrature method, into the QSVT framework, which results in polynomial speedup with respect to the size or the number of points of the grid. Our results thus provide further examples to demonstrate the potential of the QSVT and how it may enhance quantum algorithmic tasks.
Quantum singular-value transformation (QSVT) is a framework that has been shown to unify many primitives in quantum algorithms. In this work we leverage the QSVT framework in two directions. We first show that the QSVT framework can accelerate one recently introduced quantum power method, which substantially improves its running time. Additionally, we incorporate several elementary numerical integration techniques, such as the rectangular method, Monte Carlo method, and quadrature method, into the QSVT framework, which results in polynomial speedup with respect to the size or the number of points of the grid. Our results thus provide further examples to demonstrate the potential of the QSVT and how it may enhance quantum algorithmic tasks.
Quantum singular value transformation (QSVT) is a powerful framework that unifies many quantum algorithms, including Grover’s search, by enabling polynomial transformations of the singular values of linear operators embedded in unitary matrices. We present an improved quantum search algorithm within this framework. Instead of amplifying the target state amplitude, our method suppresses the non-target amplitude using a modified Chebyshev polynomial. This approach achieves the optimal O(Nlog⁡(1/δ))\mathcal {O}(\sqrt {N}\log (1/\delta))O(N​log(1/δ)) query complexity while requiring lower-degree polynomials. For N = 512, our method reduces the polynomial degree from 71 to 43 compared to prior QSVT-based fixed-point search. We also demonstrate how QSVT enables exact search construction.
The field of quantum machine learning (QML) produces many proposals for attaining quantum speedups for tasks in machine learning and data analysis. Such speedups can only manifest if classical algorithms for these tasks perform significantly slower than quantum ones. We study quantum-classical gaps in QML through the quantum singular value transformation (QSVT) framework. QSVT, introduced by Gilyén, Su, Low and Wiebe [GSLW19], unifies all major types of quantum speedup [MRTC21]; in particular, a wide variety of QML proposals are applications of QSVT on low-rank classical data. We challenge these proposals by providing a classical algorithm that matches the performance of QSVT in this regime up to a small polynomial overhead.
We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.
In this paper, we introduce a major advancement in Quantum Singular Value Transformation (QSVT) through the development of Feedforward QSVT (FQSVT), a framework that significantly enhances the efficiency and robustness of quantum algorithm design. By leveraging intermediate measurements and feedforward operations, FQSVTs reclaim quantum information typically discarded in conventional QSVT, enabling more efficient transformations. Our results show that FQSVTs can exponentially accelerate the projection of quantum states onto energy subspaces, outperforming probabilistic projection and adiabatic algorithms with superior efficiency and a drastic reduction in query complexity. In the context of superconducting qubits, FQSVTs offer a powerful tool for managing energy subspaces, improving efficiency for state preparation and leakage detection.
We present a simplified exposition of some pieces of [GSLW19], which introduces a quantum singular value transformation (QSVT) framework for applying polynomial functions to block-encoded matrices. The QSVT framework has garnered substantial recent interest from the quantum algorithms community, as it was demonstrated by [GSLW19] to encapsulate many existing algorithms naturally phrased as an application of a matrix function. First, we posit that the lifting of quantum singular processing (QSP) to QSVT is better viewed not through Jordan's lemma [Jor75; Reg06] (as was suggested by [GSLW19]) but as an application of the cosine-sine decomposition, which can be thought of as a more explicit and stronger version of Jordan's lemma. Second, we demonstrate that the constructions of bounded polynomial approximations given in [GSLW19], which use a variety of ad hoc approaches drawing from Fourier analysis, Chebyshev series, and Taylor series, can be unified under the framework of truncation of Chebyshev series, and indeed, can in large part be matched via a bounded variant of a standard meta-theorem from [Tre19]. We hope this work finds use to the community as a companion guide for understanding and applying the powerful framework of [GSLW19].