arXiv CSopen access

Optimal algorithmic complexity of inference in quantum kernel methods

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Optimal algorithmic complexity of inference in quantum kernel methods Elies Gil-Fuster,1, 2, ∗ Seongwook Shin,1, 3 Sofiene Jerbi,1, 4 Jens Eisert,1, 2, 4 and Maximilian J. Kramer1, †

arXiv:2604.15214v1 [quant-ph] 16 Apr 2026

Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany 2 Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany 3 Department of Quantum Information Science and Engineering, Sejong University, 209 Neungdong-ro, Gwangjin-gu, 05006, Seoul, Republic of Korea 4 Helmholtz-Zentrum Berlin für Materialien und Energie, 14109 Berlin, Germany (Dated: April 17, 2026)

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneckP is the cost of inference: evaluating a trained model on new data requires estimating N is the a weighted sum fα (x) = N i=1 αi k(x, xi ) of N kernel values to additive precision ε, where α ∈ R vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of 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 /ε), removing the dependence on N from the query count and yielding a quadratic improvement in both ∥α∥1 and ε. We prove a matching lower bound of Ω(∥α∥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. In particular, for realistic hardware constraints, a different strategy – combining quantum amplitude estimation with termby-term evaluation – can be preferable in terms of total gate count. Taken together, 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.

INTRODUCTION

It is difficult to overstate the importance of artificial intelligence in today’s world. Motivated by the observation that certain quantum algorithms achieve a computational advantage over classical algorithms for specific tasks, researchers have increasingly explored the potential for achieving quantum advantages in machine learning [BWP+ 17, SK19, CCC+ 19, AAA+ 20]. Quantum kernel methods [TKW26] are among the top candidates for quantum advantage in quantum machine learning (QML), as showcased in the milestone work of Ref. [LAT21]. Typical QML tasks involve a data domain X and a label co-domain Y, and the goal is to obtain a function f : X → Y which performs well under pre-specified metrics. The mainstream approach is based on embedding quantum kernels [Sch21, HWGF+ 22, GFED24], where a kernel function k is specified via an n-qubit quantum feature map x 7→ ρ(x), for x, x′ ∈ X , as k(x, x′ ) = Tr{ρ(x)ρ(x′ )}.

(1)

A crucial step in any kernel-based pipeline is related to training, i.e., finding suitable parameters α ∈ RN from a training set of size N . After training, one must evaluate the resulting hypothesis on new data – the inference step – which amounts to computing fα (x) =

N X

αi k(x, xi ).

(2)

i=1

Commonly used techniques [H+ 19, Sch21, HWGF+ 22, TKW26] estimate each of the N terms αi k(x, xi ) independently via PN 2 sampling-based amplitude estimation, resulting in a runtime of O(N ∥α∥2/ε2 ), with ∥α∥22 = i=1 αi2 . We refer to this approach as list-and-sum. This scaling can be improved along two independent axes: In the way how individual kernel values are estimated (sampling versus quantum amplitude estimation), and how the sum over training points is approximated (term-by-term versus via a single observable). We systematically investigate these choices in Section III and Appendix B. Ultimately, we show that in the

∗ [email protected] † [email protected]

How to approximate the sum: List-and-sum vs. all-at-once (Choice 1)

How to estimate expectation values: Sampling vs. quantum amplitude estimation (Choice 2)

Task: Estimate the kernel function fα(x) to additive precision ε for a given training dataset. List-and-sum via sampling

List-and-sum via quantum amplitude estimation

Training datapoints Training dataset Estimation via quantum amplitude estimation All-at-once via sampling

Estimation via sampling

All-at-once via quantum amplitude estimation

FIG. 1. Schematic overview of the four algorithmic strategies for inference in quantum kernel methods. The two axes correspond to the two independent design choices: how the sum over training points is approximated (list-and-sum versus all-at-once, vertical axis), and how individual expectation values are estimated (sampling versus quantum amplitude estimation, horizontal axis). In list-and-sum, each kernel value k(x, xi ) is estimated independently and the results are combined classically. In the all-at-once approach, the full inference sum is encoded as a single observable. Moving from sampling to quantum amplitude estimation yields a quadratic improvement in precision scaling within each row.

early fault-tolerant regime [EP25], the optimal combination – encoding the full sum as a single observable and applying quantum PN amplitude estimation – achieves a query complexity of O(∥α∥1/ε), where ∥α∥1 = i=1 |αi | (Theorem 9). We complement this with a matching lower bound of Ω(∥α∥1/ε), establishing optimality up to logarithmic factors (Corollary 11). Beyond query complexity, our results provide a practical guide to quantum kernel inference: given hardware capabilities, Algorithm 1 and Theorem 9 identify the appropriate strategy and its runtime, while Theorem 10 characterizes the corresponding gate complexity. We establish that the strategy yielding the lowest total gate count is list-and-sum with adaptive budget, via quantum amplitude estimation.

II. A.

PRELIMINARIES

Problem set-up and notation

To set the stage properly, we start by defining the problem set-up formally. Suppose we are given a learning task defined on X × Y, where a quantum kernel model has already been trained. We call the parameters of the kernel model α ∈ RN , where N is the size of the training set. We consider quantum feature maps realized via a data-dependent unitary U (x) applied to the all-0 state vector as |ψ(x)⟩ = U (x)|0⟩, with ρ(x) = |ψ(x)⟩⟨ψ(x)|. In this case, the kernel function becomes k(x, x′ ) = |⟨ψ(x)|ψ(x′ )⟩|2 for x, x′ ∈ X , and the inference task reduces to evaluating fα (x) :=

N X i=1

αi k(x, xi ) =

N X

αi |⟨0|U † (x)U (xi )|0⟩|2 .

(3)

i=1

Here, S = {(xi , yi )}N i=1 is a training set of size N , where the co-variates xi ∈ X are d-dimensional real vectors, and the labels yi can be either {±1} (in the case of binary classification) or real-valued (in the case of regression). For simplicity, we restrict our discussion to binary classification and regression; standard approaches beyond these have been discussed in, e.g., Ref. [SS02]. The vector α = (α1 , . . . , αN ) ∈ RN contains the trained parameters, with each αi being a weight assigned to a training point

3 xi . In the case of binary classification, one composes fα with a sign function to obtain hypotheses of the form gα = sign ◦ fα . Additionally, one can include a bias term b ∈ R, which we leave out for ease of presentation. We refer to N as the size of the training set for simplicity. In practice, sparsity is often imposed over the coefficients during training (e.g., via ℓ1 -regularization), so that N only includes the non-zero coefficients, sometimes dubbed support vectors. The number of support vectors can be significantly smaller than the size of the training set, though here we do not make any specific assumptions. We summarize the above in the following formal definition for the computational task of inference. N Definition 1 (Problem set-up). Let S = {(xi , yi )}N i=1 be a training set of size N ∈ N, with (xi , yi ) ∈ X × Y, let α = (αi )i=1 ∈ N R be a vector of trained parameters, let U (x) be an input-dependent unitary quantum-feature-map involving G-many gates from a fixed gate set, with U (x)|0⟩ = |ψ(x)⟩, and let ε > 0 be a precision parameter. The goal is to provide a quantum algorithm which, for any new input x, evaluates the kernel function fα (x) in Eq. (3) to additive precision ε.

Definition 2 (Norms). We use the notation ∥x∥p :=

N X |xi |p

!1/p (4)

i=1

for p ∈ {2/3, 1, 2}, although it is not a norm for 0 < p < 1 as it does not fulfill the triangle inequality. For a Hermitian operator M with eigenvalues {λi }i , we use ∥M∥∞ = maxi |λi | and refer to it as the operator norm. Definition 3 (Short-hand notation). We separate the coefficient vector into three parts: (1) its norm ∥α∥1 , (2) a probability |αi |/∥α∥1 , and (3) a vector of signs s = (s )N , with s = sign(α ). With this, we can distribution p = (pi )N i i=1 i i i=1 with pi = re-write Eq. (2) as fα (x) = ∥α∥1

N X

pi si k(x, xi ) = ∥α∥1 Ei∼p [si k(x, xi )].

(5)

i=1

Accounting for the positive and negative terms in the sum, we introduce the intermediate variables f± ∈ [0, 1] as f± :=

N X i=1

δsi ,±1 pi k(x, xi ) ≡

N 1 X δs ,±1 |αi |k(x, xi ). ∥α∥1 i=1 i

(6)

We can re-write Eq. (2) in terms of these normalized quantities as fα (x) = ∥α∥1 (f+ − f− ). Below, we define the oracle access model used throughout the work and specify the associated gate costs per query. Definition 4 (Access model with associated gate costs). To tackle the goal from Definition 1, we assume the following quantum oracle access model: • Single-input oracle U (x): given any input x and an n-qubit register, we can implement U (x), U † (x), and controlled versions thereof, with an associate cost of G-many gates. • Coefficient quantum-state oracle W (α): Given a (⌈log2 (N )⌉ + 1)-qubit register, prepare a quantum state encoding the PN √ coefficients as amplitudes |α⟩ = i=1 pi |i⟩ ⊗ |si ⟩, with pi and si as in Definition 3, and si encoding the sign of the ith coefficient as an eigenstate of the Z operator as Z|si ⟩ = si |si ⟩. The associated cost per query in terms of gates is N . We consider the following classical oracles to access the coefficient vector α: Reading oracle OR (α, i), read the ith element αi ; Norm oracle ON (α), compute the norm ∥α∥1 ; and Sampling oracle OC (α), sample an index i with probability pi (that is, proportional to the magnitude of the coefficients). In Section III B, we measure algorithmic cost by the total number of quantum oracle queries, which include the single-input oracle U (x) and the coefficient quantum-state oracle W (α). Below, we provide explicit circuit constructions that confirm that the runtime of our algorithms is indeed dominated by the quantum oracle queries. We note that the gate cost per query varies across algorithms, yet in a way that is mostly independent of ε and ∥α∥1 , and hence it does not affect the asymptotic comparisons in runtime and query complexity we perform in this work. We comment on resource estimates in terms of gates in Section III C. The access model we propose in Definition 4 not only allows us to perform a formal analysis of query complexity, but it also accurately reflects realistic implementations. The oracles we introduce can be directly instantiated on hardware, and they do not require any special computational power, nor do they hide exponential overheads. Still, we assume black-box access to U (x) and W (α) to remove the possibility of optimized implementations which would exploit the structure of the circuits involved. This is a conscious design choice, as it is our goal to focus on the fundamental complexity of the computational task, which in turn provides worst-case guarantees applicable to any specific quantum feature map. As is common in query complexity studies, nothing prevents more-efficient procedures to exist under the assumption that U (x) is of a particular known form.

4 B.

Amplitude estimation toolbox

The problem in Definition 1 can be viewed as an instance of amplitude estimation. In this section, we introduce the formal background of the amplitude estimation problem and discuss computational approaches for solving it, which we later relate to the task defined in Definition 1. Our presentation of amplitude estimation closely follows that of Ref. [TW25]. We start by defining the amplitude estimation problem. Definition 5 (Amplitude estimation problem). Let V ∈ Cd×d be a unitary such that p V |0⟩ = a |ψgood ⟩ |0⟩ + 1 − a2 |ψbad ⟩ |1⟩ ,

(7)

where |ψgood ⟩ and |ψbad ⟩ are normalized quantum state vectors, and a ∈ [0, 1]. Given access to V and V † , the task is to output an estimate â such that a − ε < â < a + ε with probability at least 2/3. Below we outline two approaches for solving this task. We start by describing a naive classical sampling approach yielding a O(ε−2 ) scaling and then explain the quantum version thereof, known as quantum amplitude estimation, which yields a O(ε−1 ) scaling for estimating a to additive precision ε.

Sampling-based amplitude estimation

In the classical setting, the amplitude a is not directly accessible; one can only sample from the distribution induced by measuring V |0⟩. Each measurement of the auxiliary register yields outcome |0⟩ with probability p = a2 , so estimating a reduces to estimating the Bernoulli parameter p and taking a square root. Theorem 1 (Sampling estimator: variance and concentration). Let X ∈ [0, 1] and let Y1 , . . . , YM be i.i.d. Bernoulli random PM variables with E[Yk ] = X. Define the estimator X̂ := k=1 Yk/M . Then the mean of the estimator fulfills E[X̂] = X and its variance Var(X̂) ≤ 1/4M . Further, for all ε > 0, the following tail bound holds P(|X̂ − X| ≥ ε) ≤ 2 exp(−2M ε2 ). In particular, to guarantee P(|X̂ − X| ≤ ε) ≥ 1 − δ, it suffices to choose M ∈ O(ε−2 log(δ −1 )). The proof is via standard Chernoff-based arguments, together with the facts that bounded random variables are sub-Gaussian, and that the observations Y1 , . . . , YM are indeed independent. p Corollary 2 (Estimation of amplitudes). Let a ∈ [0, 1] and define X = a2 . Let X̂ be as in Theorem 1, and define â := X̂. Then for a ∈ Ω(ε), the estimator â satisfies |â − a| ≤ ε with probability at least 1 − δ using, M ∈ O(ε−2 log(δ −1 )) samples.

Quantum amplitude estimation

Quantum amplitude amplification and quantum amplitude estimation, introduced by Brassard et al. [BHMT02], generalize the quadratic speedup achieved by Grover’s search algorithm [Gro96]. These techniques serve as fundamental building blocks in quantum algorithm design to speed-up certain subroutines. Theorem 3 (Quantum amplitude estimation [BHMT02, AR20]). Let a ∈ [0, 1] and V an nV -qubit unitary as in Definition 5. Given access to V and V † , there exists an estimator â such that for all ε > 0 and δ ∈ (0, 1), P(|â − a| ≥ ε) ≤ δ, using M ∈ O(ε−1 log(δ −1 )) applications of V and V † . More precisely, there exists a constant C > 0 such that P(|â − a| ≥ ε) ≤ 2 exp(−CM ε) for all a ∈ Ω(ε). The procedure from Ref. [AR20] uses nV + 1 qubits, and the total number of gates is O(M (GV + nV )), where GV is the number of gates necessary to implement V or V † . Remark The concentration bound in Theorem 3 implies that the estimator behaves as if it had variance of order 1/M 2 , in contrast to the 1/M variance of sampling-based amplitude estimation from Theorem 1. Aaronson and Rall [AR20] provide constructions for quantum amplitude estimation without using quantum phase estimation or controlled applications of V (which was required in Ref. [BHMT02]). Their analysis assumes a = Ω(ε), ensuring the estimation problem is non-trivial: in this regime, additive error ε corresponds to constant relative error. The work [TW25] argues that related techniques can be extended to regimes where a is comparable to or smaller than ε. Finally, the query complexity of Theorem 3 is optimal up to constant factors. Theorem 4 (Optimality of quantum amplitude estimation [NW99]). Any quantum algorithm that estimates a to additive error ε with constant success probability requires Ω(ε−1 ) applications of V and V † .

5 Theorem 4 follows from lower bounds for quantum counting [NW99], which reduce to phase estimation lower bounds. Refinements and extensions to arbitrary success probabilities can be found in Refs. [Lin23, MdW23]. In particular, the dependence on the failure probability δ is also tight [MdW23]. It has been recently proven in Refs. [TW25, TWZ25] that the quadratic speedup for quantum amplitude estimation requires access to the inverses. Theorem 5 (Amplitude estimation requires inverse access [TW25]). Suppose we have only access to the unitary V ∈ Cd×d from above and no access to the inverse, then any algorithm for amplitude estimation must use Ω(min(d, ε−2 )) applications of V.

Related work on quantum kernel methods

While the approach taken here is original and new, it builds on a number of previous works. The naive approach to inference, which we call list-and-sum (fixed budget) below, has already been lined out in foundational works like [H+ 19, SK19], and re-instated countless times, e.g., in Refs. [Sch21, LAT21, HWGF+ 22, GGC+ 24, TKW26]. These references elucidate the two main approaches to estimate the kernel function k(x, x′ ) on a quantum computer: either using the inverse U † (x′ ), or employing the SWAP test [NC00]. To the best of our knowledge, a formal runtime analysis of the naive approach had not been performed before, and we provide it in Theorem 9 in terms of query complexity and Theorem 10 in terms of gates, with further details in Appendix B. Previous works have also characterized the complexity of the training phase of quantum kernel methods. As the training step involves inverting a matrix, this was one of the first applications of the HHL algorithm [HHL09], called quantum support vector machine (qSVM) [RML14]. Recent efforts have further characterized the runtime of training quantum kernels on near-term devices [GTSW24]. The milestone work [LAT21] established a learning separation, proving that quantum kernel methods can learn to evaluate functions outside of P/poly under standard cryptographic assumptions. In this work, we study the complexity of inference in the oracle query model, where we do not assume any structure on the quantum feature map. Beyond this black-box setting, existing works have studied reducing inference cost via surrogates, either classically [SEM23, LTD+ 22, SRJ+ 23, SBS+ 25], exploiting the random Fourier features technique [RR07]; or quantumly [NMM+ 24], also using variants of shadow tomography [Aar18, HSK23, KGKB25]. Surrogates can reduce inference cost in restricted scenarios, but cannot work in the general setting we consider (Definitions 1 and 4).

Related work from signal processing

The approach taken here and the ideas we develop have some resemblance with notions of classical sensing, recovery and parameter-estimation in general and similar trade-offs of term-by-term estimation and global strategies exist. Say, if one is PN aiming at recovering unknown vectors x from estimating fα (x) = i=1 αi xi , this can be done with different sensing vectors α. A collection of such measurements are collected in a vector y(x) = Ax, featuring a matrix A. Then similar trade-offs exist. If x is s-sparse but one measures term-by-term, one arrives at a query complexity of O(N ). However, if one can perform coherent measurements and A satisfies the technical condition of the restricted isometry property, then x can be recovered in an all-at-once way from O(s log N ) many coherent measurements, making use of techniques of compressed sensing [EK12]. This perspective is also closely related to basis optimization techniques in quantum chemistry, as it is also made use of in quantum computing ansatzes [RBM18, LC19]. Electronic structure Hamiltonians are specified by a quartic tensor ha,b,c,d , whose complexity can be dramatically reduced by an appropriate choice of orbital basis. Under unitary mode transformations, linearly transforming one set of annihilation operators to another, the tensor may admit low-rank or factorized representations, such as those arising in tensor hypercontraction or density fitting. Conceptually, this mirrors the role of sparsifying bases in compressed sensing and again, similar trade-offs become relevant.

III.

RESULTS

As alluded to in the introduction, we start from the naive approach and propose several improvements thereof. We highlight PN two algorithmic choices to make: one regarding how the target quantity fα (x) = i=1 αi k(x, xi ) (or parts thereof) is estimated, and the other regarding how the sum is approximated. In particular, we consider the following possibilities: √

1. How to estimate expectation values: either via sampling (see Theorem 1), yielding precision O(1/ M ) from M shots, or via quantum amplitude estimation (see Theorem 3), yielding precision O(1/M ) from M coherent queries.

6 Repeat for each i ∈ {1, . . . , N } U † (xi )

n qubits ⌈log2 N ⌉ qubits |0⟩flag

n qubits =

i |0⟩flag

⌈log2 N ⌉ qubits

O† (S)

i=1 U

†

(xi )data ⊗ |i⟩⟨i|idx

FIG. 2. Realizing the “training-set oracle” O† (S) in Definition 6, as N controlled calls to the inverse of the single-input oracle U (x), one for each input in the training set xi ∈ S. The associated gate cost is O(N (G + log(N ))). This construction resembles ideas in the linear combination of unitaries (LCU) framework [CW12].

2. How to approximate the sum: the naive option is to list-and-sum, i.e., estimate each term independently and add the results classically, either with a fixed budget for each term or following an adaptive budget scheme. Alternatively, all terms can be grouped into a single all-at-once observable M. These algorithmic choices are illustrated schematically in Figure 1 to provide an intuitive overview. A priori it could be unclear whether such an all-at-once observable exists, or whether it can be efficiently implemented. We address this first in Section III A. A unified algorithm and a theorem describing the runtime complexities follows in Section III B. We comment on resource estimates in Section III C and end by providing a matching query-complexity lower bound in Section III D. A.

Existence and implementation of an all-at-once observable

Instead of estimating each kernel term individually, we reinterpret the weighted sum as a single expectation value by embedding the coefficients into a quantum state. This allows us to evaluate the entire inference expression in one coherent procedure, rather than aggregating many separate estimates. We show that the full inference sum fα (x) can be cast as the expectation value of a single observable, rather than estimating each kernel value separately. Similar versions of the following results can be found in, e.g., Refs. [NMM+ 24, GFEBP24, GFGPSD25], though not as formal statements. We start by introducing another quantum oracle that can be constructed from those in our access model. Definition 6 (Training-set oracle O† (S)). Let S = {(xi , yi )}N i=1 be the training set. Given two registers, an n-qubit “data” register and a ⌈log2 (N )⌉-qubit “index” register, which indexes each element i ∈ {1, . . . , N }, we call training-set oracle O† (S) O† (S) :=

N Y

U † (xi )data ⊗ |i⟩⟨i|idx .

(8)

i=1

We note that this construction does not require quantum random-access memory (QRAM). The training inputs {xi } are classically known and fixed after training, so the controlled unitaries can be compiled into a circuit offline. The O(N ) gate cost per query is inherent to any procedure – classical or quantum – that must touch all N training points. Lemma 6 (Query complexity training-set-oracle). The training-set oracle can be realized with N controlled queries to the single-input oracle U (xi ). The associated gate cost is O(N (G + log(N ))), and the procedure uses one extra qubit. Proof. See Fig. 2 for a visual proof. The associated gate cost is, for each i ∈ {1, . . . , N }: O(log(N )) gates to perform a multi-controlled bitflip on the flag register conditioned on the index being i, O(G) to call the controlled version of the G gates in U (xi ), and O(log(N )) to uncompute the flag bitflip, for a total of O(G + log(N )). Since these must be repeated N times, the total gate cost of the training-set oracle is O(N (G + log(N ))). We consider the training-set oracle O† (S) as another quantum oracle in the sense of Definition 4. Theorem 7 (All-at-once observable). Consider the problem set-up from Definition 1. There exists a bounded Hermitian observable M(α, S), with ∥M(α, S)∥∞ ≤ ∥α∥1 , and a quantum state vector |ϕ(x)⟩, such that ⟨ϕ(x)|M(α, S)|ϕ(x)⟩ = fα (x).

(9)

Moreover, this expectation value can be implemented using n + ⌈log2 N ⌉ + 2 qubits and O(N (G + log N )) gates. PN Proof sketch. Set M(α, S) = i=1 αi |ϕ(xi )⟩⟨ϕ(xi )| and verify directly. We give Figure 3 as visual proof, while full details and a rigorous argument are being presented in Appendix A.

7 f M(α,S) /∥α∥

n qubits: |0⟩data

U (x)

|ϕ(x)⟩

O† (S)

⌈log2 N ⌉ qubits: |0⟩idx

PN √

W (α)

i=1

|0⟩sign

pi |i⟩|si ⟩

|0⟩⟨0| PN √ pi U † (xi )|ϕ(x)⟩|i⟩|si ⟩ i=1 Z

f S) is the FIG. 3. Quantum circuit encoding the all-at-once observable as a single expectation value. The all-at-once observable M(α, collection of gates and fixed observables inside the box, up to a factor of ∥α∥1 . The intermediate-step formulas serve the purpose of illustrating the action of the gates onto the input state vector |ϕ(x)⟩. PN √ i=1

n-qubits: |0⟩data ⌈log2 N ⌉ qubits: |0⟩idx |0⟩sign

U (x)

|ϕ(x)⟩

W (α)

PN √ pi |i⟩|si ⟩ i=1

|0⟩QP,trash

pi U † (xi )|ϕ(x)⟩|i⟩|si ⟩|0, 0⟩ O† (S) √

√ f+ |ψ+ ⟩|0, 0⟩ + f− |ψ− ⟩|0, 1⟩ ′ + · · · (|ψtrash ⟩|1, 0⟩ + |ψtrash |1, 1⟩)

|0⟩QP, ± FIG. 4. Quantum circuit encoding the all-at-once observable as amplitudes. Explicit implementation of the unitary V described in Lemma 8.

The implementation follows the “adjoint” method (using U (x) and U † (x)), as opposed to the SWAP test; the main difference is a trade-off of depth versus width [Sch21, HWGF+ 22]. To perform quantum amplitude estimation, recall from Definition 5 that we must provide a unitary gate V such that p V |0⟩ = a|ψgood ⟩|0⟩ + 1 − a2 |ψbad ⟩|1⟩. (10) Here, a is the quantity we would like to estimate, and the precise form of |ψgood,bad ⟩ is not important, as long as we are able to PN implement V and V † multiple times. Our general strategy is to relate a to fα (x) = i=1 αi k(x, xi ). Following the short-hand notation from Definition 3, we use quantum amplitude estimation for f+ and f− independently, and then we reconstruct fα (x) from their difference. We provide a single unitary gate V which allows us to estimate both. Definition 7 (Amplitude-encoding unitary). Consider the problem set-up from Definition 1 and the notation from Definition 3. We the amplitude-encoding unitary V via its action: p p p ′ V |0⟩ = f+ |ψ+ ⟩|0, 0⟩ + f− |ψ− ⟩|0, 1⟩ + 1 − f+ − f− (|ψtrash ⟩|1, 0⟩ + |ψtrash ⟩|1, 1⟩) . (11) With this, specializing |ψgood ⟩ = |ψ± ⟩ and collecting the rest under |ψbad ⟩ for both f± becomes straightforward. We give a circuit depiction for how to construct V in Figure 4, further details can be found in Appendix A. Lemma 8 (Single-observable encoded in amplitude). Under the conditions of Theorem 7, there exists a quantum circuit using n + ⌈log2 (N )⌉ + 3 qubits which implements the amplitude-encoding unitary in Definition 7. Proof sketch. Refer to Figure 4 as visual proof, full details are in Appendix B 2 b.

Unified algorithm and runtime complexity

With the all-at-once observable in hand, the two algorithmic choices can be combined freely, giving rise to a landscape of algorithms summarized in Algorithm 1 (further details can be found in Appendix B). For each combination, we prove the resulting runtime complexity; the results are collected in terms of query complexity in Theorem 9 and in terms of gates in Theorem 10. Moreover, for completeness, we also analyze a sample-and-average strategy in Appendix C, which conceptually interpolates between list-and-sum and all-at-once. Its runtime matches the sampling-based approaches, but does not benefit from quantum amplitude estimation.

8 Algorithm 1 Unified inference for quantum kernel methods. Input: x ∈ X (new input), ε >P 0 (additive precision), trained coefficients α ∈ RN . Output: Estimate of fα (x) = N i=1 αi k(x, xi ) to ε additive precision. Choice 1: How to approximate the sum. (a) LIST- AND - SUM ( FIXED BUDGET ): estimate every k(x, xi ) with the same budget M . (b) LIST- AND - SUM ( ADAPTIVE BUDGET ): estimate k(x, xi ) with budget Mi . f S)|ϕ̃(x)⟩. (c) A LL - AT- ONCE: encode fα (x) as a single expectation value ⟨ϕ̃(x)|M(α, Choice 2: How to estimate expectation values. √ (I) S AMPLING: measure M times; precision O(1/ M ) per estimate. (II) Q UANTUM AMPLITUDE ESTIMATION: apply V, V † coherently M times; precision O(1/M ). 1: switch Choice 1: do 2: case (a) or (b) 3: for i ∈ {1, . . . , N } do 4: Reading oracle OR (α, i): obtain αi . 5: switch Choice 2: do 6: case (I) 7: Estimate k(x, xi ) using Mi shots: k̂(Mi ) (x, xi ). 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:

[Algorithms B.2 and B.4] [Algorithms B.3 and B.5] [Algorithms A.1 and B.8]

[Theorem 1] [Theorem 3]

▷ List-and-sum

▷ Sampling

case (II) ▷ Quantum amplitude estimation Estimate k(x, xi ) using Mi coherent queries: k̂(Mi ) (x, xi ). Compute αi k̂(Mi ) (x, xi ). end for P return fˆα (x) = N i=1 αi k̂(x, xi ). case (c) ▷ All-at-once switch Choice 2: do case (I) ▷ Sampling Implement all-at-once observable from Figure 3 (Algorithm A.1) and measure M times. (M ) return fˆα (x). case (II) ▷ Quantum amplitude estimation Consider the amplitude-encoding unitary V from Figure 4 (Algorithm B.7). √ √ Run quantum amplitude estimation on V to estimate f+ and f− each to precision O(1/M ). (2M ) return fˆα (x) = ∥α∥1 (fˆ+ − fˆ− ).

Theorem 9 (Query complexity of inference in quantum kernel methods). Consider Algorithm 1 and the problem set-up in Definition 1 for estimating the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability. The algorithmic runtime depends on the algorithmic choices as follows. (i) Choice 1(a) (list-and-sum, fixed budget): the algorithm requires ‡ N ∥α∥22 O via sampling [Corollary B.2], ε2 N ∥α∥2 via quantum amplitude estimation [Corollary B.4]. O ε (ii) Choice 1(b) (list-and-sum, adaptive budget): the algorithm requires ∥α∥21 O via sampling [Corollary B.3], ε2 ⋄ ∥α∥2/3 O via quantum amplitude estimation [Corollary B.5]. ε (iii) Choice 1(c) (all-at-once): the algorithm requires ∥α∥21 O via sampling [Theorem B.6], ε2 ⋆ ∥α∥1 O via quantum amplitude estimation [Theorem B.7]. ε

(12) (13)

(14) (15)

(16) (17)

9 We highlight list-and-sum with fixed budget via sampling (‡) as the naive approach, all-at-once via quantum amplitude estimation (⋆) as query-optimal, and list-and-sum with adaptive budget via quantum amplitude estimation (⋄) as gate-optimal (see Theorem 10). Proof. Each case follows from the corresponding statement in square brackets; the full proofs are given in Appendix B.

Resource estimates

In terms of runtime complexity, Theorem 9 dictates that the best algorithmic choice depends on the available hardware. On near-term devices without coherent multi-query access, using an adaptive budget for list-and-sum already yields the same runtime scaling as measuring the more-costly all-at-once observable. Conversely, the all-at-once approach is more beneficial in the early-fault-tolerant regime, where the runtime scaling is directly manifested by the 1-norm of the vector of coefficients, versus the 2/3-norm achieved by list-and-sum with an adaptive budget. Explicitly, within any case for Choice 1, quantum amplitude estimation yields a quadratic improvement over sampling. We expand beyond query-complexity analysis in Theorem 10, where we show the asymptotic scaling of the number of gates associated to each choice. Theorem 10 (Number of gates for inference in quantum kernel methods). Consider Algorithm 1 and the problem set-up in Definition 1 for estimating the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability. The scaling in the number of gates depends on the algorithmic choices as follows. (i) Choice 1(a) (list-and-sum, fixed budget): the algorithm requires GN ∥α∥22 O ε2

‡

GN ∥α∥2 O ε

gates via sampling,

gates via quantum amplitude estimation.

(18)

gates via quantum amplitude estimation.

(19)

(ii) Choice 1(b) (list-and-sum, adaptive budget): the algorithm requires O

G∥α∥21 ε2

gates via sampling,

G∥α∥2/3 ε

⋄

(iii) Choice 1(c) (all-at-once): the algorithm requires N G∥α∥21 Õ ε2

gates via sampling,

(N G + n)∥α∥1 Õ ε

⋆ gates via quantum amplitude estimation.

(20)

We highlight list-and-sum with fixed budget via sampling (‡) as the naive approach, all-at-once via quantum amplitude estimation (⋆) as query-optimal (see Theorem 9), and list-and-sum with adaptive budget via quantum amplitude estimation (⋄) as gate-optimal. Proof. We import the query complexity runtime results from Theorem 9 and then we must simply account for the differing gate costs of each oracle query. Our access model in Definition 4 specifies that the single-input oracle U (x) requires G gates, and the coefficient quantum-state oracle W (α) requires N gates. Further, we have shown how to construct the training-set oracle O† (S) using a number of gates in O(N (G + log(N )). Since the list-and-sum algorithms only use the single-input oracle, once for x and once for xi , their gate cost is 2G times the number of queries. Via sampling, this results in O(ε−2 GN ∥α∥22 ) gates with a fixed budget, and O(ε−2 G∥α∥21 ) with an adaptive budget. Via quantum amplitude estimation, the scaling in the number of gates is, in turn, O(ε−1 GN ∥α∥2 ) with a fixed budget and O(ε−1 G∥α∥2/3 ) with an adaptive budget. In the all-at-once approaches, the circuits used for sampling and quantum amplitude estimation are not identical, as seen when comparing Figures 3 and 4. Nevertheless, both circuits make the same number of oracle queries, visually: they contain f S) and each query to the unitary V both require one the same number and types of boxes. Namely, each measurement of M(α, call to the single-input oracle U (x), one call to the quantum-state oracle W (α), and one call to the training-set oracle O† (S). Implementing the unitary V requires one multi-controlled X gate, which has an associated cost of O(n) gates. For sampling, the gate costs per measurement add up to G + N + O(N (G + log(N )), which scales as O(N (G + log(N )). For quantum amplitude estimation, the extra multi-controlled gate results in a scaling of O(N (G + log(N )) + n). The total number of gates used in the all-at-once algorithms is, then, Õ(ε−2 N G∥α∥21 ) via sampling and Õ(ε−1 (N G + n)∥α∥1 ) via quantum amplitude estimation, where we have removed the logarithmic factors for simplicity.

10 Query-optimality versus gate-optimality. When comparing the naive and query-optimal approaches in Theorem 9, there is an N -factor speed-up in the query complexity, on top of the quadratic improvement over the norm of α and the precision ε. In terms of gates, as stated in Theorem 10, the same is no longer true: both list-and-sum with fixed budget and all-at-once have an N factor in their gate cost scaling. From the perspective of number of gates, it is not immediately clear anymore that all-at-once is better than list-and-sum with adaptive budget. In the case of sampling, list-and-sum with adaptive budget now has an N -factor improvement over all-at-once. In the case of quantum amplitude estimation, all-at-once has both an N and an n factor. Below, we make a principled comparison between the runtime scalings. Let us define GL := ε−1 G∥α∥2/3 and GA := ε−1 (N G + n)∥α∥1 the respective scaling of the numbers of gates. The subscript L stands for “list-and-sum”, and the subscript A stands for “all-at-once” in  ε−1 G∥α∥2/3 ∥α∥2/3 GL  √ := = , n n n −1 GA ε (N G+n)∥α∥1 (N + G )∥α∥1 √ N + GL . (21) =⇒ G ≤ G ≤ N + L A √  G G N ∥α∥ ≤ ∥α∥2 ≤ N ∥α∥ 1

We thus confirm that the required number of gates via all-at-once has worse scaling than that of list-and-sum with adaptive budget. Practical guidelines. As a guide to the eye for the practitioner, our results suggest the following guidelines for choosing an inference strategy: • Use all-at-once combined with quantum amplitude estimation when coherent multi-query access is available, as this achieves query-optimal scaling. • Use list-and-sum with adaptive budget combined with quantum amplitude estimation when gate cost dominates, as this minimizes the total number of gates. • Sampling-based approaches are primarily competitive in near-term regimes without coherent access, but are asymptotically suboptimal in precision.

Matching lower bound

The query complexity of the all-at-once via quantum amplitude estimation algorithm (cf. Algorithm B.8 and Theorem B.7) is optimal in V -queries up to constant factors in ε. Corollary 11 (Optimality of Algorithm B.8 in V -queries). Any algorithm that estimates fα (x) to additive precision ε with constant success probability using the amplitude-encoding unitary V from Definition 7 requires Ω(∥α∥1/ε) applications of V and V †. Proof. It suffices to consider the case N = 1 and α1 = ∥α∥1 . Then fα (x) = ∥α∥1 k(x, x1 ), so estimating fα (x) to additive ε error ε is equivalent to estimating k(x, x1 ) to additive error η = ∥α∥ . In the black-box access model of Definition 4, the unitary 1 p V prepares a state whose success amplitude is a = k(x, x1 ). Consider a hard family of instances where a ∈ [a0 , a0 + Θ(η)] for some constant a0 ∈ (0, 1), realizable in the black-box model via standard two-dimensional p state-preparation constructions. On this family, any estimator k̂ satisfying |k̂ − a2 | ≤ η induces an amplitude estimator â := max(k̂, 0) ∈ [0, 1] with |â − a| =

|â 2 − a2 | η ≤ = Θ(η), â + a a0

(22)

so precision η on a2 forces precision Θ(η) on a. By the quantum amplitude estimation lower bound (Theorem 4), this requires Ω η −1 applications of V and V † . Substituting η = ε/∥α∥1 yields Ω(∥α∥1/ε), as claimed. The reduction above shows that the single-training-point case already captures the full V -query complexity. Hence Algorithm B.8 is optimal in this model, since Theorem B.7 provides a matching upper bound with no dependence on N . Whether this lower bound extends to the full access model of Definition 4, where algorithms are not required to route all computation through V , remains open. Any improvement beyond this bound would require exploiting additional structure in the feature-map unitaries {U (xi )} beyond black-box access. Such structural access is excluded in the oracle model for any fixed N . Finally, quantum amplitude estimation is optimal for each individual kernel term: estimating k(x, xi ) to additive error εi requires Ω (1/εi ) applications of V and V † by the same hard-instance argument. Therefore, per-term estimation in list-and-sum strategies is also optimal, and any improvement must arise from changing how the sum is approximated.

11 IV.

DISCUSSION

In this work, we have scrutinized and revisited evaluation methods for inference in quantum kernel methods, which are among the top candidates to achieve quantum advantage in machine learning. Our results have practical implications for the long-term viability of quantum kernels versus other approaches in quantum machine learning (QML), and to the wider question of in what precise sense we can hope to see robust quantum advantages in quantum machine learning for classical data [EP25, LAT21, SSHE21, LLL+ 24, WJF+ 25, ZZN+ 26]. The cost of inference in kernel methods is usually cited as a critical flaw that could prevent scalability [NMM+ 24]. Our results show that the dependence on the training set size can be confined to the per-query gate cost, so that the number of oracle queries – and hence the scaling with precision – becomes independent of N . We show that 2 the query-complexity scaling of the naive approach O N ∥α∥2/ε2 can be improved down to O(∥α∥1/ε). By providing matching lower bounds, we showed that this improved scaling is optimal within our access model. Recent work has shown that using generic parametrized quantum circuits as feature maps results in so-called exponential kernel concentration [TWCH24], namely the phenomenon that the kernel function k becomes exponentially close to a Kronecker delta k(x, x′ ) ≈ δx,x′ . In such a situation, the quantities we estimate via quantum amplitude estimation become exponentially close to zero, which in turn violates the assumptions of the lower bounds for the query complexity we give in Section III D. However, the upper bound is unaffected: quantum amplitude estimation remains a valid procedure for any value of an amplitude, and the Õ(∥α∥1/ε) scaling continues to hold. The practical issue is different: when kernel values are exponentially small, the function fα (x) itself is exponentially close to zero for most inputs, so achieving any fixed precision ε is trivially easy – but the model has no predictive power. In other words, exponential concentration is not a problem for our algorithms but for the kernel itself. Our results are therefore most relevant for kernel functions whose values do not vanish asymptotically [LAT21, HBK+ 25], which are precisely the settings where quantum kernel methods are expected to be useful. One open question is whether our construction can be generalized to non-unitary quantum feature maps, leading to mixed quantum feature vectors ρ(x) in general. Our results confirm that using quantum amplitude estimation for the all-at-once observable is optimal in terms of query complexity. Taking into account hardware requirements for both noisy and early-fault-tolerant devices, it may well be that this approach is beyond budget. Accordingly, we provide a zoo of algorithms that nicely interpolate between the naive and optimal ones, and formally analyze their runtimes. As such, this work aims to constitute a useful handbook for practitioners. Indeed, we hope that our analysis clarifies some of the critical design choices involved in realistic implementations for the inference step in quantum kernel methods. Finally, an exciting open question is whether our improvements for inference can be extended to speed-up the training phase of quantum kernels. The usual pipeline in training kernel methods involves inverting an N × N matrix, and the end-to-end complexity is usually characterized as O(N 3 ). Anticipating potential paths to reduce the cost, one could take Eq. (3) without assuming that the parameters α have already been trained, and instead define a loss function with respect to those parameters. Then, one option would be to perform (stochastic) gradient descent [SSBD14] on those parameters. Gradient-based optimization of kernel methods has been considered also in classical machine learning [SS02], mostly as a proof technique, and it comes with performance guarantees owing to the fact that usual regularized loss functions are convex with respect to α [SS02]. The representer theorem [Sch21, SS02] further states that the optimal choice of α actually corresponds to the best possible linear function in terms of fitting the training set. Beyond straightforward gradient-based optimization, one could consider more advanced forms of quantum optimization [LHLW23, CSW25], which in turn enjoy favorable performance guarantees for convex loss functions.

Acknowledgements

This work has been inspired by conversations with Tom O’Brien of Google Quantum AI. The authors thank Carlos BravoPrieto, Vedran Dunjko, Tom O’Brien, Louis Schatzki and Franz Schreiber for useful references and comments in an earlier version of this manuscript. E. G.-F. is a recipient of the 2023 Google PhD Fellowship. Moreover, the authors acknowledge support by the BMFTR (PraktiQOM, QuSol, HYBRID++), the Quantum Flagship (Millenion, PasQuans2), the DFG (SPP 2514, CRC 183), the Munich Quantum Valley, Berlin Quantum, the Clusters of Excellence (MATH+, ML4Q), and the European Research Council (DebuQC).

[AAA+ 20] Giovanni Acampora, Andris Ambainis, Natalia Ares, Leonardo Banchi, Pallavi Bhardwaj, Daniele Binosi, G. Andrew D. Briggs, Tommaso Calarco, Vedran Dunjko, Jens Eisert, Olivier Ezratty, Paul Erker, Federico Fedele, Elies Gil-Fuster, Martin Gärttner, Mats Granath, Markus Heyl, Iordanis Kerenidis, Matthias Klusch, Anton Frisk Kockum, Richard Kueng, Mario Krenn, Jörg Lässig, Antonio Macaluso, Sabrina Maniscalco, Florian Marquardt, Kristel Michielsen, Gorka Muñoz-Gil, Daniel Müssig, Hendrik Poulsen Nautrup, Sophie A. Neubauer, Evert van Nieuwenburg, Roman Orus, Jörg Schmiedmayer, Markus Schmitt, Philipp Slusallek, Filippo Vicentini,

12 Christof Weitenberg, and Frank K. Wilhelm. Quantum computing and artificial intelligence: status and perspectives. arXiv preprint arXiv:2505.23860, 2020. [Aar18] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 325–338, 2018. [AR20] Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified, page 24–32. Society for Industrial and Applied Mathematics, 2020. [BHMT02] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Information, page 53–74, 2002. [BWP+ 17] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549:195–202, 2017. [CCC+ 19] Giuseppe Carleo, J. Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria Schuld, Naftali Tishby, Leslie Vogt-Maranto, and Lenka Zdeborová. Machine learning and the physical sciences. Rev. Mod. Phys., 91:045002, 2019. [CSW25] Ahmet Burak Catli, Sophia Simon, and Nathan Wiebe. Exponentially better bounds for quantum optimization via dynamical simulation. arXiv preprint arXiv:2502.04285, 2025. [CW12] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12:901–924, 2012. [EK12] Yonina C. Eldar and Gitta Kutyniok. Compressed sensing: theory and applications. Cambridge University Press, 2012. [EP25] Jens Eisert and John Preskill. Mind the gaps: The fraught road to quantum advantage. arXiv preprint arXiv:2510.19928, 2025. [GFEBP24] Elies Gil-Fuster, Jens Eisert, and Carlos Bravo-Prieto. Understanding quantum machine learning also requires rethinking generalization. Nat. Comm., 15:1–12, 2024. [GFED24] Elies Gil-Fuster, Jens Eisert, and Vedran Dunjko. On the expressivity of embedding quantum kernels. Machine Learning: Science and Technology, 5:025003, 2024. [GFGPSD25] Elies Gil-Fuster, Casper Gyurik, Adrian Perez-Salinas, and Vedran Dunjko. On the relation between trainability and dequantization of variational quantum learning models. In The Thirteenth International Conference on Learning Representations, 2025. [GGC+ 24] Jennifer R. Glick, Tanvi P. Gujarati, Antonio D. Corcoles, Youngseok Kim, Abhinav Kandala, Jay M. Gambetta, and Kristan Temme. Covariant quantum kernels for data with group structure. Nature Physics, 20:479–483, 2024. [Gro96] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery. [GTSW24] Gian Gentinetta, Arne Thomsen, David Sutter, and Stefan Woerner. The complexity of quantum support vector machines. Quantum, 8:1225, 2024. [H+ 19] Vojtech Havlı́ček et al. Supervised learning with quantum-enhanced feature spaces. Nature, 567:209–212, 2019. [HBK+ 25] Laura J. Henderson, Kerstin Beer, Salini Karuvade, Riddhi Gupta, Angela White, and Sally Shrapnel. Quantum advantage without exponential concentration: Trainable kernels for symmetry-structured data. arXiv preprint arXiv:2509.14337, 2025. [HHL09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103:150502, 2009. [HSK23] Tobias Haug, Chris N. Self, and Myungshik S. Kim. Quantum machine learning of large datasets using randomized measurements. Machine Learning: Science and Technology, 4:015005, 2023. [HWGF+ 22] Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan H. S. Derks, Paul K. Faehrmann, and Johannes Jakob Meyer. Training quantum embedding kernels on near-term quantum computers. Phys. Rev. A, 106:04243, 2022. [KGKB25] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush. Triply efficient shadow tomography. PRX Quantum, 6, 2025. [LAT21] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Phys., 17:1013–1017, 2021. [LC19] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. [LHLW23] Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu. Quantum Hamiltonian descent. arXiv preprint arXiv:2303.01471, 2023. [Lin23] Yao-Ting Lin. A note on quantum phase estimation. arXiv preprint arXiv:2304.02241, 2023. [LLL+ 24] Junyu Liu, Minzhao Liu, Jin-Peng Liu, Ziyu Ye, Yunfei Wang, Yuri Alexeev, Jens Eisert, and Liang Jiang. Towards provably efficient quantum algorithms for large-scale machine-learning models. Nature Comm., 15:434, 2024. [LTD+ 22] Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and Elham Kashefi. Classically approximating variational quantum machine learning with random Fourier features. arXiv preprint arXiv:2210.13200, 2022. [MdW23] Nikhil S. Mande and Ronald de Wolf. Tight bounds for quantum phase estimation and related problems. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 81:1–81:16, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [NC00] Michael A. Nielsen and Isaac L. Chuang. Quantum information and quantum computation. Cambridge University Press Cambridge, 2000. [NMM+ 24] Akimoto Nakayama, Hayata Morisaki, Kosuke Mitarai, Hiroshi Ueda, and Keisuke Fujii. Explicit quantum surrogates for quantum kernel models. arXiv preprint arXiv:2408.03000, 2024. [NW99] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, page 384–393, New York, NY, USA, 1999. Association for Computing Machinery. [RBM18] Nicholas C. Rubin, Ryan Babbush, and Jarrod McClean. Application of fermionic marginal constraints to hybrid quantum algorithms. New Journal of Physics, 20(5):053020, May 2018. [RML14] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Phys. Rev. Lett., 113:130503, 2014.

13 [RR07] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Adv. Neur. Inf. Proc. Sys., volume 20, 2007. [SBS+ 25] Mehrad Sahebi, Alice Barthe, Yudai Suzuki, Zoë Holmes, and Michele Grossi. On dequantization of supervised quantum machine learning via random Fourier features. arXiv preprint arXiv:2505.15902, 2025. [Sch21] Maria Schuld. Quantum machine learning models are kernel methods. arXiv preprint arXiv:2101.11020, 2021. [SEM23] Franz J. Schreiber, Jens Eisert, and Johannes Jakob Meyer. Classical surrogates for quantum learning models. Phys. Rev. Lett., 131:100803, 2023. [SK19] Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Phys. Rev. Lett., 122 4:040504, 2019. [SRJ+ 23] Ryan Sweke, Eric Recio, Sofiene Jerbi, Elies Gil-Fuster, Bryce Fuller, Jens Eisert, and Johannes J. Meyer. Potential and limitations of random Fourier features for dequantizing quantum machine learning. arXiv preprint arXiv:2309.11647, 2023. [SS02] Bernhard Schölkopf and Alexander J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive computation and machine learning. MIT Press, 2002. [SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. [SSHE21] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert. On the quantum versus classical learnability of discrete distributions. Quantum, 5:417, 2021. [TKW26] John Tanner, Chon-Fai Kam, and Jingbo Wang. Non-variational supervised quantum kernel methods: a review. arXiv preprint arXiv:2604.07896, 2026. [TW25] Ewin Tang and John Wright. Amplitude amplification and estimation require inverses. arXiv preprint arXiv:2507.23787, 2025. [TWCH24] Supanut Thanasilp, Samson Wang, Marco Cerezo, and Zoë Holmes. Exponential concentration in quantum kernel methods. Nature Comm., 15:5200, 2024. [TWZ25] Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help. arXiv preprint arXiv:2510.07622, 2025. [WJF+ 25] Yunfei Wang, Ruoxi Jiang, Yingda Fan, Xiaowei Jia, Jens Eisert, Junyu Liu, and Jin-Peng Liu. Towards efficient quantum algorithms for diffusion probability models. arXiv preprint arXiv:2502.14252, 2025. [ZZN+ 26] Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod R. McClean, and Hsin-Yuan Huang. Exponential quantum advantage in processing massive classical data. arXiv preprint arXiv:2604.07639, 2026.

Supplementary Material for “Optimal query complexity for inference in quantum kernel methods” Appendix A: Existence and implementation of an all-at-once observable

Theorem 7 (Single-observable representation). Consider the problem set-up from Definition 1, in particular the task of estimating the kernel function in Eq. (3). Then, there exists a bounded Hermitian observable M(α, S), with ∥M(α, S)∥∞ ≤ ∥α∥1 , and a quantum state |ϕ(x)⟩, such that E|ϕ(x)⟩ [M(α, S)] = ⟨ϕ(x)|M(α, S)|ϕ(x)⟩ =

N X

αi k(x, xi ) =: fα (x).

(A1)

i=1

Proof. A simple calculation confirms that it is sufficient to set M(α, S) = ⟨ϕ(x)|M(α, S)|ϕ(x)⟩ = ⟨ϕ(x)|

N X

i=1 αi |ϕ(xi )⟩⟨ϕ(xi )|, since

! αi |ϕ(xi )⟩⟨ϕ(xi )| |ϕ(x)⟩ =

i=1

N X

αi ⟨ϕ(x)|ϕ(xi )⟩⟨ϕ(xi )|ϕ(x)⟩

(A2)

i=1

αi k(x, xi ) = fα (x).

i=1

The operator norm of the observable ∥M(α, S)∥∞ =

N X

αi |ϕ(xi )⟩⟨ϕ(xi )|

i=1

≤ ∞

N X i=1

∥αi |ϕ(xi )⟩⟨ϕ(xi )|∥∞ =

N X

|αi | = ∥α∥1

(A3)

i=1

results from the triangle inequality. Theorem 7 confirms that, in principle, the inference step in kernel methods, i.e., estimating fα (x) for a data input x, can be achieved via a single expectation value, instead of taking a different expectation value for each element in the training set and then summing the results, each weighted by the corresponding αi . As presented, it may be unclear how to estimate the expectation value of the given observable with respect to the quantum state on a quantum device. A direct approach may attempt to construct a unitary gate that maps the ith computational basis element |i⟩ into the quantum feature vector |ϕ(xi )⟩, for i ∈ {1, . . . , N }. Such a transformation may be costly to obtain just from having access to the state-preparation unitary gate U (x). We next present Algorithm A.1, which can be used to implement the all-at-once observable using a few auxiliary qubits. We spell out each oracle call separately to reflect the sequential circuit structure. Note that Algorithm A.1 follows the “adjoint” method to estimate the kernel function (using U (x) and its inverse U † (x)), as opposed to the SWAP test. This is an arbitrary choice, and the main difference between the two approaches is a trade-off of depth versus width [HWGF+ 22, Sch21]. In the adjoint method, the depth of the circuit is at least twice the depth of U (x). In the SWAP method, the number of qubits in the circuit is at least twice the number of qubits U (x) acts on. Algorithm A.1 Single-observable sampling. Input: x ∈ X ▷ New input. P Output: fα (x) = N ▷ Inference, Eq. (3). i=1 αi k(x, xi ) 1: Initialize |0⟩data |0⟩idx |0⟩sign . ▷ n + ⌈log2 (N )⌉ + 1 qubits. 2: Single-input oracle U (x)data : |ϕ̃(x)⟩ = |ϕ(x)⟩data |0⟩idx |0⟩sign ▷ G gates. PN √ pi |ϕ(x)⟩data |i⟩idx |si ⟩sign ▷ N gates. 3: Quantum-state coefficient oracle W (α)idx,sign : |ϕ(x)⟩data |0⟩idx |0⟩sign 7→ i=1 PN √ P √ 4: Training-set oracle O † (S): pi |ϕ(x)⟩data |i⟩idx |si ⟩sign 7→ N pi U † (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign ▷ O(N (G + log N )) gates. i=1 i=1 5: Norm coefficient oracle ON (α): ∥α∥1 . 6: return Expectation value of observable: ∥α∥1 |0⟩⟨0|data ⊗ Iidx ⊗ Zsign ▷ Total number of gates O(N (G + log N ))

Lemma A.1 (Single-observable implementation). Under the conditions of Theorem 7, there exists a quantum circuit with n + ⌈log2 (N )⌉ + 2 qubits and O(N (G + log N )) gates which implements M(α, S), as specified in Algorithm A.1. The algorithm makes one call to each of the following oracles: single-input oracle, training-set oracle, norm coefficient oracle, and quantumf S) fulfilling state coefficient oracle. This algorithm involves measuring the expectation value of an auxiliary observable M(α, f ∥M(α, S)∥∞ = ∥α∥1 .

15 Proof. We prove the statement directly by providing a construction. Consider three registers: an n-qubit “data” register Hdata and an N -dimensional “index” register Hidx (equivalently, a ⌈log2 (N )⌉-qubit register), and a 1-qubit “sign” register. Recall the notation αi = ∥α∥1 si pi , where si = sign αi and pi = |αi |/∥α∥1 . Calling the single-input oracle on the data register, we obtain the quantum state vector U (x)|0⟩data |0⟩idx,sign 7→ |ϕ(x)⟩data |0⟩idx,sign . We refer to this state vector as |ϕ̃(x)⟩data,idx,sign . f S)|ϕ̃(x)⟩. It then follows that ⟨ϕ̃(x)|M(α,

(A4)

f S) which fulfills fα (x) = We next introduce an observable M(α,

f S)|ϕ̃(x)⟩ = ⟨ϕ(x)|M(α, S)|ϕ(x)⟩, ⟨ϕ̃(x)|M(α,

(A5)

where M(α, S) is the observable defined in Theorem 7, and the r.h.s. expectation value is defined solely on the data register. To specify M(α, S), we make use of three oracle calls, namely to the quantum-state coefficient oracle W (α), the training-set oracle O† (S), and the norm coefficient oracle ON (α). With these, it is sufficient to set f S) = ∥α∥1 O† (S)data,idx · W (α)idx,sign † (|0⟩⟨0|data ⊗ Iidx ⊗ Zsign ) O† (S)data,idx · W (α)idx,sign . M(α, (A6) Intuitively, we recognized that the weighted sum over α can be instantiated using a construction reminiscent of the linear combination of unitaries (LCU) framework [CW12]. The extra sign register allows us to flexibly combine both positive and f S)|ϕ̃(x)⟩ = fα (x). For clarity, as depicted in Fig. 3, instead of keeping the negative coefficients. We show that ⟨ϕ̃(x)|M(α, f Heisenberg picture of M(α, S), we apply the unitary gates W (α) and O† (S) on the quantum state, one at a time, !! N X √ † † O (S)data,idx · W (α)idx,sign |ϕ̃(x)⟩ = O (S)data,idx |ϕ(x)⟩data ⊗ pi |i⟩idx |si ⟩sign (A7) i=1

  N X = U † (xj )data ⊗ |j⟩⟨j|idx  |ϕ(x)⟩data ⊗ j=1

N X

√

!! pi |i⟩idx |si ⟩sign

i=1



i,j=1

N X √



  pi U † (xj )|ϕ(x)⟩data ⊗ |j⟩idx ⟨j|i⟩ ⊗ |si ⟩sign |{z} δi,j

pi U † (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign .

i=1

We consider the expectation value of the fixed observable ∥α∥1 (|0⟩⟨0|data ⊗ Iidx ⊗ Zsign ) with respect to this quantum state, to get   !† N N X X √ √ pi U † (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign ∥α∥1 (|0⟩⟨0|data ⊗ Iidx ⊗ Zsign )  pj U † (xj )|ϕ(x)⟩data |j⟩idx |sj ⟩sign  i=1

j=1

= ∥α∥1

N X i,j=1

√

N X

pi pj ⟨ϕ(x)| U (xi )|0⟩⟨0|U † (xj )|ϕ(x)⟩ ⟨i|I|j⟩⟨si | Z|sj ⟩ = si ∥α∥1 pi |⟨ϕ(x)|ϕ(xi )⟩|2 | {z }| {z } | {z } | {z } i=1 | {z } |ϕ(xi )⟩

⟨ϕ(xj )|

δi,j

|αi |

sj |sj ⟩

| =

N X

{z αi

}

αi k(x, xi ) = fα (x).

(A8)

i=1

f S). Making use of the invariance of norms under unitary transformations, the norm We next bound the operator norm of M(α, f S) is equal to the norm of M(α, f S)∥∞ = ∥∥α∥1 (|0⟩⟨0|data ⊗ Iidx ⊗ Zsign )∥ = ∥α∥1 ∥|0⟩⟨0|∥∞ ∥I∥∞ ∥Z∥∞ = ∥α∥1 ∥M(α, ∞

(A9)

of the fixed observable. We exploit the factoring of norms under the tensor product in the second line. Indeed, the Hermitian observable M(α, S) fulfills ∥M(α, S)∥∞ ≤ ∥α∥1 . These statements together prove Theorem 7.

16 Appendix B: A zoo of algorithms

Sampling Quantum amplitude estimation Section reference ‡ 2 List-and-sum fixed budget O [Corollary B.2] O N ∥α∥ [Sec. B 1] [Corollary B.4] ε ∥α∥ ⋄ 2 ∥α∥ 2/3 List-and-sum optimal query allocation O ε2 1 [Corollary B.3] O [Corollary B.5] [Sec. B 1] ε ⋆ 2 ∥α∥ 1 [Theorem B.7] All-at-once O ε2 1 [Theorem B.6] O ∥α∥ [Sec. B 2] ε

N ∥α∥2 2 ε2

TABLE B.1. Total cost required to ensure ε additive precision for each of the algorithms below. We highlight list-and-sum with fixed budget via sampling as the naive approach (‡), all-at-once via quantum amplitude estimation as query-optimal (⋆), and list-and-sum with adaptive budget via quantum amplitude estimation as gate-optimal (⋄).

In this appendix, we provide detailed analyses and proofs for each of the algorithmic combinations presented in Algorithm 1 and summarized in Theorem 9. For each combination of choices – how to approximate the sum (list-and-sum with fixed or adaptive budget, or all-at-once) and how to estimate expectation values (sampling or quantum amplitude estimation) – we state the corresponding algorithm, derive the optimal parameter choices where applicable, and prove the resulting runtime complexity. The results are collected in Table B.1. 1.

List-and-sum

We first provide a template for all list-and-sum theorems and algorithms, in Theorem B.1 and Algorithm B.1. We next specialize the template into the four possible choices. We collect these results in Table B.2. PN Theorem B.1 (List-and-sum algorithm template analysis). Let X1 , . . . , XN ∈ [0, 1] and X = i=1 αi Xi . Assume we have Mi -query independent estimators X̂i ∈ [0, 1] with EX̂ [X̂i ] = Xi and VarX̂ [X̂i ] ≤ c/Mir , for some constant c > 0 and for PN PN r ∈ {1, 2}. Define the M -query estimator X̂ = i=1 αi X̂i with M = i=1 Mi . Then, for any ε > 0, the following numbers of queries M are sufficient to ensure |X̂ − X| < ε with constant success probability: 2/r

1. With fixed budget Mi = M/N for all i ∈ {1, . . . , M }: M ∈ O(ε−2/r N ∥α∥2 ). 2/(r(r+1))

2/r

2. With optimal query allocation: Mi ∈ O(ε−2/r |αi |2/(r+1) ∥α∥2/(r+1) ), which in turn yields M ∈ O(ε−2/r ∥α∥2/(r+1) ). For any δ ∈ (0, 1), by a median-of-means amplification (repeating the estimator O(log(δ −1 )) times and taking the median), the failure probability can be reduced to δ without changing the ε-dependence of the query complexity. PN Proof. We prove this statement directly, leaving r ∈ {1, 2} free. We define Z := X̂ − X = i=1 αi (X̂i − Xi ) as the estimation-error random variable, and quickly note that its mean is EX̂ [Z] = 0. Also, we have X̂i − Xi ∈ [−1, 1] and αi (X̂i − Xi ) ∈ [−|αi |, |αi |]. From this boundedness, it follows that each αi (X̂i − Xi ) is a subgaussian random variable with 2 parameter σi2 ∼ αi/Mir . For completeness in the r = 2 case, we note that quantum amplitude estimation estimators are sub-exponential, rather than subgaussian. The concentration bound above is the variance-dominated regime of Bernstein’s inequality. A fully rigorous treatment requires checking the additional Bernstein condition ε · mini Mi / maxi |αi | ≳ log(1/δ), which for the optimal allocation reduces to a mild non-sparsity conditions on α. We use the variance-regime bound throughout as it yields the claimed asymptotic scaling. Under this consideration, the sum of independent subgaussian random variables is itself subgaussian, with parameters adding, PN 2 so Z is subgaussian with parameter σ 2 ∼ i=1 αi/Mir . From these, we can use a standard Chernoff tail bound 2 −ε . (B1) P[|Z| ≥ ε] ≤ 2 exp 2σ 2 For any δ ∈ (0, 1), we set 2 exp

−ε2 ≤ δ, 2σ 2 ε2 δ − 2 ≤ log , 2σ 2

(B2) (B3)

17 and, therefore, ε2 ≥ log 2σ 2

2 , δ ε2 . σ2 ≤ 2 log 2δ

(B4) (B5)

Together with the variances of the individual terms, we obtain N X α2

ε2 i . ≤ r Mi 2 log 2δ i=1

σ2 ∼

(B6)

In the simpler case of fixed budget Mi = M/N for all i, we directly obtain N X α2

N Nr X 2 ε2 N r ∥α∥22 i = ≤ α = Mir M r i=1 i Mr 2 log 2δ i=1 2/r

N ∥α∥2 M ∈O ε2/r

(B7)

! .

(B8)

To find the optimal query allocation (partly inspired by [RBM18]), we solve the optimization problem min M =

N X

Mi ,

(B9)

ε2 i . = r Mi 2 log 2δ i=1

(B10)

Mi ≥1

i=1 N X α2

s.t. The Lagrangian of the problem is L=

N X

N X α2

i r −C M i i=1

Mi + λ

i=1

(B11)

with C ∈ Θ(ε /log(δ−1 )). The first order condition yields ∂L αi2 = 0, = 1 − rλ r+1 ∂Mi Mi

(B12)

Mir+1 = rλαi2 ,

(B13)

1 2 (r+1)

Mi = rλαi

(B14)

Introducing this condition into the constraint, we obtain N X α2

N X αi2 i = r 2 r+1 Mir i=1 i=1 (rλαi )

i=1 |αi | r

Cr r+1

2 r+1

N X

1 r

(rλ) r+1 i=1

r 1− r+1 αi2 =

i=1 |αi |

(rλ) r+1

= λ r+1 ,

= C,

(B15) (B16)

P λ=

2 r+1

2 N r+1 i=1 |αi |

r+1 r

. r+1 rC r We can use the value of the multiplier λ to reach the final result given by 1   r+1 r+1 PN 2 r r+1   1 i=1 |αi | Mi = rλαi2 r+1 =  r αi2  r+1   rC r 2

|αi | r+1 = √ r C

N X 2 |αi | r+1 i=1

! r1

2 |αi | r+1 r(r+1) = √ ∥α∥ . 2 r r+1 C

(B17)

(B18)

18 Sampling (r = 1)

Quantum amplitude estimation (r = 2) −2 2 Fixed budget M ∈ O ε N ∥α∥2 M ∈O ε−1 N ∥α∥2 1/3 2 M ∈ O ε−2 |αi |∥α∥1 Mi ∈ O ε−1 |αi | /3 ∥α∥2/3 Optimal query allocation i M ∈ O ε−2 ∥α∥21 M ∈ O ε−1 ∥α∥2/3 TABLE B.2. Runtime scaling of list-and-sum algorithms

Spelling out the ε dependence of C, we obtain Mi ∈ O ε

− r2

|αi |

2 r+1

∥α∥

2 r(r+1) 2 r+1

(B19)

With this, we can reach the final result N X

N X

1 M= Mi = √ r C i=1 1 = √ r C 1 = √ r C

! |αi |

2 r+1

∥α∥ r(r+1) 2

N X 2 |αi | r+1 i=1

(B20)

r+1

i=1 N X 2 |αi | r+1

! r1

i=1

N X 2 |αi | r+1

! r+1 r

∥α∥ r 2 r+1 = √ . r C

i=1

The full expression including ε in turn becomes 2 2 M ∈ O ε− r ∥α∥ r 2 .

(B21)

r+1

Algorithm B.1 List-and-sum algorithm template. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. PN Output: fα (x) = i=1 αi k(x, xi ) to ε additive precision. ▷ Inference, Eq. (3). 1: for i ∈ {1, . . . , N } do: 2: Reading oracle OR (α, i): αi 3: Estimate k(x, xi ) using Mi queries to single-input oracle: k̂(Mi ) (x, xi ) ▷ Variance O(1/Mir ), with r ∈ {1, 2}. 2 (Mi ) 4: Multiply k̂ (x, xi ) with the coefficient αi ▷ Variance O(|αi | /Mir ). PN 5: end for ▷ Total number of shots is M = i=1 Mi . PN PN 2 (M ) (Mi ) |αi |2/M r ), sufficient: M ∈ O(ε−2/r ∥α∥ /r 6: return fˆα (x) := α k̂ (x, x ) ▷ Total variance O( i i i 2/(r+1) ). i=1 i=1

Below, we spell out the resulting costs for all four list-and-sum variants as corollaries of Theorem B.1. Corollary B.2 (Fixed budget, sampling). Consider Algorithm B.2 and the problem set-up in Definition 1. To estimate the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability, the runtime scaling of Algorithm B.2 is dominated by the query complexity M ∈O Proof. Immediate from Theorem B.1 with r = 1.

N ∥α∥22 ε2

(B22)

19 Algorithm B.2 List-and-sum with fixed budget, via sampling. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. P ▷ Inference, Eq. (3). Output: fα (x) = N i=1 αi k(x, xi ) 1: for i ∈ {1, . . . , N } do: 2: Reading oracle OR (α, i): αi M 3: Single-input oracle for U (x) and U † (xi ): estimate k(x, xi ) using M/N shots: k̂( /N ) (x, xi ). ▷ Variance O(N/M ). 2 M 4: Multiply k̂( /N ) (x, xi ) with the coefficient αi ▷ Variance O(N αi/M ). 5: end for ▷ Total number of shots is M . PN (M ) 2 (M/N ) (x, xi ) ▷ Total variance O(N ∥α∥2/M ), sufficient M ∈ O(ε−2 N ∥α∥22 ). 6: return fˆα (x) = i=1 αi k̂

Corollary B.3 (Adaptive budget, sampling). Consider Algorithm B.3 and the problem set-up in Definition 1. To estimate the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability, the runtime scaling of Algorithm B.3 is dominated by the query complexity ∥α∥21 . (B23) M ∈O ε2 The optimal allocation of shots is

|αi |∥α∥1 Mi ∈ O ε2

(B24)

Proof. Immediate from Theorem B.1 with r = 1.

Algorithm B.3 List-and-sum with adaptive budget, via sampling. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. PN Output: fα (x) = i=1 αi k(x, xi ) to ε additive precision. ▷ Inference, Eq. (3). 1: for i ∈ {1, . . . , N } do: 2: Reading oracle OR (α, i): αi 3: Single-input oracle for U (x) and U † (xi ): estimate k(x, xi ) using Mi shots: k̂(Mi ) (x, xi ) ▷ Variance O(1/Mi ). 2 4: Multiply k̂(Mi ) (x, xi ) with the coefficient αi ▷ Variance O(αi/Mi ). PN 5: end for ▷ Total number of shots is M = i=1 Mi . PN 2 PN (M ) (Mi ) −2 α k̂ (x, x ) ▷ Total variance O( ∥α∥21 ). 6: return fˆα (x) := α i i=1 i /Mi ), sufficient M ∈ O(ε i=1 i

Corollary B.4 (Fixed budget, quantum amplitude estimation). Consider Algorithm B.4 and the problem set-up in Definition 1. To estimate the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability, the runtime scaling of Algorithm B.4 is dominated by the query complexity N ∥α∥2 M ∈O . (B25) ε Proof. Immediate from Theorem B.1 with r = 2.

Algorithm B.4 List-and-sum with fixed budget, via quantum amplitude estimation. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. P Output: fα (x) = N ▷ Inference, Eq. (3). i=1 αi k(x, xi ) 1: for i ∈ {1, . . . , N } do: 2: Reading oracle OR (α, i): αi 2 M 3: Single-input oracle for U (x) and U † (xi ): estimate k(x, xi ) using M/N queries: k̃( /N ) (x, xi ) ▷ Variance O(N /M 2 ). 2 2 (M/N ) 4: Multiply k̃ (x, xi ) with the coefficient αi ▷ Variance O(N αi/M 2 ). 5: end for ▷ Total number of queries is M . P (N M ) 2 2 (M/N ) (x) = N (x, xi ) ▷ Total variance O N ∥α∥2/M 2 , sufficient M ∈ O(ε−1 N ∥α∥2 ). 6: return f˜α i=1 αi k̃

20 Corollary B.5 (Adaptive budget, quantum amplitude estimation). Consider Algorithm B.5 and the problem set-up in Definition 1. To estimate the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability, the runtime scaling of Algorithm B.5 is dominated by the query complexity M ∈O

∥α∥2/3 ε

(B26)

The optimal allocation of queries is  Mi ∈ O 

1/3

|αi |2/3 ∥α∥2/3 ε

 .

(B27)

Proof. Immediate from Theorem B.1 with r = 2.

Algorithm B.5 List-and-sum with adaptive budget, via quantum amplitude estimation. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. PN ▷ Inference, Eq. (3). Output: fα (x) = i=1 αi k(x, xi ) to ε additive precision. 1: for i ∈ {1, . . . , N } do: 2: Reading oracle OR (α, i): αi . 3: Single-input oracle for U (x) and U † (xi ): estimate k(x, xi ) using Mi queries: k̃(Mi ) (x, xi ) ▷ Variance O(1/Mi2 ). 2 4: Multiply k̃(Mi ) (x, xi ) with the coefficient αi ▷ Variance O(αi/Mi2 ). PN 5: end for P▷ Total number of queries is M = i=1 Mi . PN (M ) N α2 −1 i /Mi2 , sufficient M ∈ O(ε ▷ Total variance O 6: return f˜α (x) = αi k̃(Mi ) (x, xi ) ∥α∥2/3 ). i=1

i=1

All-at-once

We next provide the algorithms and analysis for the all-at-once approaches. Unlike for the case of list-and-sum, there is no single template from which all results follow, but rather we present each scenario individually. Several relevant definitions are in Section III A in the main text.

Via sampling

We now analyze the query complexity of estimating the all-at-once observable M(α, S) introduced in Theorem 7 directly via sampling, using the circuit from Algorithm A.1. The resulting algorithm is specified in Algorithm B.6 and the resulting runtime in Theorem B.6. Algorithm B.6 All-at-once via sampling. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. P Output: fα (x) = N ▷ Inference, Eq. (3). i=1 αi k(x, xi ) to ε additive precision. 1: Single-input oracle U (x): |ϕ(x)⟩ √ f f S)|ϕ(x)⟩ via sampling (see Algorithm A.1), using M shots: fˆα(M ) (x) ▷ Achieve precision O(∥M(α,S)∥ ∞/ M ). 2: Estimate ⟨ϕ(x)|M(α, √ (M ) 3: return fˆα (x) ▷ Total additive precision is in O(∥α∥1/ M ).

Theorem B.6 (Query complexity of all-at-once via sampling). Consider Algorithm B.6 and the problem set-up in Definition 1 for estimating the kernel model prediction in Eq. (3) to additive precision ε with constant success probability. The algorithm uses a total number of queries ∥α∥21 M ∈O ε2

(B28)

21 (M ) Proof. Following Algorithms B.6 and A.1, as well as Lemma A.1, using M shots produces an estimate fˆα (x) fulfilling ∥α∥1 . (B29) fˆα(M ) (x) − fα (x) ∈ Θ √ M

To achieve ε additive precision, it is thus sufficient to pick ∥α∥21 M ∈O ε2

(B30)

Since each shot constitutes three oracle queries (one execution of the circuit in Algorithm A.1), the total query complexity is 2 3M ∈ O ∥α∥1/ε2 .

Via quantum amplitude estimation

We next provide a detailed description of the algorithm used to implement the amplitude-encoding unitary V from Definition 7, with accompanying analysis in Lemma 8. Below we analyze the query complexity of the all-at-once algorithm using quantum amplitude estimation. The procedure is specified in Algorithm B.8 and the resulting runtime in Theorem B.7. Algorithm B.7 Amplitude-encoding unitary. Input: x ∈ X ▷ New input. Output: Amplitude-encoding unitary V ▷ From Definition 7. 1: Initialize |0⟩data |0⟩idx |0⟩sign |0, 0⟩QP . ▷ n + ⌈log2 (N )⌉ + 3 qubits. 2: Single-input oracle U (x)data : |ϕ̃(x)⟩ = |ϕ(x)⟩data |0⟩idx |0⟩sign ▷ G gates. PN √ 3: Quantum-state coefficient oracle W (α)idx,sign : |ϕ(x)⟩data |0⟩idx |0⟩sign 7→ p |ϕ(x)⟩ |i⟩ |s ⟩ ▷ N gates. i data idx i sign PN √ PN √ i=1 † 4: Training-set oracle O † (S): p |ϕ(x)⟩ |i⟩ |s ⟩ → 7 p U (x )|ϕ(x)⟩ |i⟩ |s ⟩ ▷ O(N (G + log N ) gates. i i i data idx i sign data idx i sign i=1 i=1 5: Project to |0⟩data onto the |0, 0⟩QP branch with a multi-control X: ▷ O(n) elementary gates N X √

pi U † (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP 7→

i=1

N X √ pi |0⟩⟨0|U † (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP + · · · |1, 0⟩QP i=1

N X √

pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, 0⟩QP + · · · |1, 0⟩QP

i=1

▷ O(1) elementary gates.

6: Separate the positive and negative terms in the sum with a CNOT N X √

pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, 0⟩QP + · · · |1, 0⟩QP 7→

i=1

N X √ 1 − si pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, ⟩QP 2 i=1

+ · · · |1, 0⟩QP + · · · |1, 1⟩QP 7: return

PN √ i=1

i pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, 1−s ⟩QP + · · · |1, 0⟩QP + · · · |1, 1⟩QP ▷ Number of gates O(N (G + log N ) + n). 2

Lemma 8 (Single-observable encoded in amplitude). Under the conditions of Theorem 7, there exists a quantum circuit using n + ⌈log2 (N )⌉ + 3 qubits which implements the amplitude-encoding unitary in Definition 7. Proof. We refer to Fig. 4 as visual proof. The quantum circuit follows the principles from Lemma A.1, though replacing the observables |0⟩⟨0|data and Zsign with controlled bitflips on auxiliary qubits. We rigorously prove the statement, by following the steps of Algorithm B.7. Using the same notation as above for the different oracles, we now introduce two controlled operations as C0 Xdata, QP,trash = |0⟩⟨0|data ⊗ IQP,trash + (I − |0⟩⟨0|)data ⊗ XQP,trash , CNOTsign, QP,± = |1⟩⟨1|sign ⊗ IQP,± + |−1⟩⟨−1|sign ⊗ XQP,± .

(B31) (B32)

Recall we defined the sign register as the eigenbasis of the Pauli Z operator Z|si ⟩ = si |si ⟩. We claim that V is of the form V = CNOTsign, QP,± ·C0 Xdata, QP,trash · O† (S)data,idx,sign · W (α)idx,sign · U (x)data ,

(B33)

22 as depicted in Fig. 4. We confirm this by applying a sequence of matrix-vector operations starting from the all-0 state, by performing the calculation V |0⟩ = CNOTsign, QP,± ·C0 Xdata, QP,trash · O† (S)data,idx,sign · W (α)idx,sign · U (x)data |0⟩data,idx,sign,QP = CNOTsign, QP,± ·C0 Xdata, QP,trash · O† (S)data,idx,sign

N X √

(B34) !

pi |ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP

i=1

= CNOTsign, QP,± ·C0 Xdata, QP,trash

N X √

! †

pi U (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP

i=1

= CNOTsign, QP,± |0⟩⟨0|data ⊗ IQP,trash + (I − |0⟩⟨0|)data ⊗ XQP,trash

N X √

! †

pi U (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP

i=1

|0⟩⟨0|data ⊗ IQP,trash

= CNOTsign, QP,±

N X √

! †

pi U (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP

i=1

+ (I − |0⟩⟨0|)data ⊗ XQP,trash

N X √

!! pi U † (xi )|ϕ(x)⟩data |i⟩idx |si ⟩sign |0, 0⟩QP

i=1

   N X √    pi ⟨0|U † (xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign  |0, 0⟩QP + · · · |1, 0⟩QP  = CNOTsign, QP,±  | {z } i=1

⟨ϕ(xi )|

   N X √   = (|1⟩⟨1|sign ⊗ IQP,± + |−1⟩⟨−1|sign ⊗ XQP,± )  pi ⟨0|U † (xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign  |0, 0⟩QP + · · · |1, 0⟩QP  | {z } i=1

N X

√

pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0,

i=1

⟨ϕ(xi )|

1 − si ⟩QP + · · · |1, 0⟩QP + · · · |1, 1⟩QP . 2

i According to our convention for the definition of the sign register, we have that 1−s 2 is 0 if si = 1, and 1 in the case si = −1. For us to confirm that the last line corresponds to the r.h.s. of Eq. (11), we must only compute its |0, 0⟩QP and |1, 0⟩QP components. We denote the projectors as P+ = Idata,idx,sign ⊗ |0, 0⟩⟨0, 0|QP , and P− = Idata,idx,sign ⊗ |0, 1⟩⟨01|QP . Then, we find

P+

N X √ i=1

N X

1 − si pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, ⟩QP + · · · |1, 0⟩QP + · · · |1, 1⟩QP 2

! (B35)

√ δsi ,1 pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, 0⟩QP = |ψ+ ⟩data,idx,sign ,

i=1

P−

N X √ i=1

N X

1 − si pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |0, ⟩QP + · · · |1, 0⟩QP + · · · |1, 1⟩QP 2

! (B36)

√ δsi ,−1 pi ⟨ϕ(xi )|ϕ(x)⟩|0⟩data |i⟩idx |si ⟩sign |01⟩QP = |ψ− ⟩data,idx,sign ,

i=1

we also compute the measurement probability for each component

⟨ψ+ |P+ |ψ+ ⟩ =

N X i,j=1

N X i=1

√ δsi ,1 δsj ,1 pi pj ⟨ϕ(xi )|ϕ(x)⟩⟨ϕ(x)|ϕ(xj )⟩⟨0|0⟩data ⟨j|i⟩idx ⟨sj |si ⟩sign ⟨0, 0|0, 0⟩QP | {z } δi,j

δsi ,1 pi |⟨ϕ(xi )|ϕ(x)⟩|2 . | {z } k(x,xi )

(B37)

23 We notice that the last line corresponds exactly to the definition of f+ from Definition 3. The same is true for f− : ⟨ψ− |P− |ψ− ⟩ =

N X i,j=1

N X i=1

√ δsi ,−1 δsj ,−1 pi pj ⟨ϕ(xi )|ϕ(x)⟩⟨ϕ(x)|ϕ(xj )⟩⟨0|0⟩data ⟨j|i⟩idx ⟨sj |si ⟩sign ⟨01|01⟩QP | {z }

(B38)

δi,j

δsi ,−1 pi |⟨ϕ(xi )|ϕ(x)⟩|2 = f− . {z } | k(x,xi )

This completes the proof. Remark Under the assumption that multi-controlled X gates with n controls require O(n) elementary gates, Algorithm B.7 uses O(N (G + log N ) + n) gates and 2 auxiliary qubits. Algorithm B.8 All-at-once via quantum amplitude estimation. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. PN ▷ Inference, Eq. (3). Output: fα (x) = i=1 αi k(x, xi ) to ε additive precision 1: Initialize |0⟩data |0⟩idx |0⟩sign |0, 0⟩QP . ▷ n + ⌈log2 (N )⌉ + 3 qubits. √ (M ) 2: ã+ ← M -query-Quantum amplitude estimation on V from Algorithm B.7 with |ψgood ⟩ = |ψ+ ⟩ ▷ Estimate f+ to precision O(1/M ). √ (M ) 3: ã− ← M -query-Quantum amplitude estimation on V from Algorithm B.7 with |ψgood ⟩ = |ψ− ⟩ ▷ Estimate f− to precision O(1/M ). 2 (M ) (M ) 4: Square estimates f˜ = ã . ▷ Estimate f± to precision O(1/M ). ±

5: Call the norm oracle ON (α) to obtain ∥α∥1 . (2M )

6: return f˜α

(M ) (M ) (x) = ∥α∥1 f˜+ − f˜−

▷ Combined additive precision in O(∥α∥1/M ). The total number of queries is 2M .

Our main contribution is the following result, which underpins the complexity of inference in quantum kernels via quantum amplitude estimation. Theorem B.7 (Query complexity of all-at-once via quantum amplitude estimation). Consider Algorithm B.8. To estimate the quantum kernel model prediction in Eq. (3) to additive precision ε with constant success probability, it suffices to choose M = Θ(∥α∥1/ε). The algorithm uses 2M applications of V and V † in total. Proof. Algorithm B.8 evaluates Eq. (3) by using quantum amplitude estimation twice as a subroutine, once for the positive terms in the sum f+ , and once for the negative terms f− . Recall we defined these terms as fα (x) = ∥α∥1 (f+ − f− ), so that f± ∈ [0, 1]. Each of the two quantum amplitude estimation subroutines uses M applications p of V and V † , for a total query 1 count of 2M . By Theorem 3, M queries yield additive error O( /M ) on each of the amplitudes f± , so that p 1 (M ) |ã± − f± | ∈ O . (B39) M 2 p (M ) (M ) . Since f± ∈ [0, 1] (as f± is a convex combination of kernel We recover estimates of f± by squaring: fˆ± := ã± p (M ) (M ) values in [0, 1]) and ã± ∈ [0, 1], we have that the factor |ã± + f± | is upper bounded by 2. Therefore, p p p 1 (M ) (M ) (M ) (M ) ˆ |f± − f± | = |ã± − f± | · |ã± + f± | ≤ 2|ã± − f± | ∈ O . (B40) M | {z } ≤2

Taking the difference and applying the triangle inequality, we get 1 (M ) (M ) (M ) (M ) − (f+ − f− ) ≤ |fˆ+ − f+ | + |fˆ− − f− | ∈ O . fˆ+ − fˆ− M (2M ) (M ) (M ) for our target function fα , we obtain Multiplying by ∥α∥1 to recover an estimate fˆα (x) = ∥α∥1 fˆ+ − fˆ−

∥α∥1 (2M ) ˆ |fα (x) − fα (x)| ∈ O . M

(B41)

(B42)

24 To achieve a final precision ε, we, therefore, set ∥α∥1 , M ∈Θ ε

(B43)

which gives a total of 2M ∈ Θ(∥α∥1/ε) applications of V and V † . Remark Algorithm B.8 does not require reading access to α as the positive and negative parts are separated implicitly inside the algorithm. Appendix C: Sample-and-average algorithms

We introduce one final algorithmic choice along the axis of how to approximate the sum in Eq. (2), which we refer to as sample-and-average. Having identified that we can express the sum as the expectation value of a quantum observable, we take a step back and notice we could have expressed it as the expectation value of a classical observable. Following the notation in Definition 3, we could re-write inference as fα (x) =

N X

αi k(x, xi ) = ∥α∥1

i=1

N X

pi si k(x, xi ) = ∥α∥1 Ei∼p [si k(x, xi )].

(C1)

i=1

Intuitively, we could now decide to approximate the expectation value on the right-most part of the equation via its finite-sample mean. In doing this, we recall that we defined k(x, x′ ) = |⟨ϕ(x)|ϕ(x′ )⟩|2 as a (quantum) expectation value itself, and hence this formula involves two sources of randomness: an inner source of randomness associated to estimating k(x, xi ) for a given i, and an outer source of randomness in selecting i from the distribution p. In the following, we give an algorithmic template as Algorithm C.1, where the inner source of randomness (evaluating the kernel, either via sampling or via quantum amplitude estimation), is wrapped by the outer source of randomness (evaluating the sum, via sampling). The template is given in terms of a free parameter r ∈ {1, 2} which can be further specialized to r = 1 for sampling and r = 2 for quantum amplitude estimation. We analyze the sample complexity of Algorithm C.1 generically in Theorem C.1, and further provide Corollaries C.2 and C.3 for the specific runtimes using sampling and quantum amplitude estimation, respectively. Theorem C.1 (Sample-and-average with fixed budget algorithm template analysis). Let X1 , . . . , XN ∈ [0, 1] be fixed values, let a ∈ R be a normalization factor, let s = (s1 , . . . , sN ) ∈ {±1}N be a vector of symbols, and let p = (p1 , . . . , pN ) be an (T ) N -outcome probability distribution. Define F := aEi∼p [si Xi ]. Assume we have T -query independent estimators X̂i with (T ) (T ) EX̂ [X̂i ] = Xi and VarX̂ [X̂i ] ≤ c/T r , for some constant c > 0, and for r ∈ {1, 2}. For L ∈ N, consider i.i.d. samples (T ) (T ) (T ) i1 , . . . , iL ∼ p, and define the intermediate T -query estimator Ŷℓ corresponding to the ℓth sample: Ŷℓ := siℓ X̂iℓ . Finally, P (T ) L define the M -query estimator F̂ (M ) = a ℓ=1 Ŷℓ /L, where M = LT . Then, for any ε > 0, to ensure |F̂ (M ) − F | < ε 2 with constant probability, it suffices to choose M ∈ O(a /ε2 ) total queries, with T ∈ O(1) inner queries per sample. For any δ ∈ (0, 1), by a median-of-means amplification (repeating the estimator O(log(δ −1 )) times and taking the median), the failure probability can be reduced to δ without changing the ε-dependence of the query complexity. Proof. We prove the statement directly by first deriving the variance of the estimator F̂ (M ) and then optimizing over the possible PL (T ) values of T and L, with M = LT . We define the intermediate quantity Ŷ (M ) = ℓ=1 Ŷℓ . From the independence of the estimators, it follows that L a2 a2 a2 a2 X (T ) (T ) (T ) Var F̂ (M ) = 2 Var Ŷ (M ) = 2 = 2 · L · Var Ŷℓ Var Ŷℓ = . Var Ŷℓ L L L L

(C2)

ℓ=1

By Chebyshev’s inequality, this implies that |F̂ (M ) − F | < ε with constant probability whenever Var(F̂ (M ) ) ∈ O(ε2 ). We next invoke the law of total variance, to obtain h i h i (T ) (T ) Var Ŷ (M ) = Ei∼p VarX̂ Ŷi i + Vari∼p EX̂ Ŷi i . (C3) We can relate each term to the estimators for the initial quantities as h i h i h c i c (T ) (T ) Ei∼p VarX̂ Ŷi = r, ≤ Ei∼p i = Ei∼p VarX̂ X̂i r T T h i (T ) Vari∼p EX̂ Ŷi i = Vari∼p (si Xi ) ≤ 1.

(C4) (C5)

25 Plugging these back in the previous formulas, we obtain a2 c 1+ r . Var F̂ (M ) ≤ L T

(C6)

This formula holds in general, and we can exploit it to bound the required number of queries. By enforcing M = LT , we would 2 like to minimize a /L (1 + c/T r ). We start by substituting L = M/T , to get a2 T c a2 c 1+ r = T + r−1 . M T M T

(C7)

To find the minimum with respect to T , we take the derivative d dT

( a2 2 c a T + r−1 = M a2 c M T M 1 − T2

if r = 1, if r = 2.

(C8)

In the case r = 1, it follows that there are no local extrema, and the first derivative is always positive,√hence the minimum is achieved at the lower limit of the domain, T = 1. In the case r = 2, the derivative nullifies when T = c, which is a constant. 2 Therefore, in both cases T ∈ O(1) achieves the optimal balance, for a total number of queries M ∈ O(a /ε2 ).

Algorithm C.1 Sample-and-average with fixed budget, template. Input: x ∈ X ▷ New input. Input: ε > 0 ▷ Required additive precision. PN ▷ Inference, Eq. (3). Output: fα (x) = i=1 αi k(x, xi ) to ε additive precision. 1: for ℓ ∈ {1, . . . , L} do: 2: Sampling oracle OC (α): iℓ ∼ p 3: Estimate k(x, xiℓ ) using T queries to the single-input oracle: k̂(T ) (x, xiℓ ) ▷ Variance O( T1r ), with r ∈ {1, 2}. (T ) (T ) (T ) ▷ Variance remains O( T1r ). 4: Multiply k̂ (x, xiℓ ) with the sign siℓ : Ŷℓ = siℓ k̂ (x, xiℓ ). 5: end for ▷ Total number of queries is M = LT . PL (T ) 6: Sum Ŷ (M ) = Ŷ ▷ Variance O(1 + Tcr ). ℓ=1 ℓ 7: Norm oracle ON (α): ∥α∥1 (M ) ∥α∥ 8: Multiply Ŷ (M ) by ∥α∥1 /L: obtain fˆα (x) = L 1 Ŷ (M ) . ∥α∥2 (M ) 1 9: return fˆα (x) ▷ Total variance O( (1 + cr )), sufficient T ∈ O(1) and M ∈ O(ε−2 ∥α∥21 ). L

Corollary C.2 (Sampling). Consider Algorithm C.1 with r = 1 and the problem set-up in Definition 1. To estimate the quantum kernel model prediction in Eq. (2) to additive precision ε with constant success probability, the runtime scaling is dominated by the query complexity ∥α∥21 M ∈O . (C9) ε2 The optimal allocation of queries is T = 1, L = M . Proof. Immediate from Theorem C.1. Corollary C.3 (Quantum amplitude estimation). Consider Algorithm C.1 with r = 2 and the problem set-up in Definition 1. To estimate the quantum kernel model prediction in Eq. (2) to additive precision ε with constant success probability, the runtime scaling is dominated by the query complexity: ∥α∥21 M ∈O . (C10) ε2 The optimal allocation of queries is T ∈ O(1), L ∈ O(M ). Proof. Immediate from Theorem C.1. In particular, as we see in Corollary C.3, quantum amplitude estimation provides no improvement over sampling in the sample-and-average framework (cf. Corollary C.2).

26 Sample-and-average recovers previous algorithms. The proof of Theorem C.1 confirms that the optimal balance between the inner and outer numbers of samples, T and L respectively, is struck by T ∈ O(1) (and even T = 1 for r = 1). Explicitly, this is independent of whether the inner estimator is based on sampling or quantum amplitude estimation r ∈ {1, 2}. The resulting estimator achieves the same query complexity scaling as both all-at-once and list-and-sum with adaptive budget, via sampling. On the one hand, we can interpret Algorithm C.1 as the all-at-once observable where the linear combination over indices is instantiated as a classical expectation value, instead of a quantum superposition. On the other hand, we can also interpret it as the list-and-sum algorithm with adaptive budget, where the number of classical samples Mi for the ith entry is automatically selected by the probability distribution i ∼ p.

Record · ID 19006 · SHA-256 f1b07e57019a94fd
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.