{"id":"086b4394-c6cf-48ae-8422-8eae58a615de","arxiv_id":"2502.08225","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"KTA-trained quantum embedding kernels can build SVM kernel matrices with Nyström approximation, cutting quantum circuit cost from quadratic to linear in training set size.","lead":"This paper applies the classical Nyström low-rank approximation to quantum embedding kernels, reducing the quantum circuit executions needed for SVM kernel matrices from quadratic to linear growth in training set size. The method keeps accuracy comparable to the full kernel on four small synthetic datasets, making quantum kernel classifiers more practical on near-term hardware.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Nyström accuracy with constant M is unverified; if M must grow with N, the linear-scaling claim fails.","rationale":"The reader's weakest_assumption identifies the same load-bearing point: the Nyström approximation's accuracy depends on the optimized quantum kernel being well approximated by a low-rank matrix, and the paper gives no spectral or scaling evidence. My stress test agrees with this and with the CONDITIONAL verdict. The paper does provide reproducible code, clear experimental methodology, and honest discussion of limitations, which I credit. However, the central complexity claim is conditional on M and D remaining small as N grows; this is not demonstrated and is not derivable from the current results. The reader's verdict already conditions acceptance on addressing exactly this issue, so no change to the verdict is needed.","tokens_in":9779,"tokens_out":5381,"duration_ms":57756,"concrete_test":"Run the pipeline from Sec. 5 on a controlled family of synthetic datasets of increasing size, e.g., N = 100, 200, 400, 800, drawn from the same distribution. For each N, find the smallest M such that the Nyström-based SVM test accuracy stays within 1-2% of the full-kernel SVM, and compute the normalized Nyström error ||K - K_NM K_MM^{-1} K_NM^T||_F / ||K||_F on the exact optimized kernel K. If the required M remains bounded or grows sublinearly and the error decays, the linear-scaling claim is supported; if M must grow roughly linearly with N, the central efficiency claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is an end-to-end quantum circuit execution count that scales linearly with training set size N. This holds only if the Nyström landmark count M and the training mini-batch size D can be held fixed (or grow slower than N) as N increases. The Nyström approximation in Eq. 13 has rank at most M, and its error is controlled by the tail of the spectrum of the optimized quantum kernel matrix. The paper provides no spectral decay, no rank estimate, and no evidence on how M must scale with N. The experiments use only N = 30 to 100, with M in {2, 4, 8}, and the authors themselves state in Sec. 6.1 that larger or more complex datasets may require increasing M and D. Furthermore, the noise experiments in Secs. 6.2 and 6.3 show that the Nyström approximation degrades faster under noise than the full kernel, making the accuracy-comparability claim fragile in realistic settings. Without a scaling law or error bound, the claim that the pipeline is linear in N is an assumption about M(N), not a demonstrated property. If M must grow as N^alpha, the quantum circuit count O(N M^2) becomes superlinear; if the kernel Gram matrix has slowly decaying spectrum, no constant-M Nyström approximation can be accurate. Thus the load-bearing point is the unverified low-rank structure of the optimized quantum kernel.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes using the Nyström low-rank approximation to construct the quantum embedding kernel matrix for an SVM after Kernel Target Alignment (KTA) training, with the goal of reducing the number of quantum circuit executions needed for the final training and testing kernel matrices. The training phase uses mini-batch KTA from prior work, and the final kernel is approximated via M randomly chosen landmarks. The authors report noiseless experiments on four synthetic 2D datasets showing SVM accuracy comparable to the standard full-kernel approach, plus noise experiments under coherent and depolarizing noise. The paper claims that this is the first quantum-kernel pipeline whose quantum circuit execution count scales linearly with training set size N in all steps.","tokens_in":10063,"tokens_out":6420,"duration_ms":62754,"significance":"If the central claim holds, the paper is a useful engineering contribution: it combines a scalable KTA training procedure with a standard classical low-rank approximation to remove the O(N^2) quantum circuit bottleneck from the final kernel-matrix construction, and it makes the code publicly available. The noiseless empirical comparison on four datasets supports the accuracy statement for the tested small-scale cases, and the authors are transparent about the dependence of the method on hyperparameters M and D. The significance is limited, however, by the lack of any spectral-decay or error-bound evidence for the optimized quantum kernels and by the fact that the linear-scaling claim is conditional on M and D remaining bounded as N grows; the paper does not currently establish that condition.","major_comments":[{"comment":"The paper repeatedly states that the Nyström method reduces the number of quantum circuit executions for the training kernel matrix to O(NM^2). This is not the quantum circuit-execution count: constructing K_MM requires M^2 circuit evaluations (or M(M+1)/2 unique entries) and constructing K_NM requires N·M circuit evaluations, for a total of O(NM + M^2). The O(NM^2) figure is the classical arithmetic cost of forming the product K_NM K_MM^{-1} K_NM^T in Eq. (13). Because the manuscript's central claim is about quantum circuit executions, this count should be corrected. The linear scaling in N remains valid for fixed M, but the prefactor and the quantitative comparison in Fig. 2 should reflect NM + M^2 rather than NM^2.","section":"§4, Eq. (13) and §5"},{"comment":"The end-to-end linear-in-N claim is conditional on M and D not growing with N. The manuscript gives no spectral-decay information for the optimized quantum kernels, no rank estimate, and no scaling law for M(N); the experiments use N between 30 and 100 and M in {2,4,8}. The authors themselves note in §6.1 that larger or more complex datasets may require increasing M and D. If M grows as N^α, the quantum circuit count becomes superlinear, so the advertised \"first pipeline that depends only linearly on the training dataset size\" is an assumption rather than a demonstrated property. Please add evidence such as spectral decay curves or approximation-error curves as N grows at fixed M, or explicitly restate the claim as conditional on constant M and D.","section":"§6.1 and §7"},{"comment":"There is a dimensional inconsistency in Eq. (14). If K_PM denotes the (P,M) cross-kernel matrix between P test points and M landmarks, then K_PM^T K_MM^{-1} K_NM is an undefined product with dimensions (M,P) × (M,M) × (N,M). The correct expression is K_PM K_MM^{-1} K_MN, where K_MN = K_NM^T (or equivalently one can define K_PM as having shape (M,P)). Please fix the indices, since this formula underlies the claimed O(PM) test-time scaling.","section":"§4, Eq. (14)"}],"minor_comments":[{"comment":"The text says \"Trace(ρ^2) = 1, where ρ = ⟨ϕ|ϕ⟩\"; the density operator should be ρ = |ϕ⟩⟨ϕ|, and the inner-product notation used for ρ is incorrect.","section":"§2.1, Eq. (8)"},{"comment":"The \"spirals\" dataset is said to be generated using the make_moons method from scikit-learn; make_moons produces two interleaving moon-shaped clusters rather than a spiral, and the library is scikit-learn rather than scipy. Please correct the name or the attribution.","section":"§6 and Appendix"},{"comment":"The statement that the input scaling weights are \"initialized as 1s, ensuring they initially have no effect on the output of the quantum kernel\" is unclear; a scaling weight of 1 still applies the encoded feature, so the sense in which there is no effect should be clarified.","section":"§6"},{"comment":"The conclusion that \"both methods perform well under realistic levels of noise\" is broader than the evidence in Fig. 5, where the Nyström accuracies decrease sharply for σ > 0.2; please qualify the noise-robustness statement to the tested ranges.","section":"§6.2, §6.3, and §7"},{"comment":"The text does not account for the symmetry of K_MM and K_NM when counting unique circuit executions; stating this explicitly would make the reported execution counts reproducible.","section":"§4, Eq. (13)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within scope for a quantum-machine-learning venue and the code availability is a strength. The main risk is that the linear-scaling claim is presented as a demonstrated property when it is conditional on an unverified low-rank assumption; the revision should address this head-on, along with the circuit-count and dimension errors. No concerns about citation practices or novelty disclosure beyond the standard need to position the contribution relative to prior Nyström work in classical kernel methods."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper does something real and modest. It takes the classical Nyström low-rank approximation and applies it to the kernel matrix of a KTA-trained quantum embedding kernel, after training, so that the final matrix fed to the SVM requires O(NM) circuit executions instead of O(N^2). Combined with mini-batch KTA training à la Sahin et al., you get a pipeline where every stage's circuit count is linear in N if M and D stay fixed. The authors test this on four small synthetic datasets and report accuracy comparable to the exact kernel in the noiseless case. They also run coherent and depolarizing noise experiments, which honestly show the approximation becomes more fragile under noise.\n\nWhat's good: the problem is real; the final kernel matrix construction is indeed a quadratic bottleneck in quantum kernel SVMs, and nobody else seems to have applied Nyström there. The presentation is clear, the code is on GitHub, and the authors explicitly flag that M and D may need to grow with dataset complexity, rather than hiding that caveat.\n\nThe soft spots are real but not fatal. First, the complexity count is off: they state O(NM^2) circuit executions, but the actual number is O(NM + M^2), since you compute an N-by-M cross matrix and an M-by-M block. It's an easy fix, but as written it's wrong. Second, the central linear-scaling claim is conditional on M not growing with N. The paper gives no spectral decay or error-bound evidence for the quantum kernel Gram matrix, and no scaling law for M(N). Their experiments use N up to 100 and M in {2,4,8}, so the linear-in-N claim is an assumption about the low-rank structure, not a demonstrated property. The noise results strengthen this concern: the Nyström approximation degrades faster than the full kernel under both coherent and depolarizing noise, so in realistic settings the accuracy-comparability claim is fragile. Third, the priority claim over prior centroid-based work is asserted rather than investigated.\n\nWhom is this for? Anyone working on practical quantum kernel methods on NISQ hardware. It's a useful empirical starting point, not a theoretical breakthrough. I'd send it to review — the core idea is valid and the issues are addressable. A revision should fix the circuit count, add at least a basic spectral/error-bound discussion, and test larger N or varying M to show what happens to M(N). If that scaling turns out to be superlinear, the headline claim falls, but the paper would still be a decent contribution.","headline":"A useful, honest empirical adaptation of Nyström to quantum kernel SVMs, but the headline linear-scaling claim rests on an untested assumption about M(N).","tokens_in":10561,"tokens_out":2399,"would_cite":true,"duration_ms":22924,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper claims that using the Nyström low-rank approximation after Kernel Target Alignment yields a quantum kernel SVM pipeline whose circuit executions scale linearly with training set size, with comparable accuracy on four datasets.","keywords":["quantum embedding kernels","kernel target alignment","Nyström approximation","support vector machines","variational quantum circuits","quantum machine learning","quantum noise","scalability"],"falsifier":"Compute the eigenspectrum of a trained quantum kernel Gram matrix on a dataset with complex structure; if the relative Nyström error $\\|K - K_{NM} K_{MM}^{-1} K_{NM}^T\\|_F / \\|K\\|_F$ does not fall sharply before $M$ becomes a substantial fraction of $N$, the linear-scaling pipeline fails on exactly the regime where it is needed.","tokens_in":9589,"feed_emoji":"⚛️","tokens_out":8761,"duration_ms":81054,"temperature":0.7,"pith_summary":"This paper claims that the main scalability bottleneck of quantum embedding kernel SVMs—the need to run a quantum circuit for each pair of training points—can be bypassed by using the Nyström low-rank matrix approximation after training. Instead of building the full N×N kernel matrix pairwise, it builds a small M×M landmark kernel and an N×M cross-kernel, reconstructing the full matrix approximately. With random landmarks M≪N, quantum circuit executions drop from O($N^{2}$) to O($NM^{2}$), and the testing matrix drops from O(PN) to O(PM). On four small synthetic datasets the SVM accuracy is comparable to the standard approach, and the authors claim this is the first quantum kernel pipeline whose circuit-execution count scales linearly with training set size at every step.","feed_headline":"Quantum kernel circuit cost drops from quadratic to linear","feed_subtitle":"Nyström approximation replaces the full pairwise kernel matrix, keeping SVM accuracy while needing far fewer quantum runs.","key_machinery":"The central object is the Nyström approximation of the quantum kernel Gram matrix. Given M randomly chosen landmark points, the quantum circuit computes the landmark-landmark fidelity matrix $K_{MM}$ and the training-landmark cross matrix $K_{NM}$; the full training matrix is reconstructed as $\\tilde{K} \\approx K_{NM} K_{MM}^{-1} K_{NM}^T$. This replaces $N^2$ quantum circuit executions with $NM + M^2$ executions. The training step uses a separate mini-batch KTA cost on $D$ points, making each iteration cost $O(D^2)$ and independent of $N$, and the same reconstruction formula gives an $O(PM)$ inference cost for $P$ test points.","core_discovery":"On its own terms, the paper's discovery is that the KTA-optimized quantum kernel matrix behaves like a low-rank Gram matrix well enough that Nyström reconstruction from M randomly chosen landmarks preserves SVM classification accuracy while removing the quadratic circuit bottleneck. The authors combine this with mini-batch KTA training, which subsamples D points per training step, so that the whole pipeline—training, final kernel construction, and inference—has quantum complexity linear in N. They demonstrate on checkers, corners, donuts, and spirals that training and test accuracies are close to, and often identical with, the standard full-kernel method, and that under coherent and depolarizing noise the approximation remains usable, though less robust than the standard method.","pith_inferences":["A practical diagnostic before adopting this pipeline is to inspect the eigenspectrum of the trained quantum kernel Gram matrix: Nyström reconstruction is faithful when its top $M$ eigenvalues dominate, and choosing $M$ by spectral energy would be more reliable than random selection.","The landmark selection strategy is an obvious lever; k-means-style landmarks could outperform random sampling on datasets with cluster structure, which the authors note but do not test.","The same Nyström reconstruction can be applied to other quantum kernel tasks, such as regression, clustering, or kernel PCA, whenever a Gram matrix must be materialized.","The noise results suggest that noisy landmark entries are amplified by the inversion $K_{MM}^{-1}$, which would explain why the Nyström method degrades faster than the full kernel under hardware noise."],"forward_implications":["The dominant final-kernel cost becomes linear in $N$, so quantum kernel SVMs can be applied to larger training sets than the quadratic pairwise approach allows.","The hyperparameter $M$ is a direct resource-accuracy knob: smaller $M$ means fewer quantum runs, while larger $M$ restores accuracy, as the experiments show.","The testing kernel matrix costs only $O(PM)$ executions, so classifying unseen points is independent of the training set size $N$.","Mini-batch KTA training plus Nyström reconstruction forms a complete recipe for end-to-end linear-scaling quantum kernel classification.","Under depolarizing and coherent noise the approximation error and device errors compound, so realistic deployments need larger $M$ or additional error mitigation."],"supporting_citations":[{"why":"Introduces KTA-trained quantum embedding kernels, the standard pipeline and checkers/donuts datasets this work builds on, and shows the adjoint fidelity computation works under depolarizing noise.","marker":"Hubregtsen et al., 2022"},{"why":"Provides the mini-batch sub-sampling approach for KTA training that makes per-iteration cost O(D^2), the stage this paper couples with Nyström.","marker":"Sahin et al., 2024"},{"why":"Supplies the Nyström method and its Gram-matrix approximation analysis, the core mathematical mechanism the paper adapts.","marker":"Drineas et al., 2005"},{"why":"Provides the coherent-noise model of Gaussian over- and under-rotations of gate parameters used in the robustness experiments.","marker":"Skolik et al., 2023"}],"fun_headline_variants":["Nyström cuts quantum kernel circuit runs from quadratic to linear","Quadratic to linear quantum kernel circuits via Nyström approximation","Low-rank Nyström method lifts quantum kernel efficiency to linear","Nyström makes quantum kernel matrix construction linear-time","Quantum kernel circuits: Nyström approximation achieves linear scaling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole speedup rests on the assumption that an optimized quantum kernel Gram matrix is well captured by a low-rank reconstruction from M randomly chosen landmarks; if the kernel's useful information is spread across many eigenvalues, accuracy collapses.","fun_headline_variants_meta":{"raw":{"variants":["Nyström cuts quantum kernel circuit runs from quadratic to linear","Quadratic to linear quantum kernel circuits via Nyström approximation","Low-rank Nyström method lifts quantum kernel efficiency to linear","Nyström makes quantum kernel matrix construction linear-time","Quantum kernel circuits: Nyström approximation achieves linear scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001246,"raw_usage":{"total_tokens":5075,"prompt_tokens":872,"completion_tokens":4203,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":4115}},"tokens_in":488,"tokens_out":4203,"duration_ms":28446,"temperature":1.0,"reasoning_tokens":4115,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T05:56:41.545397+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the eigenspectrum of a trained quantum kernel Gram matrix on a dataset with complex structure; if the relative Nyström error $\\|K - K_{NM} K_{MM}^{-1} K_{NM}^T\\|_F / \\|K\\|_F$ does not fall sharply before $M$ becomes a substantial fraction of $N$, the linear-scaling pipeline fails on exactly the regime where it is needed.","supporting_citations":[{"cited_title":"H., Faehrmann, P","cited_arxiv_id":null,"evidence_quote":"Introduces KTA-trained quantum embedding kernels, the standard pipeline and checkers/donuts datasets this work builds on, and shows the adjoint fidelity computation works under depolarizing noise."},{"cited_title":"E., Symons, B","cited_arxiv_id":null,"evidence_quote":"Provides the mini-batch sub-sampling approach for KTA training that makes per-iteration cost O(D^2), the stage this paper couples with Nyström."},{"cited_title":"W., and Cristianini, N","cited_arxiv_id":null,"evidence_quote":"Supplies the Nyström method and its Gram-matrix approximation analysis, the core mathematical mechanism the paper adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the coherent-noise model of Gaussian over- and under-rotations of gate parameters used in the robustness experiments."}],"review_version":1}