On the Relation between Trainability and Dequantization of Variational Quantum Learning Models
Authors: Elies Gil-Fuster
Casper Gyurik
Adrian Perez-Salinas
Vedran Dunjko
Venue: ICLR 2025 Poster (2025)
Keywords: quantum machine learning
machine learning theory
quantum information theory
Primary area: learning theory
TL;DR: We prove that usual quantum machine learning models can be trainable and capable of solving classically-intractable problems simultaneously.

Abstract: Quantum machine learning (QML) explores the potential advantages of quantum computers for machine learning tasks, with variational QML among the main current approaches.
While quantum computers promise to solve problems that are classically intractable, it has been recently shown that a particular quantum algorithm which outperforms all pre-existing classical algorithms can be matched by a newly developed classical approach (often inspired by the quantum algorithm).
We say such algorithms have been dequantized.
For QML models to be effective, they must be trainable and non-dequantizable.
The relationship between these properties is still not fully understood and recent works raised into question to what extent we could ever have QML models which are both trainable and non-dequantizable.
This challenges the potential of QML altogether.
In this work we answer open questions regarding when trainability and non-dequantization are compatible.
We first formalize the key concepts and put them in the context of prior research.
We introduce the role of "variationalness" of QML models using well-known quantum circuit architectures as leading examples.
Our results provide recipes for variational QML models that are trainable and non-dequantizable.
By ensuring that variational QML models are both trainable and non-dequantizable, we pave the way toward practical relevance.

Published as a conference paper at ICLR 2025
ON THE RELATION BETWEEN TRAINABILITY AND DE- QUANTIZATION OF VARIATIONAL QUANTUM LEARN-
ING MODELS
Elies Gil-Fuster* Casper Gyurik Adrián Pérez-Salinas*. Vedran Dunjko
Dahlem Center for Complex Quantum Systems, Freic Universität Berlin, 14195 Berlin, Germany
2 Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany
3 (aQa") Applied Quantum Algorithms. Universiteit Leiden
4 Lorentz Instituut, Universiteit Leiden, Niels Bohrweg 2333 CA Leiden, Netherlands
5 LIACS, Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, Netherlands mmgiilfuuter@@mall.. com
ABSTRACT
Quantum machine learning (QML) explores the potential advantages of quantum computers for machine learning tasks, with variational QML among the main cur- rent approaches. While quantum computers promise to solve problems that are classically intractable, has been recently shown that a particular quantum algo- rithm which outperforms all pre-existing classical algorithms can be matched by newly developed classical approach (often inspired by the quantum algorithm). We say such algorithms have been dequantized. For QML models to be effective, they must be trainable and non-dequantizable. The relationship between these properties is still not fully understood and recent works raised into question what extent we could ever have QML models which are both trainable and non- dequantizable. This challenges the potential of QMI. altogether. In this work we answer open questions regarding when trainability and non-dequantization are compatible. We first formalize the key concepts and put them in the con- text of prior research. We introduce the role of "variationalness" of QML mod- els using well-known quantum circuit architectures as leading examples. Our results provide recipes for variational QML models that are trainable and non- dequantizable. By ensuring that variational QML models are both trainable and non-dequantizable, we pave the way toward practical relevance.
INTRODUCTION
Machine Learning (ML. algorithms have been extensively researched and developed, resulting in numerous successful applications across various domains. Recently, there has been growing interest in Quantum Machine Learning (QML) (Schuld Petruccione, 2021; Cerezo et al., 2021b; Bharti et al., 2022), which leverages quantum computing to potentially enhance traditional ML models. A significant focus in QML is on so-called variational QML models, where quantum operations are tuned by an optimizer, analogously to neural networks in classical ML. One of the main questions in the field at the moment is how can we design good variational QML models?
Addressing this question involves tackling several challenges, many of which mirror those encoun- tered in the development of Neural Networks (NNs) for classical MI. Key considerations include properties derived from ML theory such as expressivity (Schuld et al., 2021; Pérez-Salinas et al., 2021), which refers to the model's ability to represent a wide range of functions; generalization (Caro et al., 2022; Gil-Fuster et al., 2024), the model's capability to perform well unseen data; and trainability (McClean et al., 2018; Thanasilp et al., 2023), which concerns the ease with which model can be optimized. Additionally, it is crucial to ensure both, that QML models capable of solving practically relevant problems; and that their performance cannot be efficiently replicated by classical algorithms (Tang, 2019; Schreiber et al., 2023), phenomenon dubbed dequantization.

---

Published as a conference paper at ICLR 2025
Liu et al. (2021)
"Variational"
Gyurik Dunjko (2023)
This work
Non-dequantizable
?
"Practically relevant"
Ultimate goal
Neural Networks
Trainable
Figure 1: Depiction of research landscape. Dashed lines refer to concepts that are not well-defined. The dotted arrow reflects that we consider "variational" quantum machine learning models those which resemble neural networks in some sense. The inclusion of practical relevance remains an open topic.
Before even start to think about discussing practical relevance, the questions surrounding de- quantization and trainability must be resolved. Hence we focus on establishing precise language for three of the categories depicted in Fig. 1, namely: Non-dequantizable. trainable, and variational. The question of practical relevance may be the most interesting one, as it aligns with the search for sensible applications of quantum computing. However, it also the most problematic characteristic to formally capture and treat theoretically. Our contributions pave the way towards eventually dis- cussing practical relevance. We are guided by strong wish be as broad possible while being sufficiently rigorous that mathematical proofs become possible.
Throughout this work we distinguish between QML models according to their operational resem- blance to NNs. To this end we introduce a scale of "variationalness". Intuitively, what makes a model variational is deep-layered structure (like NNs), and the trainable parameters appearing side the model's ss layers. Variational QML models hold the promise of being broadly applicable, as well as being more efficient to train and to implement than quantum kernel methods (as is the case in classical ML).
Our first contribution is the formal definition trainability and dequantization, to disentangle the discussion from related proxies. We next explain how trainability and non-dequantization tually compatible for non-variational QML models, based on prior works. We formally introduce a measure of variationalness and prove accompanying results to justify the need for restricted no- tion of trainability. Finally, we resolve the open question regarding trainability and dequantization in variational QML: there do exist variational QML models which are gradient-based based trainable and still non-dequantizable.
mu-
Our work provides clear outlook on the necessary future steps toward good variational QML models.
DEFINITIONS
In terms of notation, we call X' the data domain, and y the label co-domain. A learning task (D, R) specified by probability distribution D(X Y) over inputs and labels, and a risk functional R. Given a function f: X + y. R(f)) measures the quality of f as a solution to the learning task. We denote Dx the marginal of D over the data X. A learning model (F, A) consists of family of functions F from to y' and a learning algorithm A. The learning algorithm takes as input a training set S of labeled data and returns function in the family A(S) F'. We use N to denote the cardinality of S. We use Rs for the empirical risk, which is an estimator of R restricted the training set S. We ignore the possibility of a validation set for ease of presentation. We denote fī F an optimal solution to the task (D, R) within the model, and fī F an optimum of the empirical risk Rs for the set S. If the function family of the form F = {fo: a/:: X + y I E θ), talk about a parametrized learning model with parameters 1 O. We P(0) for a probability distribution over the parameters.
As technicality, we define F the range of A over all possible training sets, independently of their size.
2

---

Published as a conference paper at ICLR 2025
2.1 PARAMETRIZED QUANTUM CIRCUITS FOR QML
We assume some familiarity with quantum computing, for more background in the formalism of quantum circuits, we refer readers Appendix A. A Parametrized Quantum Circuit (PQC) is spec- ified by a sequence of quantum gates depending on continuous parameters (Benedetti et al., 2019). The action of a PQC can be seen as a three step process: (1) prepare fixed initial quantum state Pu. (2) transform the intial state into a different one Po + p by applying a sequence of parametrized quantum gates, and (3) measure a fixed quantum observable M. From PQCs we estimate the ex- pectation value tr(aM) (Nielsen & Chuang, 2000). Specifically for QMI,, we consider PQCs of polynomial size in the relevant scale of the learning task. The size of a PQC captures a combination of the number of qubits and the depth of the circuit. There are several approaches to designing PQCs, which make different use of the parameters of the circuit, but in every case the choice of underlying PQC is known to be critical.
A popular approach in variational QML is to consider a deep-layered PQC. where each layer may depend both the input data X' and the trainable parameters & E θ (Pérez-Salina) et al., 2020). This way, the PQC results in a parametrized state p(æ; 0). A real-valued labeling function arises from the expectation value of the fixed observable .M, fo (3r) tr tr[p(;; M). Fach such PQC then gives rise to a hypothesis family Fo {fo(x) 1 E }). The resemblance between these PQCs and Neural Networks (NNs) comes from the layered appearance and the role of the trainable parameters.
Quantum kernel methods represent the main alternative to variational QML. Quantum kernel meth- ods rely on quantum feature maps z + p(z)) (resulting in data-dependent parametrized states) to define a quantum kernel function (arr,, x') = tr (((()))((z)) (Schuld, 2021). Common quantum fea- ture maps are realized as PQCs where the parameters encode the inputs x, and so quantum kernel functions also give rise to PQC-based QMI. models. For the quantum kernel approach, the resulting
labeling functions are of the form (z) = > ax,(1,, 22). where {(z;){} is the training set of size N fed the learning algorithm, and = (cks): is real vector of trainable parameters. Quan- tum kernel methods thus differ from other variational QMI models in that their trainable parameters are not part of the PQC from where they stem, and often quantum feature maps do not display a layered-structure. Formally (see Appendix B for further details). the hypothesis family of such models is the set of real-valued linear maps of p(x): F, (fM(z) = tr(p(x)M) I E Herm), Herm being the set of Hermitian operators of the appropriate dimension, exponential in the number of qubits. Notice we do not restrict the size of the training set when defining the hypothesis family of learning model. Also, different Hermitian matrices can give rise to the same function if p(xx) is not full rank.
N
2.2 TRAINABILITY
Prior works have dealt with trainability in QML, but until now a formal definition has been lacking. Here we capture a few conflicting desiderata which we expose in detail in Appendix B.
Definition (Task- deeendet trainability.). Given a suite of learning tasks of interest {(Ds, R.)s), learning model A) is trainable if the following holds for each task: the empirical risk of the hypothesis produced by the learning algorithm is close to the optimal one within the class Rs(A(S)) z Rs(J5) with high probubility with respect to training set S of polynomial size being sampled i.i.d. according to D.
As remark, notice our definition of trainability involves the empirical risk and not the expected risk. On the one hand, the empirical risk the quantity we have access to. On the other hand, statements about the expected risk would arguably not be about trainability, but rather about generalization. In Section 3.1 we comment further on other similar notions.
We do not specify notion of closeness for the risks, as this is an issue that is usually much easier to handle on a case-by-eass by-cae basis. The conceptual idea is that a model is trainable if the labeling function outputted by the training algorithm is approximately optimal within the hypothesis family, for a set of tasks of interest. A (Q)LL model can still be considered trainable even if it displays poor performance in task it is not well-geared to solve.
3

---

Published as a conference paper at ICLR 2025
The discussion of useful notions of trainabilityy does not end here, though. In particular, the definition allows for training algorithms A different from the ones QML practitioners would use. Accordingly, it makes sense to also discuss the nature of A. For example, one could talk about efficient trainability by imposing that A must run in polynomial time the size of the model and size the training set. We could also distinguish between quantum efficient and classical efficient trainability.
2.3 BARREN PLATEAUS IN MACHINE LEARNING
The Barren Plateau (BP) phenomenon introduced in McClean et. (2018) has been taken proxy for trainability in optimization problems. Here, we adapt the definition of BPs to make sense for any parametrized (Q)ML model, in similar way to Thanasilp et al. (2023) and Barthe & Pérez- Salinas (2023). We propose a general definition which keeps the spirit that BPs are a concentration phenomenon over the variational parameters, independently of their roles. Given a parametrized (Q)ML hypothesis family F of size n, with variational parameters & O, and a probability distri- bution over O, we define BPs in ML as follows:
Definition 2 (Barren Plateaus in Machine Learning). The hypothesis family F = (fo 0 E θ}
has Barren Plateau with respect the parameter distribution P and the data distribution 'D if the function values concentrate exponentially in the following sense:
E Var [fo(z)] E @((exp(nn)), 0mP
z~-xx
where Var is the variance with respect to the parameter distribution
The data distribution D should be taken to be the one from the learning task we are tackling. In Appendix B, discuss the operational meaning of BPs for different kinds of ML models.
2.4 DEQUANTIZATION AND SIMULATION
Dequantization can understood in number of ways, but here we adhere to rather general notion in which given quantum algorithm, there (perhaps related) classical algorithm with matching performance:
Definition 3 (Dequantization in QML). Given suite of learning tasks of interest {(D,, R;),), QML model A) is dequantizable if there exists a classical hypothesis family Fo and learning algorithm Ac, such that the following holds for each of the learning tasks: given training set ~ DN, the performance of the classical learner is approximately at least as good as that of the quantum learner: R(Ac(S)) S R(A(S)).
Although we define dequantization broadly in terms of of learning tasks, wish to keep the focus on "dequantizing model", and not on "dequantizing problem", so the learning tasks of interest should be considered very general. Further discussion on this definition we defer to Appendix B.
One potential avenue for dequantization would be the ability to classically evaluate the functions fa E Fq in the hypothesis family:
Definition 4 (PQC simulation). A PQC- PQC-based function family Fq is classically simulable if there exists a classical poly-time algorithm which approximates fa( to good precision given 3 and x.
The definition can be further specialized to hold either for all inputs for all parameters 0, or with high probability under respective distributions. Notice this is statement only about a function family, and not about any learning task. Dequantization and simulation are essentially different properties in this way.
While we have focused on supervised learning tasks, recent milestone works have reported quantum advantage tasks involving random circuit sampling (Arute et al., 2019; Bluvstein et al., 2023). Fur- ther, works like Sweke et al. (2021) characterized the complexity of learning the distributions arising from random circuits, thus formalizing the problem as an unsupervised learning task. In this work focus exclusively supervised learning. An interesting future research direction is extending our formalism to also include the study of trainability and dequantization of unsupervised quantum learning models.
4

---

Published as a conference paper at ICLR 2025
3 RELATED WORK
3.1 TRAINABILITY AND BARREN PLATEAUS
An important question remains open in previous works regarding the relation between trainability and (absence of) BPs. Works like ( (You & Wu, 2021; Anschuetz & Kiani, 2022) show that absence of BPs not sufficient for trainability. Intuition in the field arguably dictates that the converse should not be true: presence of BPs should be sufficient for non-trainability. Later in Section 4, we show the opposite. We show how one can by-pass the problem BPs with a learning algorithm that does not rely on local iterative optimization.
Our definition of trainability bears some similarity to notions of agnostic PAC learning (Haussler, 1992). The main difference agnostic learning is that our definition involves the empirical risk Rs, since in practice this is the quantity have access to, and not the expected risk R. Further demanding that the output should be approximately optimal with respect to the expected risk would be a statement about generalization and inductive bias (Kübler et al., 2021), which is not our focus.
Another similarity is to the framework of Meta-learning (Schmidhuber, 1987), where a general learning model is trained to be able later specialize and solve several different tasks. Although defined trainability based on a set of tasks, we envision these to be taken to be very general while containing all possible learning tasks, to avoid complexity theory pit-falls. In this sense, we consider different instances of the model being trained for each different task, and so our definition essentially different to meta-learning.
3.2 DEQUANTIZATION AND SIMULATION
Our definition of dequantization captures general classes of wuantum-inspired algorithms à la Tang (2019), as well as the recently introduced classical surrogate approaches (Schreiber et al., 2023; Rudolph al., 2023). Our definition of simulation aligns with usual results (Bravyi & Gosset, 2016; Dias & Koenig, 2023).
In turn, Gyurik & Dunjko (2023) discuss many ways establish quantum advantages in learning, which imply non non-dequantization. Among the proposals we find the use of "non-classical" hypothe- sis families and also "non-classical" training algorithms, both of which can give rise to learning tasks that are hard for any classical learner and easy for a given quantum learner. They show that, in gen- eral, the simulation of hypothesis family is neither sufficient nor necessary for dequantization corresponding QML model, as the training algorithm itself could perform classically -ard computa- tions (see Section in Gyurik & Dunjko (2023)). Conversely, suffices to assume a classically-easy training algorithm for PQC simulation to be sufficient for dequantization of the QML model for all learning tasks. Works like Huang et al. (2021) and Schreiber et al. (2023) show that the converse is not true: there exist QML models which are dequantizable but whose circuits are not simulable.
the
Another relevant recent work is Cerezo et al. (2023), which discusses the relation between classi- cal simulation and absence of BPs in optimization problems. There are two important differences between our setting and that of Cerezo et al. (2023). First, we distinguish between dequantization and simulation, and argue that the former is the relevant quantity. Second, we do not observe the possibility of quantum pre-computation in our definitions.
A novel research avenue asks whether specialized parameter initialization techniques known as warm starts (Puig-i-Valls et al., 2024) can break current attempts to classically simulate PQCs. In warm starts, one considers task-specific parameter distributions, or even data-dependent ones, which can result in non-simulable circuits which are actually simulable under the uniform distribution. The existence of other alternatives is currently being actively researched (Zhang al., 2024).
3.3 TRAINABILITY AND DEQUANTIZATION OF EXISTING QML MODELS
In Section 2.1 we introduced two types of QML models: those based on deep-layered Parametrized Quantum Circuits (PQCs) and those based on kernel methods. Here we briefly comment on known results trainability and dequantization for both types, and defer Appendix C a deeper discus- sion of the two main examples we use in our results below. A central work in the quantum kernel literature is Liu al. (2021), where general-purpose quantum kernel was proposed that provably
5

---

Published as a conference paper at ICLR 2025
Non-variational
Vari veryational [sic]
Very variational
Most variational
Shallow HEA with
DLP kernel Liu et al. (2021)
Corollary 4
?
local observable
Cerezo et al. (2023)
Trainable & non-dequantizable
Trainable & dequantizable
Spectrum of variationalness quantum machine learning models considered in this work. The color indicates whether known trainable instances are also dequantizable across the spectrum. The shaded white area marks the possible existence of other trainable quantum machine learning models, strictly more variational than the vari veryational models we introduce, which are still non- dequantizable.
Figure 2:
solves a task based on the Discrete Logarithm Problem (DLP), which is classically intractable under standard cryptographic assumptions. Under these assumptions, it follows that there exist kemnl- based QML models which are trainable and non-dequantizable. Further, Thanasilp et al. (2022) characterized phenomenon similar to BPs for kernel-based QML models called vanishing simi- larity. The main negative effect of this phenomenon is on the generalization of kernel- based QML models, and not on their trainability, for which no major issues have been identified so far. Finally, most variational QML models can be viewed as based on family of PQCs called Hardware Ef- ficient Ansatz (HEA) (Kandala et al., 2017) The HEA suffers from BPs (Kim et al., 2021) unless the PQC is shallow and the observable is local (Cerezo et al., 2021a). Intriguingly, Basheer et al. (2023) shows that the HEA is classically simulable as long as the PQC is shallow and the observable is local. From these works it follows that existing variational QML models based the HEA are either trainable or non-dequantizable, but not both. In our main result below we show that this is not always the case: there exist variational QMI. models which are trainable and non-dequantizable.
TRAINABILITY VERSUS DEQUANTIZATION IN VARIATIONAL QML
In Section 3.3 we mentioned the DLP kernel as a proof that trainability does not imply dequantiza- tion for kernel-based QMI. models (Liu et al., 2021). In this section, we prove that the same holds for variational QML models, taking inspiration from the Hardware Efficient Ansatz (HEA) (Kandala al., 2017). We first formalize notion of variationalness, and next we show that there exist QML models which are variational in this sense, while also being trainable and non-dequantizable, We offer Fig. 2 as a schematic the interplay between trainability, dequantization, and variationalness.
4.1 DEGREES OF VARIATIONALNESS IN QML
The starting point in the discussion is: what does actually make a quantum algorithm "variational"? The concept clearly has room for different interpretations, which affect what can be proven and what is true. The concept of variationalness is not well-defined, but all variational QML models can be seen as particular cases of HEAe, where some of the parametrized 2-qubit gates are either fixed or tumned off. Accordingly we introduce proxy notion that captures the "similarity to the HEA" as a measure of variationalness.
We build up to list of well-posed properties that aim at capturing the essence of variationalness from the HEA design. We are interested bottom-up, structural properties for the design of the PQC, and not abstract quantities that might be hard to estimate for a given circuit. We propose 5 properties that capture the essence of HEA. We refer to QML models that fulfill these properties both inputs
as "vari veryational (1) the PQC should consist of single layer U depending and parameters 9, that is applied sequentially several times (z; U(; U1): (2) the number of layer applications L should be tunable and independent of the number of qubits n; (3) the PQC should start from the (0) state; (4) we should measure a fixed observable Mo. independent of the number of layers L,, at the end; and (5) the parameters must be gradient -aased trainable.
Vari veryational" spoonerism of "very variational".

---

Published as a conference paper at ICLR 2025
We say parametrized learning model is gradient-based trainable if it is trainable and the training algorithm is gradient based. We consider algorithms to be gradient based if they start from random parameters according an initialization distribution P(O) and then the algorithm is only allowed to iteratively update the parameters by exploring a small region around them at each step. This restricted notion of trainability has close ties BPs. While it still does not hold that absence of BPs is sufficient for gradient-based trainability (You & Wu, 2021; Anschuetz & Kiani, 2022), now the converse does hold: absence of BPs is necessary for gradient-based trainability. Indeed, standard optimization theory dictates that, if non-trivial optimization problem can be solved via gradient descent, then follows that the gradient is not vanishingly small elrosstee (Goodfellow et al., 2016), and so it has no BPs in the sense of Definition 2. In Appendix E we offer a deeper insight into gradient-bat baaee trainability.
Vari veryational models contain deep-layered circuits, which are the main area of study of BPs. We do not call these models "very variational" in case there is a better definition. We invite researchers to contribute new bottom-up, structural properties to be added to our list of vari veryational models so that, ideally, we reach the best possible definition, which then would receive the name very variational.
We finish this section with two small results highlighting the need for a restricted notion of train- ability (gradient-basee trainability).
Proposition 1 (Trainability with Barren Plateaus). There exist QMI models which have BPs un- der the uniform distribution of parameters and are trainable for learning tasks that are classically intractable under standard cryptographic assumptions.
Proof sketch (full proof in Appendix D). The main idea is to represent the functions arising from the DLP kernel as a HEA of polynomial depth, where only very specific choices of parameters recover the kemnel. Then it holds that the HEA has BP under the uniform distribution. At the same time, we can always fix the parameters of the HEA to recover the kernel, and this results in trainability from the trainability of kernels. The training algorithm here is not gradient based with respect to the parameters of the HEA, though, as first the optimal kernel parameters are found by an SVM and second the circuit parameters are fixed to recover the optimal kernel- -baed hypothesis.
This small result confirms that absence of BPs is neither necessary nor sufficient for trainability in general. This does not mean that BPs do not suppose problem when optimizing PQCs variationally, only means they do not prevent all forms of training.
We also show that variational QML models can be trainable in general.
Corollary 2. There exist deep-layered circuits, like Deep HEA, which are trainable and non- dequantizable.
Proof. It follows directly from Prop. and Liu et al. (2021). The training algorithm involves reduction to kernel methods and is not gradient- based. The learning task is the same as the DLP kernel, which no classical algorithm can solve.
4.2 TRAINABILITY AND DEQUANTIZATION OF VARI VERYATIONAL QML MODELS
As our final contribution, we show that trainability does not imply dequantization for vari veryational models. We show this in two steps. We first propose a general recipe in Theorem 3 for gradient- based trainable. non-dequantizable QML models based on a computationally--nn easy optimization task. We then adapt this recipe in Corollary 4 specifically for vari veryational QML models.
function and an
Theorem 3 (Existence of trainable and don-dequae QML models.). Let x= {0, 13 and y = {0,1) Let Q(x) be function in BQP and not in HeurBPP /poly under a given distribution Dx. and let Uxx) be a unitary such that (z)Z,U(z)) = Q(x). Let H be Hamiltonian, and W()) parametrized unitary for which the following optimization problem can be solved with a given gradient- based algorithm Aw:
8 + arg max ( (0)) (W)))))))))
(2)
9E0
7

---

Published as a conference paper at ICLR 2025
and such that max ( and consider the corresponding hypothesis class Fq:
Call U and M = Z1 HH
FQ (foxx) (z) E
(3)
Let D specify a learning task: D(x,y) y) = Dx(x))((= ((=)))))))>>>>))))))))))))))))>)
Then Fo is gradient-based trainable for D, and it is not dequantizable.
Proof sketch (full proof in Appendix F). Solving the learning task requires evaluating the function Q(x). Since we take the function to be neither classically evaluatable nor classically learnable, follows that no classical algorithm can solve the learning task. Since the function is in BQP and moreover we have access to the circuit that evaluates it, the quantum model can evaluate it, Then, the model is madieent-bssed trainable using the algorithm from the theorem statement.
The construction Theorem 3 resembles the construction in Appendix B of Cerezo et al. (2023), which also takes advantage of functions in BQP and not in HeurBPP HP0BP///lly /poly (under appropriate distribution) to prevent classical simulation. The main difference that we solve a supervised learning problem, instead of only evaluating the function. Note that the tensor product structure we use is clearly different from typical PQCs one may encounter in QML.
Neither the statement nor the proof of Theorem 3 mentions variationalness. It is in the following corollary that we construct learning separation based on Theorem 3 but for which the quantum model is required to be vari veryational.
Corollary 4 (Existence of trainable and non-dequantizable vari veryational QMI model). There exist vari veryational QMI. models which are gradient-bar based trainable and non-dequantizable with any number of layers up to sub sub-exponentially many in the number of qubits.
Proof sketch (full proof in Appendix F). We must only take Theorem 3 and propose special case where Fq vari veryational. The main hurdle to ensure that Fo allows deep-layered structure, in general even if a circuit (x) gives rise to hard function, sequential concatenation of the circuit (z) = (z)) -U(x))( could give rise to a non-hard function. A deep-layered structure is easy to achieve for the trainable part: first we can take H be single-qubit, with e.g.
H Z, and then we can take W(0) = I (x))) With these, it follows that initializing V uniformly random and then performing gradient ascent is enough solve the optimization task. For the classically-har unitary, we start from any given U(x) and expand it into unitary Üxx) such that any number (up to exponential) of sequential applications of Ü(x) is equivalent to single application of (xx). We combine (xx) and Rx (12)) to reach a single layer (2 0,) (xx) @ Rx (1))). It suffices for us define V(z; 0) = I ('(z;) 9,) to fulfill all the assumptions of Theorem By going through the list of properties of vari veryational QML models, we can see that indeed, this hypothesis family FQ fulfills all of them.
5 DISCUSSION
Throughout our results, we have made observations that may seen counter-intuitive at first glance. For example: absence of Barren Plateaus is neither necessary nor sufficient for trainability in general, but it is necessary for gradient-based trainability. Also: classical simulation is neither necessary nor sufficient for dequantization in general, but it is sufficient if we assume the training algorithm is classically efficient. These remarks call for a nuanced analysis when moving forward in future studies of trainability and dequantization in variational QMI.. this work we discussed exclusively supervised learning scenarios, and we identify the outlook direction to expand our formalism to also include unsupervised learning tasks.
Already in Section 1 we identify practical relevance our ultimate goal. Still, the models we have designed could be qualified as contrived, as for instance they involve PQCs split up into two discon- nected parts. One may then worry that the proof of Theorem 3 provides limited insight to the design of PQCs for variational QML. This raises an open question: how can we take our constructions closer solving practically relevant tasks? Following the statements in Cerezo al. (2023), the
8

---

Published as a conference paper at ICLR 2025
Anschuetz & Kiani (2022)
Absence of Barren Platcaus Definition 2
Gradient-based trainability
Anschuetz & Kiani (2022)
Non-variational Liu al. (2021)
Proposition
Variational Corollary 4
Trainability Definition
Cerezo et al. (2023)
Liu et al. (2021)
with easy training algorithm
Dequantization Definition 3
Gyurik & Dunjko (2023)
Simulation Definition 4
Huang et al. (2021)
Figure 3: Summary of results. The blue lines are proven implications, the orange lines indicate the existence of counterexamples. Boxes with solid line refer to contributions, boxes without solid line are results based on prior work.
road to practical relevance takes us away from most existing variational QML models, as all natural- looking ones date either trainable or non-dequantizable, but not both. This way, despite the contrived appearance, our constructions offer a basis from where to consider new approaches to the design of variational QML that can eventually mark all three boxes: trainability, non-dequantization, and practical relevance.
We next our attention the broad applicability of our result. Theorem 3 is phrased in terms of an arbitrary function that is -efttur-efficientt and classically intractable at the same time. Together with Corollary 4, our recipe can be made comain-specifit for any single field where central quantity is hard to learn and evaluate classically. It would be relatively straightforward to derive further Corollaries for example dealing with properties of quantum Hamiltonians that are known to be hard to infer classically. One could envision a situation where the effect of the variational parameters is to model a known source of noise, which while being classically tractable isolation, cannot be characterized without quantum computer when combined with the underlying quantity.
dtasically-intractabble
broader context, our results raise deeper questions. As discussed in Gyurik & Dunjko (2023), all learning separations we proved rely computationally hard problems. Learning separations based on computational separations often result in statements that are arguably not about learning. In our case, the main bottleneck in the learning task was the ability compute function, but the learning itself was easy by construction. The way in which we ensured that our QML models would solve the problem was by planting the solution in the architecture of the hypoth- esis family itself. This may be deemed unsatisfactory, as the learning task could be trivially solved by the QML model we constructed. And yet, critical question remains: how design QML mod- els with certain inductive bias (Kübler et al., 2021; Peters & Schuld, 2022). It seems, then, that a fruitful research direction shall be to explore the space between completely generic circuits (no inductive bias) and circuits where the answer to computationally hard problem is hard-coded.
glassically-intractaal
On a different note, previous proofs of simulation of circuits that do not have BPs have relied to some degree on a specific class of simulation algorithms. exploiting so-called polynomial subspaces (Cerezo et al., 2023). An advantage directly implementable algorithm. A disadvantage is that these simulation algorithms may only be guaranteed to succeed with high probability over the parameter domain, and that leaves the door open for them to fail precisely on the cases which would be interesting for QML. Our contributions in this direction show that it is easy to plant computationally-ban problems in variational QML, and so this challenges the role of average-case classical simulation algorithms.
this approach is that the dequantization proofs come with

---

Published as a conference paper at ICLR 2025
6 CONCLUSION
In this work we have discussed general notions of trainability and dequantization for variational Quantum Machine Learning (QML) models. We have proposed clear definitions for trainability and dequantization. We have proved several relations between trainability, dequantization, and other common features depicted in Fig. 3. We have introduced a new family of vari veryational QML models, which convey the essence of commonly used deep-layered QMI. models and gradient-based training algorithms. We have resolved the open question whether, specifically for variational QMI. models, trainability and dequantization are mutually compatible. Our main contributions have been a clear formalization of the question, and general recipe for variational QML models which are trainable and non- dequantizable.
the literature like Barren Plateaus (BPs) and quantum circuit simulation, as
The current main goal in variational QML is to find quantum advantage in learning using parametrized quantum circuits and practically relevant, real-life data, as sketched in Fig. 1. Our work arises in a specific context, where alignment between trainability and dequantization for existing QML models has challenged the viability of the entire field (Cerezo et al., 2023). In this perspective, resolve critical open question: there do exist variational QMI. models which trainable and non-dequantizable. We provide recipe for QML models whose guiding principle is leveraging the classical hardness of evaluating some quantum functions. Specifically for the recent trend of studying the relation between BPs and classical simulability of quantum circuits, this offers a new conceptual perspective the design of Parametrized Quantum Circuits (PQCs) for QML. The language we provide allows us to advance further, and enable formal discussion on the way toward practical relevance. From the point of view of QML practitioners, our prescription ensures that the resulting variational QML models trainable and non-dequantizable. From here, variations our recipe can be considered to eventually achieve good generalization and expressivity for specific domains of application.
ACKNOWLEDGEMENTS
The authors thank Marco Cerezo, Jens Eisert, Zoë Holmes, Jarrod McClean, Luca Franceschi. and Ryan Sweke for their insightful comments in an earlier version of this draft. EGF thanks Greg White for pointing out the concept of spoonerism. EGF is 2023 Google PhD Fellowship recipient and acknowledges support by the Einstein Foundation (Finstein Research Unit on Quantum Devices), BMBF (Hybrid), and BMWK (EniQmA). CG, APS and VD supported by the Dutch National Growth Fund (NGF), as part of the Quantum Delta NI. programme. This work was supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.00 .33) and the project Divide & Quantum (with project number 1389. 21..0.2244 20.241) of the research programme NWA-ORC, and co-funded by the European Union (ERC CoG, BeMAI- Quantum, 101 124342). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Eric R. Anschuetz and Bobak T. Kiani. Quantum variational algorithms swamped with traps. Nat. Comm., 13(1), December 2022. ISSN 2041-1723. URL http: //dx doi .org/ 10.
Frank Arute et al. Quantum supremacy using a programmable superconducting proces-
sor. Nature, 574(7779):055-500, October 2019. URL https://dol org/11..038)
s41586-
Alice Barthe and Adríán Pérez-Salinas. Gradients and frequency profiles of quantum re-uploading models. arXiv:2311.100 2023. URL https: //tpx/aavvvv////////a///e//aaav/ org/ abs /bbs/2311.. 10822.
Afrad Basheer, Yuan Feng, Christopher Ferrie, and Sanjiang Li. Alternating layered variational quantum circuits can be classically optimized efficiently using classical shadows. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 6778, 2023. URL https:/ //ooi.do..o////o worg/10.00... 609/ aaaii 63766.2580.
10

---

Published as a conference paper at ICLR 2025
M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Sc. Tech., 4(4):043001, November 2019. URL https://doi.
10t///0.1088/2000 95155--9555//bbbbb..
Kishor Bharti et al. Noisy intermediate-scalee quantum algorithms. Rev. Mod. Phys., 94:015004, Feb 2022. URL https: //tik///nnii.... aps .org//og/////o doi/10 1103/RevModPhyyee 94 015004.
Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is np-hard. Phys. Rev. Lett., 127:120502, Sep 2021. doi: 10. 10.1105/PhysReveeu..222 127. 22.71225022.. URL https: //link.
aps. ops.oorg/oi/110 wtt.:/11////yyeeeeetttt..c 120502.
Dolev Bluvstein, Simon Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong. Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin. Logical quantum processor based on reconfigurable atom arrays. Nature, 626(7997):58 65, December 2023. ISSN 1476-4687. doi: 10. 10.10088/41158--22--66666 http: /ttp:://xxxc doi www//o........ 1038 s s41586 023 023-06927-33
URL
Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. Phys. Rev. Lett. 116(25), June 2016, ISSN 1079-7114. URL http: doi. org/ 10. 1ww.1111/1... 1ww.//11s///eeeee.eeeee
250501.
M. C. Caro, H.-Y. Huang, M. Cerezo, K. Sharma, A. Sornborger, L. Cincio, and P. Coles. Gen- cralization in quantum machine learning from few training data. Nature Comm., 13(1):4919, 2022. doi: 10. 1038/s41467-0222 -22---0022--55--3 URL https: /www///wwwww/./////////////.. nature. com/ artiiles s414
M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum eircuits. Nat. Comm., 12(1). 2021a. URL
http:/ //xx
doi. orggr01110.. 10. / 0000//111100 4188//4446777 00-061-----111 021-2111111111000 728-w.
M Cerezo, Martin Larocca, Diego García-Martín, NL Diaz, Paolo Braccia, Enrico Fontana, Manuel S Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, et al. Does provable absence of barren plateaus imply classical simulability? or, why need to rethink variational quantum computing. arXiv:2312.0912) 2023. URL htw.t:t////aatt //te////axvv../// pttttps///xxi...o///bbttoee www.orrg///b/......oo 091221..
M. Cerezo et al. Variational quantum algorithms. Nature Rev. Phys., 3(9):22-6444 2021b. URL https:// /ttt::://do..ooo .org/orgg// /10.gg10000 1008/1080000 22--22222021004----1
A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations unitary operations.
Quantum Inf. Comput., 12 19:10192)9911924 November 2012. doi: 10.264211qic12.11-12211
URL https:////// //oii htt///ioooggoo/////////o.o/ooo.t http:/...22//qiiii
11-11
Beatriz Dias and Robert Koenig. wrXi:22307.12912 2023. URL
Classical simulation of non- gaussian fermionic circuits.
23t.:/a.../331121/ 12912.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term pro- cessors. arXiv: 1802.06002, 2018. URL https:://eeet /ttp///axvvvvv.///vv//eee/e.eevv org/ abs///////// 110.21000000 060020
Elies Gil-Fuster, Jens Fisert, and Carlos Bravo-Prieto. Understanding quantum machine learning also requires rethinking generalization. Nat. Comm., 15(1):1-12, 2024. URL httpht://///o..o
org/10. 10380....0///0
Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning. MIT Press, 2016. http:
/ //www. www.ddeeeeaannnnnooo.ooo
Casper Gyurik and Vedran Dunjko. sepaaaton between classical clasicda and quantum learners. arXiv:2306. 16028, 2023, httptt http://awxxvv...//b/aa/ wtsp://////bb////////////// 6028.
David Haussler. Decision theoretic generalizaations of the pac model for neural net and other learning applications. Information and Computation, 100(1))78-158)) September 1992. ISSN 0890-5401. (92) 9001 O-D.
URL http:://ttte /xx doi. http://xx......./0..100.0.00

---

Published as a conference paper at ICLR 2025
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 98):1735- 1780, 1997. URL https: /ww. wttp::...rr............ www.e///eco.1330 1997. 81135.
Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean. Power of data quantum machine learning. Nature Commun., 12(1):2631, 2021. URL https: doi..org. /00 F333822F$444555 10116600001--------2222
Sofiene Jerbi, Casper Gyurik, Simon C Marshall, Riccardo Molteni, and Vedran Dunjko. Shadows of quantum machine learning. urXiv:2306.00661, 2023. URL http:::tttseeeeeee https:///aaxivi./ org/
2306. 00061.
Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-effiiint variational quantum eigensolver for small molecules and quantum magnets. Nature, (4947671):242-2466 September 2017. ISSN 1476- 4687. doi: 10. 10.1038/nature238999 URL http::/t////. dx doi. owg/10. 0ttp:/00.00//aatre28877777 nature23879
Joonho Kim, Jaedeok Kim, and Dario Rosa. Universal effectiveness of high-depil circuits in vari- ational eigenproblems. Phys. Rev. Res., 3:023203, Jun 2021. doi: 10.1 1ee0/hhyseeeeeseencchh 3.023203. URL https:/ /tt.///inn....//../ aps www.ooggg//oooooooooooooooooo /10 1110/ 111.:///yyyeeeeeeeer..hh 023203.
Jonas Kübler, Simon Buchholz, and Bernhard Schölkopf. The inductive bias of quantum kernels. Adv. Neur Inf. Proc. Sys., 34:12661-12673, 2021. URL
http:::/pproceding.eces htt.aaaee....aaaaaaaaa.ttttt..l 69acclalDDFF77003aaaaatoaaaaaaaa
Abstract.
Martin Larocca, Supanut Thanasilp, Samson Wang. Kunal Sharma, Jacob Biamonte, Patrick J.
Coles, Lukasz Cincio, Jarrod R. McClean, Zoë Holmes, and M. Cerezo. review of bar- ren plateaus in variational quantum computing. arXiv:2405.00771, 2024. URL https:
//arxiv.org/abes...e..
00781.
Y. Liu, S. Arunachalam, and K. Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Phys., 1709:111331011, 1017, jul 2021. URL https::/dool http///o..o.///...//
Jarrod McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Bar- ren plateaus in quantum neural network training landscapes. Nat. Comm., 91)::881,, November 2018. URL httph:ttt..........t.. /ttpi///oo///////////////o.. wtwpeii.rrr.....
Hela Mhiri, Leo Monbroussou, Mario Herrero-Gonnalez, Slimane Thabet, Elham Kashefi, and Jonas Landman. Constrained and vanishing expressivity of quantum fourier models. arXiv:2403.09447,
2024. URL httts:: wrw.v.xvvvvvooo.oo.oa... abs 24003.43..00 09417.
Michael and quantum computation.
A Nielsen and Isaac
Chuang. Cambridge
Quantum information press Cambridge,
university
2000.
URL
http:://ww.cannriddge org/ / htt.bhhhgheddatii.....
books htwp:/uwwmooottttttooooaaaaaaaaa SA5.00/80..2222227772222333333e2
Alexander Nietner. Unifying (quantum) statistical and parametrized (quantum) algorithms.
arXiv:2310.17716. 2023. URL https: httpaaawwiira.aaaaaaoo/ooaoooort http://v.rrrab////3//ae httpaabb//2111111/
A. Pérez-Salinas et al. Data re-uploading for a universal quantum classifier. Quantum, 4:226. February 2020. URL htt.hhtsts:/do.rrggggooo
10003331--222000000 022-06-2266
Adrián Pérez-Salinas, David López-Núñez, Artur Garcfa-Sáez, P. Fom-Díaz, and José I. Latorre. One qubit universal approximant. Phys. Rev. A, 104:012405, Jul 2021. doi: 10.1 SiysRevA.104.0122.. 104. 012405.
URL ttttps://linkes wwwiika.p.p.... www.:aa..p.oooe..oo wrgg 110.01.../////..ee//.../.
E. Peters and M. Schuld. Generalization despite overfitting in quantum machine learning models. arXiv:2209.0553 055233, 2022. URL ht wtw.x//vvvvv//v////v///////..vvt wttp://wwrrr///////o//////..ss /2209. 05523.
12

---

Published as a conference paper at ICLR 2025
Luke Pfister and Yoram Bresler. Bounding multivariate trigonometrii polynomials with applications to filter bank design. arXiv:1802.09588, 2018. URL 09588.
Ricard Puig-i- Valls, Mare Drudis, Supanut Thanasilp, and Zoë Holmes. Variational quantum sim- ulation: a case study for understanding warm starts. arXiv:2404. 10044, 2024. URL https:
10044.
Manuel S. Rudolph, Enrico Fontana, Zoë Holmes, and Lukasz Cincio. Classical surrogate simula- tion of quantum systems with lowesa. arXiv:2308.09109, 2023. URL htttt::s//aai...o///
abs/2300 09109.
Jürgen Schmidhuber. Evolutionary principles in self-referential learning, learning how to learn: The meta-meta-.. hook. Phl) thesis, Technische Universität München, 1987. URL
attps://mediate ub. tum. de/ 2id-811188.
Franz J. Schreiber, Jens Eisert, and Johannes Jakob Meyer. Classical surrogates for quantum learning models. Phys. Rev. Lett., 131:100803, 2023. URL httptt//://doo httttp////oo...rr/11..11111 1103/
PhysRevLett 131 100803.
M. Schuld. Quantum machine learning models are kernel methods. arXiv:2101.1102) 2021. URL https: /aaaaiivv.... wttpxivoorgrbb////1// abs/2101..1111
M. Schuld and F. Petruccione. Machine Learning with Quantum Computers. Springer International Publishing, 2021. URL http:: /tt.///oiiiio//// org/ 1007/ 978 030 3038-9822 4.
M. Schuld, R. Sweke, and J. Meyer. Effect of data encoding the expressive power of variational quantum-maccinn-leernnng models. Phys. Rev. A, 103(3):032430, March 2021. URL https:
//doi.org//1 www.:ppysre...a1000 103.034330.. 032430.
B. Schölkopf and A. J. Smola. Learning with kernels: support vector machines, regulariza- tion, optimization, and beyond. Adaptive computation and machine learning. MIT Press, 2002. ISBN 978-0-262-19475-4 URL https://mitpress mit mmtt.edd./780222255555555533 97300275722227 learning-withhr wit.hng-wwihhkeeeels...
Ryan Sweke, Jean-Pierr Pierre Seifert, Dominik Hangleiter, and Jens Eisert. On the quantum versus classical learnability of discrete distributions. Quantum, 5:417, March 2021. URL https:
//doi.
org/10 //doi.org/11. 22331 ///33//-2200 2q22001-111220000 0001--0323---0-
Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC '19, ACM, June 2019. doi: 10.1145/31122663316111 URL http: /x doi. wtt.o/0...1////13227710111 331 6310.
Supanut Thanasilp. Samson Wang, M. Cerezo, and Zoë Holmes. Exponential concentration and untrainability in quantum kernel methods. Stti::2208.10666 2022. URL htttt:////xxxi org/abs/ 2208. 11060.
Supanut Thanasilp. Samson Wang, Nhat Anh Nghiem, Patrick Coles, and Marco Cerezo. Subtleties in the trainability of quantum machine learning models. Quant. Mach. Intell., 5(1):21, 2023, URL https: / www.oooorriiiioooooo //1/ 10t.://..11011111111111111110001 //42/44444 023 00103-6 6.
Roeland Wiersema, Dylan Lewis, David Wierichs, Juan Carrasquilla, and Nathan Killoran. Here comes the su(n): multivariate quantum gates and gradients. Quantum, 8:1275, March 2024. ISSN 2521-327X. doi: 10. (0.22331/q-20244 2024-0307-1122 URL http:://dke doi org/10...........ooooooo 22331/ 1-2024-03-07-122
D.H. Wolpert and W.G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82, 1997. doi: 0..1109/4235.888999 URL https:
/ //dl. acm. wwc.m.org/eaee www.ooog//oooooooooo
425//235.00 11110942355.88899.
Xuchen You and Xiaodi Wu. Exponentially many local minima in quantum neural networks. In International Conference on Machine Learning, pp. 12144-12155. PMLR, 2021. URL https: /proceeed igs. ml www.srrsssiiie pttps//119//eeeeee.. http/////1//y/l.cc.
13

---

Published as a conference paper at ICLR 2025
Hao-Kai Zhang, Shuo Liu, and Shi-Xin Zhang. depth circuits with long-range entanglement. doi: 110.03//hhyyRoLLtttt......000000 URL https:/ https://likk.o//// wts....ps.oogg///./.....oo.....a wttp:pppo/o//o/....11....// PhysReviett. 132. 150603.
Absence of barren plateaus in finite local- Phys. Rev. Lett., 132:150603, Apr 2024.
14

---

Published as a conference paper at ICLR 2025
Supplementary Material for:
"On the Relation between Trainability and Dequantization of Variational Quantum Learning Models"
A BACKGROUND ON QUANTUM COMPUTING AND PARAMETRIZED QUANTUM CIRCUITS
Basic linear algebra lends itself nicely to formally discuss quantum computing. For further details, Nielsen & Chuang (2000).
Quantum states can thought as generalizations of probability distributions over complex-values fields. First, discrete probability distribution can be represented set all discrete probability distributions corresponds to the space of all diagonal matrices with positive entries and unit trace. In particular, these matrices are always positive semi-definite (PSD). Next, we can drop the requirement that matrices be diagonal, and we are left with quantum states p: Hermitian, PSD, unit-trace matrices,
diagonal matrix. Then, the
P E Herm, p = 0, tr(p 11
(A.1)
Hermitianity imposes real-valued diagonals, so the diagonal elements of quantum state always form discrete probability distribution. Further, the off-diagonal terms correspond to correlations that become relevant if one considers transformations of quantum states. The set of quantum states over qubits corresponds to matrices of dimensions 2 x 2 Similarly, if we talked about classical bits, we would consider the space of probability distributions over bitstrings of length n, also 2n. dimensional. We reach quantum observables if we further drop the requirements of unit-trace and positive semi-definiteness. So, the set of all quantum observables over n qubits is the set of all 2n 2 Hermitian matrices.
Quantum observables, as their name indicates, correspond to observable properties of the quantum states, direct generalization of observable properties of discrete probability distributions. Math- ematically, the expectation value of a given quantum observable M with respect to a quantum state p is captured by the Hilhert-Schmidt inner product of the corresponding matrices (M) tr(pM) (there is no dagger due to the Hermitian property).
One way to conceptualize quantum computers is machines that have fixed initial quantum state Po and fixed quantum observable Mo. together with a set of possible operations 24 with which furbish circuits. For instance, the trivial circuit would give rise the value tr (r) In a simple formulation, the allowed quantum operations map quantum states to quantum states as P + Upit for U E U, where 2 a subset of the special unitary group U S SU(2"). Then, quantum circuit with G gates (Ug)= where Ug E U, gives rise to the real value tr ((UGUGG-... U1 .......U U. Mu3. We could call this a function from sequences of gates of length to the reals u + R.
For Parametrized Quantum Circuits (PQCs), we include parametrized gates in the set of allowed operations. These are operations specified by a single number w + U(w) E u. A sequence of gates now involves both parametrized and non- non-parmmetrized gates. This is how obtain a parametrized quantum state p(w), where the actual transformations we apply to the initial state Pu are ultimately specified by the values of the parameters w. A PQC gives rise function from real vectors real numbers in that, after fixing the circuit layout, we obtain a different real value for each choice of parameters. This is where we have the chance of deciding the role of the parameters, be either the input x, or the trainable ones 3.
B MOTIVATION AND LIMITATIONS OF THE DEFINITIONS IN SECTION 2
B.1 KERNEL-BASER BASED HYPOTHESIS FAMILIES FOR ML
Given quantum feature map I + p(x), corresponding quantum kernel k(2,x') (((p()) and training set S = {(x,, v:) MM 1 usual kemne--baee training algorithms output functions of the form (x) Σ ozk(,, Accordingly, the hypothesis family of such model must be the
15

---

Published as a conference paper at ICLR 2025
set of functions that can result from every possible training set Us) A(S) _ Fp. In general, these are all functions of the form ()) for any Hermitian matrix M. Said otherwise, the set of functions realizable via quantum kernels is the set of linear functions of p(z).
Usual keseel training algorithms make use of the representer theorem, which states that the op- timal function in Fp to fit the training data lives in the span of training set fa (z) = Σi= a,k(z, x²). This way, the training algorithm effectively constructs a subset of functions within the hypothesis family, specified by the training set. This way, while the training algorithm sets up optimization task involving N parameters, the hypothesis family itself remains of dimension exponential in the number of qubits.
B.2 TRAINABILITY
Our guiding principle is propose definition of trainability that captures practically relevant see- narios. For example, we should conclude that deep neural networks are often trainable. At the same time, precise definition cannot ignore the fact that finding global optima of even simple learning models NP-hard and too much to ask for (Pfister & Bresler, 2018), as we elaborate shortly. Recall that we refer to "a learning model" AF, as a pair formed by a hypothesis family F and training algorithm A. We discuss notions of trainability that involve both at the same time. Consequently, we want to capture the notion that a learning model is considered trainable if the solutions within F found by A are good enough. Two aspects need be pinned down: what does good enough mean, and which tasks should the solutions be good for.
Venturing a naive definition like "a model is trainable if the learning algorithm solves every given task perfectly" runs into fundamental issues: under this definition no model can ever be trainable due to the no-free-lunch theorem (Wolpert & Macready, 1997), which guarantees that for any model there is at least one learning task in which it must fail. We could next lower the requirement from "the learning algorithm solves every given task perfectly" to "the learning algorithm solves every given task approximately". meaning "the performance of the hypothesis reached by the learning algorithm R(A(S)) is approximately optimal within the hypothesis class R(A(S)) R(f)), for any task D Under this definition we know that neither classical neural networks nor PQCs already of logarithmic depth can be trainable, unless P NP (Bittel & Kliesch, 2021). Hence must relax the assumptions further. Responding with a more relaxed definition like "a model is trainable if there exists a learning task for which the learning algorithm outputs an approximately optimal hypothesis" results in too weak a notion for which all models are trainable, as another consequence of the no- free-lunch theorem. Basing the definition on reaching locally optimal solutions no help either, as there are models for which almost all local optima are guaranteed to be as bad as random guessing (Anschuetz & Kiani, 2022), so there would be models which are trainable under this definition, but which always output bad solutions. Many known QML models display mostly bad local minima, and it is a still poorly understood miracle of deep learning that this it so often not the case there, where empirically good local minima seem to be easy to find. To avoid these problems, we decide to work with a context-dependent notion of trainability.
Definition 1 deskndee trainability). Given a suite of learning tasks of interest {(Dr, R,) }. a learning model (F, A) is trainable if the following holds for each task: the empirical risk of the hypothesis produced by the learning algorithm is close the optimal one within the class Rs(A)() Rss( with high probability with respect to training set S of polynomial size being sampled i.i.d. according to D.
The main limitation of this definition is that it can be difficult to apply in real-life scenarios. Indeed, knowing the performance of the empirical risk minimizer is a necessary condition for assessing the trainability of learning model under this definition, which can be difficult. Also, for broad applicability of the definition, one would like to decide whether a model is trainable without having to train it, in order to efficienlly decide between different models to use.
Being careful, we must not call this hypothesis family, hecause of its training-set dependence.
16

---

Published as a conference paper at ICLR 2025
B.3 BARREN PLATEAUS
The Barren Plateau (BP) (McClean et al., 2018) phenomenon appeared in the literature of Varia- tional Quantum Algorithms (VQAs) (Cerezo et al., 2021b; Bharti et al., 2022). The main idea for VQAs to tune the control parameters of a parametrized quantum eircuit with a hybrid quantum- classical optimization loop. Such an approach requires computing gradients of the function to be optimized. The boon of this approach is that one has access to the large Hilbert space of quantum computing via self-adjusting classical control knobs. The bane of this approach is that for large systems, the gradients become smaller than the available quantum machine precision. Plenty of lit- erature has been devoted to charting the space of VQAs as to whether they suffer from BPs, ways to avoid BPs, and sharpening the analytical tools required to diagnose BPs (Larocca et al., 2024).
One can think of QML special case of VQA, where the function be optimized happens to also depend on training data. Still, the common definition of BPs anticipates a scenario where there are only optimization parameters. We would like to introduce a definition of BPs that is applicable to any parametrized learning model', be it quantum or else. For this reason, we introduce notion of BPs that relies on the concentration of measure: functions coming from the same parametrized hypothesis family should concentrate to the same function even if they are realized from different parameter specifications.
Definition 2 (Barren Plateaus in Machine Learning). The parametrized hypothesis family F == {fol 1 E } has a Barren Plateau with respect to the parameter distribution P and the data distri- bution D if the function values concentrate exponentially in the following sense:
E Var
[Fo(to)] E ((exp(-n)), Goup
(B.1)
z>-Dx
where Var is the variance with respect to the parameter distribution P, and Dx is the marginal distribution over X arising from the problem distribution DD
Indeed, this definition fulfills the two target properties: it captures a concentration phenomenon, and it can be applied to any parametrized learning model. The operational meaning of this definition changes depending on the type of the ML model, though. We set this definition so that the moral of the story remains the same: if ML model exhibits BP in this sense, then there may be obstacles preventing trainability via usual methods.
Discussing whether kernel-based QML models have BPs highlights their fundamental differences from other variational QMI models. As introduced in Section 2, the hypothesis family F, of model based on the quantum kernel arising from p(x) the set of real-valued linear functions of p(x). Then, for us to ask whether F, has BP, must provide distribution over the space of Hermitian matrices. This requirement already diverges entirely from the typical pipeline of kernel methods for (Q)ML.
For instance, the uniform distribution over all Hermitian matrices of bounded norm would result in exponentially small function values independently of p(z). That does not mean that the output functions of kernel-based training algorithms are exponentially concentrated expectation. Rather, this highlights that Barren Plateaus do not affect all possible forms of training.
The work of Thanasilp et al. (2023) performs a similar analysis. By introducing the concept of vanishing similarity (a concentration of the kernel function over random inputs), they offer a plat- form to study the learning dynamics of gradient-based training algorithms. Here we concentrate on the hypothesis family, and not on the data-dependent function family produced by the training set. We note that there could be different natural definitions of BPs for QML, and that specifically for kernel-based hypothesis families the presence of BPs would be very sensitive to small changes in the definitions.
Notice that under our definition, hypothesis family with only constant functions would not have a BP as long as the value of the constant has a high variance with respect to the model parameters.
'Recall that we defined parametrized learning models those whose functions specified by at most polynomially-many real values.
17

---

Published as a conference paper at ICLR 2025
B.4 DEQUANTIZATION AND SIMULATION
We give definition of dequantization that is task-dependent, and is set aside from common defini- tions of circuit simulation. The guiding principle was to lay out the scenario which one would not need quantum computer in order to solve learning task.
Definition 3 (Dequantization in QML). Given suite of learning tasks of interest {(D,, R.),), QML model AF is dequantizable if there exists classical hypothesis family Fc and learning algorithm Ac, such that the following holds for each of the learning tasks; given a training set S ~ DN, the performance of the classical learner is approximately at least good as that of the quantumm learner: R(Ac(S)) S R(A(S)).
The alternative would be the scenario in which one does not need to use quantum computer to evaluate expectation values.
Definition 4 (PQC simulation). A PQC-hased function family FQ is classically simulable if there exists classical poly-time algorithm which approximates fa(x) good precision given 1 and x.
As justification,, we saw that there is gap between these definitions in Section 3.
A limitation of this definition is that it could allow for very powerful learning models to be dequan- tized for relatively easy learning tasks. Indeed, if we started from learning tasks which a classical model can solve approximately optimally to begin with, then every all all-powerful learning model immediately dequantizable for those learning tasks, even if the classical model is completely unrelated to the structure of the all-powerful model. This is in contraposition for instance to the dequantization techniques proposed by Tang (2019), where a clever classical data structure was able to dequantize the proposed QML approaches by replicating their information processing pipeline. Conversely, we would say "the DLP kernel has been dequantized for the DIPP-ased learning task" already if we found ing would be done by a completely different classical method, and not necessarily a kernel-based one. Thus this definition spans also a gray area housing counter-intuitive true statements. This is not to our detriment, as it is our manifest intent to consider broad definitions that could be further specialized posteriori if needed.
efficient classical algorithm for the discrete logarithm, in which case learn-
C FURTHER DISCUSSION ON TRAINABILITY AND DEQUANTIZATION OF EXISTING QML MODELS
In this section we first provide a deeper discussion on the two models that appear in our results: quantum kernel linked to the Discrete Logarithm Problem (DLP) Liu et al. (2021), and the Hardware Efficient Ansatz (HEA) Kandala et al. (2017). At the end we comment on how other existing QML models fit our categories of trainability and dequantization.
C.1 THE DLP KERNEL.
Liu et al. (2021) used the classical hardness of the Discrete Logarithm Problem (DLP) to show quantum-classical separation in learning. They designed learning task that cannot be solved by any classical learner according standard cryptographic assumptions. They showed that the same task could be solved using general- purpose quantum kernel, which we call the "DLP kernel" from general-purpose now on. We next analyze the DLP kernel in terms of its trainability and dequantization. For further details on the DLP kernel we refer readers to Liu et al. (2021). Additionally, Appendices B and E contain thorough discussions on BPs and gradient- baaed trainability specifically for kernel methods.
First, the DLP kernel is trainable because the representer theorem guarantees that all kernel methods are trainable (Schölkopf & Smola, 2002). For instance, using a Support Vector Machine (SVM) we obtain the actual minimum of the empirical risk. Also, Thanasilp et al. (2022) identified that kernel- based ML models could suffer from a phenomenon similar to BPs, dubbed vanishing similarity, the kernel function k(x, x²) is exponentially close 0 almost everywhere. In Liu et al. (2021) see that the DLP kernel takes non-trivial values, so the DLP kernel does not suffer from vanishing similarity.
18

---

Published as a conference paper at ICLR 2025
In addition, the learning-theoreiic results from Liu et al. (2021) guarantee that no classical algorithm can solve the same learning task as the DLP kernel efficiently. This proves that the QML model based the DLP kernel is non-dequantzable. The latter argument says nothing about simulat- ing the corresponding circuit directly, but since simulable = dequantizable with a classically-easy training algorithm (like SVM), it immediately follows that non-dequantzable- = non non-simulable.
It thus follows from prior work that the DLP kernel is both trainable and non-dequantizable.
C.2 VARIATIONAL QML WITH THE HEA
The Hardware Efficient Ansatz (HEA) (Kandala et al., 2017) is a circuit template for universal quantum computation. The HEA is composed of sequential layers that respect the lower-level con- nectivity of the computing platform. A particularly well-studied version is the 1-dimensional HEA, where qubits are organized in a line and each qubit is only connected to its nearest neighbors. Such 1-dimensional HEAе² give rise to deep-layered circuits, where each layer is column of 2-qubit gates, and consecutive layers alternate between even and odd connections. HEA is a natural sub- strate for variational QML models as introduced in Section 2: first prepare parametrized state p(2; i0) and next measure a fixed observable M. For further details on the HEA we refer readers to Kandala et al. (2017), and specifically to Cerezo et al. (2021a) for a discussion on its Barren Plateau analysis. Importantly, the free parameters of 9 are typically trained variationally, via an iterative local optimization procedure. We next characterize the trainability and potential for dequantization of HEA-based QML models.
Cerezo al. (2021a) showed that HEAe can have BPs under the uniform distribution of parameters due to their generic structure. In parallel, empirically HEAe have defied being trained (Kim et al., 2021). A special case that of HEAe based on shallow PQCs, of up to logarithmic depth. Cerezo et al. (2021a) proved that shallow HEAe do not have BP when the observable is local (it acts only on a few qubits). Similarly Basheer et al. (2023) showed that HEAe are classically simulable provided the circuits are shallow and the observable is local. Thus, together with a classically- tractable training algorithm, shallow HEAe with local observable are dequantizable. Crucially, while generic HEAc of linear depth or shallow HEAe with global observables are not classically simulable, training them by usual means is expected to be difficult due to BPs.
Indeed, the same conditions that ensure absence of BPs in HEAe also allow for their dequantization. Intriguingly, this is not an isolated case: Cerezo et al. (2023) shows that for most PQC Ansätze for which we have proof of absence of BPs, we also have proof of classical simulation. This hints at larger question: Does absence of BPs imply classical simulation for all variational quantum circuits? The answer is negative in general, as one can construct contrived counter-examples (see Appendix B of Cerezo et al. (2023)). Still, the question of absence of BPs versus classical simu- quantum optimization problems is not fully resolved. Comprehensive
lation in naturally-occurrin sufficient and necessary conditions for absence of BPs to imply dequantization are not yet known.
Also, the question of trainability versus dequantization of variational QML models has not been previously addressed.
C.3 OTHER EXISTING QML MODELS
We again separate two types of QML models: those based on kernel methods and those based on PQCs with local optimization methods.
For kernel-based models, the discussion in Thanasilp et al. (2022) covers most of the ground. They explain that trainability is not a central issue in kernel-based MI., both quantum and not, as the training algorithms used in practice ability of the training algorithm to output a close-to-optimal solution with respect to the empirical risk. is generally true that kernel-based (Q)ML models fulfill this condition, so they are generically trainable. Regarding dequantizability, not many results have proven quantum advantage in learning using kernel-based model beyond Liu al. (2021) and Huang et al. (2021). An alarm raised in Thanasilp et al. (2022) is that, for QML models based on generic quantum kernels, one expects an alignment between "lack of vanishing similarity" and classical simulation of the PQC. In this case
empirical risk minimizers. We defined trainability as the
'The plural of Ansatz is Ansätze.
19

---

Published as a conference paper at ICLR 2025
lack of vanishing similarity is linked to good generalization performance, so the off becomes between generalization and non-dequantization which is also negative. It remains an open question whether the ceneral-purposs DLP kernel is the only one which formally fulfills both trainability and non-dequantization.
Most existing variational QML models can be seen special cases of the HEA, where different models arise from different choices of which gates are fixed to be data-dependent, and which gates are left open for their parameters to be optimized. In this sense, one would expect generic variational QML models to suffer from BPs whenever the HEA they are based on suffers from a BP. This effect could be mitigated either by considering very specific circuit structures, or by turning several gates completely off, or by introducing correlations between the parameters that would break the i.i.d assumptions the theorems that diagnose BPs. This way, regardless whether encoding first (Farhi & Neven, 201 2018), data re-uploading Pérez-Salinas et al. (2020), or flipped models Jerbi et al. (2023), the trainability of variational QMI. models could be thwarted by the propensity of HEA to suffer from BPs. The picture is similar for dequantization: if the underlying PQC is classically simulable, then generically the resulting QML is also simulable, relatively independent of the type of variational QML model at hand. A potential cure against BPs is the fact that the data distribution is unknown. Parametrized function families have BPs according to a specific distribution. In supervised learning, typically assume the data distribution is fixed but unknown. So, formally this means that cannot establish analytically whether a variational QMI. model suffers from BP unless we impose certain assumptions on the data distribution. Noteworthy is also that recent works have specialized the study of BPs to data re-uploading circuits (Barthe & Pérez-Salinas, 2023; Mhiri et al., 2024), via the Fourier picture introduced in Schuld et al. (2021).
D PROOF OF PROPOSITION
Here we restate and prove the proposition in Section 4, using the definitions for trainability and Barren Plateaus (BPs) introduced in Section 2.
Proposition 1 (Trainability with Barren Plateaus). There exist QML models which have BPs un- der the uniform distribution of parameters and are trainable for learning tasks that are classically intractable under standard cryptographic assumptions.
Proof. We prove the statement directly by giving an example. Consider the DLP kernel kDLP( x²) tr(p(z)p(=')) introduced in Liu al. (2021). Given a training set v:)), consider the set of functions resulting from using the representer theorem:
N
F& fa(z)= Σ ag tr(((())((a)) a GERN
(D.I)
To evaluate fx), typically evaluate each overlap tr(p(z)p(z;)) separately and then sum. We could instead evaluate it all at once with a single circuit, using the Linear Combination of Unitaries (L.CU) formalism (Childs & Wiebe, 2012). Here, corresponds to a mixed quantum state, which we express as a classical mixture of pure states explic- itly. In this way, we do not take advantage of the interference phenomena that LCU usually allows, but rather use it to create a linear combination of states.
LCU to design a circuit whose observable
We consider the parametrized observable M(a, - a,p(2;;) and we recognize we can implement it as an LCU circuit. On the one hand, we prepare the state (a) E, on an auxiliary system. W.L.o.g. the vector a can be taken to be appropriately normalized. On the other hand, we consider the data-dependent unitary gate V(xr) that gives rise to the quantum embedding Then, we construct circuit in which, after (a) has been prepared, apply (x;) the work register, controlled on the auxiliary register being in state It). We initialize the computer to be on the all (0) state, then evolve it to become (a) @ V (z)))),, then apply the controlled-V (x:;) gates, and finally measure the projector onto 10) on the work register and diagonal observable that takes care of the signs on the auxiliary register. The resulting expectation value is the same for the kernel method (r(((x))))))))()()(())) M(, (2x).)) (x).
p(x) = ((=))0)(()//(())
In the LCU circuit, some gates are 1-qubit trainable, and some gates are 2-qubit fixed, but we have an efficient description of the whole circuit. Next, rewrite all gates 2-qubit arbitrary gates,
20

---

Published as a conference paper at ICLR 2025
with a given known parametrization, from which we can recover the LCU circuit explicitly. The 2-qubit gates at this step must observe a 1-dimensional connectivity graph, so each qubit may only be connected to adjacent qubits. This means that any non-local 2-qubit gate must be compiled as linearly many local 2-qubit gates. Organize all gates in non-commuting layers, and complete any layers with new 2-local gates, overall resulting in a deep-layered brickwork architecture. This step includes also the encoding gates required to prepare p(r), where possibly-discrete gate set is compiled with the continuous set of arbitrary local 2-qubit gates.
We call 0 the parameters of the brickwork Ansatz, for which, crucially, we have an efficient spec- ification (a: (x:);) + e such that we recover the LCU kemel--baee parametrized observable. We choose not to write (a;; (2z)4) for ease of notation. The depth of the circuit is at least linear in the size of the training set, and also at least linear in the required complexity of preparing p(x). The observable we measure at the end is global: it consists of a collection of Pauli-Zs and projectors onto the (0) state on all qubits. Then, from Cerezo al. (2021a) we know that this quantum circuit has a BP under the uniform distribution over 0, as it is an instance of the HEA with linear depth and global observable. Crucially, this Ansatz has a BP with respect to the circuit parameters 0, and not the free parameters of the kernel-based functions a, which just a subset of the entire function family, and have a very particular parametrization associated to it.
Nevertheless, from Liu et al. (2021) we know this model is capable of solving learning task based on the DIP which is assumed to be hard for any classical learner. The reduction from this model onto that of Liu et al. (2021) needs only that we fix the parameters to recover the LCU circuit. So, the learning algorithm we use takes two steps:
1. Use the KDLP and Support Vector Machine (SVM) reach the optimal a* vector, which we know actually solves the problem as explained in Liu et al. (2021).
2. Set the parameters 1 of the brickwork Ansatz to recover fo- (xx) as an LCU circuit.
The solution we are left with for satisfics the requirement of the proposition: is trainable, in the sense that there is a training algorithm with which it solves a task of interest; and it has BP, in the sense that the cost function concentrates exponentially with respect to the uniform distribution of the circuit parameters. Crucially, say the model is trainable because, even though the hypothesis family generated by the brick layered Ansatz is strictly larger than that generated only by the quan- tum kernel, the representer theorem guarantees that the solution found by SVM is optimal over all linear models, of which anything generated by the layered Ansatz is a special case. This completes the proof.
We note the same strategy would not necessarily follow from any arbitrary trainable circuit: in the sense that just compiling a trainable PQC into a deep-layered brickwork Ansatz because the added functions might give rise to better solution to the learning task. It could be that by making the hypothesis family larger, what used to be a good-enough solution for the smaller model stops being close to optimal for the larger model. For this step to still work, we must exploit some guarantee of optimality like the one given by the representer theorem.
The goal of this result is to reinforce the difference between the notions of trainability that we introduce in this work and its proxy, Barren Plateaus. Prop. only points out that trainability and BPs are phenomena of different nature.
E GRADIENT-BASED TRAINABILITY
Trainability as introduced in Definition 1 is very broad, since it allows for unconventional training algorithms unused in practice. We introduce gradient-based training algorithms with the goal of reaching more stringent notion that relates to currently used training algorithms (Cerezo et al., 2021b; Bharti et al., 2022; Nietner, 2023). In the language of Section 2, for a model (F,A) to be basedd trainable, it needs to be trainable according to Def. 1, and the training algorithm A needs to be a gradient- based. This section introduces and motivates gradient-based training algo- rithms and discusses the relation between bradient-based trainability and BPs.
21

---

Published as a conference paper at ICLR 2025
We draw inspiration from the well-known Gradient Descent (GD) algorithm, which requires an initial specification of parameters, and uses the gradient of the empirical risk with respect to the parameters V (fo). In GD an initial parameter specification typically sampled from a distri- bution P over the parameter domain +. Then, parameters sequentially updated in the direction opposite the gradient V (Jo)( to minimize the empirical risk. The partieular parametrization & + fo is relevant, as different parametrizations of the same hypothesis family give rise to different gradients, and thus to different outputs using GD (Wiersema et al., 2024). This way, whether GD produces a good output from a hypothesis family F depends not only on the task (D, R), but also on the initialization distribution P. and the specific parametrization.
To paint concrete picture, we offer an algorithmic description of a general gradient-based training algorithm in Algorithm 1. The following example retains the central role of both: the initialization distribution P and the specific parametrization of F
Algorithm 1 Gradient-based training algorithm.
Input: F = (ʃo 6)
D Parametrized hypothesis family.
Input: Rs(fs)
D Empirical risk functional.
Input: P(e)
Parameter initialization distribution.
Input: C(B) + (VoRs(fa),
b Learning rate.
Output: 1 E θ
D Trained parameters.
1: Og ~ P
> Sample initial parameters
2: for in {I,..., T) do:
3:
V O, + 0. + C( VoRRs
Update rule.
4: end for
5: return 0T
An important restriction of gradient- gradient-based training algorithms is that they should not be allowed to evaluate the empirical risk corresponding to arbitrary parameters O. Rather, the algorithm should start from random initial specification On ~ P, and then only be allowed to iteratively select new parameters which are geometrically close in parameter space. This why we limit the algorithm to only take steps in the direction of the gradient, up to an adaptive learning rate C(Ø). We prevent more complex algorithms to hide inside this update rule by restricting the allowed functional form of C(0), which at step t may only depend on t, (o..).o.). and Ha (Rs(fo.)), where Ha denotes the Hessian.
We note that a parameter distribution P already played a central role when introducing Barren Plateaus (BPs) in Def. 2. Gradient-based trainability and BPs are clearly deeply related: if the model has BP according to the distribution P, then the value of all functions concentrates expo- nentially with high probability over P. and so the gradient becomes exponentially small with high probability over P. Having exponentially small gradients signifies a much harder problem for QML than for classical ML models. For QML models, the available precision only polynomial in the total quantum runtime (or said otherwise, exponential precision requires exponential quantum time). Conversely, for classical MI models, precision is exponential in the number of bits of memory, and the total runtime is polynomial in the number of bits, so exponential precision is within budget. All together: having exponentially small gradients already represents a problem by itself, as the time to convergence could be exponentially long. But furthermore, for QML models we would not be able to resolve the exponentially small gradients in polynomial time, so exponentially small gradients are statistically indistinguishable from 0 gradients.
We next briefly comment on the gradient- based trainability of learning models based on quantum kernels. The defining factor of these learning models is that the training algorithm uses kernel-based techniques. Kernel-based training algorithms invoke the representer theorem to build an effective, data-dependent function family over which optimize few parameters. Since this step is not in-
'There exist non- con-gradient-oo gradient-based methods which share these features, like genetic or evolutionary algo- rithms, which we could have also included in even more general family. We decide against more general notion for the of presentation.
22

---

Published as a conference paper at ICLR 2025
cluded among the allowed operations of gradient-basee training algorithms, it follows that in general these models are not gradient- basedd trainable.
Said differently, kernel-based training algorithms first restrict the search space to a subspace given by data, and then optimize within the subspace. Often, this second optimization can follow the gradient- based prescription, which would be efficient. However, the first step (restriction subspace) is something other than "random parameter initialization plus local optimization". In all, even though kernel-based training algorithms could have gradient-based optimization subroutine, we demand for an algorithm to be end-to-end gradient based in order to qualify for our definition.
data-dependent
As we introduced, the hypothesis family of learning models based on quantum kernels is the set of linear models of the feature map (r(r for M E Herm. On the one hand, usual risk functionals could be convex in the space of linear models, which would in principle open the door to gradient-based trainability. On the other hand, the expected runtime of such an algorithm would be least linear the dimension of the space. Given that Herm is of dimension exponential in the number of qubits, these models are in general not efficiently gradient-based trainable.
In general, may well be that a given parametrized learning model has a BP or gradient-based trainable under given distribution, but the same statement is not true for the same model under different distribution. For this reason, the presence of BPs and the gradient- given parametrized learning model should always be discussed with respect to the same parameter distribution P. In particular, it follows that, for the same distribution P, a model that has a BP cannot be efficiently gradient- praseent-based trainable. In this direction, new research trends ask about specialized parameter distributions to improve the gradient- based trainability of variational QML models, under the name of warm starts (Puig-i-Valls et al., 2024).
trainability of a
As a closing remark, the importance of the initialization distribution is intuitive when discussing Neural Networks (NNs). Improvements in initialization have brought about major steps in the de- velopment of successful NN-based ML. This way, our definition of BPs for ML also captures the vanishing gradients problem of NNs (Hochreiter & Schmidhuber, 1997), strictly from the lens of the initialization distribution (and not from the lens of the activation function, normalization, regu- larization, or residual activations).
F PROOF OF THEOREM 3 AND COROLLARY 4
We first re-state and prove the results from Section 4.2, and next we briefly discuss their relation to the construction in Appendix B of Cerezo et al. (2023).
Theorem 3 (Existence of trainable and non-dequantizable QML models.). Let X {0, and Y = 1). Let Q(x) be a function in BQP and not in HeurBPP under a given distribution Dx. and let Uxx) be a unitary such that (0)U² (x) (z)))))))) = Q(x). Let H be Hamiltonian, and (D)) parametrized unitary for which the following optimization problem can be solved with a given gradient- based algorithm Aw:
0- + arg max [0) (0) DEB
(F.I)
and such that maxage (O) (0)0) 1. Call (())&W(0), and M 2, HH, and consider the corresponding hypothesis class Fo:
Fq = (fa()) (0)V (MM 0)) 1 e O).
(F.2)
Let 'D specify a learning task: D(I, Dx(x))(y ((())))(((()))
Then Fo is gradient-based trainable for DD and it is not dequantizable.
Proof. As explained in Gyurik & Dunjko (2023), for Q 20. 1} - 10,1} to not be in HeurBPP/ /poly. Q must be hard to evaluate and learn classically from examples. That means, that given polynomially many input-out pairs, no classical algorithm can evaluate it classically with probability larger than 1/2 + 1/ //pol(() over x ~ (x) This could be for example the most significant digit of the discrete logarithm of according to known basis. Based on Q(x), can consider a binary classification task in which each integer x is assigned a class y(x) E {+1} depending on Qxx), by identifying the outcome measurement O with class 11
23

---

Published as a conference paper at ICLR 2025
In parallel, we have the optimization task of finding the highest energy of H by optimizing the parameters of V()), which is assumed to be efficiently solvable.
Then as supervised learning task. consider training set S = {(z,, ()) where Dx(x) and yi = 1 if (x) = 1, y/ = -1 (x)) = O. The hypothesis class FQ we consider is = (f) [0lV (z; MI; 0)(0) 1 @
(F.3)
We consider the problem solved when we find hypothesis specified by parameters &sal for which it holds that
f(x; (sa)) = =(x)
(F44
with high probability over Dx(x)) Using the training set we have access to, and using the mean squared error, we are left with the following optimization problem:
sot arg min
-))
(FF.)
2N
min
(F.6
2N
arg min
{
(F.7)
2.N
arg min
{
(000 yx11
(F88)
2.V
arg min
[x:0))(0) -
(F.9)
2N
arg min
(O) 1)
(F.10)
2N
arg minn (imiii(n(((()))))) (O)) 1)²}
(F.11)
= arg max (O) 0"
(F.12)
9
(F.13)
We see that the solution of our classification problem Peal is the same as the solution 0* of the optimization problem based only H and (U)), which can be solved by the given training algo- rithm Aw by assumption. Because we assumed the optimization problem to be efficiently solvable by gradient-based optimization, it follows that our binary classification problem is also efficiently solvable by gradient- based optimization. Here, similarly to Prop. 1, we took a trainable model and added more ingredients to it to make it look difficult. But, in the end, training our model to fit data according to the function Q is as easy as training the simple quantum state optimization task, so the model we proposed is gradient- based trainable. Still, the same task cannot be solved by a classical model because that would imply a classical algorithm being able to evaluate Q(z), which we ruled out by assumption.
Corollary 4 (Existence of trainable and non-dequantizable vari veryational QML model.). There exist vari veryational QML models which are gradient- based trainable and non-dequantizable with any number of layers up to sub aab-epponentially many the number of qubits.
Proof. We prove this statement by giving an explicit example of vari veryational model that ful- fills the assumptions of Theorem 3. The model corresponds to a tensor product of two PQCs, one corresponding to the hard computational task of evaluating Q(r), and one corresponding to the easy optimization task corresponding to and (0)).
We start with the computational part, where we have the unitary U(x) which implements the classically-har hard function Qz)). From Uxx), we must construct a layered circuit where all lay- equal, and which still produces ((x) when Pauli Z is measured the first qubit, at
24

---

Published as a conference paper at ICLR 2025
the end. To achieve this, consider auxiliary register made of E N qubits and consider an integer-adder t-qubit unitary gate A whose action on the computational basis is to add modulo 2': Alb) = bb + mod 2*). Then, we define the (n + t)-qubit unitary (z) as a sequential two-step process:
1. Implement U (2) on the first n qubits conditioned on the extra & qubits being in state (0).
2. Apply A on the working qubits.
With this, the action of (2x) on the (n + 1) qubits is:
{x)))0)b) (Ux)) 0000 0)) 1 mod 2*).
(F.14)
Here da is the Kronecker delta, which equals if a = and is 0 otherwise. In particular, for the first n qubits, (xr applies Uxx) if 0, and does nothing in any other case. Also, follows that
(1))010)10 = (U(x))L/2))))))) [0) mod 2¹). And, in particular, 10)) - (U(z) 0)) L) for any L < 2'. That means, when using (0) as the input state for both registers, applying (xr L
times in sequence has the same effect on the first n qubits only applying once, given than L is
not exponential in t. So, provided the number of layers is subexponential L. < 25, it holds that
& (x)100) (x))
(o)o)((=)) & (=)(0))))0)
(F.15)
(0]U(x)) (1U())
(F.16)
Q(x).
(F.17)
For the easy optimization task, we could take any Hamiltanlnnn combination that we know to be trainable and deep-layered. For this proof, it is enough to pick a very simple one. We can take the single-qubit observable H = Z, and the layered Ansatz W (d) = 11 Rx(ú;). With these, it follows that initializing & uniformly at random and then performing gradient descent is enough to solve the optimization task. Since the highest-energy state of Z already the initial state (0), this optimization problem reduces to finding a specification of 0 fultilling Σラ= 0z M,, for any M E Z, since Rx forms a (1) group and Rx (x I up to global phase for any M E Z. This optimization problem easy regardless of I., so in particular it also works for T. 2
All together, the PQC we are considering consists of I. layers uniformly repeated:
Fo = (fo(z) = (0)V MV 0) 0 E O}
(F.18)
1.
Va;; = II (()) & Rx(O)).
(F.19)
2=1
We have seen that this PQC fulfills the assumptions of Theorem 3 and it also fulfills the defining requirements for QML model to be vari veryational from Section 4.1. This completes the proof.
Both this construction and that of Cerezo et al. (2023) leverage a hard computational task to make statement about trainability and dequantization. In both cases there is an encoding unitary which, upon measuring Pauli Z on the first qubit, evaluates a specific function of bitstrings to a single bit. The quantum function is chosen ensure that no classical algorithm can evaluate it, even when given advice.
The main difference is two-fold. On the one hand, we pose a learning problem and a model that can solve it, and not just a computational problem. At the same time we also propose a learning algorithm that ensures that the quantum algorithm actually solves the task. On the other hand, we force ourselves to work with so-defined vari veryational models, which rely on deep-layered variational circuits, as opposed to the circuit constructed in Cerezo et al. (2023). That being said, a valid criticism of our construction is that the way in which we turn computational task into learning task is almost trivial. The trainable component of our circuit is detached from the encoding part, and it only appears as multiplication factor independent of the input. Indeed, our proof does not educate us on how to design PQCs for QML, but rather it is the minimal construction necessary to prove the statement.
25


Reviews:
[{"review_id": "6YEsNeQVmr", "reviewer": "Reviewer_K1hL", "summary": "This paper discusses and clarifies several important concepts in quantum machine learning (QML), including trainability, simulatability, and de-quantization. Building upon the established concepts, this paper introduces a new family of \"vari veryational\" QML models, a spoonerism of \"very variational\", that capture the essence of deep-layered QML models and gradient-based training algorithms. It is shown that in this family of QML models, there exist non-dequantizable but trainable models. This resolves an open question that trainability and dequantization are mutually compatible.", "questions": "- What does \"gradient-based trainable\" mean precisely? Does it mean there is no barren plateau in the sense of Definition 2?\n- On page 2, the risk functional is defined over the space $\\mathcal{Y}^\\mathcal{X}$. Can you explain this notation, specifically, why the data domain $\\mathcal{X}$ appears as the power in the label co-domain $\\mathcal{Y}$, but not vice versa?\n- I am a bit uncertain about the name \"vari veryational\". Is there further justification for this name, besides it's a spoonerism of \"very variational\"? It feels a bit uninformative to the general quantum information audience.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes clear definitions for trainability and dequantization using a rigorous learning theory language. This clarifies the vagueness of many seemingly related but not equivalent concepts in quantum learning theory.\n- This paper constructed a QML model that is gradient-based trainable but not dequantizable (based on standard cryptographic assumptions).\n- This paper provides an extended discussion of several related results in the quantum learning theory (Figure 3).", "weaknesses": "- The QML model constructed in this paper seems a bit contrived. The construction is based on a computationally hard problem, and the proposed training method is quite specific and not able to generalize to other QML designs. I feel this construction is mostly of theoretical interest and has limited connection to practically relevant variational quantum algorithms.\n- Several definitions in Section 2 are quite formal and math-heavy, and it’s unclear whether such definitions are truly necessary in light of the paper’s main technical contributions. I feel the theoretical framework may be somewhat excessive relative to the provable results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1HbOEWgkcn", "reviewer": "Reviewer_1RRV", "summary": "This paper tries to establish a relationship between trainability and dequantization in the context of QML models. The authors present a formalization of these concepts and attempt to illustrate conditions under which these properties co-exist.", "questions": "- It would enhance the paper if the authors could offer insights or preliminary guidelines on designing QML models that are trainable, non-dequantizable, and very variational.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper commendably formalizes the concept of dequantization, linking several key concepts in QML models, including trainability, dequantization, and classical simulation. This integration provides a valuable framework for understanding QML models.\n\n- The paper is well written and concepts are explained clearly.", "weaknesses": "- From a technical standpoint, the paper's contribution appears limited, primarily synthesizing existing results rather than offering new findings. It attempts to establish connections between different unclear concepts but lacks significant technical contributions.\n\n- The discussion would benefit from a more detailed analysis of existing QML models to determine which categories they fall into. Such a comparison would enhance the paper's relevance and applicability in the field.\n\n- On the practical side, the paper falls short of providing actionable insights or guidelines for designing effective QML models, which limits its utility for practitioners in the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NnRhjLNLVO", "reviewer": "Reviewer_sYUX", "summary": "This paper formalizes the relationship between differing ideas in the QML literature regarding different aspects of learning QML models. With these formalizations in hand, the authors then prove that there exist variational QML models which are trainable and non-dequantizable.", "questions": "- If “de-” is the prefix for the reverse of something, can non-dequantizable just be “quantizable”?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Figures 1 and 3 are good, and help with reader comprehension\n- The paper is generally well written and understandable\n- The writing style especially is very approachable and the focus on explanation is beneficial to the paper\n- The coverage of recent literature is sufficient", "weaknesses": "- This paper seems to want to do two things. After introducing a new representational/formal scheme for QML, it wants to (a) show how other papers fit into this scheme and (b) use this scheme to prove novel results. However, in attempting to do both, results in both being weaker. If the paper were to lean into (a) and be more of a review paper (where the formalize in the synthesis of many previous papers) and give more examples of how the literature fits into this paradigm, it would be good. Or, if the paper were to lean into (b) and emphasize more the research power of this paradigm through novel theoretical contributions, that would also be good. To be concrete for this latter approach, this would largely involve moving 3.3/3.4 to an appendix.\n- Figure 2 and Table 1 seem to convey the same information redudantly\n- This paper is generally interesting and is a quality paper, but I question whether ICLR is the ideal venue for it and whether there is sufficient novelty of interest to this community\n- Not a major point, but the “vari veryational” term doesn’t seem ideal, both for speaking (sorry for the phonocentrism Derrida), but also for writing (with autocorrect/spell check). Maybe a different abbreviation would clarify better?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kfvHmR1VGj", "reviewer": "Reviewer_LzqN", "summary": "The authors address a pressing question in the field of quantum machine learning: do there exist \"variational\" (i.e., trained via gradient descent) quantum neural networks which are both efficient to train and also difficult to classically simulate? The authors answer this question in the affirmative, giving a general method for constructing variational quantum machine learning models with these two properties.", "questions": "What implications do the authors' results have on the construction of quantum neural network architectures?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The authors prove concrete, rigorous results, which are hard to come by in the field of quantum machine learning; this is particularly true of concrete quantum-classical separations in machine learning (where the quantum model is assumed to be efficiently trainable). The authors give explicit examples of efficiently trainable quantum networks with provable quantum advantages in learning over their classical counterparts.", "weaknesses": "The authors' Theorem 3 and Corollary 4---which give the recipe for constructing a learning problem solved by a quantum model efficiently trainable via gradient descent, but which is unable to be dequantized---essentially separates these two conditions out, considering a tensor product of two systems where one is trivial and easy to optimize and the other implements a quantumly-easy, classically-hard function, but is untrained. Because of this, it is difficult to know what broader impact this work has on the actual design of variational quantum algorithms (see Questions).\n\nA minor additional weakness is that the authors' proposed criteria for \"dequantizable\" focuses on the supervised learning setting; the unsupervised learning setting (e.g., sampling problems) may also contain concrete quantum advantages in an efficiently trainable setting, particularly with the current wealth of quantum experiments demonstrating a quantum advantage in sampling tasks (Nature 574, 505; Nature 626, 58).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)