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

Summary

The paper presents two novel machine learning algorithms for predicting ground state properties of quantum systems with constant sample complexity, independent of system size. The first algorithm modifies an existing ML model, while the second introduces a deep neural network model, both showing improved scaling in numerical experiments.

Strengths

1. The introduction of a deep learning model with rigorous sample complexity bounds is a significant contribution to the field. The constant sample complexity, regardless of system size, is particularly noteworthy and addresses a critical challenge in quantum many-body physics. 2. The authors provide numerical experiments that validate the theoretical claims. The experiments demonstrate the practical effectiveness of the proposed algorithms, especially the deep learning model, which outperforms previous methods.

Weaknesses

1. 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. 2. While the paper claims improved computational complexity, the actual implementation details and computational resources required for the deep learning model are not thoroughly discussed.

Questions

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

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have discussed the limitations.

Summary

In this paper, the authors focused on utilizing deep learning methods to predict the ground states. They made an important assumption that brings theoretical improvement to achieve constant sample complexity in the training data. They also made two main alternations to the learning model compared to previous literature, including incorporating Pauli coefficients in feature mapping and utilizing kernel ridge instead of Lasso. Numerical results for up to 45 qubit systems are provided, supporting the theoretical findings.

Strengths

1. High-quality paper with rigorous theoretical findings and comprehensive numerical results. 2. Improved the sampling overhead to constant complexity, independent of the system size. 3. Explored new possibilities for predicting the ground state properties of quantum many-body systems using neural network models.

Weaknesses

The main concern is that the improvement of this paper against precious works is limited. The main theoretical finding is based on an additional assumption that we know the property we'd like to predict in advance. The proposed learning method has only two minor alternations. These issues prevent me from giving a higher evaluation score, but they do not overshadow the fact that this article is of high quality.

Questions

No questions

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

See weakness

Summary

This paper studies the sample-efficient learnability of properties of grounds states of local Hamiltonians. Ground states of local Hamiltonians are hard to compute, even for quantum computers and to circumvent this hardness, several recent works proposed learning the trace inner product of local observables with the ground state given labeled training data. This setting is exactly PAC learning, i.e. given labeled data from a worst-case distribution, the goal is to get low prediction error wrt the same distribution on future samples. The best sample complexity for this problem is known to be log(n) 2^{polylog(1/eps)}, shown by Lewis et al. The main questions addressed in this work are (1) whether the sample complexity can be improved to be independent of the system size and (2) whether there are rigorous guarantees for learning properties of the ground state via neural network based algorithms.

Strengths

The paper provides several technical results on the representation and learnability of ground-state properties. The improved sample complexity follows from tweaking the algorithm is [2] and making additional assumptions about the training distribution. The neural net sample complexity result proceeds in two steps. First the authors prove an approximation-theoretic result for functions that look like ground state properties and show they can be well-approximated by neural networks. They then obtain a generalization bound using fairly sophisticated technical machinery.

Weaknesses

I think the paper does not resolve the questions it claims to resolve and does so in a slightly camouflaged way. 1. Question 1 in the paper asks whether you can get sample complexity that is independent of system size for learning properties of ground states, aka the PAC learning setting for ground states of local Hamiltonians. The answer obtained is yes, under two crucial caveats, the observable is known in advance and the distribution over the training data is not worst-case. This diverges significantly from the PAC learning model. The same critique holds for Question 2. Further, reference [1] does not state this as an open problem. 2. The assumptions on the training distribution are not stated upfront and do not appear to be mild. The assumptions include the distribution g to be strictly non-zero on [-1,1], and zero outside; g being continuously differentiable; and component-wise independent. Are there any natural distributions that satisfy all these properties simultaneously? 3. There is no discussion of why each of these properties is needed, which ones are crucial to the argument and which ones are for technical convenience. Having 4 non-trivial technical assumptions of the pdf is a major weakness, especially since it makes the result incomparable to prior work [1,2], where the setting is truly PAC learning. 4. In the numerical experiments, I see no discussion of what distribution was used to generate the training data, and how many of the technical conditions this distribution satisfies. It remains unclear to me what the experimental section is trying to convey, since it does not complement the main theorems. 5. When is it reasonable to expect labeled data for the observable / property you want to learn? What is a real-world scenario where one would expect to obtain such labeled data? 6. Is there a way to get some non-trivial sample complexity (not necessarily system independent) bound for PAC learning via neural networks, without the extra assumptions on the training distribution? 7. There are completely unjustified claims such as the neural network achieving low loss and finding a bounded magnitude solution after constant many steps and O(n) time. It is not clear why this should ever be the case.

Questions

I included the questions with the weaknesses.

Rating

3

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

Yes.

Summary

This work builds upon the work of Huang et al. and Lewis et al. by introducing two new approaches to get constant sample complexity for predicting properties of a ground state of a many-body local Hamiltonian. The two new approaches are a modified ML model that requires knowledge of the property of interest and a deep neural network model that does not need prior knowledge of the property. In this paper, the authors provide both proves and small experimental evaluations to show that both approaches achieve constant sample complexity, independent of system size.

Strengths

The paper is well-organized and clearly written. The paper includes rigorous theoretical guarantees and small numerical experiments to confirm the efficacy of the proposed methods compared to the existing algorithm.

Weaknesses

Even though it is a strong paper, the issue addressed here is a specific case that builds upon two other papers. Additionally, the related published works are mostly, if not all, published in physics journals. I do not see why the results shared in this paper are valuable to share with the broader NeurIPS community, especially since the mathematical proofs are very rigorous, I would expect that it is not accessible to the broader audience. Some assumptions and conditions required for the theoretical guarantees may also limit the applicability of the results.

Questions

How do the parameters or phases of the random Heisenberg model affect the training performance?

Rating

5

Confidence

1

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitations are addressed in the paper.

Summary

In this work, the authors give two algorithms that predict (geometrically local) properties of ground states of gapped geometrically local Hamiltonians. This problem has been introduced by Huang et al. [HKT+22], and the previous best known algorithm is given by Lewis et al. [LHT+24], which uses $\log(n)$ samples, where $n$ is the number of qubits in the Hamiltonian. This paper further improves on the $log(n)$ sample complexity, and gives two algorithms that only use a constant number of samples. The first algorithm is modified from the algorithm of [LHT+24], changing the regression part of the algorithm from LASSO to kernel ridge regression. The second algorithm uses deep neural network, having the advantage of not needing to know the observables in advance, but requires more restriction on the distribution of the Hamiltonian parameters. The authors complement their theoretical results with numerical simulations. [HKT+22] Huang, Hsin-Yuan, Richard Kueng, Giacomo Torlai, Victor V. Albert, and John Preskill. "Provably efficient machine learning for quantum many-body problems." Science 377, no. 6613 (2022): eabk3333 [LHT+24] Lewis, Laura, Hsin-Yuan Huang, Viet T. Tran, Sebastian Lehner, Richard Kueng, and John Preskill. "Improved machine learning algorithm for predicting ground state properties." nature communications 15, no. 1 (2024): 895.

Strengths

The work achieves the optimal sample complexity of the problem and is written in good English.

Weaknesses

The part of preliminaries that are restating definition and result of [LHT24+], is not well written, and I believe has led to a critical bug to the first algorithm. In particular, Theorem 8 claims that for every $O\sum_{P} \alpha_P P$ that can be written as sum of geometrically observables, $\sum_{P} |\alpha| =O(1)$. However, the counterpart in [LHT24+] has extra restrictions: $||O||_{infty}=1$ and $O$ need to be inside a radius of $R=O(1)$. Therefore, where the authors uses Theorem 8 in equation (B.28) to bound the kernel, the result is incorrect since they do not have $R=O(1)$. Other minor inconsistencies includes: line 642: $S^{geo}$ not defined line 660: $h_{c(j)}$ not defined

Questions

Some typos: line 121: geometrically [local] observable line 148: || \omega || -> || w ||

Rating

5

Confidence

2

Soundness

1

Presentation

2

Contribution

3

Limitations

The authors adequately addressed the limitations.

Summary

The authors propose an ML based method to predict properties of ground states of quantum systems which comes with provable guarantees. Improving on recent work by Huang et al and Lewis et al, they give sample complexity bounds which are independent of the number of qubits. This approach is applicable when the observable one is trying to predict is predetermined. The authors also suggest a deep learning based approach for the case where the observable is not known in advance. They support their theoretical wok with numerical experiments.

Strengths

The paper adresses an important probelm, and is well written and argued. The authors clearly explain the previous state of the art in ML based prediction of ground state properties, as well as their own contribution. Their proposed modification to the procedure suggested by Lewis et al., which results in Theorem 1 of the paper, seems interesting and worthwhile. Likewise the guarantees obtained for the training of a custom Neural Network architecture are intriguing from a learning theoretic perspective.

Weaknesses

It is unclear to me how the Neural Network generalization result compares to known results in the literature- the setting which the authors study is quite specific and thus it is not easy to relate the result they obtained to those in the theoretical deep learning literature.

Questions

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. Presumably the results would not apply to standard Neural Network architectures- what specifically would break in the analysis? How does the sample complexity depend on the constant the authors assume the network weights are bounded by?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

I believe the authors have adequately adressed the limitations of the paper.