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

Optimal algorithmic complexity of inference in quantum kernel methods

Elies Gil-fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, Maximilian J. Kramer

quant-phcs.LGSubmitted Apr 16, 2026• Announced Apr 17, 2026• 0 citations
v1 · Apr 16, 2026v2 · Apr 17, 2026
arXivHTMLPDF

Abstract

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum $\sum_{i=1}^N α_i k(x,x_i)$ of $N$ kernel values to additive precision $\varepsilon$, where $α$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $O(N\lVertα\rVert_2^2/\varepsilon^2)$. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of $O(\lVertα\rVert_1/\varepsilon)$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVertα\rVert_1$ and $\varepsilon$. We prove a matching lower bound of $Ω(\lVertα\rVert_1/\varepsilon)$, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

Comments
26 pages (13+13), 4 figures, comments welcome

Related papers

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803•Oct 6, 2026•0 citations

Near-optimal quantum kernel principal component analysis

Youle Wang

Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.

Quantum Science and Technology•Nov 12, 2024•6 citations

Improved Quantum Algorithms for Rényi Entropies Estimation

Zongxing Xiong, Chengshen Gao, Lvzhou Li

Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy $H_α(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access. For non-integer $α> 1$, our algorithm estimates $H_α(\mathbf{p})$ to within additive error $ε$ using only $\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)$ queries, which improves the best known upper bound for dependence on both $n$ and $1/ε$. For $0<α<1$, our algorithm has query complexity $\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)$, which improves the dependence on $1/ε$ of the current best upper bound without incresing its $n$ dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to $Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)$ for $0<α<1$, which identifies the optimal precision dependence of our algorithm.

quant-pharXiv:2610.19936•Oct 15, 2026•0 citations

The Input Problem: A Permanent Bottleneck for Quantum Machine Learning

Muhammad Faryad

Quantum algorithms are conventionally presented with their input state supplied for free. When the input is classical data, this convention conceals a cost that is frequently larger than the algorithm it precedes. We review what the three standard encodings, such as basis encoding, amplitude encoding, and Grover--Rudolph distribution loading, actually cost once transpiled to a hardware gate set, and argue that the resulting $Θ(N)$ bound is a counting theorem rather than an engineering limitation that improved hardware will remove. Measured gate counts for a representative loading task are reported: an optimal library implementation requires $247$ CNOT gates at $n=8$ qubits and doubles with each additional qubit, while the classical preprocessing that produces the rotation angles requires reading the entire input vector. We show how this cost eliminates the quadratic advantage of quantum amplitude estimation for Monte Carlo integration, and argue that the same accounting constrains quantum machine learning more broadly: the strong input models that make quantum algorithms fast on classical data also enable classical dequantization, and quantum kernel methods carry a $Θ(M^2)$ state-preparation cost for the Gram matrix that does not amortize. We explain that the efficiently preparable states, device-generated distributions, variationally learned loading, and amortized preparation are required to get advantage from quantum machine learning and close with a checklist for evaluating input-dependent advantage claims. Executable notebooks reproducing every construction and measurement discussed here are available.

quant-pharXiv:2608.08433•Aug 11, 2026•0 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

•Jul 24, 2020•0 citations

A shortcut to an optimal quantum linear system solver

Alexander M. Dalzell

Given a linear system of equations $A\boldsymbol{x}=\boldsymbol{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $|\boldsymbol{x}\rangle$ for which the amplitudes are proportional to the solution vector $\boldsymbol{x}$. Asymptotically optimal QLSSs have query complexity $O(κ\log(1/\varepsilon))$, where $κ$ is the condition number of $A$, and $\varepsilon$ is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm $\lVert\boldsymbol{x}\rVert$ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is $(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)$. If the norm is unknown, our method allows it to be estimated up to a constant factor using $O(\log\log(κ))$ applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal $O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))$ total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(κ)$ complexity can be achieved for norm estimation, yielding an optimal QLSS with $O(κ\log(1/\varepsilon))$ complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of $56κ+1.05κ\ln(1/\varepsilon)+o(κ)$ for the complexity of our optimal QLSS.

arXiv:2406.12086•Jun 17, 2024•1 citation
Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum ∑i=1Nαik(x,xi)\sum_{i=1}^N α_i k(x,x_i)∑i=1N​αi​k(x,xi​) of NNN kernel values to additive precision ε\varepsilonε, where ααα is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of O(N∥α∥22/ε2)O(N\lVertα\rVert_2^2/\varepsilon^2)O(N∥α∥22​/ε2). In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of O(∥α∥1/ε)O(\lVertα\rVert_1/\varepsilon)O(∥α∥1​/ε), removing the dependence on NNN from the query count and yielding a quadratic improvement in both ∥α∥1\lVertα\rVert_1∥α∥1​ and ε\varepsilonε. We prove a matching lower bound of Ω(∥α∥1/ε)Ω(\lVertα\rVert_1/\varepsilon)Ω(∥α∥1​/ε), establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most qqq oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision εεε requires Θ(1qε2)Θ(\frac{1}{q ε^2})Θ(qε21​) queries; (ii) (Unbiased) Amplitude estimation up to a precision εεε requires Θ(p(1−p)qε2)Θ(\frac{p(1-p)}{q ε^2})Θ(qε2p(1−p)​) queries; (iii) Search among NNN items requires Θ(Nq)Θ(\frac{N}{q})Θ(qN​) queries; (iv) Two level AND-OR tree (AND of mmm ORs, with nnn inputs to each OR) requires Θ(nmq)Θ(\frac{nm}{q})Θ(qnm​) queries. All of these bounds are optimal up to a constant factor, for all qqq from 1, corresponding to the classical complexity, to Q(f)Q(f)Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.
Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy Hα(p)H_α(\mathbf{p})Hα​(p) for any distribution p=(pi)i=1n\mathbf{p} = (p_i)_{i=1}^np=(pi​)i=1n​ given its purified quantum query-access. For non-integer α>1α> 1α>1, our algorithm estimates Hα(p)H_α(\mathbf{p})Hα​(p) to within additive error εεε using only O~(nmax⁡{1/2,1−1/α}/ε)\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both nnn and 1/ε1/ε1/ε. For 0<α<10<α<10<α<1, our algorithm has query complexity O~(n1/(2α)/εmax⁡{1,1/(2α)})\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)O(n1/(2α)/εmax{1,1/(2α)}), which improves the dependence on 1/ε1/ε1/ε of the current best upper bound without incresing its nnn dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to Ω(1/εmax⁡{1,1/(2α)})Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)Ω(1/εmax{1,1/(2α)}) for 0<α<10<α<10<α<1, which identifies the optimal precision dependence of our algorithm.
Quantum algorithms are conventionally presented with their input state supplied for free. When the input is classical data, this convention conceals a cost that is frequently larger than the algorithm it precedes. We review what the three standard encodings, such as basis encoding, amplitude encoding, and Grover--Rudolph distribution loading, actually cost once transpiled to a hardware gate set, and argue that the resulting Θ(N)Θ(N)Θ(N) bound is a counting theorem rather than an engineering limitation that improved hardware will remove. Measured gate counts for a representative loading task are reported: an optimal library implementation requires 247247247 CNOT gates at n=8n=8n=8 qubits and doubles with each additional qubit, while the classical preprocessing that produces the rotation angles requires reading the entire input vector. We show how this cost eliminates the quadratic advantage of quantum amplitude estimation for Monte Carlo integration, and argue that the same accounting constrains quantum machine learning more broadly: the strong input models that make quantum algorithms fast on classical data also enable classical dequantization, and quantum kernel methods carry a Θ(M2)Θ(M^2)Θ(M2) state-preparation cost for the Gram matrix that does not amortize. We explain that the efficiently preparable states, device-generated distributions, variationally learned loading, and amortized preparation are required to get advantage from quantum machine learning and close with a checklist for evaluating input-dependent advantage claims. Executable notebooks reproducing every construction and measurement discussed here are available.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
Given a linear system of equations Ax=bA\boldsymbol{x}=\boldsymbol{b}Ax=b, quantum linear system solvers (QLSSs) approximately prepare a quantum state ∣x⟩|\boldsymbol{x}\rangle∣x⟩ for which the amplitudes are proportional to the solution vector x\boldsymbol{x}x. Asymptotically optimal QLSSs have query complexity O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)), where κκκ is the condition number of AAA, and ε\varepsilonε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm ∥x∥\lVert\boldsymbol{x}\rVert∥x∥ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is (1+O(ε))κln⁡(22/ε)(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)(1+O(ε))κln(22​/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(log⁡log⁡(κ))O(\log\log(κ))O(loglog(κ)) applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal O(κlog⁡log⁡(κ)log⁡log⁡log⁡(κ)+κlog⁡(1/ε))O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))O(κloglog(κ)logloglog(κ)+κlog(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ)O(κ)O(κ) complexity can be achieved for norm estimation, yielding an optimal QLSS with O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of 56κ+1.05κln⁡(1/ε)+o(κ)56κ+1.05κ\ln(1/\varepsilon)+o(κ)56κ+1.05κln(1/ε)+o(κ) for the complexity of our optimal QLSS.