Summary
This paper studies quantum learning theory, in particular the relationship between the quantum version of PAC learning and the quantum version of the statistical query (QSQ) model, as well as their connection to other considerations in quantum computing, such as entangled measurements and separable measurements. Specifically, the authors proved that
1. For learning Boolean concept classes, the entangled and separable sample complexity are polynomially related (at most quadratic power).
2. There exists a concept class with an exponential separation between quantum PAC learning with classification noise and QSQ learning.
Along this, the authors also proposed novel technical tools of quantum statistical query dimension, and these technical results are applied to problems ranging from states learning, distribution learning, and specific problems in quantum computing such as shadow tomography, error mitigation, etc.
Strengths
This paper is technically very solid and is able to prove a series of new results in quantum learning theory. PAC learning and SQ learning models are both important concepts in classical learning theory, and it’s nice to see that the authors are able to generalize them to the quantum domain, connect them to natural definitions in quantum, and prove separation results between these concepts. It’s also nice to see that the authors are able to find wide applications in quantum learning theory.
Weaknesses
From my perspective, the most notable weakness of this works is its interest to the general machine learning community. There are theory papers in NeurIPS each year, many of which are very interesting and well received by NeurIPS audiences, but I’m afraid that this one falls into too much on the theory side and might be of limited interest to the NeurIPS community. In general, the topics of PAC learning and SQ model are more of theoretical interest and target more on theoretical computer science. The quantum version further delves into those directions and bring into definitions that do not exist in classical machine learning, such as entangled measurements/separable measurements, shadow tomography, etc. As another evidence, the references in the main body contain literally 0 paper coming from top-tier machine learning conferences targeting at general audiences, including, NeurIPS, ICML, ICLR, AAAI, etc. Instead, there are many top-tier theory papers at STOC/FOCS, Journal of the ACM, and top-tier physics journals. In general, I believe that this paper can be quite competitive in top-tier theoretical computer science venues or quantum physics venues, but is out of scope for NeurIPS due to lack of insights for up-to-date trends in current machine learning research.
As a minor point of weaknesses, I think the references can be better presented. First, I find it a bit hard to locate references: there are quite a few big brackets citing >5 papers at the same time, and it’s very difficult to determine which paper talks about which topic. For instance, in Page 1, “There have already been many theoretical proposals for quantum algorithms providing speedups for practically relevant ML tasks such as clustering, recommendation systems, linear algebra, convex optimization, SVMs, kernel-based methods, topological data analysis [34, 14, 9, 42, 32, 26, 35, 23, 49, 46]” can be better written as … such as clustering [xx], recommendation systems [xx], linear algebra [xx], convex optimization [xx], SVMs [xx], kernel-based methods [xx], “and” topological data analysis [xx].
Actually, I think here the authors lost some quantum computing papers accepted by past NeurIPS/ICML conferences that provide quantum speedup for solving machine learning problems, such as Kapoor et al. (https://proceedings.neurips.cc/paper/2016/hash/d47268e9db2e9aa3827bba3afb7ff94a-Abstract.html) and Li et al. (http://proceedings.mlr.press/v97/li19b.html) for classification, Arunachalam and Maity (https://proceedings.mlr.press/v119/arunachalam20a.html) for boosting, Childs et al. (https://proceedings.neurips.cc/paper_files/paper/2022/hash/933e953353c25ec70477ef28e45a2dcc-Abstract-Conference.html) for logconcave sampling, etc.
Questions
Can the techniques in this paper be applied to prove separation results between quantum and classical PAC learning or SQ models? As far as I see, this paper studies purely quantum learning concepts and their relationships. It would be helpful to deliver more conceptual message about the difference between quantum and classical learning, which may be of general interest (this is also the storyline set at the beginning of intro, but quickly drives into purely quantum things).
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.