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

We appreciate how reviewer LzqN highlighted the explanations of broader impact and missing literature links as areas of potential improvement. Prompted by these, we have added clarification text in Sections 2, 5, and 6. We believe these changes improve the overall quality of the manuscript, and hope the reviewer also sees it this way when evaluating our updated submission.

What implications do the authors' results have on the construction of quantum neural network architectures?

We presumably have already answered this question in our response to the Weaknesses. But briefly: we first remark that current design principles for the construction of variational QML models seem to be doomed, and based on this a clear implication is the possibility of using “classical hardness” as an explicit feature in the design of variational QML models. We recognize that it will require future work to design variational QML models that have a chance of being practically relevant, but we believe we offer a solid place from where to start.

We thank the reviewer for their positive and helpful assessment of our work. We believe this summary correctly identifies our core contributions in terms of resolving a pressing question and providing a general method for constructing variational QML models. It makes us very happy that the reviewer highlights the rigor of our results, which was a concrete goal for us while preparing this submission. In particular, we are pleased to contribute to the corpus of quantum separations in learning with variational QML models.

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

We agree with the reviewer that this was one of the least clear points in our original submission, as it was also raised by reviewers K1hL and to some extent 1RRV. We have added new Sections 5 and 6 to better discuss precisely the breadth and depth of impact of our work. For the actual design of variational quantum algorithms, we have avoided relating our construction to other pre-existing trends, largely because of the dire perspectives put forward in Cerezo et al. (2023). The current broadly-accepted opinion is that all generic variational QML models to date can be either trainable or non-dequantizable, but not both. For this reason, we concentrate on showing that there exist generic variational QML models that fulfill both those properties. One message to be drawn is: we likely need to rethink the design principles we had until now, since they result in an alignment between trainability and dequantizability. Another message, more direct, is: following our prescription we are guaranteed to check two important boxes: trainability and non-dequantization. This should inspire the community to look for other novel schemes that achieve comparable scores also for expressivity and generalization when compared to current approaches suffering from dequantization. Future work is needed to improve on our constructions, but our paper proposes footing from where to start building toward actual practical relevance.

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

We thank the reviewer for pointing this missing gap in the literature, we agree we should have mentioned this line of work in our original submission, and so we have added a paragraph in Section 2.4 commenting on trainability and dequantization of unsupervised learning, as well as a short sentence in the first paragraph of the new Section 5. The random-circuit-sampling problem has received a fair share of attention and has been formalized in Sweke et al. (2021). We then consciously chose to stay in the domain of supervised learning. It is still clear to us that we should mention unsupervised learning, for clarity and completeness.

M. Cerezo et al. Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing. arXiv:2312.09121, (2023)

F. Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574, 505, (2019)

D. Bluvstein et al. Logical quantum processor based on reconfigurable atom arrays. Nature, 626, 58, (2023)

R Sweke et al. On the quantum versus classical learnability of discrete distributions. Quantum, 5, 417, (2021).

We thank the reviewer for providing concrete feedback on improving the presentation of our text. Prompted by the question regarding ICLR being the correct venue for our work, we have improved the explanation of the nature and impact of our contributions in the new Sections 5 and 6. We are very satisfied with the updated streamlined version of our submission, and we hope the reviewer assesses positively the improvements they helped accomplish in the text.

If “de-” is the prefix for the reverse of something, can non-dequantizable just be “quantizable”?

This is a good question, and it highlights the issue of having to say “non-” at every occasion. Unfortunately, we believe there is no alternative to the current formulation. Our assessment may be a bit subjective, but we would say that “quantizable” is the property that something “can be quantized”. Since this property lies at the very core of quantum mechanics, “quantizable” already carries historic meaning that likely make it confusing if we used it to mean “quantum machine learning models that cannot be de-quantized”. This is because “quantizing” is a partial synonym of “discretizing”, while “de-quantizing” has become a synonym of “making something classical”. Since “dequantization” in our sense is essentially a one-way process, there is no standard word for “the impossibility of this process”, and simply removing the prefix “de-” linguistically would go in the direction of “reverting the process”, which is not what we want to capture.

An alternative could be “robust against dequantization”, though this would likely prove too long to be a convenient replacement for “non-dequantizable”.

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.

We appreciate the kind words by the reviewer, we take “generally interesting” and “quality paper” as notable praise. This weakness is similar to the first weakness raised by reviewer 1RRV’s, which makes us further convinced that we should have done a better job at clarifying the interest and novelty of our work. By streamlining parts of Sections 2 and 3 as advised by the reviewers, we hope to bring our results more front and center, and we have added new discussion in Section 5 to consider our contributions under complementary perspectives.

We would like to take a chance to explain why we decided to submit this work to ICLR based on what we believe are the novelty and potential impact of our work. We apologize for partially repeating the response to reviewer 1RRV, but upon reading the submission and review guidelines, we understood that the scope and range of ICLR are papers reporting novel findings and maintaining a high degree of correctness and scientific rigor. We chose to submit our work to ICLR because we are convinced that our work presents novel findings that are broadly and deeply relevant to the QML community. We believe the ultimate goal in the field of QML is to find a quantum advantage in learning using variational QML models for a real-life, practically relevant task. Recent progress in this direction has been called into question by the threat of “trainability implies dequantization”. According to well-spread opinions presented in Cerezo et al. (2023), the situation is dire: most-if-not-all generic variational QML models proposed to date can be either trainable or non-dequantizable, but not both. If no variational QML model exists that is trainable and non-dequantizable, then there is no hope for quantum advantage, and we cannot hope to eventually reach practical relevance. From this it follows that the road towards practical relevance is most likely not following current trends in the design of variational QML models. The analytic tools used to characterize this situation resulted in a seemingly iron-clad case against the existence of generic variational QML models being trainable and non-dequantizable. The picture resulting from the study of polynomial-sized Dynamical Lie Algebras (DLAs) does not offer much room for escape.

Recognizing this state of affairs, we establish formal language to not only clear the current situation, but also to help us move forward as a field toward practical relevance. At the same time, our main technical contribution is the resolution of an important open question: we prove a rigorous quantum advantage in learning using variational QML models; we further propose a general recipe to yield domain-specific advantageous variational QML models for any quantum function that is classically intractable, as we highlight in the new paragraph in Section 6, we propose “the ability to evaluate classically intractable functions” as a design feature. This convinces us that our work is novel at least on two accounts: we prove a solid result that had eluded the community until now (made possible by our formalization of the key concepts), and we offer this formalization to move forward toward practical relevance. In terms of impact, our contributions have far-reaching consequences: by giving a general recipe our results can be further specialized to a broad spectrum of domains of application (as briefly discussed in the new Section 5), and by realizing that existing trends are unlikely to yield practical relevance unless major breakthroughs are found, our contribution has the potential to deeply shift the paradigm on how we approach the design of variational QML models.

M. Cerezo et al. Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing. arXiv:2312.09121, (2023)

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.

The reviewer identified an issue that we indeed struggled with in the conversations about how to present our work, and we’re thankful for the provided valuable advice. We agree with the assessment of the reviewer, and we followed their advice by moving Sections 3.3 and 3.4 into the new Appendix C. We have decided against further thinning the parts of the text that would fall under category (a) because we believe that the context in which our work arises should not be understated. A critical question had been floating in the air that challenged the viability of the entire field by half-conjecturing that there could be no variational QML models that are simultaneously trainable and non-dequantizable. Except the language in which this question had been stated was that of variational optimization problems, and not QML. Further, formal language was generally missing that allowed for a precise study of the problematic. These are the reasons why we would be reluctant to remove much more content from Section 3, but we are eager to hear the reviewer’s thoughts.

Figure 2 and Table 1 seem to convey the same information redundantly.

Thank you for catching this, this was an artifact from a previous version of this manuscript. We have removed Table 1.

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?

We thank the reviewer for raising this point, as it has been a point of tension for the authors. The main advantage of “vari veryational” is that it perfectly captures the concept we want to transmit: that these models are almost very variational, but not quite. The current option of “vari veryational” won mostly due to the peculiar sense of humor the authors seem to share (and, we agree, not for purely scientific reasons). By taking this humorous option, we anticipate that this term will not be used extensively. Instead, we hope it brings attention to the fourth paragraph of Section 4.1, where we extend an invitation to the community to help us converge to a good definition of very variational. In the future, either we have an agreed-upon definition of very variational, or these ideas have been forgotten, but in both cases the need to speak up or type down “vari veryational” vanishes quickly.

That being said, we have spent more time considering alternatives, also prompted by a question by reviewer K1hL. We are ready to change the name if we find a better one, but until now everything we could think of fails at transmitting the core message: that these models are almost very variational, but not quite. Some of the alternatives are: quasi-variational, semi-variational, almost-variational, para-variational, and similar. But all of these fail on the account that these models are variational, just not very variational.

We value the effort on the reviewer’s side to carefully understand our work and help us enhance it. We believe this summary accurately represents the merits and contributions of our submission. We enjoy the positive feedback on the overall clarity and accessibility of our work. We are happy to hear that the effort we put into writing an approachable text has been appreciated by the reviewer. We thank the reviewer for highlighting the sufficiency of our literature coverage. We tried to be comprehensive, but it is perfectly possible that we missed some relevant works, which we would be happy to include if the reviewer has some in mind.

We thank the reviewer once again for their valuable feedback on our work. Prompted by the well-targeted comments, we have extensively clarified the nature and reach of our contributions in the new Sections 5 and 6. We have also added a discussion on how existing QML models fit in our categories in the new Appendix C. With these changes together with the comprehensive explanation in this response, we hope the reviewer shares a positive evaluation of our updated manuscript with respect to the original submission.

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.

We thoroughly agree that “offering insights or preliminary guidelines on designing QML models that are trainable, non-dequantizable, and very variational” would enhance the quality of the paper. To our understanding, though, this is precisely what our paper does! Except the reviewer carefully wrote “very variational”, and manifestly not “vari veryational”. This is very much in line with the issue that “variationalness” is not a well-defined quantity. In Section 4.1 we introduce “vari veryational” QML models, and in the fourth paragraph we extend an invitation to the community to converge into a good definition of very variational. The current status is that there is no proposed attempt at formalizing “very variational” QML models beyond our “vari veryational” ones. We are excited for the community’s proposals to improve on the list of structural properties. But we would argue our definition “vari veryational” is reasonably acceptable, and then we would claim that Theorem 3 and Corollary 4 provide precisely what the reviewer requests. These results are, precisely, “insights and preliminary guidelines on designing QML models that are trainable, non-dequantizable, and vari veryational”.

We have further added a last paragraph in the new Section 6 address some of these points that we failed to make clearer in our original submission.

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.

We have extended this part of the related work section. Following and earlier comment and also a comment from reviewer sYUX, though, we have deferred most of this discussion to the new Appendix C.

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.

As mentioned earlier, and as stated in Section 5 of the original submission, we agree that our results don’t immediately provide guidelines for designing effective QML models. To our knowledge, there are precious few (if any) such actionable insights across the entire literature of QML, and none that do not immediately suffer from dequantization or expressivity, so we would not count this as a major weakness of our work, nor one that could have been reasonably expected for us to fill.

A simple and potentially helpful perspective is to distinguish current research between “how to QML?” and “why to QML?”. In this picture, we would place ourselves firmly in the latter (although not exclusively). We would also understand that providing actionable advice should be the manifest goal of works that fall in the first category. We fundamentally agree with the reviewer that our ultimate goal is to understand how to design good QML models, which can eventually rival classical ML methods on practically relevant tasks. As we argue in the introduction and discussion, though, we identified that a crucial previous question was still open.

We venture the possibility that the reviewer has judged our work as “how to QML?”, and we would like to respectfully request that it be judged as “why QML?”. We hope our new Sections 5 and 6 help bring forward these nuanced points and better explicate the novelty and nature of our contributions.

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.

We appreciate the critical feedback from the reviewer. We respectfully disagree on what are the core contributions of our work. While we do connect some concepts, this is not the main point of the work nor the majority of the contribution in our view. Instead we formalize the necessary criteria needed to eventually make solid progress in the field. Our goal is to be precise, not to re-state existing results. Further, by delving into our formalism, we are able to prove important rigorous results that had remained elusive until now. In this sense, we also believe these are indeed new findings, and moreover key findings for a large and broadly recognized debate in the QML community.

We can understand the view of the referee: the immediate consequences of our results are not a list of design principles for QML that can rival the performance of well-established classical ML, which had been the perhaps-overly-enthusiastic dream in the early days of the field. In fact, we agree with the reviewer that our core contributions are conceptual in nature, more than technical. But then again - we do formally prove the existence of new classes of models in a constructive way, so it is also not just conceptual. Furthermore, we have a differing opinion about our work lacking significant technical contributions, as we prove a rigorous generic quantum advantage in supervised learning, of which there is no abundance in the literature.

In our search for the right venues for our work, we analyzed the scope and range of ICLR’s call for papers. The reviewer guide lists as strong points: “technical correctness, [...], and novel findings” among others. It is our understanding that we should be judged on the genuine interest and novelty of our findings, and not exclusively on the technical aspects of our contributions. Indeed, as also listed under considerations for reviewing submissions: the “objective of the work” is mainly conceptual, and this is fully aligned with the stated scope of this conference. For this reason we believed, and still believe, that ICLR is the right venue for our work, as we do provide novel findings that are broadly and deeply relevant to the QML community.

Nonetheless, the concerns of the reviewer are fully understandable, and while we don’t think they fully apply to our work, we see them as guidelines on how to improve the presentation and content. In this direction, we have replaced what used to be Section 5 with two new sections: Discussion (new Section 5) and Conclusion (new Section 6). We have added several paragraphs to hopefully better highlight the nature and depth of our contribution versus the known results before our work. To avoid confusion, we have also moved part of the related work section into an appendix: what used to be sections 3.3 and 3.4 are now mostly the new Appendix C.

We thank the reviewer for their time and interest in improving our submission. We appreciate the honest criticism as it gives us a way to further clarify and highlight our contributions. We feel there may be a misalignment between the merits of our work and the qualities for which it has been judged in this review, so we would like to take the chance to hopefully clarify our contributions, both conceptual and technical.

We feel somewhat uneasy that the reviewer considers that our work only “tries to establish” a relationship between trainability and dequantization, and that our formalization merely “attempts to illustrate” conditions under which these properties co-exist. It is our view that we do establish the relationship, and that our formalization does precisely illustrate the conditions, among other contributions. Said otherwise, the statements in this summary are all correct - and it seems to us that we agree with the reviewer on these, but in our view they may have under-represented the novelty and impact of our submission. We wonder whether the depth of our results has not been appreciated, which would also explain the low soundness score, while no specific problems with the soundness of our work are highlighted in the review.

Again, we take this whole-heartedly as a chance to improve on our work. We will be more explicit on our contributions in the remainder of the rebuttal, and we have better highlighted our contributions by separating the Discussion (new Section 5) from the Conclusion (new Section 6) in the revised manuscript.

We thank the reviewer for their positive feedback on our formalization, as well as our work in linking relevant concepts in QML. We appreciate the notion that our work is a valuable contribution. We may be optimistic that “understanding QML models” includes a broad range of useful applications, thus potentially highlighting the potential impact of our work.

Thanks for the detailed response. I have no further questions and also raised the score.

We appreciate the reviewer’s efforts to improve our submission. We thank the reviewer for the detailed work and thoughtful reading and review. We celebrate that the clarity and rigor of our work are highlighted as main strengths. Indeed, one of the goals of our work was to serve as a basis for further discussion.

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.

We agree with the reviewer that the models constructed in this paper can be considered contrived, we highlighted this issue in the third paragraph of Section 5 in the original submission. Since our objective was to resolve a pressing open question about trainability and dequantization, indeed our results are theoretical, but we do believe they have critical practical implications. As we explain in an added paragraph at the end of the new Section 6: our work arises in a context where the entire field of variational QML has been called into question, where doubt has been cast on the possibility of variational QML models being both trainable and dequantizable. Critically, progress toward useful variational QML models necessitates these doubts be cleared. We notice that in recent discussions of trainability versus dequantizability (where these terms had not been properly defined), the fact that quantum computers can compute hard things tends to be ignored, and so we construct models based on this feature. We provide a broadly applicable recipe for designing variational QML models that are trainable and non-dequantizable, as we now remark in the third paragraph of the new Section 5.

Just as a side remark: we agree that the models constructed in our work may be contrived, but we disagree that “the proposed training method is quite specific and not able to generalize to other QML designs”, as the proposed training methods are the broadly-applicable gradient descent and kernel-based training. Proving quantum advantage in learning with arbitrary training algorithms is easier than proving quantum advantage in learning with everyday-looking training algorithms, and in our work we provide the latter.

The reviewer notes that our contribution has limited connection to practically relevant variational quantum algorithms. In the specific context of QML, we have a different opinion: the community generally agrees with Cerezo et al. (2023) that there are some fundamental issues in the way QML models have been designed until now. There is to date no convincing evidence that any of the variational QML models proposed to date are practically relevant. We would like to highlight that in our work we are not trying to establish connections to other variational QML models, rather we aim to fix the language that will enable us to achieve real practical relevance. It has always been our goal to reach practical relevance, but by now it has become clear that the way to practical relevance is not following the mainstream trends in the field. Our added text in the new Sections 5 and 6 aims to clarify some of these points.

For these reasons, we do believe that while our work is predominantly theoretical in nature, it does have non-trivial practical repercussions.

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.

We thank the referee for pointing out this imbalance between the level of formalism in the definitions and in the results. Indeed, we noticed that the first part of Section 2 contained much technical language that was not used later on. Accordingly, we streamlined this first part of Section 2, removing unnecessary notation, and concentrating only on the elements of supervised learning that we use in our definitions and results.

M. Cerezo et al. Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing. arXiv:2312.09121, (2023)