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.01492 · Society for Industrial and Applied Mathematics eBooks

An Improved Classical Singular Value Transformation for Quantum Machine Learning

Ainesh Bakshi, Ewin Tang

Published Jan 1, 2024• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/1.9781611977912.86

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 Quantum Power Method and Numerical Integration Using Quantum Singular Value Transformation

Nhat A. Nghiem, Hiroki Sukeno, Zhang, Shuyu +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.

arXiv:2407.11744•Jul 16, 2024•0 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

Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms

François Le Gall

Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. This assumption, which is standard in the field of randomized linear algebra, means that for a unit-norm vector $$u\in\mathbb{C}^{n}$$ , we can sample from the distribution $$p_u\colon\{1,\ldots,n\}\to [0,1]$$ defined as $$p_u(i)=|u(i)|^2$$ for each $$i\in\{1,\ldots,n\}$$ . Since this distribution corresponds to the distribution obtained by measuring the quantum state | $$u$$ > in the computational basis, length-squared sampling access gives a reasonable classical analogue to the kind of quantum access considered in many quantum algorithms for linear algebra problems. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gilyén, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.

Computational Complexity•Jan 18, 2025•5 citations

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén, Yuan Su, Guang Hao Low +1 more

An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.

arXiv:1806.01838•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•645 citations

Quantum Machine Learning: Algorithms and Applications A Focused Review on Performance Comparison Between Classical and Quantum Implementations

Arimondo Scrivano

Quantum Machine Learning (QML) represents a promising frontier of research where the principles of quantum mechanics are combined with machine learning to offer potentially superior performance over classical counterparts. This review article explores the current advancements in QML, specifically focusing on the performance improvement and comparison between standard classical algorithms and their quantum implementations. We initiate with an overview of fundamental quantum algorithms that have found applicability within machine learning contexts, such as quantum principal component analysis and quantum support vector machines. The review then delves into a critical assessment of these quantum approaches, highlighting case studies where quantum implementations have demonstrated computational speedups or improved accuracy. Furthermore, we investigate the inherent challenges and limitations that currently hinder the widespread adoption of QML technologies, including the issues of decoherence, error rates, and quantum resource requirements. In addition, the review provides insights into the current state of quantum hardware and its scalability for machine learning tasks. Throughout, comparisons are made to outline scenarios in which quantum machine learning presents a genuine advantage over classical techniques, supported by performance metrics and benchmark datasets. The article concludes by discussing future directions in QML research, with an emphasis on algorithmic innovation and hardware improvement, to realize the full potential of quantum-enhanced machine learning.

•Jun 11, 2025•0 citations
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.
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.
Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. This assumption, which is standard in the field of randomized linear algebra, means that for a unit-norm vector u∈Cnu\in\mathbb{C}^{n}u∈Cn , we can sample from the distribution pu ⁣:{1,…,n}→[0,1]p_u\colon\{1,\ldots,n\}\to [0,1]pu​:{1,…,n}→[0,1] defined as pu(i)=∣u(i)∣2p_u(i)=|u(i)|^2pu​(i)=∣u(i)∣2 for each i∈{1,…,n}i\in\{1,\ldots,n\}i∈{1,…,n} . Since this distribution corresponds to the distribution obtained by measuring the quantum state | uuu > in the computational basis, length-squared sampling access gives a reasonable classical analogue to the kind of quantum access considered in many quantum algorithms for linear algebra problems. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gilyén, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.
An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.
Quantum Machine Learning (QML) represents a promising frontier of research where the principles of quantum mechanics are combined with machine learning to offer potentially superior performance over classical counterparts. This review article explores the current advancements in QML, specifically focusing on the performance improvement and comparison between standard classical algorithms and their quantum implementations. We initiate with an overview of fundamental quantum algorithms that have found applicability within machine learning contexts, such as quantum principal component analysis and quantum support vector machines. The review then delves into a critical assessment of these quantum approaches, highlighting case studies where quantum implementations have demonstrated computational speedups or improved accuracy. Furthermore, we investigate the inherent challenges and limitations that currently hinder the widespread adoption of QML technologies, including the issues of decoherence, error rates, and quantum resource requirements. In addition, the review provides insights into the current state of quantum hardware and its scalability for machine learning tasks. Throughout, comparisons are made to outline scenarios in which quantum machine learning presents a genuine advantage over classical techniques, supported by performance metrics and benchmark datasets. The article concludes by discussing future directions in QML research, with an emphasis on algorithmic innovation and hardware improvement, to realize the full potential of quantum-enhanced machine learning.