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

Quantum machine learning with subspace states

Iordanis Kerenidis, Anupam Prakash

Published Jan 31, 2022• 10 citations
arXivHTMLPDF

Abstract

We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$. The state of art classical algorithm for the task requires $O(d^{3})$ operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices $\mathcal{A}^{k}$, the speedup for this algorithm is potentially exponential. It decomposes a $\binom{n}{k}$ dimensional vector of order-$k$ correlations into a linear combination of subspace states corresponding to $k$-tuples of singular vectors of $A$. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$. Our basic tool are quantum subspace states, defined as $|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in \mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$, that encode $d$-dimensional subspaces of $\mathbb{R}^{n}$. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries $Γ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}$ with $O(\log n)$ depth circuits that we term Clifford loaders.

DOI
10.48550/arxiv.2202.00054

Related papers

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

Shadow Quantum Singular Value Transformation with Shallow Quantum Circuits

Nai-Hui Chia, Hyunseong Kim, Chia-Ying Lin +1 more

We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|ψ\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of observables $\{O_1,\dots,O_m\}$, the goal is to estimate $\langleψ|f(H)^{\dagger}O_j f(H)|ψ\rangle$ for all $j\in\{1,\dots,m\}$. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of $f(H)$. It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with $H$ and $|ψ\rangle$ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from $H$, $f$, and $|ψ\rangle$ without prior knowledge of the observables or explicit preparation of the target state proportional to $f(H)|ψ\rangle$. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.

quant-pharXiv:2609.40167•Oct 1, 2026•0 citations

Design and analysis of quantum machine learning: a survey

Linshu Chen, Tao Li, Yuxiang Chen +4 more

Machine learning has demonstrated tremendous potential in solving real-world problems. However, with the exponential growth of data amount and the increase of model complexity, the processing efficiency of machine learning declines rapidly. Meanwhile, the emergence of quantum computing has given rise to quantum machine learning, which relies on superposition and entanglement, exhibiting exponential optimisation compared to traditional machine learning. Therefore, in the paper, we survey the basic concepts, algorithms, applications and challenges of quantum machine learning. Concretely, we first review the basic concepts of quantum computing including qubit, quantum gates, quantum entanglement, etc.. Secondly, we in-depth discuss 5 quantum machine learning algorithms of quantum support vector machine, quantum neural network, quantum k-nearest neighbour, quantum principal component analysis and quantum k-Means algorithm. Thirdly, we conduct discussions on the applications of quantum machine learning in image recognition, drug efficacy prediction and cybersecurity. Finally, we summarise the challenges of quantum machine learning consisting of algorithm design, hardware limitations, data encoding, quantum landscapes, noise and decoherence.

Connection Science•Mar 29, 2024•36 citations

Quantum Machine Learning in Feature Hilbert Spaces

Maria Schuld, Nathan Killoran

A basic idea of quantum computing is surprisingly similar to that of kernel methods in machine learning, namely, to efficiently perform computations in an intractably large Hilbert space. In this Letter we explore some theoretical foundations of this link and show how it opens up a new avenue for the design of quantum machine learning algorithms. We interpret the process of encoding inputs in a quantum state as a nonlinear feature map that maps data to quantum Hilbert space. A quantum computer can now analyze the input data in this feature space. Based on this link, we discuss two approaches for building a quantum model for classification. In the first approach, the quantum device estimates inner products of quantum states to compute a classically intractable kernel. The kernel can be fed into any classical kernel method such as a support vector machine. In the second approach, we use a variational quantum circuit as a linear model that classifies data explicitly in Hilbert space. We illustrate these ideas with a feature map based on squeezing in a continuous-variable system, and visualize the working principle with two-dimensional minibenchmark datasets.

arXiv:1803.07128•Physical Review Letters•Feb 1, 2019•1,856 citations

Hermitian Matrix Function Synthesis without Block-Encoding

Anuradha Mahasinghe, Kaushika De Silva, Xavier Cadet +3 more

Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.

quant-pharXiv:2512.18249•Dec 23, 2025•0 citations

Quantum Topological Data Analysis with Linear Depth and Exponential Speedup

Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S. Squillante +2 more

Quantum computing offers the potential of exponential speedups for certain classical computations. Over the last decade, many quantum machine learning (QML) algorithms have been proposed as candidates for such exponential improvements. However, two issues unravel the hope of exponential speedup for some of these QML algorithms: the data-loading problem and, more recently, the stunning dequantization results of Tang et al. A third issue, namely the fault-tolerance requirements of most QML algorithms, has further hindered their practical realization. The quantum topological data analysis (QTDA) algorithm of Lloyd, Garnerone and Zanardi was one of the first QML algorithms that convincingly offered an expected exponential speedup. From the outset, it did not suffer from the data-loading problem. A recent result has also shown that the generalized problem solved by this algorithm is likely classically intractable, and would therefore be immune to any dequantization efforts. However, the QTDA algorithm of Lloyd et~al. has a time complexity of $O(n^4/(ε^2 δ))$ (where $n$ is the number of data points, $ε$ is the error tolerance, and $δ$ is the smallest nonzero eigenvalue of the restricted Laplacian) and requires fault-tolerant quantum computing, which has not yet been achieved. In this paper, we completely overhaul the QTDA algorithm to achieve an improved exponential speedup and depth complexity of $O(n\log(1/(δε)))$. Our approach includes three key innovations: (a) an efficient realization of the combinatorial Laplacian as a sum of Pauli operators; (b) a quantum rejection sampling approach to restrict the superposition to the simplices in the complex; and (c) a stochastic rank estimation method to estimate the Betti numbers. We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.

arXiv:2108.02811•Aug 5, 2021•18 citations
We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution Pr⁡[S]=det(XSXST)\Pr[S]= det(X_{S}X_{S}^{T})Pr[S]=det(XS​XST​) for ∣S∣=d|S|=d∣S∣=d using O(nd)O(nd)O(nd) gates and with circuit depth O(dlog⁡n)O(d\log n)O(dlogn). The state of art classical algorithm for the task requires O(d3)O(d^{3})O(d3) operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices Ak\mathcal{A}^{k}Ak, the speedup for this algorithm is potentially exponential. It decomposes a (nk)\binom{n}{k}(kn​) dimensional vector of order-kkk correlations into a linear combination of subspace states corresponding to kkk-tuples of singular vectors of AAA. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from O(n)O(n)O(n) to O(log⁡n)O(\log n)O(logn). Our basic tool are quantum subspace states, defined as ∣Col(X)⟩=∑S⊂[n],∣S∣=ddet(XS)∣S⟩|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle∣Col(X)⟩=∑S⊂[n],∣S∣=d​det(XS​)∣S⟩ for matrices X∈Rn×dX \in \mathbb{R}^{n \times d}X∈Rn×d such that XTX=IdX^{T} X = I_{d}XTX=Id​, that encode ddd-dimensional subspaces of Rn\mathbb{R}^{n}Rn. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries Γ(x)=∑ixiZ⊗(i−1)⊗X⊗In−iΓ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}Γ(x)=∑i​xi​Z⊗(i−1)⊗X⊗In−i with O(log⁡n)O(\log n)O(logn) depth circuits that we term Clifford loaders.
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.
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state ∣ψ⟩|ψ\rangle∣ψ⟩, a Hermitian matrix HHH, a polynomial fff, and a set of observables {O1,…,Om}\{O_1,\dots,O_m\}{O1​,…,Om​}, the goal is to estimate ⟨ψ∣f(H)†Ojf(H)∣ψ⟩\langleψ|f(H)^{\dagger}O_j f(H)|ψ\rangle⟨ψ∣f(H)†Oj​f(H)∣ψ⟩ for all j∈{1,…,m}j\in\{1,\dots,m\}j∈{1,…,m}. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of f(H)f(H)f(H). It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with HHH and ∣ψ⟩|ψ\rangle∣ψ⟩ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from HHH, fff, and ∣ψ⟩|ψ\rangle∣ψ⟩ without prior knowledge of the observables or explicit preparation of the target state proportional to f(H)∣ψ⟩f(H)|ψ\ranglef(H)∣ψ⟩. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.
Machine learning has demonstrated tremendous potential in solving real-world problems. However, with the exponential growth of data amount and the increase of model complexity, the processing efficiency of machine learning declines rapidly. Meanwhile, the emergence of quantum computing has given rise to quantum machine learning, which relies on superposition and entanglement, exhibiting exponential optimisation compared to traditional machine learning. Therefore, in the paper, we survey the basic concepts, algorithms, applications and challenges of quantum machine learning. Concretely, we first review the basic concepts of quantum computing including qubit, quantum gates, quantum entanglement, etc.. Secondly, we in-depth discuss 5 quantum machine learning algorithms of quantum support vector machine, quantum neural network, quantum k-nearest neighbour, quantum principal component analysis and quantum k-Means algorithm. Thirdly, we conduct discussions on the applications of quantum machine learning in image recognition, drug efficacy prediction and cybersecurity. Finally, we summarise the challenges of quantum machine learning consisting of algorithm design, hardware limitations, data encoding, quantum landscapes, noise and decoherence.
A basic idea of quantum computing is surprisingly similar to that of kernel methods in machine learning, namely, to efficiently perform computations in an intractably large Hilbert space. In this Letter we explore some theoretical foundations of this link and show how it opens up a new avenue for the design of quantum machine learning algorithms. We interpret the process of encoding inputs in a quantum state as a nonlinear feature map that maps data to quantum Hilbert space. A quantum computer can now analyze the input data in this feature space. Based on this link, we discuss two approaches for building a quantum model for classification. In the first approach, the quantum device estimates inner products of quantum states to compute a classically intractable kernel. The kernel can be fed into any classical kernel method such as a support vector machine. In the second approach, we use a variational quantum circuit as a linear model that classifies data explicitly in Hilbert space. We illustrate these ideas with a feature map based on squeezing in a continuous-variable system, and visualize the working principle with two-dimensional minibenchmark datasets.
Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.
Quantum computing offers the potential of exponential speedups for certain classical computations. Over the last decade, many quantum machine learning (QML) algorithms have been proposed as candidates for such exponential improvements. However, two issues unravel the hope of exponential speedup for some of these QML algorithms: the data-loading problem and, more recently, the stunning dequantization results of Tang et al. A third issue, namely the fault-tolerance requirements of most QML algorithms, has further hindered their practical realization. The quantum topological data analysis (QTDA) algorithm of Lloyd, Garnerone and Zanardi was one of the first QML algorithms that convincingly offered an expected exponential speedup. From the outset, it did not suffer from the data-loading problem. A recent result has also shown that the generalized problem solved by this algorithm is likely classically intractable, and would therefore be immune to any dequantization efforts. However, the QTDA algorithm of Lloyd et~al. has a time complexity of O(n4/(ε2δ))O(n^4/(ε^2 δ))O(n4/(ε2δ)) (where nnn is the number of data points, εεε is the error tolerance, and δδδ is the smallest nonzero eigenvalue of the restricted Laplacian) and requires fault-tolerant quantum computing, which has not yet been achieved. In this paper, we completely overhaul the QTDA algorithm to achieve an improved exponential speedup and depth complexity of O(nlog⁡(1/(δε)))O(n\log(1/(δε)))O(nlog(1/(δε))). Our approach includes three key innovations: (a) an efficient realization of the combinatorial Laplacian as a sum of Pauli operators; (b) a quantum rejection sampling approach to restrict the superposition to the simplices in the complex; and (c) a stochastic rank estimation method to estimate the Betti numbers. We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.