{"id":"1fe5d6a1-83e7-4c72-aa5f-ee31a758807f","arxiv_id":"2505.22502","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum algorithms for Gaussian process regression lose their exponential speedup because kernel matrix condition numbers grow at least linearly with dataset size.","lead":"This paper proves that for most kernels and datasets, the condition number of a Gaussian process covariance matrix grows at least linearly with dataset size, which eliminates the exponential speedup claimed by existing quantum Gaussian process regression algorithms. Why it matters: it draws a clear boundary around when quantum machine learning can beat classical computers.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1.1's deterministic uniform bounds do not follow from the almost-sure Theorem 1 and are false for null-probability sample sequences; the main a.s. linear-scaling result and no-exponential-speedup conclusion appear sound.","rationale":"The paper's central claim is that the condition number of a regularized kernel matrix grows at least linearly with m almost surely, which removes exponential quantum speedup for the three GPR algorithms considered. Theorem 1 is proven correctly from Lemma 1 (spectral convergence of Gram matrices) and Lemma 2 (monotonicity of the smallest eigenvalue under nested data). Lemma 1 is a standard consequence of Koltchinskii-Giné applied to the empirical covariance operator, and the bounded-diagonal condition is sufficient to control the diagonal perturbation. Lemma 2's use of Cauchy interlacing is valid under the Data Assumption. The subsequent substitution of κ=Θ(m) into the quantum runtimes in Table 2 is faithful to the cited algorithms. The load-bearing weakness I found is in Corollary 1.1, which asserts a uniform deterministic bound for all ω. This does not follow from the almost-sure asymptotic and is actually false: there exist null-probability sample sequences for which the Gram matrix is nearly diagonal and the condition number remains O(1). This is a genuine but localized flaw; it does not undermine Theorem 1 or the main no-exponential-speedup conclusion, which is asymptotic almost surely. The paper should be accepted after correcting Corollary 1.1 to an almost-sure statement or adding a genuine uniformity argument. The reader's weakest-assumption analysis focused on Lemma 1 and the Data Assumption; my concern is related but distinct, hence partial agreement.","tokens_in":15324,"tokens_out":28183,"duration_ms":311608,"concrete_test":"Compute κ_{m,σ} for the RBF kernel k(x,y)=exp(−(x−y)²/2) with σ²=0.01 and the deterministic sample x_i=100i for i=1..m, m=100,200,...; verify that κ stays O(1), falsifying Corollary 1.1. Alternatively, weaken the corollary to 'for almost every ω' and re-check the proof; the asymptotic argument then carries through.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Corollary 1.1 claims there exist C1, C2, M such that C1 m ≤ κ_{m,σ}(ω) ≤ C2 m for every ω ∈ Ω. The proof only notes 0 ≤ C(ω) ≤ B, which bounds the coefficient in the asymptotic formula, not the finite-m convergence. Theorem 1 is an almost-sure pointwise limit; it provides no uniformity over ω and no rate. The claimed ∀ω statement is false: for the RBF kernel on R with unit length scale, the null-probability deterministic sequence x_i = 100i gives K_m ≈ I for large m (diagonal 1, off-diagonal ~0), so κ_{m,σ} ≈ (1+σ²)/(1+σ²) = O(1), violating any linear lower bound. This overclaim is peripheral to the central message, which only needs the almost-sure linear scaling proven in Theorem 1; that theorem and the subsequent no-exponential-speedup discussion stand.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the condition number of kernel (Gram) matrices arising in Gaussian Process Regression. For square-integrable, symmetric, positive semidefinite kernels with bounded diagonal and i.i.d. samples satisfying a nested-data assumption, Theorem 1 gives an almost-sure asymptotic formula for the condition number of the regularized matrix K + σ²I: κ_{m,σ} ~ (λ1/(C(ω)+σ²)) m, where λ1 is the largest eigenvalue of the integral operator and C(ω) is a bounded random variable. Theorem 2 gives an almost-sure lower bound κ_m = Ω(m) for the unregularized case. Theorems 3 and 4 show that sparsity and Frobenius norm also scale linearly in m. The authors use these results to argue that three proposed quantum GPR algorithms (Zhao, Chen, Farooq) have at best a polynomial speedup from O(m³) to O(m² log m) over classical Cholesky, hence no exponential quantum advantage. Numerical experiments with RBF and dot-product kernels support the linear scaling.","tokens_in":15465,"tokens_out":6813,"duration_ms":67425,"significance":"If the results hold, they constitute a substantial and rigorous negative result for quantum advantage in GPR: under common kernel and data assumptions, all currently proposed quantum GPR algorithms inherit a polynomial (quadratic or worse) dependence on the number of data points, so their best possible speedup over classical Cholesky is only polynomial. The proof strategy is transparent and relies on an external spectral convergence theorem due to Koltchinskii and Giné, with the paper providing a concrete derivation of the asymptotic constant using known eigen-decompositions for the RBF kernel. The numerical verification, including a plot without the nested-data assumption, is a strength. The provided code and the identification of open problems (e.g., unbounded kernels, non-i.i.d. data) make the paper a useful contribution. The main caveat is that the central theorem is almost-sure, and the paper's deterministic Corollary 1.1 overclaims uniformity across all sample sequences.","major_comments":[{"comment":"Corollary 1.1 is false as stated. Theorem 1 is an almost-sure limit statement; it does not imply deterministic finite-m bounds valid for every ω ∈ Ω. The proof of the corollary bounds the limiting coefficient C(ω), but the asymptotic formula says nothing about the rate of convergence or about null-probability sample sequences. A concrete counterexample is the RBF kernel on R with unit length scale and the deterministic sequence x_i = 100i: for large m the Gram matrix is approximately the identity (diagonal 1, off-diagonal about 0), so κ_{m,σ} = O(1), violating the claimed lower bound C1 m. This sequence has probability zero under any continuous data distribution, so the almost-sure results remain valid, but the corollary's 'for all ω' formulation is wrong. The authors should either remove the corollary or restate it almost surely with ω-dependent constants, and correspondingly qualify the abstract's 'rigorously proving' claim.","section":"Corollary 1.1 and Section 2.1 (Theorem 1 statement)"},{"comment":"The statement '∀σ > 0, ω ∈ Ω, κ_{m,σ}(ω) ∼ ... where the above holds with probability 1' is internally contradictory: the universal quantifier over ω conflicts with the almost-sure qualification. The theorem should be stated as 'for almost every ω ∈ Ω the limit holds', as the proof correctly does using the probability-one event A. This is a presentational issue but it is directly tied to the overclaim in Corollary 1.1 and should be fixed together with it.","section":"Statement of Theorem 1 (Section 2.1)"}],"minor_comments":[{"comment":"In the proof of Theorem 2, the event A is defined with λ1(ω), but λ1 is deterministic; this notation should be corrected to λ1 to avoid confusion.","section":"Theorem 2 proof (Section 4.2)"},{"comment":"The counterexample kernel is zero almost everywhere on χ² and hence has λ1 = 0, which violates the assumptions of Theorem 1. The text acknowledges this, but the presentation as a 'counterexample to C = 0' should clarify that it does not fall under the theorem's hypotheses and hence does not disprove the possibility that C = 0 for all admissible kernels.","section":"Supplementary Material S1"},{"comment":"The claim that 'multiple realisations show identical behaviour' is not supported by displayed data; adding error bars or multiple overlaid curves would strengthen the numerical evidence.","section":"Section 2.2 Numerical Results"},{"comment":"The symbol σ² is used both for the regularization and for the noise variance in GPR; a brief note clarifying that these coincide in the standard GPR formulation would help the reader.","section":"Equation for κ_{m,σ} (Section 2.1)"}],"recommendation":"major_revision","confidential_remarks":"The central almost-sure results and the no-exponential-speedup conclusion are sound and valuable. The only substantive issue is the deterministic Corollary 1.1, which is false and which overstates the paper's own rigorous findings in the abstract and Section 2.1. This is fixable by reformulating the corollary and the theorem statements in almost-sure terms, but the correction is mathematically non-trivial because it changes the strength of the headline claim. I therefore recommend major revision rather than acceptance in the current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper should go to a serious referee. The main theorem is correct and the negative result for quantum GPR is real. But Corollary 1.1 overclaims: the deterministic bounds don't follow from the almost-sure asymptotics and are false on some null-probability sequences.\n\nThe genuinely new item is the asymptotic formula for the regularized condition number of kernel matrices, κ_{m,σ} ~ λ1/(C(ω)+σ^2) m, with C(ω) a bounded random variable. The derivation is a clean combination of Koltchinskii–Giné spectral convergence and Cauchy interlacing under the nested-data assumption. The linear lower bound in the unregularized case, plus the sparsity and Frobenius-norm bounds, round out the picture. No exponential speedup for the three existing quantum GPR algorithms follows once κ ~ m, and the argument is robust to data-loading assumptions. The numerics match the formula for RBF, and the tests for non-nested data and the unbounded dot-product kernel are honest extras.\n\nThe soft spot is Corollary 1.1. The proof only bounds the coefficient in the asymptotic expression; it says nothing about the finite-m error or uniformity over ω. For the RBF kernel, the sequence x_i = 100i is a null-probability element of the probability space, yet its Gram matrices are essentially the identity, so κ is O(1) and the claimed deterministic linear lower bound fails. The almost-sure statement of Theorem 1 is what the rest of the paper actually uses, and it stands. This is a fixable overclaim, not a broken main argument.\n\nThe nested-data assumption is also worth a comment. It is natural for datasets that grow by adding points, but it is not the standard i.i.d. redraw model for random matrix theory. The authors themselves report numerics showing linear scaling persists without nesting, so the gap is empirical rather than hidden.\n\nWho is this for? People thinking about quantum advantages in kernel methods, and anyone using condition-number scalings in GP approximations. It deserves a full referee report, with the instruction that Corollary 1.1 be corrected or downgraded to an almost-sure statement.","headline":"Solid negative result on quantum GPR speedup; main theorem a.s. linear scaling is correct, but Corollary 1.1's deterministic claim is false as stated.","tokens_in":15998,"tokens_out":7046,"would_cite":true,"duration_ms":73496,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","65F35","60B20"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The condition number of a kernel matrix grows at least linearly with its size, so quantum Gaussian process regression cannot offer exponential speedup.","keywords":["Gaussian process regression","quantum advantage","condition number","kernel matrix","quantum machine learning","spectral convergence","HHL algorithm","dequantisation"],"falsifier":"Find a square-integrable, bounded-diagonal, positive semi-definite kernel with $\\lambda_1 \\neq 0$ and a nested i.i.d. data sequence for which $\\kappa_{m,\\sigma}/m$ does not converge to a positive constant; Theorem 1 predicts linear growth for every such case.","tokens_in":15091,"feed_emoji":"⚛️","tokens_out":8491,"duration_ms":77757,"temperature":0.7,"pith_summary":"This paper asks whether the quantum algorithms proposed for Gaussian process regression can deliver exponential speedups. It answers no for a broad class of kernels: the condition number of the regularised kernel matrix grows at least linearly with the number of data points, and all three published quantum GPR algorithms scale polynomially in that condition number. The paper proves an asymptotic formula for the condition number in terms of the largest eigenvalue of the integral operator and the regularisation parameter, and verifies it numerically for RBF and dot product kernels. If correct, the best possible quantum speedup over classical Cholesky is from $O(m^3)$ to $O(m^2 \\log m)$, not exponential.","feed_headline":"Kernel matrices are ill-conditioned, capping quantum GPR gains","feed_subtitle":"Condition numbers grow at least linearly with data size, so the best quantum gain is O(m³) to O(m² log m).","key_machinery":"The load-bearing mechanism is the almost-sure spectral convergence of the normalised Gram-matrix eigenvalues $\\frac{1}{m}\\tilde\\lambda_{n,m}$ to the integral operator eigenvalues $\\lambda_n$ (Lemma 1), combined with an interlacing argument showing that, under the nested-data assumption (keeping old data points when adding new ones), the smallest eigenvalue $\\tilde\\lambda_{m,m}$ decreases to a bounded limit $C(\\omega)$ (Lemma 2). These lemmas together yield the explicit asymptotic formula for $\\kappa_{m,\\sigma}$ and the deterministic bounds of Corollary 1.1.","core_discovery":"The paper's central claim is that, for a broad class of kernels and data distributions, the condition number $\\kappa_{m,\\sigma}$ of the regularised kernel matrix $K + \\sigma^2 I$ grows at least linearly with the number of data points $m$, almost surely. Theorem 1 gives the sharper asymptotic form $\\kappa_{m,\\sigma} \\sim \\frac{\\lambda_1}{C(\\omega)+\\sigma^2} m$, where $\\lambda_1$ is the largest eigenvalue of the integral operator defined by the kernel and $C(\\omega)$ is a bounded random variable coming from the limit of the smallest Gram-matrix eigenvalue. Because the three published quantum algorithms for Gaussian process regression all have runtimes polynomial in this condition number, the paper concludes that, even granting perfect quantum data loading, they achieve at best a polynomial speedup over classical Cholesky inversion — from $O(m^3)$ to $O(m^2 \\log m)$ — rather than an exponential one.","pith_inferences":["The same linear scaling argument likely extends beyond GPR to any kernel-matrix-based quantum algorithm whose cost is polynomial in the condition number, since the proof never uses the regression labels.","The paper's numerics hint that the linear bound may survive without the nested-data assumption and for unbounded kernels such as the dot product; proving either would broaden the result's reach.","A remaining route to exponential speedup would be a quantum linear-system solver whose runtime is independent of condition number and sparsity, for example one based on a Pauli decomposition with small $\\ell^1$ norm, as the paper notes.","For practitioners, the result is a guide to classical algorithm choice: when inverting kernel matrices, any solver whose cost grows with the condition number will degrade linearly with dataset size."],"forward_implications":["For bounded kernels with i.i.d. data and $\\sigma>0$, all three quantum GPR algorithms run in polynomial time in $m$; the best is $O(m^2\\log m)$ against $O(m^3)$ for classical Cholesky.","The regularised condition number admits deterministic bounds: constants $C_1,C_2$ exist such that $C_1 m \\le \\kappa_{m,\\sigma} \\le C_2 m$ for all large $m$ and every sample.","Sparsity and Frobenius norm of kernel matrices also grow at least linearly, so quantum algorithms and quantum-inspired solvers that pay for sparsity or Frobenius condition number gain no exponential advantage.","Unregularised strictly positive definite kernels still give $\\kappa_m \\in \\Omega(m)$ almost surely.","These conclusions hold independently of data-loading assumptions and also apply to dequantised algorithms, because they concern the matrix itself."],"supporting_citations":[{"why":"Supplies the spectral convergence lemma that connects normalised Gram-matrix eigenvalues to integral operator eigenvalues.","marker":"[44]"},{"why":"Provides the interlacing theorem used to show the smallest eigenvalue sequence is decreasing under nested data.","marker":"[45]"},{"why":"One of the three quantum GPR algorithms whose runtime depends quadratically on condition number and sparsity.","marker":"[12]"},{"why":"One of the three quantum GPR algorithms; its runtime scales linearly in the condition number.","marker":"[13]"},{"why":"One of the three quantum GPR algorithms; its runtime scales quadratically in the condition number.","marker":"[14]"},{"why":"Gives the explicit spectral decomposition of the RBF kernel under Gaussian measure used in the numerical verification.","marker":"[27]"},{"why":"The standard reference for Gaussian process regression and its kernel matrix inversion bottleneck.","marker":"[11]"}],"fun_headline_variants":["Kernel condition numbers grow linearly, capping quantum GPR speedup","Quantum GPR speedup is polynomial, not exponential, proof shows","Ill-conditioned kernels foil exponential quantum gains for GPR","Gaussian process regression: quantum advantage bounded at best"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof rests on (i) a spectral convergence theorem for random kernel matrices and (ii) the nested-data assumption that each Gram matrix contains the previous one as a principal submatrix; if either fails for a chosen kernel or sampling scheme, the linear bound is not established.","fun_headline_variants_meta":{"raw":{"variants":["Kernel condition numbers grow linearly, capping quantum GPR speedup","Quantum GPR speedup is polynomial, not exponential, proof shows","Ill-conditioned kernels foil exponential quantum gains for GPR","Gaussian process regression: quantum advantage bounded at best"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000598,"raw_usage":{"total_tokens":2749,"prompt_tokens":853,"completion_tokens":1896,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":1825}},"tokens_in":469,"tokens_out":1896,"duration_ms":14742,"temperature":1.0,"reasoning_tokens":1825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:05:49.705381+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a square-integrable, bounded-diagonal, positive semi-definite kernel with $\\lambda_1 \\neq 0$ and a nested i.i.d. data sequence for which $\\kappa_{m,\\sigma}/m$ does not converge to a positive constant; Theorem 1 predicts linear growth for every such case.","supporting_citations":[{"cited_title":"Random matrix approximation of spectra of integral operators","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral convergence lemma that connects normalised Gram-matrix eigenvalues to integral operator eigenvalues."},{"cited_title":"A very short proof of cauchy’s interlace theorem for eigenvalues of hermitian matrices, 2005","cited_arxiv_id":null,"evidence_quote":"Provides the interlacing theorem used to show the smallest eigenvalue sequence is decreasing under nested data."},{"cited_title":"Fitzsimons, and Joseph F","cited_arxiv_id":null,"evidence_quote":"One of the three quantum GPR algorithms whose runtime depends quadratically on condition number and sparsity."},{"cited_title":"Quantum algorithm for Gaussian process regression","cited_arxiv_id":null,"evidence_quote":"One of the three quantum GPR algorithms; its runtime scales linearly in the condition number."},{"cited_title":"Galvis-Florez, and Simo S¨ arkk¨ a","cited_arxiv_id":null,"evidence_quote":"One of the three quantum GPR algorithms; its runtime scales quadratically in the condition number."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the explicit spectral decomposition of the RBF kernel under Gaussian measure used in the numerical verification."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The standard reference for Gaussian process regression and its kernel matrix inversion bottleneck."}],"review_version":1}