On the Relation between Trainability and Dequantization of Variational Quantum Learning Models

Authors: Elies Gil-Fuster, Casper Gyurik, Adrian Perez-Salinas, Vedran Dunjko
Primary area: learning theory
Keywords: quantum machine learning, machine learning theory, quantum information theory

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1729784054824

thread_type:
official_review

<thread_object>
creator: reviewer_lzqn

<content>
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.

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).

A 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).

questions:
What implications do the authors' results have on the construction of quantum neural network architectures?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730241572909

thread_type:
official_review

<thread_object>
creator: reviewer_syux

<content>
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.

strengths:
- Figures 1 and 3 are good, and help with reader comprehension
- The paper is generally well written and understandable
- The writing style especially is very approachable and the focus on explanation is beneficial to the paper
- 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.
- Figure 2 and Table 1 seem to convey the same information redudantly
- 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
- 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?

questions:
- If “de-” is the prefix for the reverse of something, can non-dequantizable just be “quantizable”?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730443299046

thread_type:
official_review

<thread_object>
creator: reviewer_1rrv

<content>
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.

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.

- 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.

- 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.

- 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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694753853

thread_type:
official_review

<thread_object>
creator: reviewer_k1hl

<content>
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.

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.
- This paper constructed a QML model that is gradient-based trainable but not dequantizable (based on standard cryptographic assumptions).
- 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.
- 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.

questions:
- What does "gradient-based trainable" mean precisely? Does it mean there is no barren plateau in the sense of Definition 2?
- 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?
- 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731770652687

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updated submission, redline version

comment:
Dear reviewers, dear Area Chairs,

Following the advice from the reviewers, we have improved our manuscript by implementing a number of changes.
We have uploaded a redline version of our updated manuscript, where the main changes are highlighted in blue.

These changes have been prompted by specific comments from the reviewers, which we briefly summarize for reference:
 - First part of Section 2: We have streamlined the notation and the presentation of supervised learning, to clear the notational clutter and center on the relevant quantities for our analysis further below.
 - Last paragraph of Section 2.4: We have added a paragraph with a brief discussion of recent advances in random-circuit-sampling and unsupervised learning.
 - Section 3.3: This is a new section that contains only the critical parts of what used to be Sections 3.3 and 3.4. This section now references Appendix C for the extended discussion, containing what used to be Sections 3.3 and 3.4, as well as new discussions on how existing QML models fit in our formalism.
 - First paragraph of Section 4: Since this is a transition paragraph that quotes Section 3, we had to make small adjustments for consistency.
 - Third paragraph of Section 4.1: We have added a proper explanation about the relation between gradient-based trainability and absence of Barren Plateaus, which was missing in the initial submission.
 - Section 5: This is a new section, containing parts of what used to be Section 5, as well as new paragraphs discussing the nature and impact of our contributions.
 - Section 6: This is a new section, containing parts of what used to be Section 6, but especially serving the purpose of separating the summary from the discussion. We have added a paragraph with closing remarks about the broad applicability of our results.
 - Appendix C: This is a new appendix, containing what used to be Sections 3.3 and 3.4, as well as a new Section C.3 discussing how other existing QML models fit our formalization.

We hope this overview of changes aids in highlighting our earnest effort in improving our manuscript following the advice and comments by the reviewers, which we found invariably helpful and valuable.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates the compatibility of trainability and non-dequantizability in variational quantum machine learning (QML) models. The authors introduce the concept of "vari veryational" models, providing a theoretical framework and constructions that meet these two criteria. While reviewers raised concerns about the limited practical implications of the constructions, the focus on supervised learning, and the somewhat contrived nature of the proposed models, the work offers valuable insights into the design of variational QML models and advances understanding in the field.