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• 55 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

Quantum Algorithms for Linear Algebra and Machine Learning.

Anupam Prakash

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

•Jan 1, 2014•51 citations

Quantum algorithms for linear algebra and machine learning. - eScholarship

Anupam Prakash

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

•Jan 1, 2014•0 citations

Quantum Linear Algebra for Machine Learning

Hamid D. Ismail

This chapter examines quantum linear algebra as a foundational framework for quantum machine learning. Because many core learning tasks, including regression, dimensionality reduction, kernel evaluation, recommendation systems, and representation learning, depend on linear algebraic operations, this chapter explores how these operations can be reformulated in the quantum setting. Emphasis is placed on the shift from explicit numerical computation to coherent manipulation of quantum states and measurement-based access to information. This chapter introduces quantum inner product estimation as a primitive for similarity and kernel evaluation, highlighting the swap test and related overlap-estimation methods. It then develops quantum matrix inversion and the HHL algorithm, emphasizing the preparation of solution states rather than explicit solution vectors and discussing the importance of conditioning and regularization. Quantum singular value decomposition is presented through Hermitian embeddings, phase estimation, block encoding, and quantum singular value transformation, providing a unified framework for spectral filtering and low-rank approximation. This chapter concludes with quantum principal component analysis, in which covariance structure is represented by a density matrix and accessed through quantum phase estimation and density matrix exponentiation. Throughout, practical demonstrations in Qiskit and PennyLane illustrate the algorithms, while careful attention is given to the limitations imposed by state preparation, measurement, noise, and classical data loading.

CRC Press eBooks•Nov 4, 2026•0 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•50 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•2 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.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAMQRAMQRAM, the standard model studied in quantum query complexity, requires time O(sqrtn)O(sqrt{n})O(sqrtn) to encode vectors vinRnv in R^{n}vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAMQRAMQRAM, that enable vectors vinRnv in R^{n}vinRn to be encoded in time O(logn)O(log n)O(logn), with pre-processing. The augmented QRAMQRAMQRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAMQRAMQRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketvket{v}ketv for AinRmtimesnA in R^{mtimes n}AinRmtimesn, the singular value sigmaisigma_{i}sigmai​ is estimated within additive error epsilonnormAFepsilon norm{A}_{F}epsilonnormAF​. The first algorithm requires time wt1/epsilon3wt{1/epsilon^{3}}wt1/epsilon3 and uses the approach for simulating e−irhoe^{-i rho}e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilonwt{1/epsilon}wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAMQRAMQRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CXCXCX and CURCURCUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon))O(mn log n + poly(1/epsilon))O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta))O(sqrt{m}poly(1/epsilon, k, Delta))O(sqrtmpoly(1/epsilon,k,Delta)) where k,Deltak, Deltak,Delta are the rank and spectral gap. The running time of the quantum CXCXCX decomposition algorithm does not depend on mmm, it is polynomial in problem parameters. We also provide quantum algorithms for ell2ell_{2}ell2​ regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2deltawt{1/mu^{2} delta}wt1/mu2delta to output a quantum state that is deltadeltadelta close to the solution, where mumumu is the regularization parameter.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAMQRAMQRAM, the standard model studied in quantum query complexity, requires time O(sqrtn)O(sqrt{n})O(sqrtn) to encode vectors vinRnv in R^{n}vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAMQRAMQRAM, that enable vectors vinRnv in R^{n}vinRn to be encoded in time O(logn)O(log n)O(logn), with pre-processing. The augmented QRAMQRAMQRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAMQRAMQRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketvket{v}ketv for AinRmtimesnA in R^{mtimes n}AinRmtimesn, the singular value sigmaisigma_{i}sigmai​ is estimated within additive error epsilonnormAFepsilon norm{A}_{F}epsilonnormAF​. The first algorithm requires time wt1/epsilon3wt{1/epsilon^{3}}wt1/epsilon3 and uses the approach for simulating e−irhoe^{-i rho}e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilonwt{1/epsilon}wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAMQRAMQRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CXCXCX and CURCURCUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon))O(mn log n + poly(1/epsilon))O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta))O(sqrt{m}poly(1/epsilon, k, Delta))O(sqrtmpoly(1/epsilon,k,Delta)) where k,Deltak, Deltak,Delta are the rank and spectral gap. The running time of the quantum CXCXCX decomposition algorithm does not depend on mmm, it is polynomial in problem parameters. We also provide quantum algorithms for ell2ell_{2}ell2​ regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2deltawt{1/mu^{2} delta}wt1/mu2delta to output a quantum state that is deltadeltadelta close to the solution, where mumumu is the regularization parameter.
This chapter examines quantum linear algebra as a foundational framework for quantum machine learning. Because many core learning tasks, including regression, dimensionality reduction, kernel evaluation, recommendation systems, and representation learning, depend on linear algebraic operations, this chapter explores how these operations can be reformulated in the quantum setting. Emphasis is placed on the shift from explicit numerical computation to coherent manipulation of quantum states and measurement-based access to information. This chapter introduces quantum inner product estimation as a primitive for similarity and kernel evaluation, highlighting the swap test and related overlap-estimation methods. It then develops quantum matrix inversion and the HHL algorithm, emphasizing the preparation of solution states rather than explicit solution vectors and discussing the importance of conditioning and regularization. Quantum singular value decomposition is presented through Hermitian embeddings, phase estimation, block encoding, and quantum singular value transformation, providing a unified framework for spectral filtering and low-rank approximation. This chapter concludes with quantum principal component analysis, in which covariance structure is represented by a density matrix and accessed through quantum phase estimation and density matrix exponentiation. Throughout, practical demonstrations in Qiskit and PennyLane illustrate the algorithms, while careful attention is given to the limitations imposed by state preparation, measurement, noise, and classical data loading.
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.
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.