Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms

Reviewer Comment: The training objective for the neural network is non-convex, which poses challenges in finding a global optimum efficiently. The paper does not address how to overcome this issue or guarantee convergence to optimal weights.

Author response: To address non-convexity of the training objective, we refer to literature on overparametrized deep neural networks, Ref. [74], (see Lines 283-284 in our manuscript), where it is shown that Gradient Descent finds the global optimum in settings very close to ours. A similar result was proven for Stochastic Gradient Descent [Oymak et al., "Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?" PMLR 2019]. Those results can likely be adapted to our setting. Furthermore, the experimental results show that this does not seem to be an issue in practice.

Reviewer Comment: While the paper claims improved computational complexity, the actual implementation details and computational resources required for the deep learning model are not thoroughly discussed.

Author response: The computational requirements and implementation details for generating the training data and training are detailed in Appendix D.1. Moreover, we provide code for the experiments in https://anonymous.4open.science/r/anonymous-B093, as referenced in Section 4.

Reviewer Question: The reviewer would appreciate if the authors could elaborate on how the performance of the deep learning model generalizes to Hamiltonians that extend beyond the specific cases examined in the numerical experiments.

Author response: The performance of the deep learning model holds for any Hamiltonian satisfying the conditions outlined in Section 2.1. Namely, this is any $n$-qubit gapped geometrically-local Hamiltonian that can be written as a sum of local terms such that each local term only depends on a constant number of parameters. There are many physically relevant Hamiltonians where this holds. Some examples are the 2D random Heisenberg model (as considered in the numerical experiments), the XY model on an $n$-spin chain with a disordered $Z$ field, and the Ising model on an $n$-spin chain with with a disordered $Z$ field.

Reviewer Question: Can the authors provide more insights into the practical implementation of their algorithms, particularly regarding the initialization and regularization procedures used during training? This will be helpful for readers reproduce the results of the paper.

Author response: We will add that we used Xavier initialization [71] and no regularization. The latter is implicitly shown in the loss function we used [Equation D.3]. The code for implementing the numerical experiments is given in https://anonymous.4open.science/r/anonymous-B093, as referenced in Section 4.

Thank you for your reply. I would like to keep my score.

We thank the reviewer for the careful reading of our paper. The reviewer's comments only apply to our first result in Section 3.1, and we acknowledge that the reviewer's comments are accurate for this portion of our paper. However, the improvement is significant - reducing sample complexity from logarithmic in system size to constant. Moreover the reviewer appears to have missed entirely our second result in Section 3.2, we obtain a rigorous guarantee for neural-network-based algorithms predicting ground state properties.

• This is the first work to give a practical deep learning based approach for predicting ground state properties with both theoretical guarantees and good experimental performance, and there is nothing similar in previous literature. We introduce several new techniques to this problem setting, such as the use of the Hardy-Krause variation, which is likely to be widely applicable in future research.

• This neural network result does not require knowledge of the property (unlike the result in Section 3.1). In addition, we would like to comment that knowing the property in advance is a natural assumption, as often scientists will have a particular observable in mind that they would like to study (as further discussed in lines 168-175).

Moreover, since our algorithm in Section 3.1 also applies to classical representations of the ground state (such as classical shadows), this can also be used to mitigate the issue of having to know the observable in advance (as we can learn a classical shadow of the state and then use that to predict properties of an observable of interest which need not be known in advance). See corollary 1.

We thank the reviewer for the careful reading of our paper.
First, we would like to clarify some statements made by the reviewer. We remark that our first answer to Question 1, namely our result discussed in Section 3.1, does not make any assumptions on the data distribution (as in the PAC learning model) but does require that the observable is known in advance. In contrast, our Neural Network (NN) guarantee in section 3.2 introduces assumptions on the data distribution but does not require the observable to be known. Note that the assumptions on the data distribution for the NN guarantee (stated in [Line 1336-1340]) are satisfied by natural distributions such as Uniform and Gaussian distributions on $[-1,1]^m$. Hence, they are milder than in Ref. [1], where the guarantees hold exclusively for the uniform distribution. Those distributions often suffice in physically relevant models such as the Sachdev-Ye-Kitaev (SYK) model, which requires Gaussian parameters. Moreover, given that there are few rigorous guarantees for NNs in the literature, we view our work as a step in this direction. In the following, we will do our best to address each point of criticism by the referee in detail.

1. Mostly addressed above. Ref. [1] does state that "Rigorously establishing that NN-based ML algorithms can achieve improved prediction performance and efficiency for particular classes of Hamiltonians is a goal for future work'' in the sentence right above Section III.B.
2. We agree with the reviewer that we could emphasize and further discuss the assumptions on the distribution, although we do state them in the main text in Lines 234-238. We want to further emphasize that $g$ needs to be continuously differentiable only on $[-1,1]^m$. Examples of natural distributions satisfying all conditions simultaneously are uniform and the normal distribution. The latter is important for physical models such as the SYK model.
3. We note that our assumptions on the distribution do not make our work incomparable with Refs. [1, 2]. Ref. [1] applies only to the uniform distribution over $[-1,1]^m$, which is a stronger restriction than ours. Ref. [2] covers any arbitrary distribution, similar to PAC learning, as our first result in Section 3.1. In Section C.3, Line 1344, we mention that assumptions (a) and (b) can be relaxed. Assumption (a) ensures strict positivity on $[-1,1]^m$ to avoid divisions by zero, but this can be managed by splitting the integral on $g$'s support. Requiring $g=0$ outside $[-1,1]^m$ is natural since it is the parameter space. Assumption (b) can be relaxed to continuous $g$ using mollifiers. Assumption (c) on component-wise independence is necessary to reduce the input domains of $f_P^{\theta_P}$. We will add this in Section C.3.
4. We briefly mention the distributions used in the caption of Figure 2 and Lines 354-355 in the main text and discuss this further in Section D.1, line 1628-1630. Namely, we utilize points from the uniform distribution over $[-1,1]^m$ (as in the numerics in Refs. [1,2]) and low-discrepancy Sobol sequences, complementing Theorem 14. We respectfully disagree with the comment that the numerics do not complement our theorems. We reproduce the setup of the numerical experiments in Refs. [1,2] and compare the performances of our model and the previously-best-known algorithm from Ref. [2]. The experiments illustrate that our method outperforms the method from Ref. [2] in practice (Figure 2, left). Moreover, they show that our assumptions in Theorem 5 are often satisfied in practice, i.e., small training error is achieved for proper choice of locality (Figure 2, right) and is independent of system size (Section D.2, Figure 4).
5. We briefly mention this in Lines 169-171, but agree it needs more discussion. The setting of receiving labeled data is consistent with Refs. [1, 2]. Our ML approach applies in scenarios like a scientist studying ground states of Hamiltonians $H(x)$. The scientist can use quantum experiments or classical simulations to investigate ground state properties. ML algorithms like ours and those in Refs. [1, 2] help extrapolate from existing data without additional costly experiments. In this scenario, it is realistic to assume the scientist can choose the training data, reducing the need to cover the worst-case distribution. Relevant examples of experiments generating data for quantum states include [A,B,C].
6. As discussed in point 3, the only assumption that is truly necessary for the argument is Assumption (c) (component-wise independence). Allowing long-range correlations for the parameters of a geometrically local system seems unnatural, so we are unsure whether this request makes sense physically. In that case, our methods yield a similar bound as in Ref. [1].
7. We justify those claims by referring to literature on overparametrized deep NNs Refs. [74], (see Lines 283-284 in the text), where it is shown that Gradient Descent finds the global optimum in settings very close to ours. A similar result was proven for Stochastic Gradient Descent [D]. Those results can likely be adapted to our setting. Moreover, our experimental results demonstrate that these claims are satisfied in practice in the setup we tested. The cost per iteration is $\mathcal{O}(n)$, due to the model's size. The model's size does not affect the number of gradient steps required for convergence (see e.g. Ref. [74], Theorem 5.1).

References

[A] Huang et al., "Quantum advantage in learning from experiments.", Science 2022
[B] Struchalin et al., "Experimental estimation of quantum state properties from classical shadows." PRX Quantum 2021
[C] Elben et al., "Mixed-state entanglement from local randomized measurements." Physical Review Letters 2020.
[D] Oymak et al., "Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?" PMLR 2019

Our work aims to solve an important physics problem by leveraging machine learning. Thus, we expect it to be of broad interest to physicists, theoretical computer scientists, and machine learning practictioners, as our algorithms not only have rigorous proofs but are also readily implementable, as seen in the numerical experiments.

• We identify the first result using deep learning for predicting ground state properties, with both theoretical guarantees and good experimental performance. This is a very practical algorithm accessible to the broad community and the code is available via an anonymous repo. The assumptions are natural and realistic (as discussed in other responses below) and conclusions are of direct practical relevance to physicists and chemists in their experimental work.

• We highlight that many papers of similar levels of mathematical rigor on topics in physics/quantum information have been present at ICML and NeurIPS in the past. A few examplex are [A,B,C,D]. The recent ICML 2024 conference featured a workshop devoted to "AI for Science: Scaling AI for Scientific Discovery."

In regards to the question about parameters/phases of the random Heisenberg model, could you please clarify what you mean by this? In the below, we try to answer to our understanding of your question, but please let us know if we misunderstood what you meant. The parameters of the Hamiltonian are inputs to the machine learning model (as a part of the training data). Although our rigorous guarantee only holds for training and testing points in the same quantum phase of matter (as in previous work), in the 2D random Heisenberg model, we may predict across phase boundaries. However, as seen in the numerical experiments, our algorithm still performs well.

References

[A] Yamasaki et al., "Learning with optimized random features: Exponential speedup by quantum machine learning without sparsity and low-rank assumptions." NeurIPS 2020
[B] Aaronson et al., "Online learning of quantum states." NeurIPS 2018
[C] Abbas et al., "On quantum backpropagation, information reuse, and cheating measurement collapse. NeurIPS 2024
[D] Michaeli et al., "Exponential Quantum Communication Advantage in Distributed Inference and Learning." ICML 2024

Bug The claim by the reviewer is incorrect, as our observables satisfy exactly the same conditions as those considered in [LHT+24].
In particular, we state throughout the paper that

• we only consider observables that satisfy $\lVert O\rVert_\infty \leq 1$, e.g., in lines 122, 225, 301, etc.
• We state clearly (lines 121-122) that $O$ is an observable that can be written as a sum of geometrically local observables. In [LHT+24], requiring that $R = \mathcal{O}(1)$ is exactly the definition of geometric locality (see, e.g., Definition 5 in [LHT+24]). Thus, the two definitions are exactly the same and conditions of Corollary 4 in [LHT+24] still hold in our setting.

We will clarify this explicitly in the final version.

We define $S^{(\mathrm{geo})}$ later in line 654. We will make this change to introduce it earlier. The term $h_{j(c)}$ denotes the same as in [LHT+24]. This is discussed in lines 655-657 and we will make this explicit in the main text.

We should also highlight our second result in section 3.2 which is completely different and uses deep learning techniques. This is a very practical algorithm (code available via anonymous repo) which has strong empirical performance and for which we give theoretical guarantees using innovative new techniques such as bounding the Hardy-Krause variation.

We thank 7tNg for acknowledging that their misunderstanding has been clarified and are happy that they are convinced of the soundness of the results. So, we wonder why the soundness score is still 1. Also, if they have any other issues we could address that leads to the overall score of only 5, we are happy to respond.

We thank the reviewer for the careful reading of our paper and their constructive comments.

Reviewer Comment: It is unclear to me how the Neural Network generalization result compares to known results in the literature.
Author Response: This is the first rigorous sample complexity bound on a neural network model for predicting ground state properties. We extend the tools from Ref. [54] beyond low-discrepancy sequences and explicitly bound the Hardy-Krause variation, such that our result is comparable to Refs. [1,2].

Reviewer Question: How restrivtive is the assumption about the dependence of each local term on a fixed number of parameters? It would be instructive to give physically relevant examples where this does and does not hold.
Author Response: The assumption that each local term depends on a fixed, i.e., system-size independent, number of terms is not particularly restrictive. Since each local term only acts on a system size-independent number of particles in the system, it is natural that this also holds for its parametrization.
Moreover, we note that this assumption is not something new to our work and was introduced in Ref. [2].

There are many physically relevant examples where this holds. A few examples are are

• the 2D random Heisenberg model (as considered in the numerical experiments).
• the XY model on an $n$-spin chain with a disordered $Z$ field.
• the Ising model on an $n$-spin chain with with a disordered $Z$ field (see, e.g., [A]) .
• the Sachdev-Ye-Kitaev (SYK) model, which requires Gaussian parameters.

We thank the referee for this comment and will add such examples to demonstrate its wide applicability.

[A] Lieb et al., "Two soluble models of an antiferromagnetic chain." Annals of Physics 1961

Reviewer Question: Presumably the results would not apply to standard Neural Network architectures- what specifically would break in the analysis?

Author Response:

• As mentioned in the discussion [starting from line 1660], the practical performance of our model can most likely be improved by applying the vast body of recent results in the theory of deep neural networks.
• Approximation results like those we used for tanh neural networks also exist for the ReLU activation function [53] and require neural networks of depth $\mathcal{O}(\log{\frac{1}{\epsilon}})$. Directly bounding the respective Hardy-Krause variation does not work however, since ReLU does not have bounded partial derivatives around $0$. It may be possible to work around this issue by bounding it with mollifiers, but we leave this open for future work.
• We believe that our analysis can be extended to standard architectures such as convolutional or residual neural networks, as long as the width and number of hidden layers does not exceed the that needed for fully connected neural networks (so that the Hardy-Krause variation is $\mathcal{O}(2^{\mathrm{polylog}(1/\epsilon)})$. We limited our attention to fully connected networks here, as bounding the Hardy-Krause variation of more elaborate architectures would have been more tedious than instructive.

Reviewer Question: How does the sample complexity depend on the constant the authors assume the network weights are bounded by?
Author Response: One can see this dependence in Eq. (C.93) in the appendices.