pith. sign in

arxiv: 2503.20683 · v3 · pith:TDEM4JZVnew · submitted 2025-03-26 · 🪐 quant-ph

New perspectives on quantum kernels through the lens of entangled tensor kernels

Seongwook Shin , Ryan Sweke , Hyunseok Jeong This is my paper

Pith reviewed 2026-05-22 22:15 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum kernelsquantum machine learningentangled tensor kernelsproduct kernelsembedding mapsinductive biasdequantization
0
0 comments X

The pith

All embedding quantum kernels can be understood as entangled tensor kernels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces entangled tensor kernels as a generalization of classical product kernels. It proves that every embedding quantum kernel corresponds exactly to an instance of an entangled tensor kernel. This unifies quantum kernel methods with classical kernel theory. The connection matters because it makes the inductive bias of quantum kernels more transparent and identifies routes toward their dequantization.

Core claim

By generalizing product kernels to entangled tensor kernels, the authors show that any quantum kernel arising from an embedding feature map is an entangled tensor kernel. This establishes a direct structural correspondence that preserves the properties relevant to learning while making the role of quantum entanglement explicit in the kernel definition.

What carries the argument

Entangled tensor kernels, the generalization of product kernels that incorporates entanglement across tensor factors in the feature map.

If this is right

  • The inductive bias of quantum kernels becomes analyzable through the lens of entangled tensor kernel properties.
  • Classical techniques for handling tensor kernels can be adapted to derive dequantization methods for quantum kernels.
  • Quantum kernels and classical kernels can be compared directly within the same generalized framework.
  • The distinct behavior of quantum kernels traces to the entanglement built into the tensor kernel structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Classical kernels engineered to match the entangled tensor form might reproduce quantum kernel performance on certain tasks.
  • Links to existing tensor network approximations in machine learning could yield efficient classical surrogates.
  • Empirical tests on benchmark datasets would show whether the identified dequantization paths remain competitive.

Load-bearing premise

The generalization from product kernels to entangled tensor kernels must preserve every relevant structural property of embedding quantum kernels without adding extraneous constraints or dropping essential quantum features.

What would settle it

An explicit embedding quantum kernel whose associated kernel function cannot be rewritten in the entangled tensor kernel form would disprove the claim.

Figures

Figures reproduced from arXiv: 2503.20683 by Hyunseok Jeong, Ryan Sweke, Seongwook Shin.

Figure 1
Figure 1. Figure 1: A circuit diagram for quantum kernel evaluation – i.e. for the evaluation of Eq. (10). White boxes represent data-dependent quantum gates, while gray ones are non-parametrized gates. kernel methods such as projected quantum kernels [15]. For a detailed benchmarking study of both embedding and projected quantum kernels we refer to Ref. [31]. III. ENTANGLED TENSOR KERNELS There are a variety of situations in… view at source ↗
Figure 2
Figure 2. Figure 2: An overview of the conjectured landscape of ETKs, for some fixed set of local feature maps derived from [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The scaling of the largest eigenvalues with [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Eigenvalue spectra of quantum kernels satisfying two assumptions in Sec. VI. These plots are from one instance among 30 experiments. plot all eigenvalues with a log scale. One can clearly see rather non-flat eigenspectra of the s-concentrated mod￾els, and their concentration to large values. The large step-like structure of spectra from concentrated mod￾els arises because only s components contribute signi… view at source ↗
Figure 5
Figure 5. Figure 5: Learning curves for kernel ridge regression [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Eigenspectra of the largest P eigenvalues of kernel models, where P is the number of target function’s supports. Appendix E: Possible sources for bad performance of 4-sparse model in our numerics. The performance of quantum kernels depends not only on the scaling of the largest eigenvalue but also on ker￾neltarget alignment, which quantifies how well the func￾tion space spanned by the eigenfunctions with t… view at source ↗
read the original abstract

Quantum kernel methods are one of the most explored approaches to quantum machine learning. However, the structural properties and inductive bias of quantum kernels are not fully understood. In this work, we introduce the notion of entangled tensor kernels - a generalization of product kernels from classical kernel theory - and show that all embedding quantum kernels can be understood as an entangled tensor kernel. We discuss how this perspective allows one to gain novel insights into both the unique inductive bias of quantum kernels, and potential methods for their dequantization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces entangled tensor kernels as a generalization of classical product kernels k(x,y)=k1(x1,y1)k2(x2,y2) to non-factorizable kernels on tensor-product feature spaces via an entangled feature map. It claims that all embedding quantum kernels (data encoded in quantum states with kernel given by state overlap) arise exactly as such entangled tensor kernels by direct construction, and uses this representation to analyze the inductive bias of quantum kernels and routes toward dequantization.

Significance. If the direct-construction identification holds without extraneous constraints, the work supplies a concrete bridge from quantum embedding kernels to classical kernel theory. This could clarify the source of any quantum advantage in kernel methods and suggest systematic dequantization strategies. The absence of free parameters or ad-hoc axioms in the core identification is a strength.

minor comments (3)
  1. [§2] The definition of the entangled tensor kernel (likely in §2 or §3) should explicitly state whether the feature map is required to be a valid quantum embedding or if classical entangled maps are also included; this affects the scope of the 'all embedding quantum kernels' claim.
  2. [§3] Notation for the tensor-product feature space and the entanglement operation should be unified across the quantum and classical sides to avoid reader confusion when comparing to standard product-kernel literature.
  3. [§4] The dequantization discussion would benefit from a concrete example showing how a specific quantum kernel is recovered as a classical entangled tensor kernel, including any resource scaling.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, recognition of the direct-construction bridge to classical kernel theory, and recommendation for minor revision. We are pleased that the absence of free parameters or ad-hoc axioms is noted as a strength.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper introduces the definition of entangled tensor kernels as a generalization of classical product kernels to non-factorizable tensor-product feature maps, then proves by direct construction that every embedding quantum kernel (overlap of encoded quantum states) arises exactly in this form. This is a mathematical identification resting on the definitions and the explicit mapping, not on any fitted parameters, self-referential equations, or load-bearing self-citations whose validity depends on the present work. The inductive-bias and dequantization discussions follow from the same representation without reducing to the inputs by construction. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the newly introduced definition of entangled tensor kernels and the domain assumption that quantum kernels arise from embeddings; no free parameters or independent evidence for the new entity are provided.

axioms (1)
  • domain assumption Quantum kernels are constructed via data embedding into quantum states
    Standard assumption in quantum kernel methods invoked to frame the result.
invented entities (1)
  • entangled tensor kernel no independent evidence
    purpose: Generalization of product kernels to capture quantum kernel structure
    New mathematical object introduced by the paper to enable the unification claim.

pith-pipeline@v0.9.0 · 5605 in / 1084 out tokens · 89017 ms · 2026-05-22T22:15:47.328035+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

76 extracted references · 76 canonical work pages

  1. [1]

    (20) In particular, we see from Eq

    (19) = K((x1, x2), (x′ 1, x′ 2)). (20) In particular, we see from Eq. ( 16), that for any kernel defined via Eq. ( 15), the feature vector jF (x1, x2)i is simply the tensor product of feature vectors jF (1)(x1)i and jF (2)(x2)i. This motivates the name product kernels [32] for such kernels. We note that the construction above clearly generalizes to N kerne...

    work page

  2. [2]

    In particular, one can notice that here the eigenfunctions 6 and eigenvalues of the product kernel are simply the products of those of the individual kernels

    (21) where fγ(1,2) i g and fe(1,2) i g are the non-zero eigenvalues and corresponding eigenfunctions for the respective kernels, and d1,2 is used to denote the number of non-zero eigenvalues. In particular, one can notice that here the eigenfunctions 6 and eigenvalues of the product kernel are simply the products of those of the individual kernels. Let us...

    work page

  3. [3]

    An extended domain and feature space (if the con- stituent kernels act on different domains)

    work page

  4. [4]

    An extended feature space (if the constituent ker- nels act on the same domain)

    work page

  5. [5]

    kernel trick

    Computational complexity of evaluating product kernels Consider a kernel KF , for which KF ( , ) = hF ( )jF ( )i, where F : X 7! Rd. Assuming knowledge of the feature map F , the naive way to evaluate KF (x, x′) is to first construct the feature vectors jF (x)i, jF (x′)i 2 Rd, and then take the inner product, which requires d multiplica- tions. However, as...

    work page

  6. [6]

    This requires O(dN ) multiplications – i.e

    First explicitly construct the feature vectors jF (x)i, jF (x′)i 2 RdN , then take the inner prod- uct. This requires O(dN ) multiplications – i.e. the cost scales exponentially with the number of con- stituent kernels

    work page

  7. [7]

    Finally, take the product of all con- stituent kernel evaluations

    For each i 2 [N ], evaluate Ki(x, x′) by first eval- uating jF (i)(x)i, jF (i)(x′)i 2 Rd, then taking the inner product. Finally, take the product of all con- stituent kernel evaluations. This requires O(N d) multiplications

    work page

  8. [8]

    en- tangled

    For each i 2 [N ], simply use the appropriate kernel trick to evaluate Ki(x, x′), then take the product of all constituent kernel evaluations. This requiresQ i Ti < N d multiplications. As such, we see that product kernels do indeed admit kernel tricks, which allows for the kernel to be evaluated significantly more efficiently than via the naive method of ex...

    work page

  9. [9]

    Do there exist kernels in KQ,eff {ϕ} that are not in KMPO {ϕ} ? Said another way: Are there quantum ker- nels which can be evaluated efficiently with a quan- tum computer, but do not admit efficient evalua- tion via the ETK perspective? If the answer to this question is “Yes”, then what properties do these kernels have? Are they potentially useful? We ex- plor...

    work page

  10. [10]

    Similarly, are there kernels in KMPO {ϕ} that are not in KQ,eff {ϕ} ? We conjecture that the answer to this question is “Yes”, but leave a resolution of this to future work

    work page

  11. [11]

    We discuss the potential and limitations in this regard in Section V C

    Finally, given the existence of kernels in the inter- section KQ,eff {ϕ} \ KMPO {ϕ} , to what extent can we use 13 this to dequantize quantum kernel methods. We discuss the potential and limitations in this regard in Section V C. A. Quantum kernels can potentially realize super-polynomial bond-dimension ETKs As illustrated in Figure 2, there is the possibi...

    work page

  12. [12]

    Can be evaluated efficiently via the execution of a polynomial depth quantum circuit

    work page

  13. [13]

    super- polynomial bond-dimension

    Do not admit a polynomial bond-dimension MPO decomposition for the core tensor of the ETK rep- resentation. We refer to such quantum kernels as having “super- polynomial bond-dimension” . As per the discussion in Section III C, such kernels cannot be evaluated effi- ciently classically by simply contracting the tensor net- work defining the ETK representatio...

    work page

  14. [14]

    How can we design quantum kernels to ensure that they have super-polynomial bond-dimension?

    work page

  15. [15]

    Can one construct and analyze examples of super- polynomial bond-dimension ETKs, which can nev- ertheless be evaluated efficiently classically? B. Do useful quantum kernels exist? In the previous section, we discussed how having super- polynomial bond-dimension is a necessary but not suffi- cient condition for a quantum kernel to be hard to eval- uate classic...

    work page

  16. [16]

    Generalize efficiently: The spectrum of the kernel is concentrated on polynomially many eigenvalues, and therefore the kernel method is biased towards functions spanned by a polynomial number of top eigenfunctions

    work page

  17. [17]

    One final important remark is that the above conditions are only necessary (but not sufficient) for useful quantum kernels

    Classically hard eigenfunctions: The top eigenfunc- tions that span the (polynomially large) effective function space cannot be efficiently evaluated using only the given description of the data-dependent circuit U (x). One final important remark is that the above conditions are only necessary (but not sufficient) for useful quantum kernels. More specifically, w...

    work page

  18. [18]

    Assess whether the structure of the quantum cir- cuit U allows for efficient extraction of an MPO representation of the corresponding ETK core ten- sor

    work page

  19. [19]

    Learn a polynomial bond-dimension positive semidefinite MPO core tensor (via optimization of kernel-target alignment for example [ 10]), and use the corresponding ETK

    work page

  20. [20]

    We leave further study of these approaches to dequanti- zation of classical kernel methods to future work, however we make a few remarks

    Use the structure of the quantum circuit U to make informed guess, or random selection, of a polynomial bond-dimension positive semidefinite MPO core tensor, and use the corresponding ETK (in some ways, analogously to the use of Ran- dom Fourier Features for dequantizing variational QML [ 25, 39]). We leave further study of these approaches to dequanti- za...

    work page

  21. [21]

    Note that these are different from the eigenspectra of unitaries or quantum states themselves

    Eigenvalue scaling Here we study the scaling of eigenvalues of the kernel in- tegral operators which come from given unitaries. Note that these are different from the eigenspectra of unitaries or quantum states themselves. To study, we construct 30 random kernel instances and observe the magnitudes of their largest eigenvalues as the number of qubits in- c...

    work page

  22. [22]

    no free lunch

    Generalizability comparison on synthetic dataset Given the “no free lunch" theorem of ML, we cannot ex- pect a single kernel to perform well on all learning prob- lems. In particular, all kernels have different strengths, and a kernel can only perform well when the target func- tion has a large overlap with its dominant eigenspaces. In other words, even if...

    work page 2023

  23. [23]

    Supervised learning with quantum comput- ers

    Maria Schuld. Supervised learning with quantum comput- ers. Springer, 2018

    work page 2018

  24. [24]

    Machine learning & artificial intelligence in the quantum domain: a review of recent progress

    Vedran Dunjko and Hans J Briegel. Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Reports on Progress in Physics , 81(7): 074001, 2018

    work page 2018

  25. [25]

    Variational quantum algorithms

    Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Si- mon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644, 2021

    work page 2021

  26. [26]

    Parameterized quantum circuits as machine learning models

    Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology , 4(4): 043001, 2019

    work page 2019

  27. [27]

    Learning with kernels: support vector ma- chines, regularization, optimization, and beyond, 2002

    B Schölkopf. Learning with kernels: support vector ma- chines, regularization, optimization, and beyond, 2002

    work page 2002

  28. [28]

    Support vector machines

    Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008. doi: https://doi.org/10.1007/978-0-387-77242-4

    work page doi:10.1007/978-0-387-77242-4 2008

  29. [29]

    Kernel methods in quantum machine learning

    Riccardo Mengoni and Alessandra Di Pierro. Kernel methods in quantum machine learning. Quantum Ma- chine Intelligence , 1(3):65–71, 2019

    work page 2019

  30. [30]

    & Killoran, N

    Maria Schuld and Nathan Killoran. Quan- tum machine learning in feature hilbert spaces. Phys. Rev. Lett. , 122:040504, Feb 2019. doi: 10.1103/PhysRevLett.122.040504. URL https: //link.aps.org/doi/10.1103/PhysRevLett.122.040504

    work page doi:10.1103/physrevlett.122.040504 2019

  31. [31]

    Córcoles, Kristan Temme, Aram W

    Vojtch Havlíek, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum- enhanced feature spaces. Nature, 567(7747):209–212,

    work page

  32. [32]

    doi:10.1038/s41586-019-0980-2

    ISSN 0028-0836. doi:10.1038/s41586-019-0980-2. 21

    work page doi:10.1038/s41586-019-0980-2

  33. [33]

    Thomas Hubregtsen, David Wierichs, Elies Gil-Fuster, Peter-Jan H. S. Derks, Paul K. Faehrmann, and Jo- hannes Jakob Meyer. Training quantum embedding ker- nels on near-term quantum computers. Physical Re- view A , 106(4), October 2022. ISSN 2469-9934. doi: 10.1103/physreva.106.042431. URL http://dx.doi.org/ 10.1103/PhysRevA.106.042431

    work page doi:10.1103/physreva.106.042431 2022

  34. [34]

    On the expressivity of embedding quantum kernels

    Elies Gil-Fuster, Jens Eisert, and Vedran Dunjko. On the expressivity of embedding quantum kernels. Machine Learning: Science and Technology , 5(2):025003, April

    work page

  35. [35]

    doi:10.1088/2632-2153/ad2f51

    ISSN 2632-2153. doi:10.1088/2632-2153/ad2f51. URL http://dx.doi.org/10.1088/2632-2153/ad2f51

    work page doi:10.1088/2632-2153/ad2f51

  36. [36]

    A unified framework for trace-induced quantum kernels

    Beng Yee Gan, Daniel Leykam, and Supanut Thanasilp. A unified framework for trace-induced quantum kernels. arXiv preprint arXiv:2311.13552 , 2023

    work page arXiv 2023

  37. [37]

    A rigorous and robust quantum speed-up in su- pervised machine learning

    Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in su- pervised machine learning. Nature Physics , 17(9):1013– 1017, 2021

    work page 2021

  38. [38]

    The Inductive Bias of Quantum Kernels

    Jonas M Kübler, Simon Buchholz, and Bernhard Schölkopf. The Inductive Bias of Quantum Kernels. arXiv, 2021. doi:10.48550/arxiv.2106.03747

    work page doi:10.48550/arxiv.2106.03747 2021

  39. [39]

    Power of data in quantum machine learn- ing

    Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jar- rod R McClean. Power of data in quantum machine learn- ing. Nature communications, 12(1):2631, 2021

    work page 2021

  40. [40]

    Exponential concentration in quantum kernel methods

    Supanut Thanasilp, Samson Wang, M Cerezo, and Zoë Holmes. Exponential concentration in quantum kernel methods. Nature Communications, 15(1):5200, 2024

    work page 2024

  41. [41]

    Ruslan Shaydulin and Stefan M. Wild. Importance of kernel bandwidth in quantum machine learning. Physical Review A , 106(4), October 2022. ISSN 2469-9934. doi: 10.1103/physreva.106.042407. URL http://dx.doi.org/ 10.1103/PhysRevA.106.042407

    work page doi:10.1103/physreva.106.042407 2022

  42. [42]

    Importance of kernel bandwidth in quantum machine learning

    Ruslan Shaydulin and Stefan M Wild. Importance of kernel bandwidth in quantum machine learning. Physical Review A , 106(4):042407, 2022

    work page 2022

  43. [43]

    Wild, and Ruslan Shaydulin

    Abdulkadir Canatar, Evan Peters, Cengiz Pehlevan, Ste- fan M. Wild, and Ruslan Shaydulin. Bandwidth enables generalization in quantum kernel models. Transactions on Machine Learning Research , 2023. ISSN 2835-8856. URL https://openreview.net/forum?id=A1N2qp4yAq

    work page 2023

  44. [44]

    Neu- ral quantum kernels: Training quantum kernels with quantum neural networks

    Pablo Rodriguez-Grasa, Yue Ban, and Mikel Sanz. Neu- ral quantum kernels: Training quantum kernels with quantum neural networks. Physical Review Research , 7 (2), June 2025. ISSN 2643-1564. doi:10.1103/xphb-x2g4. URL http://dx.doi.org/10.1103/xphb-x2g4

    work page doi:10.1103/xphb-x2g4 2025

  45. [45]

    Tensor net- works for dimensionality reduction and large-scale opti- mization: Part 1 low-rank tensor decompositions

    Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, Danilo P Mandic, et al. Tensor net- works for dimensionality reduction and large-scale opti- mization: Part 1 low-rank tensor decompositions. Foun- dations and Trends ® in Machine Learning , 9(4-5):249– 429, 2016

    work page 2016

  46. [46]

    Tensor networks in machine learning,

    Richik Sengupta, Soumik Adhikary, Ivan Oseledets, and Jacob Biamonte. Tensor networks in machine learning,

    work page

  47. [47]

    URL https://arxiv.org/abs/2207.02851

    work page arXiv

  48. [48]

    Tensor decom- positions for learning latent variable models

    Animashree Anandkumar, Rong Ge, Daniel J Hsu, Sham M Kakade, Matus Telgarsky, et al. Tensor decom- positions for learning latent variable models. J. Mach. Learn. Res., 15(1):2773–2832, 2014

    work page 2014

  49. [49]

    Expressive power of tensor-network factorizations for probabilistic modeling

    Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling. Advances in neural information processing systems , 32, 2019

    work page 2019

  50. [50]

    Potential and limitations of random fourier features for dequantizing quantum machine learning, 2023

    Ryan Sweke, Erik Recio, Sofiene Jerbi, Elies Gil-Fuster, Bryce Fuller, Jens Eisert, and Johannes Jakob Meyer. Potential and limitations of random fourier features for dequantizing quantum machine learning, 2023

    work page 2023

  51. [51]

    Schollw \"o ck ,\ 10.1016/j.aop.2010.09.012 journal journal Ann

    Ulrich Schollwöck. The density-matrix renormalization group in the age of matrix product states. Annals of Physics, 326(1):96192, January 2011. ISSN 0003-4916. doi:10.1016/j.aop.2010.09.012. URL http://dx.doi.org/ 10.1016/j.aop.2010.09.012

    work page doi:10.1016/j.aop.2010.09.012 2011

  52. [52]

    Hand- waving and interpretive dance: an introductory course on tensor networks

    Jacob C Bridgeman and Christopher T Chubb. Hand- waving and interpretive dance: an introductory course on tensor networks. Journal of Physics A: Mathematical and Theoretical, 50(22):223001, May 2017. ISSN 1751-

    work page 2017

  53. [53]

    URL http://dx

    doi:10.1088/1751-8121/aa6dc3. URL http://dx. doi.org/10.1088/1751-8121/aa6dc3

    work page doi:10.1088/1751-8121/aa6dc3

  54. [54]

    On kernel-target alignment

    Nello Cristianini, John Shawe-Taylor, Andre Elisseeff, and Jaz Kandola. On kernel-target alignment. Advances in neural information processing systems , 14, 2001

    work page 2001

  55. [55]

    Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks.Nature Communications, 12(1):2914, May 2021

    Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehle- van. Spectral bias and task-model alignment explain gen- eralization in kernel regression and infinitely wide neu- ral networks. Nature Communications, 12(1):2914, 2021. doi:10.1038/s41467-021-23103-1

    work page doi:10.1038/s41467-021-23103-1 2021

  56. [56]

    Shot-frugal and robust quan- tum kernel classifiers, 2023

    Abhay Shastry, Abhijith Jayakumar, Apoorva Patel, and Chiranjib Bhattacharyya. Shot-frugal and robust quan- tum kernel classifiers, 2023. URL https://arxiv.org/abs/ 2210.06971

    work page arXiv 2023

  57. [57]

    Quantum kernel methods under scrutiny: a benchmarking study

    Jan Schnabel and Marco Roth. Quantum kernel methods under scrutiny: a benchmarking study. Quantum Ma- chine Intelligence , 7(1), April 2025. ISSN 2524-4914. doi: 10.1007/s42484-025-00273-5. URL http://dx.doi.org/10. 1007/s42484-025-00273-5

    work page doi:10.1007/s42484-025-00273-5 2025

  58. [58]

    Wainwright

    Martin J. Wainwright. Reproducing kernel Hilbert spaces, page 383415. Cambridge Series in Statistical and Proba- bilistic Mathematics. Cambridge University Press, 2019

    work page 2019

  59. [59]

    Matrix- product operators and states: Np-hardness and undecid- ability

    Martin Kliesch, David Gross, and Jens Eisert. Matrix- product operators and states: Np-hardness and undecid- ability. Physical review letters , 113(16):160503, 2014

    work page 2014

  60. [60]

    Werner, D

    A.H. Werner, D. Jaschke, P. Silvi, M. Kliesch, T. Calarco, J. Eisert, and S. Montangero. Positive tensor network approach for simulating open quantum many-body sys- tems. Physical Review Letters , 116(23), June 2016. ISSN 1079-7114. doi:10.1103/physrevlett.116.237201. URL http://dx.doi.org/10.1103/PhysRevLett.116.237201

    work page doi:10.1103/physrevlett.116.237201 2016

  61. [61]

    Purifications of multipar- tite states: limitations and constructive methods

    Gemma De las Cuevas, Norbert Schuch, David Pérez- García, and J Ignacio Cirac. Purifications of multipar- tite states: limitations and constructive methods. New Journal of Physics , 15(12):123021, December 2013. ISSN 1367-2630. doi:10.1088/1367-2630/15/12/123021. URL http://dx.doi.org/10.1088/1367-2630/15/12/123021

    work page doi:10.1088/1367-2630/15/12/123021 2013

  62. [62]

    Vartiainen, Mikko Möttönen, and Martti M

    Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa. Efficient decomposition of quantum gates. Phys. Rev. Lett. , 92:177902, Apr 2004. doi: 10.1103/PhysRevLett.92.177902. URL https://link.aps. org/doi/10.1103/PhysRevLett.92.177902

    work page doi:10.1103/physrevlett.92.177902 2004

  63. [63]

    Dequantizing algorithms to understand quantum advantage in machine learning

    Ewin Tang. Dequantizing algorithms to understand quantum advantage in machine learning. Nature Reviews Physics, 4(11):692–693, 2022

    work page 2022

  64. [64]

    Schreiber, Jens Eisert, and Johannes Jakob Meyer

    Franz J. Schreiber, Jens Eisert, and Johannes Jakob Meyer. Classical surrogates for quantum learning models. Physical Review Letters , 131(10), September 2023. ISSN 1079-7114. doi:10.1103/physrevlett.131.100803. URL http://dx.doi.org/10.1103/PhysRevLett.131.100803. 22

    work page doi:10.1103/physrevlett.131.100803 2023

  65. [65]

    Classically approximat- ing variational quantum machine learning with random fourier features, 2022

    Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and Elham Kashefi. Classically approximat- ing variational quantum machine learning with random fourier features, 2022. URL https://arxiv.org/abs/2210. 13200

    work page 2022

  66. [66]

    Jordan and Pawel Wocjan

    Stephen P. Jordan and Pawel Wocjan. Effi- cient quantum circuits for arbitrary sparse uni- taries. Phys. Rev. A , 80:062301, Dec 2009. doi: 10.1103/PhysRevA.80.062301. URL https://link.aps. org/doi/10.1103/PhysRevA.80.062301

    work page doi:10.1103/physreva.80.062301 2009

  67. [67]

    On verifiable quan- tum advantage with peaked circuit sampling

    Scott Aaronson and Yuxuan Zhang. On verifiable quan- tum advantage with peaked circuit sampling. arXiv preprint arXiv:2404.14493 , 2024

    work page arXiv 2024

  68. [68]

    Effect of data encoding on the expressive power of variational quantum-machine-learning models

    Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of varia- tional quantum-machine-learning models. Physical Re- view A , 103(3), March 2021. ISSN 2469-9934. doi: 10.1103/physreva.103.032430. URL http://dx.doi.org/ 10.1103/PhysRevA.103.032430. Appendix A: Examples of entangled tensor kernels. We supplement ...

    work page doi:10.1103/physreva.103.032430 2021

  69. [69]

    (A1) One can immediately see that K(N,c)(x, x′) = NY Kc(x, x′), (A2) where Kc(x, x′) = c + x⊤x′

    Polynomial kernel The polynomial kernel K(N,c) is defined via K(N,c)(x, x′) = ( c + x⊤x′)N . (A1) One can immediately see that K(N,c)(x, x′) = NY Kc(x, x′), (A2) where Kc(x, x′) = c + x⊤x′. (A3) As such, the polynomial kernel K(N,c) is a product ker- nel. Note, that from the feature map perspective, we can write K(N,c)(x, x′) = hF (x)jF (x′)i, (A4) where j...

    work page

  70. [70]

    K(N,a)(x, x′) := NX i=1 aiKi(x, x′) (A7) is a valid kernel

    Linear sum kernels It is a well-known fact that any linear sum of kernels with positive coefficients is also a valid kernel, i.e. K(N,a)(x, x′) := NX i=1 aiKi(x, x′) (A7) is a valid kernel. To represent this kernel as an ETK, we construct a prod- uct feature map jF (x)i = NO i=1 1 Fi(x) . (A8) Additionally, let us denote the dimensions of local fea- ture ma...

    work page

  71. [71]

    standard form

    Shift-invariant kernels A shift invariant kernel is one satisfying K(x, x′) = K(x x′) (A12) for some positive semi-definite function K : X 7! R. If we consider X = [ π, π], then any such shift invariant kernel can be written as K(x x′) = ∞X j=0 γj cos(j(x x′)), (A13) with γj 0 [32]. Here, we show that all shift invariant kernels on X with a finite frequency...

    work page

  72. [72]

    We stress that as the subspace in which the rotation occurs is fixed, the order and position of the CNOT gates and single qubit gates are also fixed – i.e

    Any such rotation can be written as a multi- controlled parameterized sinqle-qubit rotation, which in turn can be decomposed into a circuit consisting only of CNOT gates and parameterized single-qubit gates R : X ! SU(2). We stress that as the subspace in which the rotation occurs is fixed, the order and position of the CNOT gates and single qubit gates ar...

    work page

  73. [73]

    Each parameterized single-qubit rotation can be written as R( ) = RZ(ϕ1( ))RY (ϕ2( ))RZ(ϕ3( )) (C5) where ϕi : X ! [0, 2π) are functions that depend on U

    work page

  74. [74]

    Each RY gate can be decomposed into RZ gates and basis rotations using the relation Y = F †ZF , where F := 1√ 2 1 1 i i If one does all of the above, and then groups together all data-dependent gates and data-independent gates into separate layers, one finally arrives at a circuit in the form of Eq. ( C1). At this stage we stress that in the worst case, th...

    work page

  75. [75]

    L is exponentially large in the number of qubits

    work page

  76. [76]

    The functions fϕjk g are extremely complicated. However, in practice, one normally starts not from some arbitrarily defined data-dependent unitary U : X ! SU(2n), but rather from some parameterized quantum circuit C : X ! SU(2n) with a polynomial number of gates, of which the data-dependent gates are all of some fixed simple form (eg: gates that encode data...

    work page