Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms
Authors: Marc Wanner
Laura Lewis
Chiranjib Bhattacharyya
Devdatt Dubhashi
Alexandru Gheorghiu
Venue: NeurIPS 2024 poster (2024)
Keywords: Deep Learning
Learning Theory
Quantum Many-Body Problems
Primary area: machine_learning_for_physical_sciences

Abstract: A fundamental problem in quantum many-body physics is that of finding ground states of local
Hamiltonians. A number of recent works gave provably efficient machine learning (ML) algorithms
for learning ground states. Specifically, [Huang et al. Science 2022], introduced an approach for learning
properties of the ground state of an $n$-qubit gapped local Hamiltonian $H$ from only $n^{\mathcal{O}(1)}$ data
points sampled from Hamiltonians in the same phase of matter. This was subsequently improved
by [Lewis et al. Nature Communications 2024], to $\mathcal{O}(\log 𝑛)$ samples when the geometry of the $n$-qubit system is known.
In this work, we introduce two approaches that achieve a constant sample complexity, independent
of system size $n$, for learning ground state properties. Our first algorithm consists of a simple
modification of the ML model used by Lewis et al. and applies to a property of interest known beforehand. Our second algorithm, which applies even if a description of
the property is not known, is a deep neural network model. While empirical results showing the
performance of neural networks have been demonstrated, to our knowledge, this is the first rigorous
sample complexity bound on a neural network model for predicting ground state properties. We also perform numerical experiments that confirm the improved scaling of our approach compared to earlier results.

Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms
Mare Wanner
Laura Lewis
Computer Science and Engineering Chalmers University of Technology and University of Gothenburg
Applied Mathematics and Theoretical Physies University of Cambridge Cambridge, United Kingdom llewis@alumee caltech. edu
Sanner@chalmers.
Chiranjib Bhattacharyya
Devdatt Dubhashi
Computer Science and Automation Indian Institute of Science Bangalore, India chiru@iisc. ac.in
Computer Science and Engineering Chalmers University of Technology and University of Gothenburg Srohashi@chalmerr. se
Alexandru Gheorghiu
Computer Science and Engineering
Chalmers University of Technology and University of Gothenburg aleghe@chalmers.cc
Abstract
A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. number of recent works gave provably efficient machine learning (ML) algorithms for learning ground states. Specifically, Huang et al. in (.] introduced an approach for learning properties the ground state an r--uuit gapped local Hamiltonian H from only (11) data points sampled from Hamiltonians in the same phase of matter. This was subsequently improved by Lewis al. (2) to Olognn) samples when the geometry the n-qubit system known. In this work, introduce two approaches that achieve constant sample complexity, independent of system size n, for learning ground state properties. Our first algorithm consists of simple modification of the ML model used by Lewis et and applies to a property of interest known in advance. Our second algorithm, which applies even if description of the property is not known, is deep neural network model. While empirical results showing the performance neural networks have been demonstrated, to our knowledge, this is the first rigorous sample complexity bound on a neural network model for predicting ground state properties. We also perform numerical experiments systems of up 45 qubits that confirm the improved scaling of our approach compared to
Introduction
One of the most important problems in quantum many-body physics is that of finding ground states of quantum systems. This is due to the fact that the ground state describes the behavior of electronic systems (e.g., metals, magnets, etc.) at room temperature well. Thus, understanding
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the ground state can provide insights into, for example, chemical properties of molecules, leading to many potential applications chemistry and materials science. However, despite extensive
13 [4] an efficient classical algorithm solving this problem in full generality remains out of reach. On the other hand, researchers have successfully leveraged classical machine learning (ML) techniques to solve (albeit largely heuristically) the ground state
research
6
9 10 12
problem and other related quantum many- -ody problems [15] 16
17
18
18
19
20
21
22 23 24, 25
26 27 [28 29 30] 31
32
33 34 35 36
37 38
39
40
41 42
43
44
45
46
Rather than solving
these problems directly from first principles, ML algorithms are given some training data collected from physical experiments and are asked to generalize it to new inputs. Intuitively, this additional data can make the problem easier and thus may open the door to obtaining provably efficient classical ML algorithms for finding ground states. This data-driven approach is in some sense necessary. since finding the ground state from the Hamiltonian alone is known to be QMA-hard in general [47]. and thus out of reach for both efficient classical and quantum algorithms.
In a recent work D. Huang et al. proposed the first provably efficient ML algorithm for predicting ground state properties of gapped geometrically local Hamiltonians. In particular, the algorithm in [ uses an amount of training data (or sample complexity) that scales as O(n where n is the system size and e the prediction error of the ML algorithm. Recently, 2 improved this guarantee, achieving (log (n) )2nolylog(1/c) an exponential improvement with respect to the system size n. The same sample complexity was obtained by [48] for the task of learning thermal state properties with exponential decay of correlations. Moreover, 49] extended this to Lindbladian phases of matter [50] with local rapid mixing, including both ground states of gapped Hamiltonians and thermal states. The work of [51] obtains a similar guarantee assuming the continuity of quantum states in the parameter range of interest but focusing on the scaling with respect to 1/c rather than system size.
These previous works drastically improve the sample complexity of the original Huang et al. result [1, but none prove sample complexity lower boundy for their respective tasks, leaving open the possibility all use fairly simple learning models, i.e., regularized linear regression or taking empirical averages of classical shadows [52]. respectively. With the emergence of neural networks as a popular model in practical ML, one may wonder if these more powerful ML tools may be useful to predict ground state properties as well. In fact, recent works 37 36) empirically demonstrate a favorable sample complexity using netral--
of further reducing the sample complexity. In addition, [2] 48 49)
ML algorithms. However, there are currently no rigorous theoretical guarantees
regarding the amount of training data needed achieve a desired prediction error. These remarks lead us to the following two central questions of this work.
Question 1. Can classical ML algorithms predict ground state properties with even less than (loog(n) ((Loo(n))2oolyannn 22olylog(1/0) data?
This is especially relevant for systems approaching the thermodynamic limit, where the system size can be arbitrarily large. Needing fewer samples also means less work for experimentally preparing ground states of the system. The second question, stated as an open question in 2 is:
Can we obtain rigorous sample complexity guarantees for neural- based ML. algorithms for predicting ground state properties?
Question 2.
Our results
We give positive answers to both questions. We consider the same assumptions as 2 with minimal additional ones that we mention here. First, we show that a simple modification to the approach in 2 allows us to achieve a sample complexity that is independent of the system size. This does, however require knowledge of the property we wish to predict in advance, whereas this is not requirement in [2]. We view this as a reasonable assumption, since in practice we can imagine preparing ground states of some system in order to measure specific property of interest. We show the following theorem, stated informally here. The formal statement, including all the assumptions required for proving the result, can be found in Appendix B
Theorem I (Informal). Let (x) be an n-qubit gupped, geometricully local Hamiltonian with ground state p(x). Given an observable O with known decomposition as a sum of local Pauli operators and given training data (1 ve) Tezn sampled from arbitrary distribution, with ye se tr tr(Op(zz)),
2

---

aP
:
tr(Op(x))
PM
Bros P
Figure 1: A deep network model for predicting ground state properties. Given vector r [-1, 11 that parameterizes quantum many-body Hamiltonian H (xx), the algorithm uses geometric structure create "local" neural network models f.. The ML algorithm then combines the outputs of these local models predict a property tr tr(Op(z)), where p(x) is the ground state of Hxx). Here, we decompose O Σ Ei= ap, Pj for Pauli operators P., where the final layer takes linear combination of the outputs of the local models weighted by some trainable parameters wp, that intuitively should approximate the Pauli coefficients app.
M
there is an ML algorithm for predicting ground state properties tr(Op(z)) to within precision e 0 using N = O (2polylog(1/e) training samples.
Note that the number of samples N depends only on the desired prediction error and is independent of the system size. In particular, this means that for a fixed prediction error our algorithm requires only a constant amount of training data. Moreover, the computational complexity our algorithm improves upon 2 having (n) runtime, compared to the previous O(n log n.). While removing the log n factor may seem like small improvement, in practice this can make a significant difference. For instance, for system of 1000 qubits, removing the log factor would result in ten-fold reduction training data and time.
Much like in 2 this result also extends to learning classical representations of p(x). In other words, the algorithm is instead given classical shadows [52] of the ground state as training data. it can then predict a classical representation of p(z) for new parameters æ. This can mitigate the requirement that the observable is known Theorem T as predicting properties from classical representation clearly requires knowledge of the observable.
Our second result shows the same sample complexity guarantee for neural network ML algorithm (Figure I [53], in which one does not need to know the observable being measured in advance. An additional constraint that we require in this case is that the training data is not sampled according to an arbitrary distribution, but a distribution satisfying some technical assumptions. We note that these assumptions are satisfied for common distributions such uniform and Gaussian.
Theorem 2 (Informal). Let (x) be an n--ubiit gapped, geometrically local Hamiltonian with ground state p(x). For any observable O, expressible as of local Pauli operators and given training data (W 1 sampled from a distribution satisfying certain assumptions with ye Re tr tr( O O(æx)); there neural network ML algorithm for predicting ground state properties tr(Op(z)), for uniform to within precision
using N O (2polytoz(1/e) training samples under mild assumptions
on training.
We prove this result by making use of the Koksma-Hlawka incquality from quasi-Monte Carlo
theory [54 55
56
57
58) and combining it with the spectral flow formalism 59 60 61
Similar to Theorem 1 we can also extend this result to learning classical representations of p(x) when given classical shadow training data. The formal statement and proof can be found in Appendix C We also remark that, much like the setting in [11. more favorable scaling with respect to can be achieved if the number of parameters that the Hamiltonian depends on constant. particular, it was shown in [5I) that if the number of parameters is constant, the sample complexity scales

---

as N = (o/y(1/e, log(n)). For our results, this similarly yields N = poly(1/e), preserving the independence on the system size while also achieving a polynomial scaling c/c.
Furthermore, we perform numerical experiments on system sizes of up to 45 qubits, which support theoretical findings, and show that, in practice, deep learning algorithm outperforms previous methods 22.
We describe them in detail in Appendix D and they are illustrated in Figure 2
2 Preliminaries
2.1 Problem statement
First, we formally describe the problem setting, which is the same as 2 We consider a family
of n--ubii Hamiltonians (xx) smoothly parameterized by an m-dimensional vector x: E [-1, 1)m. We assume that these Hamiltonians are gapped for all choices of parameters x E 1-1, and geometrically local such that they can be written as a sum of local terms
H(x) (E,)
(2.1)
where the parameter vector x is concatenation of the constant-dimensional vectors T7. ........ of these constant-dimensionall vectors i parameterizes the local interaction term (T,) Crucially, we assume that each local term h2 only depends
"iii....,,. Tr. Each
constant number of parameters rather than the
entire parameter vector z. We also assume that the geometry of the n-qubit system is known.
Throughout this work, we use p(x) to denote the ground state of the Hamiltonian (x)) and O to denote an observable that can be written as sum of geometrically local observables with bounded spectral norm ||O]| S 1. Here, the ground states p(z) form gapped quantum phase of matter. Given samples of quantum states drawn from this phase, we wish to predict expectation values of observables O with respect to other states in the same phase. In other words, we are given training data ((1r, ye) )= where y R tr(Op( (xe)) approximates the ground state property for a parameter choice Tg E [-1, 1] sampled from some distribution 'D over the parameter space. We aim to learn function (x)) that approximates the ground state property tr(Op(z)) for some unseen parameter
while minimizing the amount of training data, sample complexity, N. How well we learn the ground state property is quantified by the average prediction error
E (x) tr(Op(z))) <.
(2.2)
We describe the precise conditions under which Theorems I and hoold in the following sections.
2.2 Review of previous algorithm
In this section, we review the previous algorithm from (2] as our proofs rely on similar ideas. For full details, refer the reader to (2) and our more detailed presentation in Appendix [A.I] The ML algorithm proposed in (2) requires some geometric definitions. Fix a geometrically local Pauli observable P (T, X, Y, @n.
Let 61, B set Ip of coordinates such that x. parameterizes some local term hy(c) that is close the Pauli P. Here, the distance between two observables dobs is defined as the minimum distance between the qubits that the observables act where the distance between qubits is given by the geometry of the system, which we assume to be known. Formally, we define this set of local coordinates as
efficiently-come compuuttl hyperparameters that we define Appendix A. Define the
Ip a {c E {1...., m) dobs(hy(e)) P) < 81}.
(2.3)
where hy(c) is the local term in the Hamiltonian H (x) whose parameters Zz(e) include the variable Fe. The intuition behind this set of coordinates is that indexes the parameters Ie that influence the ground state property tr (z)p(z)) corresponding to the Pauli P. The algorithm consists of two steps. First, it maps the parameter space [-1, 1]m to a high dimensional space via a nonlinear feature map 6. Second, it runs l reguulaare linear regression (LASSO) [22 63 64] over the feature space.
This first step encodes the geometry of the problem. The feature map intuitively projects given parameter vector x onto the local parameter space {ze : E Ip). We define this precisely in

---

Appendix A. Following the feature mapping, the ML algorithm uses LASSO 62 63 64 to learn
functions of the form {h(z) ((x) |wll S B} for chosen hyperparameter B We
denote the learned function by h- (z) = w ((x). For our purposes, we set 20 This algorithm obtains the following rigorous guarantee.
of Theorem 3 (Theorem 1 in (2 Given n, > 0, >>>>> 0 and a training data set {( We) 3e
size
= 1
(2.4)
where xı is sampled an unknown distribution D and ye - (ev-((((p(e))) S c. With a proper choice of the efficiently computable hyperparameterss 51, 62, and B, the learned function h" h²(x) w ((x) satisfies
F 1h (x) - tr(o))))( <
(2.5)
with probability at least 1 - The training and prediction time of the classical ML model are bounded by O(nN) log(n/ 1og(n/6)2poosloog) 280llllog)))))
crucial step in the proof is that ground state properties can indeed be approximated by linear functions the feature space. Along the way, 2 proves that the ground state property can be approximated by a linear combination of "local functions," " which are local in that they only depend on parameters with coordinates in the Tp. We relegate further details Appendix A. and 2
T
3 Main results
In this section, we discuss our rigorous guarantees for predicting ground state properties with constant sample complexity and with neural-network-based MI algorithms.
3.1 Constant sample complexity
In this section, show that a simple modification of the algorithm from 2 can achieve sample complexity that is independent of the system size n, under the additional assumption that the observable O is known. In practice, scientist often has specific ground state property in mind that they wish to study, so we view this as natural assumption. Moreover, this is still an interesting learning problem, as when obtaining the training data via quantum experiments, preparing the ground state p(z) in the laboratory for new choice of parameters may be difficult experimentally. This in turn means that accurately predicting some property tr(Op(z)) for new choice of x may be challenging, even if the property of interest, O, is known. ML algorithms can allow us to circumvent this issue and generalize from the results of few training data points without needing to prepare the ground state directly.
Let O EPE(I.XY223. P be an observable that be written sum of geometrically local observables. Because O is assumed be known, we can find this decomposition of O in terms of the Pauli observables P. The overall structure of the algorithm remains the same: perform a nonlinear feature mapping followed by linear regression. However, there are two key differences from the previous algorithm (2). First, we change the feature mapping of [2] to incorporate the
Pauli coefficients ap. We define this new feature mapping ø in Appendix B The second difference
from 2 is that we use ridge regression 65] 66) instead of LASSO 62
66). Recall that LASSO
learns hypothesis functions of the form (h(z) w w-o(z)) // S B} for some hyperparameter
B > 0. In contrast, ridge regression replaces the -nomm constraint |[w]|, < B with an f--m constraint: ||w||2 S A, for some hyperparameter > O. Namely, for a chosen efficiently-computall hyperparameter A > 0, ridge regression finds vector w that minimizes the training error subject to the constraint that ||w]]2 S A, i.c.
N
min
w
(w.d(x))= - yel
(3.1)
W N
W
Standard results machine learning theory give sample complexity upper bounds for ridge regression in terms of A and the form of the feature vector d(xr) new feature mapping, we can still approximate the ground state property by a linear function over
65 666. The key idea is that with our
5

---

the feature space, as in (2) to obtain low training error. Meanwhile, by incorporating the Pauli coefficients op into the feature map, we can bound the f2-norm of o(x:) by a quantity independent of system size, leveraging bounds on the norrr of the Pauli coefficients 2 67 We note that naively applying ridge regression with the feature map from ( does not achieve the same guarantees and in fact gives worse scaling than [2]. Similarly, we can also choose a suitable A independent of system size. Thus, we obtain the following guarantee.
Theorem 4 (Constant sample complexity). Given n. Ó > O, 1/e c > 0 and a training data set (Ire, ve) of size
N = log(1/8)ppoksooz(/))
(3.2)
where Dy is sampled from an unknown distribution D and - (er((0((=e)) S c. With a proper choice of the efficiently computable hyperparameters d1, d2, A, the learned function h² (x(x) satisfies
E 2~D
E - (r(p))))
(3.3)
with probability least 1 - 5. The training and prediction time of the classical ML model are bounded by (ol)pooylog(1// (18))polyyoogg///
We compare this result to Theorem 3 For constant prediction eπror c O1), our proposed algorithm achieves a constant sample complexity N = (()), compared to the logarithmic sample complexity N Olognn of [2]. Moreover, we also improve the computational complexity, achieving a linear-in-n runtime, compared to the previous (n log n). The scaling with respect to the prediction error é is the same as the previous algorithm [2] This means that regardless of how large our quantum system is, we need the same amount of samples to predict ground state properties well This is especially important for settings in which obtaining training data for large systems is difficult.
Thus far, we have only considered the setting in which we learn specific ground state property tr(Op(z)) for fixed observable O. Because our training data is given in the form {(Iz, be)le where Ye approximates tr(Op(z)) for this fixed observable O, if we want to predict a new property for the same ground state p(x), we would need to generate new training data. Thus, it may be more useful to learn ground state representation, from which we could predict tr(Op(z)) for many different choices of observables O without requiring new training data. In this case, suppose we are instead given training data {az, oT (p(x)))] where ()(((x)) is a classical shadow representation [52 68
69 70 71 of the ground state p(zz). An immediate corollary of Theorem 4 is that we can predict ground state representations with the same sample complexity. This follows from the same proof as Corollary 5 in [2]
Corollary 1 (Learning representations of ground states). Let n, > 0, 1/e > e > and ō > Given training data {(1,, oT(p())))) of size
N = ((0oyyoot))))
(3.4)
where we is sampled from 'D and or (p(xe) is the classical shadow representation of the ground state p(az) using T randomized Pauli measurements. For T = ((og((1/5) / with probability at least 1 - 8, the ML algorithm will produce a ground state representation PN.((z) that achieves
E [r((0p.r(x)) - trr(Op(=)) S
(3.5)
anD
for any observable with ||0 I 1 that can be written as sum of geometrically local observables.
3.2 Rigorous guarantees for neural networks
In this section, we prove the existence of deep neural network model that can predict ground state properties using a constant number of training samples. In particular, we prove that after training on a constant number of samples from distribution D on [_1, satisfying certain technical assumptions, our model can achieve a low prediction error under mild assumptions on training. this case, for predicting properties tr(Op(x)), the observable O need not be known in advance. However, we need to assume that all mixed first order derivatives of the Hamiltonian ||am (x)/ax) dxmillo S 1 exist and are bounded. This not much stronger than 2, which assumes that directional derivatives 0h,/0o /a are bounded by one for any direction û. Moreover,

---

also need the training data to be sampled from a distribution D with probability density function g satisfying the following assumptions: 9 has full support and is continuously differentiable on [-1,1|", Also, g is of the form g(æ) = I 93 (īz). This resembles our assumption on the form of the Hamiltonian H (x)). Furthermore, the average prediction error is measured with respect to the same distribution D. We note that these assumptions satisfied for common distributions such as uniform and Gaussian.
As in the previous algorithm (2), we leverage the geometry of the n--ubit system to approximate the ground state properties by linear combination of smooth local functions, which only depend on parameters with coordinates in the local coordinate set Ip defined in Equation (2.3). Crucially, the size m A Ipl of the domains of these local functions is independent of the system size.
Instead of using feature map and linear regression learn the ground state properties. we utilize a deep neural network model defined as follows. Inspired by the local approximation of ground state properties, we define "local models" fpr [-1, 1 th ++ R, which are neural networks consisting of three layers of affine transformations and applications a nonlinear activation function. In particular, ffr has two hidden layers with the affine transformations given by the trainable weights and biases denoted by 0p. We take hyperbolic tangent, tanh, as the activation function. These local models are then combined into a model f0,w
[-1,1] - R given by
0 (x))
Σ
wPSp 10 (z);
(3.6)
PESG
where wp E IR are the weights in the last layer and θ = (0r) reStweo)- This model is schematically illustrated in Figure [
We refer to Definition Appendix C for full description of the model.
Consider training data {Ire, 3e) ==) where 2, are sampled according to distribution D satisfying the assumptions described above and |3/e tr(Op(ze)) S e. The ML algorithm first initializes the weights via standard deep learning initialization procedures, e.g., Xavier initialization [72]. Then,
the algorithm performs quasi-Mont Monse Carlo training given the training data, e.g., Adam weights O*, w² which minimize the training objective function
73 to find
( vel2 + A||w||1,
(3.7)
where À is some regularization parameter that may depend on For this algorithm, we prove the following theorem bounding the average prediction error of our deep neural network model.
Theorem 5 (Neural network sample complexity guarantee). Let 1/e > Let D be a distribution with probability density function g satisfying the properties stated above. Let f8",'"" _="" [-1, be a neural network model trained data {1z,, y of size
N = (1og(1/8)2pobyoogt1/) (000)/oooooooo(2//)) )
(3.8)
where the Vy's 's are sampled from DD and lye - -r(Op(zz)) < c. Suppose that fo _o" achieves a value no larger than O(e) on the training objective (Equation
(3.7) with X(e) O(e). Additionally,
suppose that all parameters O of pee _w"" satisfy |0 S W for some Wmax 0 that is independent of n. Then
1 w - trOp))(O SE. D>D
E
(3.9)
Similar to Theorem for constant prediction error O(), the deep neural network algorithm achieves constant sample complexity N = O(1). In contrast to Theorem we do not require knowledge about the observable, O. This is direct consequence of the regularity of wp, which is achieved when the training objective is small. Theorem 6 guarantees, that a model with such regularity can yield a small prediction error.
There are, however, some caveats compared to the previous result. First, the training data is restricted to being sampled from a distribution satisfying our technical assumptions stated previously, in contrast to Theorem 4 which holds for data sampled from any arbitrary unknown distribution. Second, in regards to the model, the weights must be bounded by constant W Waxx Finally, we cannot guarantee
7

---

priori that the network will indeed achieve low training error. This is due to the fact that our training objective non-convex and thus, globally optimal weights cannot be found efficiently in general [74]. Even so, we are still able to prove the existence of suitable weights such that the resulting network approximates tr(Op(zz) for any x E [] (see Theorem 6 in the next section).
However, we view the assumptions made in Theorem 5 as being mild in practice. Small training objectives are commonly achieved in deep learning so we expect our training algorithm to produce a model which fulfills the assumptions of Theorem 5 after ((1) training steps and ((n) runtime. Moreover, it is known that gradient descent provably converges to the global optimum for over- parametrized deep neural networks, while the weights remain small, when properly initialized [75]. We verify that these conditions are satisfied in practice through our numerical experiments in Figure 2 and ?? To our knowledge, Theorem is the first rigorous sample complexity bound on neural network model for predicting ground state properties.
We also note that if the training data is instead sampled according to a low-discrepancy sequence (LDS) [55] 76 (77 78. [57 79 58 80 [1]. we can obtain better guarantees, but these improvements are hidden in the polylogarithmic factors in the exponential. We discuss learning given data from a Intuitively, LDS is collection of points in the parameter space that covers the space such that there are no large gaps, or discrepancies.
LDS in Appendix C
Similar to Corollary if are instead given training data {.e, (r(x)r(((())) 1-11 where or (p(zt) is a classical shadow representation [52] (68 69 77 [7]] of the ground state p(zz). then we obtain the following immediate corollary of Theorem 5
Corollary 2 (Learning representations of ground states with neural networks). n,, 8, > 0, 1/e> 6 > 0 and 8 O. Given training data {(re, (T(((())) N of size
N = (Log(L/6)22aalloec()))
(3.10)
where Ne is sampled from a distribution D satisfying the same assumptions as Theorem and or (p(xs) is the classical shadow representation of the ground state p(æz) using I randomized Pauli measurements. For T = (llog(n/5)/e (²²,, with probability at least 1 - 8. the ML algorithum will produce ground state representation PN, (zz) that achieves
AND [t((OpN.(T)) - tr(Op()))) SE
(3.11)
for any observable with ||Oll S 1 that can be written as sum of geometrically local observables.
3.2.1 Proof ideas for neural network guarantee
To prove Theorem
first show that neural network model f can approximate the ground state properties well. In particular, we show that there exist weights O' w' such that fōe, ww approximates the ground state properties and thus achieves small value for the training objective (Equation B.7 ). Then, we bound the prediction error using tools from deep learning and quasi-Monte
Carlo theory 54 55 56
We ensure the existence of f8r. ,"'" in the following theorem.
Theorem 6. For any 1/e >> 0 and width W, there exist weights O w/ such that the neural network model per satisfies
p on (r)= Se, E
E 1-1,
(3.12)
Moreover, each parameter Q of the network has magnitude of Oil (0poyylog(1/e))
This implies that for suitable choice of regularization parameter = (c), the training objective from Equation (.7) is also small. We prove this statement by combining results in deep learning regarding tanh neural networks approximating functions [53] with the geometric locality of the
system and smoothness of the ground state properties. We note that the weights O' w' in Theorem are not necessarily the weights O³, w² found via the neural network training procedure in Theorem Because the training objective is non-convex, O', w'. However, assuming that f does indeed achieve low training error (which is often satisfied practice), we are able to rigorously guarantee that the model will generalize well and achieve low prediction error in Theorem 5
cannot guarantee convergence to these weights
8

---

Notice that the guarantee of Theorem 6 holds for all I and, in particular, does not require our assumptions on the distribution D. The assumption that the network is trained on such data only becomes relevant when bounding the prediction error. While not explicitly stated here, we also note that Theorem gives a bound on the number of trainable parameters [O, that has a similar dependence on as the model in 2 Furthermore, the parameters are independent of system size, Additional smoothness assumptions on the Hamiltonian H (z) can yield mild improvements on the dependence in terms of e, as briefly discussed in Appendix C.I Moreover, because of this bound on |6:|, applying an additional penalty on the f--norm the weights @ can help ensure that the weights remain small. In practice, this is usually satisfied during training when the weights are initialized properly and the inputs are regularized, e.g. [53]. Thus, the condition that |o)] S W Wmax is often satisfied in practice and is not considered a strong assumption in deep learning.
To prove the prediction error bound in Theorem 5 assuming that a low training error is achieved, we combine techniques from quasi-Monte Carlo theory applied to deep learning (54] (see Appendix A.2 for a review) along with our knowledge of the geometry of the n-qubit system. In contrast to [44] we need to characterize the dimension of the input domain in our approach. The reason for doing this is that the approximation error depends on the size m p (Equation
2.3 ) of our local models //r
The central result we use here is the Booksma-Hlawkee inequality [56] (see Theorem I0 in Ap-
pendix (n.2) from quasi-Monte Carlo theory. This produces a bound on the prediction error in terms of the star-discrypancy (see Definition X in Appendix (A.2) and the Hardy-Krause variation. The star-discrepancy can be controlled by known bounds on the star-discrepancy of random points [82] We bound the Hardy-Krauu Krause variation by explicitly computing the mixed derivatives of the local models for and the ground state properties tr(Op(z)) ). In particular, we bound the latter using tools from the spectral flow formalism [59 60 61] and this is where the assumption that the mixed first order derivatives of the Hamiltonian are bounded needed, Putting these steps together, we arrive at the rigorous guarantee in Theorem 3
4 Numerical experiments
We conduct numerical experiments to observe the performance of our model in practice. The results demonstrate that our assumptions in Theorem are often satisfied in practice and that our deep learning algorithm outperforms the previous best-known method [2]. Moreover, we generate and utilize significantly more training data than in prior works [ (2). The code can be found at httpp://gi thub. con/marrcwnnne. chwwahhs
www.ueerrreammeeeeeeeaiiiinn wwtp/eeeannnnggng lewaannnnngrouddd.... states..t........... .it
We consider the classical neural network model discussed in the previous section and defined formally in Definition 6 For each of the local models flr, we use fully connected deep neural networks with five hidden layers of width 200. We train the model with the AdamW optimization algorithm [83] We measure the training error and prediction error via the root-mean-square error (RMSE). The model is discussed further in Appendix []
As in 2), we consider the two-dimensional antiferromagnetic random Heisenberg model on between 20 45 qubits and predict two-body correlation functions. The corresponding Hamiltonian is
H Σ (x,(X,X + Y.Y, + +2,2,, (1))
(4.1)
where (ij) denotes all pairs of neighboring sites on the lattice. The coupling terms Jeg correspond to the parameters x of the Hamiltonian and are sampled uniformly from [0, 2).
We generate training data similarly to I 2]. using the density-matrix renormalization group (DMRG) [9] based on matrix paadixxproduuc-sstttes (MPS) (84). To assess the performance of our model, we consider both uniformly randomly distributed Jıj and coupling parameters, which are distributed as a Sobol sequence. It is easy to see that the distributions and H satisfy the requirements of Theorem 5
In Figure 2 (Left), we see that our deep learning algorithm consistently outperforms the previous best-known ML algorithm from 2 achieving approximately half the prediction error on the same training data. The prediction error also exhibits a constant scaling with respect to system size, agreeing with our rigorous guarantee in Theorem 5 Another noteworthy observation is that the MI. algorithm's 's performance on LDS is nearly equivalent to performance on uniformly random points. We discuss a potential reason for this in Appendix D

---

0.08
0.08
0.00
6
0.07
0.07
0.07
1.50
Avrnge peoleston d105
0.06
Avwag geelestoe 6E11
0000
Average training CEOP
0.90
1.25
0.05
0.06
01
6.05
Triining
Mettie
1.00
0.04
0.04
0.04
[e]]
0.77
0.02
Algoni Lourrins, L.DS
0002
0.02
0.50
Regrossoon 1,188
Deep Learning, Randem
0.25
Regression Random
0.00
155
5x5
665
755
8
165
0.00
600
1228
2048
2807
3696
0..00
055
500
6x5
7x5
8d5
965
0.00
Trainin
(N)
Systom
Figure 2: Numerical experiments. (Left) Comparison with previous methods. Each point indicates the prediction error (RMSE) of our deep learning model the regression model of [2] fixing the training set size N = 3686 and the size of the local neighorbood 61 = 0 (Equation (..3 both algorithms point indicates the prediction error of our deep learning model given LDS training data for various ő1 and training data sizes. (Right) Neural network weights and training error. Blue points correspond the training error of the neural network model. Red points correspond to the & norm of parameters in the last layer or the largest absolute value of the parameters of the neural network, fixing N 3686 and 61 = 1. This shows that the assumptions in Theorem 5 are achieved in practice. The shaded areas denote the I-sigma error bars across the assessed ground state properties.
We train either LDS or uniformly random points. (Center) Scaling with training size. Each
Figure (( illustrates the prediction error scaling with respect to the training set size for various choices of 81 (size of the local neighborhood from Equation (2.3). For 51 = 0, the error arising from approximating the ground state property via local functions dominates. For d1 > O, we observe smaller local approximation error and thus achieve a smaller prediction error for sufficiently large training sets. This is consistent with theoretical results.
Finally, Figure (Right) (Right) illustrates that our assumptions Theorem are mild in practice. Namely, the blue points show that a small training error can be achieved. The red points also demonstrate that the -norm of the parameters the last layer and the largest absolute value the parmeters in the trained neural network remain small. In particular, in Figure the weights exhibit scaling independent of system size n. Hence, we find that the assumptions needed to guarantee the prediction error bound in Theorem namely that the training objective is small and the weights of the neural network are small and independent of system size, are fulfilled in our numerical experiments. We provide further details of the numerical experiments in Appendix
Discussion
We have shown that construct ML models for predicting ground state properties that require only a constant number of training samples, for a fixed prediction error. Specifically, we showed that a simple modification to the linear regression model in !2 only requires 2polylog(c)) samples in order to achieve prediction error of e, provided that we know a decomposition of the observable of interest in terms of Pauli operators. We then showed that a neural network model which is trained on 20olylog(<")) training samples and which achieves Occ) training a prediction error of at most c. In this case, knowledge of the observable
these samples will also have no longer required.
Our work leaves open several avenues for future exploration. First, it would be desirable to understand the conditions under which we can prove convergence for the training error. For instance, could the model be changed so as to use convex objective, thereby avoiding the issues associated with finding a global optimum in a non-convex landscape? Following (4 [50]. we would also like to know whether the results obtained for neural networks can be extended to thermal states Lindbladian phases of matter. Finally, for both results it would be desirable to improve the scaling with respect to the error e. Currently, the models have quasipolynomial scaling in 1/c and the only case in which we know how to achieve poly(1/c) scaling is when the number of parameters, m, is constant (as in (5I).
10

---

Acknowledgements
MW and DD are supported by SSF (Swedish Foundation for Strategic Research), grant number FUS21-0063. LL is supported by Marshall Scholarship. CB is partially supported by grant from DIA-COE. AG is supported by the Knut and Alice Wallenberg Foundation through the Wallenberg Centre for Quantum Technology (WACQT). This work was done in part while subset of the authors were visiting the Simons Institute for the Theory of Computing.
References
[1] Hsin- Yuan Huang. Richard Kueng. Giacomo Torlai, Victor V Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 377(6611) 2022.
[2] Laura Lewis, Yuan Huang, Viet T Tran, Sebastian Lehner, Richard Kueng, and John Preskill. Improved machine learning algorithm for predicting ground state properties. Nature Communications, 15(1):895, 2024.
[3] Hohenberg and W. Kohn. Inhomogeneous electron gas. Phys. Rev, 136:8864-B871 1964.
[4] W. Kohn. Nobel lecture: Electronic structure of matter functions and density functionals.
Rev. Mod. Phys., 71:1253-1266, 1999.
[5] Anders W. Sandvik. Stochastic series expansion method with operator-loop update. Phys. Rev.
B, 59:R14157-R14160, 1999.
[6] David Ceperley and Berni Alder. Quantum Monte Carlo. Science, 231 137(38))) 560, 1986.
[7] Federico Becca and Sandro Sorella. Quantum Monte Carlo Approaches for Correlated Systems. Cambridge University Press, 2017.
[8] James Gubernatis, Naoki Kawashima, and Philipp Werner. Quantum Monte Carlo Methods. Cambridge University Press, 2016.
[9] Steven R White. Density matrix formulation for quantum renormalization groups. Physical review letters, 69(19):2863, 1992.
[10] Steven R White. Density-matrix algorithms for quantum renormalization groups. Phys. Rev. B, 48(14): 1993.
[11] Guifré Vidal. Class of quantum many-body states that can be efficiently simulated. Physical review letters, 101(11):
10501, 10000,, 2008.
[12] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Kiao-Qi Zhou, Peter J Love, Alán Sspuru-Gzzik and Jeremy L. O'brien. variational eigenvalue solver on a photonic quantum processor. Nat. Commun., 5:4213, 2014.
[13] J Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Verstracte. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Reviews of Modern Physics, 9344)0045003, 2021.
[14] Toby S Cubitt. Dissipative ground state preparation and the dissipative quantum eigensolver. arXiv preprint arXiv:2303.11966 2023.
[15] Giuseppe Carleo, Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria Schuld, Naftali Tishby, Leslie Vogt-Maranto, and Lenka Zdehorová. Machine learning and the physical sciences. Rev. Mod. Phys., 91:045002, 2019.
[16] Juan Carrasquilla. Machine learning for quantum matter. Adv. Phys.: X, 5(1):1997528. 2020.
[17] Dong-Ling Deng, Xiaopeng Li, and S. Das Sarma. Machine learning topological states. Phys. Rew. B, 96519510 195145, 2017.

---

[18] Juan Carrasquilla and Roger G. Melko. Machine learning phases of matter. Nat. Phys., 13:431, 2017.
[19] Giuseppe Carleo and Matthias Troyer. Solving the quantum many-body problem with artificial neural networks. Science, 355(6335))602-660) 2017.
[20] Giacomo Torlai and Roger G. Melko. Learning thermodynamics with Boltzmann machines. Physical Review B, 94(16):165134, 2016.
[21] Yusuke Nomura, Andrew S. Darmawan, Youhei Yamaji, and Masatoshi Imada. Restricted boltzmann machine learning for solving strongly correlated quantum systems. Phys. Rev. B, 96:205152, 2017.
[22] Evert P. L. van Nieuwenburg, Ye-Hua Liu, and Sebastian D. Huber. Learning phase transitions by confusion. Nat. Phys., 13:435, 2017.
[23] Lei Wang. Discovering phase transitions with unsupervised learning, Phys. Rev. B, 94:195105, 2016.
[24] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212 2017.
[25] Giacomo Torlai, Gugliclmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo. Neural-network quantum state tomography. Nat. Phys., 14(5):447-450, 2018.
[26] Rodrigo A VarnaseHer,ández, John Sous, Mona Berciu, and Roman V Krems. Extrapolating quantum observables with machine learning: inferring multiple phase transitions from properties of single phase. Physical review letters, 121 2018
[27] KT Schütt, Michael Gastegger, Alexandre Tkatchenko, K-R Müller, and Reinhard J Maurer. Unifying machine learning and quantum chemistry with a deep neural network for molecular wavefunctions. Nat. Commun., 10(1):1-10, 2019.
[28] Ivan Glasser, Nicola Pancotti, Moritz August, Ivan Rodriguez, and J. Ignacio Cirac. Neural- network quantum states, string-bond states, and chiral topological states. Phys. Rev. X, 8:01::100 1006, 2018.
[29] Matthias C Caro, Hsin- Yuan Huang. Nicholas Ezzell, Joe Gibbs, Andrew T Sornborger, Lukasz Cincio, Patrick J Coles, and Zoë Holmes. Out-of-distribution generalization for learning quantum dynamics. arXiv preprint arXiv:2204.1022 2022.
[30] Joaquin F Rodriguez-Nieva and Mathias S Scheurer. Identifying topological order through unsupervised machine learning. Nat. Phys., 15(8):790-795. 2019.
[31] Zhuoran Qiao, Matthew Welborn, Animashree Anandkumar, Frederick Manby, and Thomas Miller III. Orbnet: Deep learning for quantum chemistry using sympetry-adapted atomic-orbital features. Chem. Phys., 124411):22411, 2020.
[32] Kenny Choo, Antonio Mezzacapo, and Giuseppe Carleo. Fermionic neural-network states for ab-initio electronic structure. Nat. Commun., 11(1):2368, May 2020.
[33] Hiroki Kawai and Yuya Nakagawa. Predicting excited states from ground state wavefunc- tion by supervised quantum machine learning. Machine Learning: Science and Technology. 14))0450227 2020.
[34] Javier Robledo Moreno, Giuseppe Carlco, and Antoine Georges. Deep learning the hohenberg- kohn maps of density functional theory. Physical Review Letters, 125(():076402, 2020.
[35] Korbinian Kottmann, Philippe Corboz, Maciej Lewenstein, and Antonio Acín. Unsupervised mapping of phase diagrams of 2d systems from infinite projected entangled-pair states via deep anomaly detection. SciPost Physics, 11(2):255 2021.
[36] Haoxiang Wang, Maurice Weber, Josh Izaac, and Cedric Yen- Yu Lin. Predicting properties of quantum systems with conditional generative models. arXiv preprint 211643 2022.
12

---

[37] Viet T Tran, Laura Lewis, Hsin- Yuan Huang, Johannes Kofler, Richard Kueng, Sepp Hochreiter, and Sebastian Lehner. Using shadows to learn ground state properties of quantum hamiltoni- ans. Machine Learning and Physical Sciences Workshop at the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.
[38] Kyle Mills, Michael Spanner, and Isaac Tamblyn. Deep learning and the schrödinger equation. Phys. Rev. A, 96:042113, 13, Oct 2017.
[39] N Saraceni, S Cantori, and S Pilati. Scalable neural networks for the efficient learning of disordered quantum systems. Physical Review E, 102(3):033301, 2020.
[40] Cancan Huang and Brenda M Rubenstein. Machine learning diffusion monte carlo forces. The Journal of Physical Chemistry A, 127(1):339-355, 2022.
[41] Matthias Rupp, Alexandre Tkatchenko, Klaus-Rober Müller, and O Anatole Von Lilienfeld. Fast and accurate modeling molecular atomization energies with machine learning. Physical review letters, 108(5)005301, 2012.
[42] Felix A Faber, Luke Hutchison, Bing Huang, Justin Gilmer, Samuel S Schoenholz, George E Dahl, Oriol Vinyals, Steven Kearnes, Patrick F Riley, and O Anatole Von Lilienfeld. Prediction errors of molecular machine learning models lower than hybrid dft error. Journal of chemical theory and computation, 13(11):5255-526 2017.
[43] Benno Rem, Niklas Käming, Matthias Tarnwwki,, Luca Asteria, Nick Fläschner, Christoph Becker, Klaus Sengstock, and Christof Weitenberg. Identifying quantum phase transitions using artificial neural networks on experimental data. Nature Physics, 15(9):917-920, 2019.
[44] Xiao- Yu Dong, Frank Pollmann, Xue-Feng Zhang, et al. Machine learning of quantum phase transitions. Physical Review B, 99(12):121 2019.
[45] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671 (199661)):195 195-202, 2017.
[46] Luuk Coopmans and Marcello Benedetti. On the sample complexity of quantum boltzmann machine learning. arXiv preprini arXiv:2306. 2.t.:23366.999999 /4969, 2023.
[47] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. Siam journal on computing, 1070 2006.
[48] Cambyse Rouzé, Daniel Stilck França, Emilio Onorati, and James D. Watson. Efficient learning of ground and thermal states within phases of matter. Nature Communications, 15(1), September 2024.
[49] Emilio Onorati, Cambyse Rouzé, Daniel Stilek França, and James D Watson. Provably efficient learning of phases of matter via dissipative evolutions. arXiv preprint arXiv:2311.07500, 2023.
[50] Andrea Coser and David Pérez-Gareía. Classification of phases for mixed states via fast dissipative evolution. Quantum, 3:174, 2019.
[51] Yanming Che, Clemens Gneiting, and Franco Nori. Exponentially improved efficient ma- chine learning for quantum many-body states with provable guarantees. arXiv preprint arXiv:2304.0 04353, 2023.
[52] Hsin- Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nat. Phys., 16:1000 2020.
[53] Tim De Ryck, Samuel Lanthaler, and Siddhartha Mishra. On the approximation of functions by tanh neural networks. Neural Networks, 143:732-750, November 2021.
[54] Siddhartha Mishra and T. Konstantin Rusch. Enhancing accuracy of deep learning algorithms by training with low-discrepancy sequences. SIAM Journal on Numerical Analysis, 1811- 1834, 2021.
[55] Stanislaw K Zaremba. The mathematical basis of monte carlo and quasi-monte carlo methods. SIAM review, 10(3):303-314, 1968.
13

---

[56] Russel E Caflisch. Monte carlo and quasi- quasi-monte monte carlo methods. Acta numerica, 7:1-49, 1998.
[57] Harald Niederreiter. Random number generation and quasi-Monte Carlo methods. SIAM, 1992.
[58] Pierre I. 1''Ecyyer and Christiane Lemieux. Recent advances in randomized quasi-monte carlo methods. Modeling uncertainty: examination of stochastic theory, methods, and applications, pages 419-474, 2002.
[59] Sven Bachmann, Spyridon Michalakis, Bruno Nachtergaele, and Robert Sims. Automor- phic equivalence within gapped phases quantum lattice systems. Commun. Math. Phys., 309(3):835-877 2012.
[60] Matthew B Hastings and Xiao-Gang Wen. Quasiadiabatic continuation of quantum states: The stability of topologiaal ground-state degeneracy and emergent gauge invariance. Phys. Rev. B, 72(4):04514,, 2005.
[61] Tobias J Osborne. Simulating adiabatic evolution of gapped spin systems. Phys. Rev. A, 75(3)0033321, 2007.
[62] Fadil Santosa and William W. Symes. Linear inversion of band-limited reflection seismograms. SIAM Journal on Scientific and Statistical Computing, 7(4):1307-1330 1986.
[63] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[64] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
The MIT Press, 2018
[65] Craig Saunders, Alexander Gammerman, and Volodya Vovk. Ridge regression learning algo- rithm in dual variables. In Proceedings of the Fifteenth International Conference on Machine Learning, pages 515-521, 1998.
[66] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[67] Hsin-Yur Yuan Huang, Sitan Chen, and John Preskill. Learning to predict arbitrary quantum processes. PRX Quantum, 4(4):040337, 2023.
[68] Andreas Elben, Richard Kueng, Hsin- Yuan Huang, Rick van Bijnen, Christian Kokail, Marcello Dalmonte, Pasquale Calabrese, Barbara Kraus, John Preskill, Peter Zoller, and Benoît Vermersch. Mixed-state entanglement from local randomized measurements. Phys. Rev. Lett., 125:200501, 2020.
[69] Andreas Elben, Steven T Flammia, Hsin- Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, and Peter Zoller. The randomized measurement toolbox. arXiv preprint arXiv:2203.1133 1/37. 2022.
[70] Kianna Wan, William J Huggins, Joonho Lee, and Ryan Babbush. Matchgate shadows for fermionic quantum simulation. arXiv preprint arXiv:2207.13723, 2022.
[71] Kaifeng Bu, Dax Enshan Koh, Roy J Garcia, and Arthur Jaffe. Classical shadows with pauli- invariant unitary ensembles. arXiv preprint arXiv:2202.03272 0222222...22.................... 2022.
[72] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedfor- ward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 256. JMLR Workshop and Conference Proceedings. 2010.
[73] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988 2014.
[74] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[75] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
14

---

[76] Ilya M Sobol. Uniformly distributed sequences with an additional uniform property. USSR Computational mathematics and mathematical physics, 16(5):236-242) 1976.
[77] I'a Meerovich Sobol'. On the distribution points a cube and the approximate evaluation of integrals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 7(4):784-80)) 8027 1967.
[78] Harald Niederreiter. Point sets and sequences with small discrepancy. Monatshefte für Mathe- matik, 104:273-332 - 1987.
[79] Harald Niederreiter: Low-discrepancy and low-dispersion sequences. Journal of number theory, 30(1):51-70, 1988.
[80] John H Halton. On the efficiency of certain quasi-ran muss-rranoom sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik, 2:84-90, 1960.
[81] Art B Owen. Monte carlo variance of scrambled net quadrature. SIAM Journal on Numerical Analysis, 34(5):18441110 1997.
[82] Christoph Aistleitner and Markus Hofer. Probabilistic discrepancy bound for monte carlo point sets, 2012.
[83] Uya Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019.
[84] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Mach. Learn., 20(3):273-29) 1995.
[85] Kjetil O Lye, Siddhartha Mishra, and Deep Ray. Deep learning observables in computational fluid dynamics. Journal of Computational Physics, 410: 109339, 2020.
[86] Art Owen. Multidimensional variation for quasi-monte carlo. In Contemporary Multivariate Analysis And Design Of Experiments: In Celebration of Professor Kai-Tai Fang 's 65th Birthday, pages 19-74. World Scientific, 2005.
[87] Christoph Aistleitner and Josef Dick. Functions of bounded variation, signed measures, and a general koksma-hlawka inequality, 2014.
[88] E. Hlawka and R. Mück. Über eine transformation von gleichverteilten folgen ii. Computing. 9(7):1277138, Jun 1972.
[89] Mohammad Mahdi Bejani and Mehdi Ghatee. A systematic review overfitting control in shallow and deep neural networks. Artificial Intelligence Review, pages 1-48, 2021.
[90] George Casella and Roger L Berger. Statistical Inference. Duxbury press, 2002.
[91] Murray Rosenblatt. Remarks on multivariate transformation. The Annals of Mathematical Statistics, 23(3):470-472, 1952.
[92] Mei Zhang, Aijun Zhang, and Yongdao Zhou. Construction of Uniform Designs on Arbitrary Domains by Inverse Rosenblatt Transformation, pages 111-126. 05 2020.
[93] 2. Quasi-Monte Carlo Methods for Numerical Integration, pages 13-22.
[94] Ohad Shamir. A variant of azuma's inequality for martingales with subgaussian tails. arXiv preprint 110.2211 2011.
[95] Howard E. Haber. Notes on the matrix exponential and logarithm. Santa Cruz, Institute for Particle Physics, University of California: Santa Cruz, CA, USA, 2018.
[96] Steven R. White. Density matrix formulation for quantum renormalization groups. Phys. Rev. 1992.
Lett.,
[97] De Huang, Jonathan Weed, Joel A Tropp, and Rachel Ward. Matrix concentration for products, arXiv preprint arX4:72003.05437, 2020.
15

---

Appendices
Contents
Preliminaries
16
A.I Review previous algorithm and proof
16
A.1.1 ML Algorithm
17
A.1.2 Proof Ideas
18
A.2 Deep learning with cow-eiccypyancy sequences
20
Constant sample complexity
23
B.1
Training error bound
Prediction error bound
25
B.3
Computational time for training and prediction
27
Rigorous guarantees for neural networks
27
Approximation of ground state properties by neural networks
Prediction error bound
33
Prediction on general distributions
4
Bound on the mixed derivatives
49
D
Details of numerical experiments
53
Experimental setup
53
D.2
Additional experiments and discussion
54
D.3 Experiments with non-geomeetriallly-ooall Hamiltonians
56
These appendices provide the technical details of the ideas discussed in the main text. In Appendix A we review several important concepts for our proofs such as the algorithm and rigorous guarantee from 2 in Appendix A. and background
classical deep learning techniques in Appendix A.2 In Appendix we build on 2 to obtain a sample complexity upper bound for predicting ground state properties independent of system size. In Appendix C prove guarantee for predicting ground state properties using neural networks.
A Preliminaries
A.1 Review of previous algorithm and proof
In this section, we review the previous algorithm from 2 along with intermediate results we use throughout our proofs. For full details, refer the reader to 22] Throughout this section, let 1/e > 61, 62, <3 > 0. One can think of 6 as the approximation error caused by the hypothesis of our ML algorithm not exactly capturing the ground state property; c represents the noise in the training data; E3 corresponds to the generalization enror.
Recall that we consider a family of n-qubit Hamiltonians H(x) smoothly parameterized by an m-dimeensional vector æ []1,1]m that satisfies the following assumptions, which we restate from (2).
16

---

(a) Physical system: We consider n naite-dimensional quantum systems that are arranged at locations, or sites, in a d-dimensional space, e-g., a spin chain (d 1). square lattice (d = 2), or cubic lattice (d = 3). Unless specified otherwise, our big-O, S2 θ notation is with respect to the thermodynamii limit n -> 00.
(b) Hamiltonian: H(x) decomposes into a sum of geometrically local terms ((x)
وك each of which only acts on an (11) number of sites in a ball of O(1) radius. Here, J. E R q = O(1) and æ is the concatenation of vectors Zi,..., Hr, with dimension m T4-- (n). Individual terms h,(55) obey 11 (o1 S 1 and also have
bounded directional derivative: ||0hy/öüll S 1, where à is a unit vector in parameter
space.
(c) Ground-star state subspace: We consider the ground state p(z) for the Hamiltonian ((x) to be defined as p(x) = lim e (BB((x)x// tr(e-~8(()) This equivalent to a uniform mixture over the eigenspace of (x) with the minimum eigenvalue.
(d) Observable: O can be written
sum of few-body observables 0 0= E, Oj. where each (11) number of sites. Hence, can also write 0 Σ resto apP,
Oj only acts where P E (T, X,Y, 2] sm and 5(xeo) is the set of all geometrically local Pauli observables. We focus on O given as sum of geometrically local observables E, Oj. where each O, only acts (1) number of sites in a ball of (1) radius. Moreover, O has ||O|| O(1).
We also assume that the spectral gap of (x) is bounded from below by some constant y for all choices of parameters x E 1mm.
The ML algorithm is given training data set {01, ye) where De is sampled from some distribution D over the parameter space [-1, and ye approximates the ground state property: lye tr(C tr(Op(xz)) I 62. The goal is to learn some function h" (²(x)) that achieves low average prediction error
(=) Sc. anD
E
(A.1)
A.1.1 ML Algorithm
The ML algorithm proposed in (2) requires several geometric definitions. We use S(geo) to denote the set of all geometrically local Pauli observables throughout.
Let 82, 52, B= > 0 be pirciientlycoopuutbbbl hyperparameters that we define later. Then, define the set Ip of coordinates that parameterize some local term hyte) that is close to Pauli P (T,X, Y, ) S", Here, the distance between two observables dabs is defined the minimum distance between the qubits that the observables act on, where the distance between qubits is given by the geometry of the system, which assume to be known. Formally, we define the set of local coordinates as
1p a {c E {I,..., m). dobs (hbe( P) S 61..
(A.2)
where hy(e) is the local term in the Hamiltonian (x:) whose parameters (f(c) include the variable Teg- The intuition behind this set of coordinates is that it indexes the parameters x. that influence the ground state property prx))())) corresponding to this Pauli P. Using this intuition, because these parameters Ne for e Lp matter most for the property we are trying learn (as (2] proves and we give the ideas for later), then we can define a new effective parameter space in which all other parameters are set to zero. Moreover, parameters ze for Ip can be discretized to lie on a lattice. This gives the following set Xp
x E 1| c Ip. =0
Xp A
(A.3)
if Ip, E {0, td2 .,,,
...,
We can also define set Tz,P for each vector & E Xp which is the of parameters x' that are close to x for coordinates in Tp:
82 <s. x Vc Vee Tr o' s' =(1,
82 2
T Trr
(A.4)
With these definitions in place, we set the hyperparameters as follows. Define 61 as
81 2 max (Cinax loC C4, Cs, max(5900, a, 7(d + 11).0)
(A.5)
17

---

where b, Cuax, C2, C5 8, C' are all constants. We refer to the supplementary information of for full description of these constants. Moreover, 82 is given by
82 _
(A.6)
2 C'TTl
where C" a constant. Finally, we define an additional hyperparameter > 0 as
_ 20(polylog(//)))
(A.7)
The MI. algorithm from 2 algorithm consists of two steps. First, maps the parameter space [-1, 1| to high dimensional space ! for
utilizes these objects to encode the geometrie locality of the system. The
m
Σ
Xp ((n)22(ppoyybottee
(A.8)
PES(m))
via a nonlinear feature map Φb Second, runs f1-regularized linear regression (LASSOO) over the feature space.
This first step encodes the geometry of the problem. In particular, the feature map is defined as follows, where each coordinate of ((x) is indexed by x' Xx and P E S(8en)
(A.9) In this way, the feature map o(x) identifies the nearest lattice point to æ. The idea that one can approximate the ground state property well by only approximating it at these representative points and summing up. We make this intuition rigorous the following section.
)(r).', 1/x E P..
63 64 to learn functions of the form (h(z) w σ(x) ||l|] S B}. In particular, for chosen hyperparameter B 0, LASSO finds a coefficient vector w that solves the following optimization problem minimizing the training error subject the constraint that ||w]]] I
Following the feature mapping, our ML algorithm uses LASSO 62
min 1 N
w ((T;) - y/ 12
(A.10)
WER" |wll
We denote the learned function by (z) w ((x). Note that the learned function does not need achieve the minimum training error, but be some amount eg/2 above it. For purposes, set B p0polylog(1//))
This algorithm obtains the following rigorous guarantee.
Theorem 7 (Theorem 5 in (2). Let 1/e 61,62, and 8 0. Given training data ((te.ee) N of size
N log(n/ (ol(m//))p (eoo:)o))ooog(t//)///ooaooo
(A.11)
where xe is sampled from D and yt is an estimator of tr(Op(zz)) such that 1ye tr(OO(az)) s e2. the ML algorithm can produce ht (x) that achieves prediction error
E 1hh tr(p)tt())x)=p----- (E1 t2) + InD
(A.12)
with probability at least - 5. The training time for constructing the hypothesis func- tion h and the prediction time for computing h² upper bounded by O(nN) log(n/8))220 (00og/00000lggaa)))aa/aa polyoog())))))
A.1.2 Proof Ideas
This rigorous guarantee is proven by first showing that the training error
N
R(hh) min
[M(x)))
yel*
(A.13)
1=1
is small.
18

---

Lemma (Lemma 15 in (2). The function
g(x)
Σ Σ Txx w/ .6(x)
(A.14)
PES(x))) x'EXp
achieves training error
R(g) S (c +2)
(A.15)
The proof of this consists of three different steps. First, one can show that tr(Op(z)) can be approximated by sum of smooth local functions, denoted as f(x) = Epesion) f2(2), where fr(x) = or tr( tr(Pp(xr(z)) for T:===pee (P) a.P and
Tie CE
xp(x)c = (0 o 1p
(A.16)
for all e E {I....,my m. J. In other words, parameters that parameterize local terms h2 far away Pauli P (xe for e $ Ip) do contribute much the ground state property, and thus we can simply them to zero. Formally, this approximation is given in the following lemma.
Lemma 2 (Corollary& 2 in (2). Consider class of local Hamiltonians (H)))
[-1,1]m} and
an observable O (1), apP satisfying assumptions
(a) (d) There exists constant
C > O such that for any 1/e > 00,
[r((O(())) - f(x) s Cei
Σ PES(On))
Jarl
(A.17)
where f(x) EpESt fr(x).
Second, one can also show that this sum of local functions f(z) = Epeslon) fr(x) can in turn be approximated by a linear function over the feature space g(z) = w/ -((x), where w' is vector with entries indexed by P E g(geo) and x' E Xp given by w' w'',p fp(x').
Lemma (Corollary 3 (2). For g(z) = w' o(x) and f(x) = EpES(or) fP(x), then writing an observable = EPE(L.XY.. ap we have
[5(x) f(x) <e1
Σ PESTE
Japl
(A.18)
for any x.
This tells us that the hypothesis functions of the ML algorithm indeed approximate the ground state properties well. The final piece needed is norm inequality bounding the fn-nrr of the Pauli coefficients. This allows us to bound the terms involving a in Lemma and and Lemma 3 In particular, we have the following bound.
Theorem 8 (Corollary written as a sum of geometricully local observables. Then,
22). Let O EPE(I.XY.2J ap be an observable that can be
Caap==011
(A.19)
Given these results, Lemma [ follows directly by triangle inequality and rescaling 61 when using Lemma and Lemma 3 Finally, to prove Theorem 7 it remains to bound the generalization error by E3. This follows directly from known sample complexity guarantees for the LASSO algorithm [64], which learns L reguulariz linear functions. In order to apply this known result, one needs to provide a regularization parameter, i.e., some > such that the MI. algorithm learns functions the form (()))) = w Φ(x) for w/l < B. To choose such a B, Lewis et al. bound the & of w', where recall w/ '' (p(x').
Lemma (Lemma 14 in 2D. Let w' be the vector of coefficients defined by w fp(x'). Then.
ww/l 1l1
Σ Σ
lff(z')) ((polslog(///))
(A.20)
Peg(x x'EXp
Using = (0polyoog())ee) in the known guarantees for LASSO 64 gives Theorem
19

---

A.2
Deep learning with low-discrepancy sequences
In this section, we review results in classical deep learning theory for obtaining rigorous guarantees when learning from data sampled according to low- cow-disrrepancy sequence (LDS) [55] 56 76 77 78
57 79 58
80
8T For this discussion, we follow [54 85].
We consider a neural network or multi-layer perceptron model as a composition of several layers of affine transformations and nonlinear activation functions. Namely, let a : R IR be nonlinear activation function. Then, a neural network with L layers is defined as follows. Let do....,dy ,d, E IN be the dimension (number of neurons width) of each layer k E {0, ..... L}. Here, the zeroth layer is the input layer and the Lth layer is the output layer. At each layer k E {O....,L- L 1 except for the output layer, we define an affine transformation Wx Rdx - Rdx11 by Wx(x) = A& + by for a matrix of weights Ag E IRde+1xd, xdz and vector of biases by E Rdx+1, Then, a neural network is defined as
fo(x) = (WL)=(WW-1000--
Wo)(
(A.21)
where a is applied element-wise and 0 = ((Au, bo)..........................b (AL-1, The hidden layers the first I, - 1 layers. Here, are the trainable parameters of the neural network, which can be iteratively updated through training on data. A deep neural network is neural network with at least three layers: 2 3. In this work, we consider the activation function
o (xx) tanh(x)
(A.22)
ex e
We refer to such neural networks with this activation function as tanh neural networks.
Suppose neural network So aims to approximate some target function f, given training data {(Fe, (() Then, the training error is defined as
N
R((0)
1 N
Σ - - fo(w)))? E=1
(A.23)
The prediction error is then defined over the whole domain, including unseen data,
R(0)=
= E
R~D [xx) - fa()))
(A.24)
where the training data is sampled from some distribution D. canonical result in deep learning theory [66] is that the generalization error can be bounded by roughly
R(O)= S Ri()) +
(A.25)
where S indicates that only state this result schematically. Importantly, this means that in order for the neural network fo to approximate f with high accuracy. many training data points N are needed, which is undesirable. In order to fix this issue, [54] combines ideas from deep learning with to achieve generalization error bound of
tools from quasi-Monte Carlo methods [55 56
57
58
R(0) S R(00
(A.26)
N
where Ö indicates that we are suppressing polylogarithnic factors. The key tool used here is low- discrepancy sequences [55] 56 76 77 78 57 77 58
80 [1] Intuitively, this is collection of points that covers domain of the function f in such way that there are no large gaps, or discrepancies. By filling these gaps, one can ensure that the training data accurately represents the target function, more so than even uniformly random data. We leverage these ideas to obtain our rigorous guarantee on the sample complexity of deep learning algorithm for predicting ground state properties. In the following, we formally define diwdeiccepaancy sequences and a key inequality in quasi-Mont Carlo theory for obtaining our generalization bound.
First, we define the discrepancy
sequence, which is measure of uniformity.
Definition 1 (Discrepancy (56)). Let X be the Lebesgue measure, N E N. Let x = {xe) be sequence of points with z; [0, 1]dh for all f. The discrepancy of the sequence is defined
(x(d)
sup |R (J),.
(A.27)
JEE
20

---

where
Rx(J)= 1 N 12 J}- X())
(A.28)
N 2=1
for a Lebesque- set J - [0, 1]". Also, E is the set of all rectangular subsets of [0, 1] i.e.
E = a b.) : -000aab. : s
(A.29)
Intuitively, one can consider the discrepancy as measure of how well the sequence fills rectangular subsets of [0, 1]d. If the discrepancy is small, this means that the sequence fills these subsets well. We can similarly define the dinreecirep,nyy where the supremum is instead taken over rectangular subsets of [0, 1]a such that one endpoint is 0.
NN be Definition (Star-diserepancy [56]). Let be the Lebesgue measure, N E IN. Let = {
sequence of points with zς E [0, 1] for all t. The star-discrepancy of the sequence x is defined as
D2 (d)
sup [Rx(J)),
(A.30)
JEF
where Ry is defined in Equation (A.2 for a Lebesgue- set J S 13 Also, E is the set of all rectangular subsets of [0, 1 iee.
E"
(A.31)
With these definitions, can define low-discrepancy sequences.
Definition (Low-discrepancy sequence [56]). A sequence of points = (xe) with me [0, 1j
for all l a low-diserepancy sequence if
(d) S (log N)
(A.32)
N
where a constant that possibly depends on d but independent of N.
The value of the constant C in this definition depends on the construction of the low-discrepancy
sequence. Several constructions of low-discrepancy sequences are known [80 77 81 57]. this work, we consider Sobol sequences in base 2 [57]. For these sequences, we have the following guarantee
Theorem (Theorem 4.17 in (7)) Let N E 1 are [0, 1]4 for all E, then the star-discrepancy satisfies
a Sobol sequence in base 2 with
(log Nyd N
(2(() S C(d)
(A.33)
where ((d) a constant satisfying
C(d)
(A.34)
d!
log(2d) 2d)
We state this result without proof and refer to [57 for details on this construction. Another important
the following bound on the star- known discrepancy bound that we will use Appendix C.3 discrepancy of uniformly random points.
Lemma 5 (Corollary in (2)). For any d > N,N 2 1 and E (0, a (uniformly) randomly generated d-dimensional point (I1, IN) satisfies
1 dd
(d) s 5.7, 4.9 + log
(A.35)
with probability at least 1 8.
21

---

As discussed earlier, low-diserepaney sequences allow us to obtain better sample complexity guar- antees for neural networks. The key result in quasi-
Carlo theory that enables this is the Koksma-Hlawka inequality [56]. In order to properly state it, we first need to define the Hardy- Krause variation. A full technical definition can found in, e.g., (54), but for our purposes, suffices to consider the following upper bound [86]. Let f be "sufficiently smooth" function. Then, its
Hardy-Krause variation can be upper bounded by
0 flv) Oy. Oya
VHK (f) & VHK = 1o.11a
dy Σ Vuk (1 2=1
(A.36)
where 5 is the restriction of the function the boundary Y: 1. If all of the mixed partial derivatives are continuous, then this inequality is actually an equality (56). Now, we can state the Noksma-Hlawke incquality.
Theorem 10 (Koksma Hlawka inequality). Let f [0. 11dh + R be a function whose mixed derivatives are absolutely integrable over its domain with bounded Kardy-Kraus variation VHK (f) < co. Let {re N be sequence of N d-dimensional points in [0, 1] with star- dirrriicrepancy D'y (d). Then
Voare f(x)
N
Σ f(xz) S (FD(()) 8=1
(A.37)
N
This theorem is used in quasi-Monte Carlo methods to estimate the error of approximating integral of function f by the empirical average of evaluated on sequence of points. Notice that if the sequence is low-discrepancy sequence, then by definition, we can upper bound the star- -ta--discrepancy D Moreover, recalling the definitions of prediction error and training error (Equations (A.23) and (A.24)), ) one can see how this relates to our task of bounding the prediction error.
To generalize results to wider class of distributions, need to extend these tools for arbitrary measures, rather than just the Lebesgue measure. First, we restate the definition of discrepancy and star-discrepancy (87).
Definition 4 (General Discrepancy 88)). Let μ be a normalized Borel measure on [0, 1] Ler x = {ar N be a sequence of points with me E [0, 1] for all f. The discrepancy with respect to μ of the sequence is defined as
Dw(d: = sup RR (Jx(J)))
(A.38)
JER
where
1 N
RN(J:P)= = Σ 1l E - u(J)
(A.39)
N
for a Borel- measuraee set J C [0, [0. Also, is the set of all rectangular subsets of [0, 1]d, i.e.,
E ai b.): a d x1
(A.40)
Definition 5 (General Star- Mta--Discrepancy (71). Let μ be normalized Borel measure on [0, 1Jd, and let N E N. Let x = { be sequence of points with Ie E [00,10 1] for all f. The star-discrepancy with respect to p. of the sequence is defined
D2 (d:
sup [Rx(J:)), JEE
(A.41)
where Rx is defined in Equation A.39 for Borel-measurable set J C [0, 11s. Also, E is the set of all rectangular subsets of [0, 1 iee.
[o. [o..):0<bb5
(A.42)
These definitions coincide with Definition D and Definition 2 when μ is the Lebesgue measure Moreover, we can define general low-discrepange sequences similarly to Definition 3 with respect this general star-discrepancy. There is also generalized Koksma-Hlawka inequality 87 which we state below.
22

---

Theorem 11 (Generalized Haaaka inequality; Theorem 1 in 87). Ler [0, 1 + R be measurable function whose mixed derivatives are absolutely integrable over its domain with bounded Hardy-K Krause variation VHæ(J) (f) < cc. Let be normalized Borel measure on [0. 10,1], and let be sequence of N d-dimensional points in [0, 1] with general star-discrepaney 1N I = } = (2 p). Then,
N [(x))
- -S [()) S (dx)))D)(()))
(A.43)
N
t=1
B Constant sample complexity
In this section, we show that with simple modification of the algorithm from [2] can reduce the sample complexity to (11) for a constant prediction error. We consider all the same definitions/no- tation as in Appendix A. This section is similar to Section IV in the Supplementary Information of [2]. As in (2). our algorithm first maps the parameter space [-1, 1] into a high-dimensional feature space RT for my given in Equation (A.8) via feature map Φ. Our simple modification is to use the feature map defined by
(()) A sign(ap) E Tw),P),
(B.1)
where each coordinate of (xx) indexed by E S(gen) x' E Xp. Note that defining the feature map in this way requires knowledge of the observable 0 Ep corresponding to the ground state property be predicted. However, in practice, this is natural assumption. The hypothesis class for our proposed MI. algorithm consists of linear functions in this feature space, i.e., functions of the form h(r)) = w (xx). Then, our algorithm learns these functions via ridge regression 65 66] For chosen hyperparameter A >> O, ridge regression finds a vector w' that solves the following optimization problem minimizing the training error subject to the constraint that |[w||2 S A
N
min WER [ [w]|.SA
w d(xx)) - yel
(B.2)
N
where ye approximates tr tr(Op(z:)). We denote the learned function by h h²(x)) w .zz). Note that the learned function does not need to achieve the minimum training error, but can some amount say <3/2 above it. For our purposes, we choose the hyperparameter to be 20(polyoog(//=)) which we justify in the next section.
Note that there two main differences from the algorithm in 2 First, recall from Appendix A. that the feature map was previously defined ((x),', p 1(x P for P E 5(geo) xx' Xp. Second, instead of using LASSO (E--regularized regression), our proposed algorithm uses ridge regression.
With this algorithm, we obtain the following guarantec.
Theorem 12 (Constant sample complexity; Detailed restatement of Theorem Let 1/e > E1, 62, Eg > 0 and 8 > 0, Given training data {(x,, ve) of size
log (ooel///oolllot/////oooooooll/)
(B.3)
where xe is sampled from D and ye is an estimator of tr(p((z)) such that lye tr((p((z)) S c2. the ML algorithm can produce h" (x) that achieves prediction error
E
tr(p(=)) (())))()))((((++))))) 22) +
(B.4)
IND
with probability at least 1 8.8. 8. The training time for constructing the hypothesis function h" and the prediction time for computing hi" (xx) are upper bounded by
O(m)polylog(1/822) 1 /ttl1//000000/0///////aaa
(B.5)
Comparing to Theorem 7 notice that our sample complexity guarantee completely independent of system size
23

---

The theorem in the main text corresponds to = 0.2c, 62 and 63 0.4c. In this way, (e) + 62)² I 1.44c² I 0.53e and (G1 + + c3 S.
So far, we have only considered the setting which we learn a specific ground state property tr(Op(a)) for fixed observable O. Because our training data is given in the form ((1,, be) where approximates tr(Op(z)) for this fixed observable O, if we want to predict a new property for the same ground state p(z), we would need generate new training data. Thus, may be more useful to learn ground state representation, from which we could predict tr(Op(z)) for many different choices of observables O without requiring new training data. In this case, suppose we are instead given training data {az, (((z)))]==> where (p(p(zz) is a classical shadow representation [52 68 69 70 7 of the ground state p(æz). An immediate corollary of Theorem 12 is that we can predict ground state representations with the same sample complexity. This follows from the same proof as Corollary 5 in [2]
Corollary 3 (Learning representations of ground states; detailed restatement of Corollary D. Let 1/e > E1, E2, E3 >> 0 and > O. Given training data
of size
= looll//6)///// (att)))))ottee((/aaaaaaaaaaaaaaa
(B.6)
where 2e is sampled from D and o (p(z)) is the classical shadow representation of the ground state p(æz) using T randomized Pauli measurements. For T = (Log((2V/0)) (log((n66)/ the ML algorithm produce ground state representatiion (N,T(I) that achieves
| [t((OpN,(<z) (r(x)r(())))-(0()))))))) (e1 62) +
F z~D
(B.7)
with probability at least 1- - 6, for any observable with eigenvalues between -1 and 1 that can be written as a sum of geometrically local observables.
We note that the number of measurements T needed to generate the training data scales as log(n), but the amount training data still remains constant with respect to system size. We do not consider the number of measurements as contributing to the sample complexity because in our setting, the ML algorithm is given this training data as input and does not generate itself.
B.1 Training error bound
To prove Theorem 12 we first derive a bound on the training error. Recall that the training error is defined as
R((h) min 1 N
Σ [M(x))) -vl
(B.8)
Define the vector w with entries indexed by P E S(800) x' Xx by
Wx'pP aap ur (P)(xp(1)),
(B.9)
where Xx(x) is defined in Equation A.16 Then, notice that
x(x) - w
((x)
(B.10)
Σ
Σ
sigpaarloopptiP/xxxeellllll Tr.e
(B.11)
PeS(er) z'EXp
Σ
Σ
(B.
PeS( r'EXp
= w' +((x)
(B.13)
g(x),
(B.14)
where g(x) w'-o(x) with w = ap ap ()(p(x((())) ((x)rrP = 1fx Te.P). By Lemmal 1 know that g(x)) approximates the ground state property with low training error, and thus, in turn, g(x) also approximates the ground state property well. The existence of w such that ğ(x) w Ō(x)
guarantees that the function h² (x) = w xxxx) found by performing via ridge regression will also yield small training error. More formally, have the following guarantee
24

---

Lemma 6 (Training error). The function
ğ(z) w x(x)
= Σ
Σ
(B.15)
PESOxe)) x'EXp
achieves training error
R(0) S (1 (c)
(B.16)
Since ((æ) (()), this follows directly from Lemma Moreover, we can obtain an fg-norm bound on w. We can utilize this upper bound choose the hyperparameter A such that || A.
Thus, we have the following lemma,
Lemma (fr-Norm bound). have
Let w be the vector of coefficients defined in Equation
B. Then, we
Σ
E
|a
[(Pp((p(p)))) - 20ppolyoo((/ea))
(B.17)
PES(x() x'EXp
Proof. This simple consequence of Lemma
Explicitly, we have
|w|2=
Σ [a=]|u((p((x(()))]
(B.18)
PeS(se)) z'EXp
|ap||=[(P((x<()))
(B.19)
PES(AC)) x'EXp
2 (polyyoog(1/er))
(B.20)
where the second line follows because tr tr(Pp(xp(z))) & 1 and the last line follows by Lemma
This justifies our choice of 2(poolyoo((1/e)) Now consider the learned function h h"(x) w* (xx), where w is found by minimizing the training error subject to the constraint that ||w||2 S We do not require the learned function achieve the minimum training error, but it can be some amount 63/2 above it, i..,
1 N
R(h")
+ min
Σ w Ö(xz) - yel
(B.21)
2
|wl
Since we chose (0polylog(1/ei) and we showed in Lemma 7 that || S A, then the minimum
training error is at most R(ğ). We also know that this is bounded by (el + e2)² by Lemma 6 This then implies
R((h)) + (((g) s (er + E2) E3
(B.22)
B.2
Prediction error bound
To prove Theorem 12 remains bound the prediction error. We machine learning theory on the prediction error of ridge regression algorithms [66] 64]
standard result from
Theorem 13 (Theorem 26.1 12 in (66)). Suppose that is a distribution over X' x y such that with |w|] |w]l22 A} and let é H. Z R be a loss function of the form E(w, (x,1)) v)) ø(w x, y) such that for all E V, + a(a, y) is g-Lipschitz function and such that max
probability we have that ||x||2
Let H fx
(a, y)1 c. Then, for any å (0, 1), with
probability of at least 1 5 over the choice of an i.i.d. sample of size for all E H.
2pAR
log(2//)
R(h) < R(((h) +
+ +op
(B.23)
VN
Here, R(h) denotes the prediction error for the hypothesis h. With this, we can complete the proof of Theorem
25

---

Proof of Theorem 72 First, let us reframe the theorem in our setting. Consider the imput space X
to be the parameter space [-1, 1 and our input variable is x Φ(x). Since the observables we consider have spectral norm most 1, the output space fulfils y 1 1]. The hypothesis set
H {x + w ((x) ||w]l2 A}. where in the previous section, we set 20(polylog(//ei))
It remains to check the conditions of the theorem. We begin by showing that | S R for some R > O. We have the following computation:
|x||| = Ō(x) x(x) = [0(x) ||
(B.24)
= =E
Σ
sign(ap) TTpp
(B.25)
P x' ex
Σ
Σ
lor|1fx E Tp.p)
(B.26)
PES(se) z'EXp
Σ
larl
(B.27)
PES(
= =1)),
(B.28)
where the second to last line follows because for given P. E Trip P for exactly one x' E Xp. This is shown in Corollary R = ((1)
[2]. Also, the last line follows by Theorem Thus, we can take
Finally, note that E(w, (x, 8)) |w x yl @(w x, v). Therefore, Φ(a, y) is 1-Lipschitz function and fulfils
max la - -- S AR ARA- Thus, consider p and 0(1) 20(poyyoo(((/)/) +1.
max AR,-A
16(a, 3)1
(B.29)
By Equation B.22). know that the learned model h²(x) w -z(x) achieves
A(hh) = (G c2)
63
(B.30)
2
Plugging in R = 0(1), 1, A = 20pooylog(1/et) and c 0(1) (0ppoylog(1/en) + into Theorem we have
R(h") - (G1 + )2)²² 63
(B.31)
2
+ VN (001)) 20polylog((/ee))
1
(0(1) ( 20 +1) v log(2/8) (B.32)
with probability least 1 ó. In order bound the prediction emror by (E1 c2) ) + 63, we need N to be large enough such that
(20(1)- 20pololog(2/e1) + (O(1): - 20poollog(///ii) + +1) 2 log(2/5)
I 2
(B.33)
Solving for N in this inequality and simplifying we have
N 4 20pplylog(1/a)) (1 + Vlog(1/8))² 200lo((/e 1og(1/8).
(B.34)
Thus, for this N. we can guarantee that R(h*) < (EI e2)² + E3, claimed.
On another note, when considering scenario with a fixed number of parameters m = 0(1), much like the setting in [5 the expression derived from the result in Lemma 10) exhibits polynomial dependence on 6. One can incorporate the constant number of parameters by setting mn = m. Thus, we recover the exact ground state properties tr(Pp(x)) fe and the approximation error resulting from applying Lemma vanishes completely. Furthermore, we can slightly adapt the proof of Lemma 7 and obtain
Σ
Σ
larl] (pp(xt(((ppx)())) =
max
Xrr
Σ (E
larl = O(c"),, (B.35)
PeSTom) x'EXp
where the last step is performed similarly as in the proof of Lemma
26

---

B.3
Computational time for training and prediction
remains analyze the computational time for the ML algorithm's 's training and prediction.
The training time is dominated by the time required for ridge regression over the feature space defined by the feature map Φb Recall that the optimization problem under considerations is
Proof of computational time in Theorem 72
N
min W W
w Ō(xx) - ye ?
(B.36)
N
One can show that this is convex optimization problem so that we can solve its equivalent dual problem instead. This dual optimization problem given by
max aER
a (K + Al)a + 2a Y,
(B.37)
where the kernel matrix is K = XTX, for the feature matrix E RT defined by X (Ō(=1) ... ((xx)) and the response vector Y -y1,...,,y'' UN If x. is the maximum time it takes to compute a kernel entry K (xx,x') = ((x) "(x'). then one can show that the time to solve this dual be executed in OxxN). For more details in this
problem is +xxN² )²). Moreover, prediction
analysis, we refer the reader to, e.g., Section 1 11.3.2 of (64).
In our case, & = O(ms) since δ(x) Rm and the kernel is simply the dot product two of these vectors. By Equation (A.8), we know that
m ((n)2))polyyoo(Laa)
(B.38)
so that O Moreover, by Theorem 12
N log (L())))2000o(UU))aaaaooooo
(B.39)
Plugging this into the time required to solve the dual problem for kernel ridge regression, we have
Onx22 + 2² = Chappppyood//ggg0leessss/hhaaaap
(B.40)
Moreover, the prediction time is given by
OkNN) //opppoooooo///pphhh////////a//a
(B.41)
C Rigorous guarantees for neural networks
In this section, derive a rigorous guarantee on the sample complexity of deep-learning based model for predicting ground state properties. Similarly to the previous sections, let 1/c > (1, 62, > throughout. One can think of 6 as the approximation error caused by our neural network model not exactly capturing the ground state property; 62 represents the noise in the training data; 63 corresponds to the generalization error.
Recall again the setup, where we consider family of n-qubit Hamiltonians H(x) Ef (T,
parameterized by an m-dimeensional vector x E [-1, 1)mh, which satisfies the assumptions (c) in
Appendix A.] Let p(z) denote the ground state of (z). We consider the task of predicting ground state properties tr tr(Op(z)) for some observable that satisfies assumption (d) in Appendix A. where given training data { ye) ) with z x tr(Op(zz)). In particular, suppose lyee tr(Op(zz)) < E2 Furthermore, we also assume that all mixed partial derivatives of order
v A Ipl of h2 are bounded as
m
h (x)
S 1,
(C.1)
De Org
Oxm
where Tp the set of local coordinates defined in Equation A.2). Here, we denote the number of local coordinates by m //ll for ease of notation. This is similar in spirit to assumption (b) in
27

---

which we assume that the local terms have bounded directional derivatives: ||āh,/0ūl S 1, where is a unit vector in parameter space.
Let S(geo) denote the set of geometrically local Pauli observables. Our deep neural network model consists of [S(Reo]] = (n)) "local" multi- perceptron models (defined in generally in Ap- pendix | with two hidden layers and tanh activation functions. Their outputs are combined through a linear layer without activation function. Formally, our model is defined as follows.
Definition (Deep neural network model). The neural network model is given by function fo. 1-1, 1,m + R defined by
Σ
wPsP (x);
Op
(C.2)
PESTON)
where the "local models" f/r 11-1,11m= + R are given by
f8 (x) (Wout o tanh o Whidden tanh Win oF
(C.3)
with T- (x) = (z + 1)/2 and 0p ((Win: (W hiddenn bhidden), (Wout, bour)]. Here, Win RüxW bin E RW,, Wiideen E IRW bridden E RW, W Wout E RW and bout E R, where W denotes the width of the hidden layers. The weights given by Q {0p: P E S(ieoo) in the local models and w E in the last layer. Furthermore, we denote the individual parameters by O₂ E R.
Using this model, we can establish an objective function that we aim to minimize during the training process. Specifically, this objective function comprises the mean square error along with lasso penalty applied to the weights wo in the final layer.
Definition 7 (Training objective). Let f be neural network model in Desinition 6 Let {(12, ye) 12 be the training data set and X > 0 be some regularization parameter that may depend on E2 0. The training objective is given by
N
(xx))) - yel? + A/[w||2.
(C.4)
N
Our proposed ML algorithm then operates as in Algorithm
Algorithm 1: Deep learning- prediction of ground state properties
Sample N low-discrepancy points {
Collect training labels {ye) J.V where ye tr(Op(z))):
Data: (112, (
Fix Tpl:
Initialize model architecture according Definition witth appropriate hyperparameter 8, width W as in Theorem a6] weights O, w using an appropriate initialization method (c.g., Xavier initialization 772
Train with respect to the objective in Definition 7 with appropriate hyperparameter À >> 0 using a quasi-Monte Carlo training algorithm, e.g., Adam 73 until convergence: Obtain locally optimal parameters O* w";
Result: Classical representation rer "=""""
After training our model using Algorithm I we obtain the following rigorous guarantee.
Theorem 14 (Neural network sample complexity guarantec). Let 1/c E1, 61,62, cg > O. Let f0r,""" 11 + IR be a neural network model produced from Algorithm 7 trained on data {(rs ve) N
of size
N (tgppoowwlggt/////ooooooog//////
(C.5)
where the ve's 's form a low-discrepancy Sobol sequence and ye ir(Op(zz))) S e2. Suppose that gor _s=" "0""" achieves a training error of at most ((q x2)² + c3)/2. Additionally, suppose that all parameters O of g satisfy |0 < Wmaxo for some Wmax > 0 that is independent of the system
size n. Then the neural network fb .w¹ achieves prediction error
8 "00"."" (x) tr(pp())) < 2(e1 =2) + c3:
(C.6)
W~ 1111pm
where x U1-1, 11th denotes sampling x from uniform distribution over [-1,
28

---

We prove this theorem in the next two sections (Appendices C.1 and C.2). As a corollary of this, we obtain the theorem stated in the main text. We discuss the assumptions that the distribution D must
satisfy in depth and prove the corollary in Appendix C.3 The theorem in the main text (Theorem
5
corresponds 61 = 63 = 0.1c and 62 = c. Hence, 2 + c2)² 2.44c I 0.9c for 1/e
and so 2(c1 + 22) 63 S c.
Corollary 4 (Neural network sample complexity guarantee; detailed restatement of Theorem 3 let
1/e E1, E2, eg 0. distribution with PDF g satisfying the following properties: g has full support and is continuously differentiable on 1-,, Moreover, is of the form
g(x) II (T,))
(C.7)
f0','', Let fer "0"; 1-11,11 - R be neural network model produced from Algorithm trained on data ((Te, v) of size
N = (bgt1//8yy2llooooat/////>)ooo
(C.8)
where the It ~ D and ye tr(Op(xz)) I <2- Suppose that f8r ,"' achieves a training error of at most ((E) + E2)² + e2) Additionally. suppose that all parameters Ø of f _"" satisfy 10; &
some max > that is independent of the system size n. Then the neural network fot s²" achieves prediction error
E 1f """""" - tr(p))(( 2(e1 + +2)² +E3.
(C.9)
IND
with probability at least
Moreover, while we can show the existence of suitable parameters that achieve a low training error. quantified by our training objective in Definition 7 in general, we cannot prove that Algorithm ] converges to parameters close this optimum because our training objective not convex. Thus, to
obtain the guarantee in Theorem 14 we need to assume that low training error is indeed achieved by Algorithm [ This is commonly satisfied in practice.
Similar to Corollary if we are instead given training data {Iy, (r(p(z)))) where (p((pz)) is
71 of the ground state p(zze) then immediate corollary of Theorem 14is that we can predict ground state representations with the same sample complexity. This follows from the same proof as Corollary 5 in 22.
classical shadow representation [52 68 69 70
Corollary 5 (Learning representations of ground states with neural networks; detailed restatement of Corollary 2). Let 1/e > E1, 62, E3 > and ô > Given training data {(I,, or (p(x)))) of size
N (oogl///
(C.10)
where ze is sampled from a distribution satisfying the same assumptions as Corollary and or (p(xz) is the classical shadow representation of the ground state p(zz) using T randomized Pauli measurements. For T = (loog(nN//)/e = (llo((n/8)/() the ML algorithm can produce ground state representation (x.)(x) that achieves
[t((Opx.(())) - tr(00(=)) < 2(c1 + 62)
(C.11)
RnD
with probability at least - 6, for any observable with eigenvalues between - and 1 that can be written as sum of geometrically local observables.
We review low-discrepancy sequences and techniques in quasi-Monte Carlo theory in Appendix A.2 which we use our proof. To prove Theorem 14, we first show that there exists weights O' w' such that our proposed neural network fe', _e" achieves low training error, i.e., approximates the ground state properties tr tr(Op(z)) well. We show this using results in classical deep learning theory about approximating arbitrary functions with neural networks (53]. Then, we use the Koksma-Hlaww Hlawka inequality (Theorem 10 to bound the prediction error of our model, similarly to [54]. As we want to derive a bound which is independent of the size of the physical system, our approach requires some additional steps. Since the dimension of the input domain of our model depends on the size of the physical system, we cannot treat as constant in (54. Therefore, we bound the prediction error with respect to local functions, whose domain size is independent of the system size.
29

---

Moreover, recall that the Koksma-Hlawis inequality produces bound in terms of the star-discrepang (Definition 2) and the Hardy-Krauu Krause variation. The star-discrepancy can be bounded by considering low-discrepancy sequences (Definition 3 and the Hardy-Krause variation can be bounded by Equation (A.36). We derive explicit bounds for the Hardy- Krause variation of the ground state properties tr tr(Op(zr), using tools from the spectral flow formalism [59] 660 61]. To obtain Corollary we follow a similar proof but use results relating the discrepancy with respect to the Lebesgue measure
to the discrepancy with respect to arbitrary measures and bounds on the discrepancy of uniformly random points (Appendix A.2)).
we prove that our model approximates the ground state properties well. Then, in Appendix C.2, use the Loksma-Hlawke inequality bound the prediction error of our model. Technical results explicitly bounding the mixed partial derivatives of the ground state properties are found in Appendix C.4 We use these in Appendix C.2 to bound the Hardy-Krause variation. We
In Appendix C.I
then generalize this to data sampled from different distributions, as in Corollary 4 in Appendix C.3
C.1 Approximation of ground state properties by neural networks
In this section, we prove that when choosing the number of parameters and width of the model appropriately, there exists a parameter set for which the deep neural network model approximates the ground state properties well. This shows the existence of neural network with low training error. The proof is a direct application of the main result from (53), which proves that tanh neural networks can approximate sufficiently smooth functions, in combination with the bounds on the mixed derivative of (r(Pp(z)) we derived in Appendix C.4
We consider the local functions defined as in Appendix A.1.2 Namely, define f(x) Eesteoo) (pfr(x), where fr(x)= = tr(Pp(xp(xt) for O EPE(L.XY.2JO. apP and
Xp(x), = {000 Fee CE
(C.12)
c Ip
for all E {1.....m m) for 1p defined in Equation (A.2) Note that here, we slightly alter the definition from Appendix where we do not include the coefficient ap in the definition of fr(z). Because all parameters with coordinates not in 1p are set to O, can view fp function taking inputs in []1, where recall that we use m |p| to denote the number of local coordinates.
We show that there exists a neural network that can approximate these local functions fo well. In order to apply the result from 53 to approximate tr( (r(P)(x((x))) we need to transform its inputs, such that it becomes map (0, 1 - R. Therefore, we introduce an appropriate function
T(r) = 2x To avoid confusion when considering the different domains [-1, 1)mh versus [0, 1)m", if an input [-1, I|"h, simply denote it by If [0, 1) we denote it æ. We similarly use this notation for other domain dimensions.
In the following lemma, we use W (52 for Ω C 1T to denote the Sobolev space
gialS
tho (22) & (EL Or Oz
E L ( for all a E Ng with |a| S k
(C.13)
so that the Sobolev norm is defined as
alal f
max [a|=s
(C.14)
Fx
(x)))
for a E N and the _ norm is defined by [[
sup #eft
(C.15)
Lemma 8 (Existence of approximating neural network). Let E > 0. s. E N. Let
[H(=)]l===(((..))) < 1. Define functions fP [0, R fr(r(ā)) (((p((x((7())) where T(ž) = 25 - 1. Then, there exist neural networks fM such that
|
(1= Se
(C.16)
with at most 6
m+1 20th log(m))
parameters. Furthermore, the weights scale (poly(log(/ee)).l)
30

---

To prove this, we utilize the main result from [53]. which states that neural network with tanh activation functions can approximate effectively any function.
Theorem 15 (Theorem 5.1 in (31). Let d. E IN R > O, d > O and f E W ((0, 1."). There exist constants C(d, k 8, f). No(d) > O, such that for every N with > No(d) there exists a lanh neural network fN with two hidden layers, one of width at most 3| 1 P- + d(N 1) (where [Pn.a (m+d-1)) and another of width at most 3 d+2 P Nd (or 3 2 + N and 6.N for d = 1), such that,
Ilf fM [11=(10111)) S (1+ 8) C(d,0,
(C.17)
N
and for 1,...,8-
Ilf (1 $ - =3((00))(((++ max A* In (BNotct22} C(d, ki S)
(C.18)
No-k
where we define
k Vd [ (10.000)
(C.19)
8 m s,(d,k,s,
E ( 1](), then it holds that
1
3d 8-1
3d
Cid, 8,
max Osisk
If/wa.0(00.19))
No(d) 2
(C.20)
(s - 1)!
and else it holds that
max 71/410 /8 OStck (s (s-l- 1)!
k. S. kt In addition, the weights of fN scale as (c=s/22ddctt 22) 2))3a(x+2))
(5d7)* Iflw..>(uu.)))))
No(d) =5d.
(C.21)
The proof of Lemma follows by an application of Theorem 15
Proof of Lemma g We directly apply Theorem 15 with the input space dimension m, where mn is the number of local parameters m = [Ip.. By Corollary g then we have
(1 +1+
3mCss 8
fpor - -M
(C.22)
s!
2M
We want show that this is bounded above by 61. By rearranging, we find that this holds when
1
6 - (1++))
3 mCs² < M.
2
(C.23)
Note that by composing with fp with т, we acquire an extra factor of 2", which can be considered a component of C. Using M O(E ms?), this results in the widths of the two layers being
s
+
m 2
2m M
+ m(M 1) and m + 1
(C.24)
2
d + 1
and therefore most
(c.m)oume
m-
20 (l(g)
(C.25)
trainable weights in the neural network. The constants e₁ and c2 independent of m, but may depend on s. By Theorem [5] the weights scale as
o (( (cc- c-0/2 (ei' mms) of
(s(s + 2) 23))0(0+22)
=1
m-1
(1(hloo((m))
log(m))
(C.26)
31

---

Although the dependence on s is not relevant for our final statement, it is important to comment on the effect of the smoothness of H (x). The result states that the dependence of the required parameters with respect to 1 1/c1 improves with the highest degree for which all mixed derivatives of (xx) are bounded. When (xr) is analytic, 8 can chosen be very large so that the number parameters in the neural network almost scales as Ofms The constant scales rather poorly with s; however, this effect is only be visible for very small 61.
Using Lemma 8 we can show that there exist parameters such that the complete model approximates (r(Op())) and obtains a small training objective (defined in Definition) 7 The theorem (Theorem 6)
in the main text corresponds to E 0.2c, E2 e so that (c1 E2) S I.442 I 0.53e <.
Theorem 16 (Detailed restatement of Theorem 6). For any 1/e c1. c2 0 and appropriate width W, there exist weights O' w' such that the neural network model for ,w' satisfies
| w' (x) - tr(Op(z))) 61
(C.27)
for any [-1, In particular, for any collection of N training data points {(ze. yo) with lyee tr(Op(ze)) S 62, we have
p w (Fx) vel2 X||wo|1 (c
(C.28)
N
for a suitable choice of regularization parameter À = Oct)). Moreover, each parameter O of the network has a magnitude @ (20oolyoo())/e1)
Proof. Write O =Epaptr(Pp(e)) By Theorem g let D (1) be constant such that
Σ Japl S D.
(C.29)
For every Pauli P. then by Lemma 8 there exist weights Or, such that a neural network 5% [0, 1 + with two hidden layers as in O
the local functions fr (r(()) = tr( (P)())(((())) where Tα)) 27 up to error </(4D), when the width of their hidden
m+1 20 log (17)) where the number of local coordinates is given by layers is chosen as W E
in l/pl and by the smoothness assumption Item (d) s N 1. In other words, we have
(P())=((Pppx((7(())) 4D
(C.30)
where 3 e [0, 1] Because 7 simply a coordinate transformation, then we also obtain
(rPpxx(((())))) s 61
(C.31)
4D
for x E [-1,
Furthermore, by Lemma in Appendix A.1.2 the sum of the local functions f(x) apfr(a) approximates the ground state property (r()p())) = Σp ap tr(Pp(z)) well. In particular, combin- ing Lemma with Theorem 8 have
Σ aapt((p(xp(e)))
Σ ap (ptr((P(()) S E1
(C.32)
This holds when choosing the local radius 8, (defined in Equation (A. ) to be 61 = 4C (1/ee) for some constant C. This implies that m = |Trl (ppoyylog( 1/ (e.g., Equation (S33) of 2
Thus, for the model fe' with architecture defined in Definition and weights w/p ap and O' = {6r}p, we have
r (x) - (r(Op(z))
(C.33)
Caps E -u((Po(x((o)) + Σ ((PP(xp())) tr((p(x))
(C.34)
32

---

Σ lap
c1
Σ [r((Po(x(=)))) - E D cr(Po(z))
(C.35)
AD
61
+
tr(Pp(x((a)) E cr((p(()))
(C.36)
4
61
(C.37)
2
Moreover, by definition of the training data, we have lye tr(Op(ze)) S c2. Thus, by triangle inequality and choosing regularization parameter (2((DD, we have
N N
p al (Ix) vel A1/w'll1
(C.38)
1
8 ad (Ix) + - yel +Nllw'li
(C.39)
N
2 (e1/2 + 62) + N|w'll
(C.40)
1 (1
2 +
&
2 +
(C.41)
2
< 22)
(C.42)
Finally, plugging in m = Opoolyog(1/aa), by Lemma 8 then we obtain [6 = (0ppoylog((/ea) required.
C.2 Prediction error bound
In this section, we derive our result on the prediction error to complete the proof of Theorem 14 The central result we use is the aakssa-HHlawka inequality (Theorem [T) from quasi-Monte Carlo theory, which produces bound in terms of the star-discrepancy (Definition 2 and the Hardy-Krause variation (Equation (A.36). We review these tools Appendix A.. To bound the star-discrepancy, we consider specific low-discrepancy sequence with guarantees described in Appendix A.2 The Hardy-Krause variation can bounded by considering the mixed derivatives of our target function tr(Op(z)) and neural network model. We relegate the bounds on the mixed derivatives of (r()p()) to Appendix C..4 as the discussion is fairly technical. To bound the mixed derivatives of model, we consider the following lemma.
Lemma (Bound on mixed derivatives of neural network). Let k. d E Let 1-1, + R be a tanh neural network with two hidden layers of width W 2 d and maximal weight Wmax- Then
(1-1,119) 20k log(k)+ (ow(edWWW/)))) Wmax))
(C.43)
Proof. Recall that tanh deep neural network with hidden layers is defined as function f: [-1, -> such that
f()) = (Wout tanh o Whidden tanh W (z))
(C.44)
where the activation function tanh is applied element-wise. Note that this result holds for any tanh neural network with two hidden layers, where this neural network does not necessarily have to be the same model as Definition 6
Let W, E (Win: Whidden, Wont } denote the layers of the neural network that perform an affine transformation for L E {in, hidden, out]. We can also use L E {0, 1),), where 0 corresponds to in, 1 corresponds to hidden, and corresponds to out. Let d, denote the width (number of input neurons) in each layer, where we define do din, dj d2 W, d3 dout- In this way. W2 Rdd - Rd for {0, 1, 2}. Explicitly, we have Wi, Rdi.. - RWW Whidden W - RW Wout : RRW - Rdout,
Since Wa performs an affine transformation, we can write it has Wz = (f1 (z), farm (z)),
where Rdz and fi are linear functions f((z) w. x b, for wy Rdz by E R. For these linear
33

---

layers, we observe for any function g: R - Rd with input dimension dg and for L E (0,1,2)
we have
max ggidd++1
IIWL o g): g):ll
max [If(g(e))lllv..o(--111)) IgiSd
(C.45)
1111
|/ g(x) + billlx..
(C.46)
max 1 13i
(C.47)
where we use the notation
d
WElh A
[bs]
+
(C.48)
where w is matrix with rows given by the vectors w. wy [R42, To show this inequality, we used Hölder's inequality in the last step. With this, by factoring out one layer Wr. at a time, we can bound the Sobolev norm of f. In particular, we have
I ((1.)))
(C.49)
(W lanh o Whidden tanh o (w))
(C.50)
|| Woutll [1 max [1 o W Wiideen tanh o Win)sllws.. 15/5
(C.51)
Wouth | 16(e 2 k(++1)
max 1575
[W hidden o tanh
(C.52)
Woot (alullllWWiiddn
1lf 16( (2A) (k++1) max [[(annh Win) Win):llixx=<(1111)1
(2k)
(C.53)
15i$W
Won ||
||WiaddeeW 11 16 dd) (2k) 2k(k+1) W
(C.54)
In the second line, we used Equation CC.47 In the third line, we used the two following inequalities:
dm
tanh(x))
s (2m) minfexp(-2o)) exp(2xx)
(C.55)
dx
for all x E R, m E N (see Lemma A.4 in (31). and
llg o fllw S 16(e n (oimdd) IIgll
max Ises
II
(C.56)
for any functions f C (n( and g E C' (S2g; R) defined Q C Rd. Q2 C RR with d, m, n E N (see Lemma A.7 in (33). In the fourth and fifth lines, we used Equation (C.47) and these inequalities again. Furthermore, we used that our inputs are absolutely bounded by in the last step.
We can further bound this term using that Waxx is the maximal weight of f and the width of the hidden layers lower bounded by W 2 d.
[1flw S 16a (62 (2k) 1h(k+1))k2 33++1 200k(( Wmae<
max
(C.57)
Now we have all the necessary tools in order to derive bound on the generalization error for our neural network model of the form given in Definition 6 In our proof, we first bound the prediction error in terms of functions with 2m--imension Boksma-Hlawwke incquality. Then, we use the previous result to obtain an explicit bound. Due to the regularity of the parameters ax and our model parameters wp, this prediction error bound is independent of the system size n.
domain and which we can directly apply the
Before stating the formal result bounding the prediction error, we introduce some notation. We define the prediction error a neural network pe.w w with weights given by θ w as
R(O)
A
E
()0)"()) (x) tr(Op(=)))
(C.58)
p~ -1
34

---

where in our case, a ~ -[-1, 11th denotes sampled from a uniform distribution over [-1, 1|" We suppress the notation avoid cluttering. For neural network fe. generated from training on some data {(ze, ye)) we can define the training emor as
1
R(O)
I 8 (xe) yel..
(C.59)
Moreover, as in our analysis Appendix C.I we rely on an approximation of the ground state prop- enty (x)) by sum of smooth local functions Σp fr(r) (Lemma 2). Namely, combining Lemma 2 and Theorem we have that for 6 > 0, then choosing > as Equation (A.5). i.e.,
51 (log" 2 (1/G)),
- (r S
E1 2
(C.60)
Note that here, again, slightly alter the definition from Appendix A.1.2. where do not include the coefficient ap in the definition of fe(x). With these definitions, we have the following guarantee on the prediction error.
Consider a lanh neural network fo., 1- - IR with architecture defined in Definition 7 with weights O₁ S Wmax for some Wmax independent the system size and weights w in the last layer. Suppose train f on data {(re, be) of size N, where the xe 's form a low-discrepancy sequence with star star-discrepang D and lye tr((O((z))) 62. Then, we have
Lemma 10 (Prediction error bound). Let 1/e c1,
+ of
R(O)= & (()))
+ 2 + (1well + 1wll)) [[polylog(W Wenx/es))
(C.61)
2
where m- [p| O (log (lgg@211/))) (1/a)) for Ip defined in Equation A.2
Proof. Recall the definition of neural network model in Definition 6 In particular, model is given by a function 90 [-,1, 11 + IR defined by
g = Σ PES(
wpfp (z):
(C.62)
where we refer to ffr 1_,, + R as the local models. For f2(x) tr(Pp(xp(z))) as considered in Equation (C60)) we can define the following quantities. Define the training error with respect to this local approximation by
Rion (
Σ
(0.)())) - Eapsp((n)
(C.63)
Also define the prediction error with respect to the local approximation as
Rine )
E
Earsr(s)
(C.64)
xNO 1.11
where x ~ U[-1, 1) means that is sampled according to the uniform distribution.
By Lemma 2. for our choice of 8,, we have Equation (C.60):
Σ arfr(x) (r((r(t)-i(OOpaaa))) <
E1
(C.65)
2
By the triangle inequality, we can bound the prediction error as
ot
R(O)=
E
e (z) Σ @aff((z) + E -apfp(t)-u(0ppp))) Rlo
-~U[-1,1]"
(C.66)
35

---

By applying the reverse triangle inequality, we can further bound this as
c
R(O) -
+ (9) + (Rlo (e))
(C.67)
4
c
+
(e)
(C.68)
4
N (xx) - apSp(v0)
+
E
(0) - Σ Eapso(x)
(C.69)
m- U--U1-1
N
+
(C.70)
4
2
N
+
E
pe (z) (x)
(a))(((()((
Σ P
wpfp
80 (xt) - arfr((t))
1-111m
N
t=
(C.71)
We can expand the term in the expectation/sum as follows
Σ wpff (2))((()) (z)- arfp(x)
(C.72)
[artells) + (Iartela)
Σ wpf pip
(x) (x)
-2 Σ Supfpr fr (()
(C.73)
Dr wP. (2) P.
Orz (x) 2wp,
en
-
(C.74)
Plugging this into the absolute value term in Equation inequality, we have
C.7l and upper bounding it with the triangle
|Bloc(0) (9) (9)l <
U (x)
pp 2 (x)]
1
Σ
fr.
9pz (Iz) (xz)
--U(-1,1]
N
PI
t=1
lorzl
F 1_11-1
OPI
(x) (z) (x))
Sn (1e)
Mp
N
N
+ 11
UA (x)ss - N (n(W))A( p~U1-1,1]"
1
Σ
(C.75)
Notice that in the expectation over [-1, 1 1mm we can replace this by an expectation over the set of local parameters, i.e., the parameters with coordinates Ip, U Tp., which we denote by Sp, This is because the functions in the expectations parameters. The dimension of the domain we integrate over thus becomes independent of the system size as P.p.PP. < 2m 2//pl.
local functions that only depend on these local
We can now bound this term further using the Koksma-Hlawka inequality (Theorem TOp. We apply a simple variable transformation r(z) 2x - 1 so that the domain of fp o o becomes [0, 1]"h. Furthermore, we denote the domain associated with Sp.P, by 2p,,ps 2 [0, 11 Starting with
the first term in Equation (C.7). we obtain
E
f (T(3))
1
jA
8p (π(Ze)) (T(3))
(C.76)
2~110.11m
N
1=1
N
1r (T(
1
fr.
(T(2)))
(C.77)
N
36

---

NV
1o (T or (r(3))do
f (T(2))) (T(3T))
(C.78)
Sp,.ps P2
< Diy VnK (UR 8p, Sr )
(C.79)
where F2 = - (x)) (zt), such that Equation (C.76) matches the expression referenced in Equation (C.75) Note that we also applied in the last step that the sarrdiicrepancy is increasing with respect to the dimension of the sequence. By application of the chain rule and the Cauchy-Schwarte inequality in the definition of the Hardy-Krant Krause variation (Equation (A.36), is easy to see that
VHK (UPA ( S
2 VHK(P pr,
(C.80)
For all subsets S' S Ps, applying the product rule yields
0 S"1
Ø|Ai
Mrz P2
Arz P2
2 log( WWW.wwm +ihh log(())), log()))))))))))))))))))))))))))) (C.81)
Up.
S
J
Ōrg
AÇS
where the last equality follows from applying Lemma 9
from Appendix C.4 with k 2m and 8i
[A: A S S = 2 Here, we are using the notation drn to denote the mixed derivative with respect to all parameters 24 E B for some set B. Thus, applying Lemma 9 again, we obtain
@is'1
VHKUPP, SP5
Or (P))
Um
)
20 log (og(()))
(C.82)
Örs
Sr
Thus, putting it all together, we see that
E S (x) OPz (x)]
(x)
Σ
S (2))f
0rz (xe)
(C.83)
a~U1 1-U1-
s 2 DI (2m) (r log(W LoogWWWWmseee Wms 1ogs))
(C.84)
The remaining terms in Equation CC75) can be bounded similarly using Lemma 22 from Ap- pendix C.4 This lemma is applicable to fp because the derivatives are with respect to the local parameters. In this way, we can upper bound Equation (C.75) by
Rioo(()) (ooo(())
Σ PL
(1wp, 1/pp, /wp, Iap,, log(W log(m))
(C.85)
+aa Iap (20(m D (2m).
(C.86)
Plugging this back in to Equation (C.67 we have
e R(O)= + (l) +
Σ
([wp, wwp Iwp, Ila (m log(WWoax)) log(m)
(C.87)
P1.
+app, ||ppp (m log(m))) (M( D (2m).
(C.88)
Lastly, we can bound RIoc (l) $ 2//4 A(0) in the same way in Equation C.66
NN
Rioc (
(
Σ Caffr(x((z)))
(C.89)
N
8=1
P
N
2
+lye tr(Op(z:))) tr(Op(z))) Σ Carfr(xe(ze)
N
8=1
(C.90)
&
< A(()) + E +
(C.91)
37

---

Inserting m = [pl = O (polylog (1/e1)) and using that Σp lappl = (1) (Theorem 8 yields
c + c + (1|2)11 + [ (2m) (pooyylog Wmax/e1))
R(() < (())
(C.92)
Using the previous result and the results from low-diserepancy theory (see Appendix A.2 for review), we can now show that Algorithm wiill, under mild assumptions for training, output model, which yields low prediction error. Thus, using Lemma I0 we can easily prove Theorem 14
Proof of Theorem 14 By Theorem 9 know that for Sobol sequences in base 2 with points in [0, 1] the star-discrepancy bounded by
(d) S C(d) l
(C.93)
N
where C(d) constant such that
C(d) 1 ( d
d! (og((d))
(C.94)
Since C(d) o(1, there exists a constant C, such that C C(d) for all d >> 0. our case, 2m,
so we have
D2 (2m) S c 2
(C.95)
Using the assumption that the training objective is not larger than ((c1 + c2) + cs)/2, by Lemma 10 we have
R(O))=
E | _ (x) (tt((((()))
(C.96)
s~U[-1,1]"
2
(EI 62) + c² log holpu//ooooluug///allllooooooooo
2
2
(C.97)
N
$ 2(1 (2) + c log(NN) /agpooooooo//llllgonooooo//aaoa
(C.98)
N
where C" is constant. We also used here that mn data has size N O (2polylng(1 http://)tttllll//////// W be chosen with respect to c1, é3 and independent of the system size n such that
[pl = (ppolylog(/ee). Since the training
O log( NY /fr) (ttgll/g////00(0glnggggg aman//))
63
<
(C.99)
N
In this way, we obtain
R(O") s 2(c + (2) +
(C.100)
Since the training objective from Definition 7 non-convex, we cannot guarantee that our algorithm converges to neural network with low training error. However, the assumptions made in Theorem) 14 are rather mild in practice. Small training errors are well-known phenomenon in deep learning and usually come at the expense of larger prediction error, which is referred to as overfitting. Overfitting may arise due to excessive model complexity 189), i.c. too many trainable parameters. This is reflected by Lemma 10 since the generalization error increases with the width W of the layers. The major challenge practice lies in finding an appropriate balance between achieving small training objective and model complexity, rather than only the latter. Furthermore, when the inputs are regularized, the weights usually remain small during training when initialized properly. This for example observed in [53].
Finally, it is worth noting that in scenario with a constant number of parameters O(1), similar to the setup in [5I), the expression derived from the outcome in Lemma TO exhibits nearly linear dependence e. When incorporating the constant number of parameters by setting mn m,
38

---

recover the exact ground state properties tr tr(Pp(z)) in fp. Thus, éj in Lemma 10 becomes 0. Hence, the ability of LDS training to overeome the curse of dimensionality can unfold its full potential, since the domain dimension becomes independent of e and expression Equation (C.88) reduces to
constant multiplied by N' (2m). By Equation (C.95) we obtain R(()) = O (Pe==(1F0) for any d > 0 and small enough, when the conditions of Theorem are fulfilled.
C.3 Prediction on general distributions
In this section, we generalize our results to hold for a wider class of distributions. Recall that our rigorous guarantee proven so far (Theorem 14] holds when the training data is generated according to a low-discrepancy sequence and the prediction error is measured with respect the uniform distribution. We want to extend this result for different choices of both training and prediction error distributions. Notice that our prediction error bound (Lemma I0p is the only place that requires these assumptions on the distributions. Thus, in this section, we establish bounds on the expected prediction error for more general family of distributions. We consider the following two cases.
1. The training data is generated according to general low-discrepancy sequence (in the sense of Definitions 4 and 5). and the prediction error is measured with respect to some distribution D)
2. The training data consists of independently and identically distributed (i.i.d.) random samples according to a distribution D, and the prediction error is measured with respect to the same distribution D.
There are some conditions on the distributions that we discuss shortly. In Case I suppose for example that we want to provide rigorous guarantees the prediction error when the parameters x E [-1, 1] are sampled from a standard normal distribution (restricted to [-1, 1 and normalized appropriately). As normally distributed test samples more densely populated around the mean and more sparse around the boundary of the input domain, we need to predict more accurately around the mean than close to the boundary. When using a uniform cow-disceppancy sequence for training, in Algorithm| [ the predictive capabilities of our model are not exploited properly. To remedy this, we consider the training data form general disdeeceepancy sequence, where it is low- -iediicry with respect to a normal distribution. We can relate this general low-discrepancy sequence to an LDS with respect the Lebesgue measure, which are the sequences considered in Appendix C222 via the probability integral transform (see, e.g., (90).. We sometimes refer to LDS with respect to the Lebesgue measure as uniform low-discrepancy sequences. Formally, for any random variable X, which follows some probability distribution P(X 2 x) - Fx)))) the random variable Y (X) follows uniform distribution. It turns out that the same transformation on LDS produces LDS with respect to other measures than the Lebesgue measure, as illustrated in Figure 3 Moreover, under some assumptions on the distribution, we can bound the discrepancy with respect to other measures in terms of the discrepancy with respect to the Lebesgue measure, which we know how to bound as in Appendix C.2
In the following, formalize this argument and adapt it to problem setting. We refer the reader to Appendix A.2 to review the necessary concepts of generalized (star-) (utrr)ddscrepancy, the Koksma- Hlawka inequality, and related results. Then, we demonstrate that generalization of Lemma 10 and Theorem 14 can be achieved by incorporating these findings with slight adjustments to the proofs.
In Case 2 consider training data sampled i.i.d. from some distribution D and prediction error measured with respect to the same distribution D. To obtain a rigorous guarantee on the prediction error in this case, we leverage probabilistic bound on the discrepancy of uniformly random points from [82]. Utilizing the previously established framework from C we can bound the discrepancy of points sampled from D in terms of the discrepancy of uniformly random points. This allows to establish similar guarantees for Case 2
Before proving each of these cases, we set up our probabilistic framework and define the Borel measure with respect to which our low-discrepancy sequence is defined. Let PDF be the probability density function (PDF) of the data distribution and let G A CDF(D) be the corresponding cumulative distribution function (CDF). In the following, assume that the PDF g satisfies the following properties.
39

---

Transformed LDS
1.00
(xx)
0.75
0.50
0.25
0.00
0.25
0.50
0.75
-1.00
1.00
0.75
0.50
0.25
0.00
0.25
0.50
0.75
1.00
X1
Figure 3: Transformed low-discrepancy sequences. The blue circles correspond to two-dimensional uniform Sobol points æ. The orange triangles indicate the corresponding Sobol points with respect to the CDF of the standard normal distribution, denoted by O. The latter forms a low-discrepancy. sequence with respect to the Borel measure μ T.
(a) Strict positivity: g has full support on 1-, i... g(x) 0 [-1,1]" and g(x) 0 otherwise.
(b) Continuity: g(x) continuously differentiable on [-1, 1|
(c) Component-wise independence: The (random) variables 7,, उ. upon which different local terms ( (ā,, of the Hamiltonian depend on, are independent. Hence, the PDF is of the form
g(x)
II 9,, 1=1
(C.101)
for PDFs 9ý-
We implicitly assume that y also satisfies all properties of a probability density function. It should be noted that Assumptions (a) (b) could technically be relaxed. We expand more on this later. Notice that if g [-1, 1] - meets these requirements, the same holds for ğ 2 got [0, 1]Th + Here, we use the notation from the previous section, where bar denotes that are working in the domain [0. 11 as opposed to [-1, 1]", and r((x)) = 2F - 1. Since the available results hold on [0, 1)"", we will mostly work with and the corresponding CDF G.
We continue to set up the necessary notation to formally state our prediction error bound for Case Let Sr, Sr,, be as in the proof of Lemma T0 Namely, let Sr,2,, be the parameters with coordinates in Ip, Ips, where Ip defined in Equation (A.2). and let Op..rs [0, 1] 1| 121, Additionally, define MPIPP & IIiEspp (z as the probability measure of the marginal for all (random) variables with indices in SP..P- Due to Assumption (c) PP..P depends on at most 2m variables. Furthermore, we define
n arg max DN (x PP,P;
(C.102)
and denote by the corresponding coordinate set. 5* forms the domain of μ², and we use d' to denote the dimension of the domain.
40

---

In both Case 1 and Case 2 the idea is to define a transformation F that maps random variables with an arbitrary distribution uniformly random variables. Namely, we construct a mapping such that
E [u(=)] IeD
E --U111,11 [u()(z))]
(C.103)
for any function u. In the following, introduce the transform F - ~-' has been introduced in [91 [88 [2].. F can nicely be characterized using 9 and G, and assumptions on F are easy to verify for a given data distribution. In fact, if F satisfies Lipschitz condition, then known results (88) bound the discrepancy with respect to an arbitrary measure in terms of the discrepancy with respect to the Lebesgue measure, i.e., prediction error bound for more general distributions follows from this result and the results from Appendix C.2
directly upper-bound Dy (d"; (x" ) in terms of (d)). Our
Let 9" be defined such that (x) = g (x)dr. Also, let A, B C S* be such that An = 0 and
C = S* (AUB), Then, we define the conditional marginal PDF
Jomle 9 (x)dxc
(x =BB -
(C.104)
J Io.114n111 So p(aeh... ... -o f (x))
and the corresponding CDF as
(ma))
GO (XA==aAXX==00 &
g g"(#A(=B)dLA
(C.105)
For convenience, we refer to the indices of x in 5 via Fı, 32, Tgt We can do this without loss of generality by permuting the order of the parameters. Using these definitions, we can now define the reverse transformation as F [0, 1]dd + [0, 10" where the indices of F are given by
(x) - (X; æ, |X1 = E1. x 1)
=
(C.106)
If random variables are distributed as X ~ G*, then F(X) U1- 1) (or equivalently U(0, 1j under the variable transformation (Ix) = 2x 1), since X1, X2 Xx | XX.... X are independent and
11 =
(C.107)
Finally, with this notation set up, we can formally state our result for Case
Corollary 6 (Neural network sample complexity guarantee; generalization of Theorem 14p. Let 1/e > 61, E2 Ez > and let D be a distribution with PDF g fulfilling assumptions (a) and F according to Equation (C.106). Let f0r " [-1, 1] + R be a neural network model produced from Algorithm 1 trained on data {(Ee, de be of size
N (pooyylo (annolylog(///))ttooot / (oo)))oolloo(((/a)))
(C.108)
where the xe 's form low-discrepancy Sobol sequence, 3, = F- and 00 tr(ppi(( S c2 Suppose that f0r _=" achieves a training error of at most ((E) + 62 + ea) Additionally, suppose that all parameters Ø of f f0","" satisfy |0; S W Wmaxo/ for some W Wmax= > that is independent of the system size n. Then the neural network per _w" achieves prediction error
15 xo (x) tr((0(()))1 2(E1 + =2) E3. BnD
E
(C.109)
Similarly, also have guarantee for Case 2. which is the version we state in the main text and the beginning of this appendix.
Corollary 7 (Neural network sample complexity guarantee; generalization of Corollary for random
data). Let 1/e > 61,62,63 63 > 0, D a distribution with PDF y satisfying assumptions (a) Let
for _.=" 1-1, 1]mh + R be neural network model produced from Algorithm 1 trained on data
{Ex,, 2 of size
N 1ogg1////ohhhhooo/////ooo/aoaaa
(C.110)
41

---

e2. Suppose that f8r."" achieves a training error of at most ((11 + x2)2 + c2)/2. Additionally, suppose that all parameters Q of I w"" satisfy 10; I W Wmax. some W max > that is independent of the system size n. Then the neural network 1 we achieves prediction error
where the Zt ~ D and ye tr(Op((z)) S E2.
10"0 (x) tr(O0(())) 2(1 + (2) + c3.
(C.111)
aND
with probability at least 1 5.
We first prove Corollary similarly to how we proved Theorem 14 In particular, we can prove a generalized version of Lemma TO where and wish to bound the prediction error with respect to D, as Case Define the prediction error of neural network f,, with weights given by θ with respect distribution D as
given low-discrepancy sequence with respect to jr
/ 111.11m
RD ()) A E (x) pwD
1 (x) (r(OO(())) (C.112)
where x ~ D denotes x sampled from the distribution D over [-1, and = g(x)dr. Again, suppress w in the notation to avoid cluttering. Then, have the following lemma.
Lemma 11 (Generalized prediction error bound). Let 1/e > 61,62 > 0. Consider a tanh neural network f [-1, + IR with architecture defined in Definition Awit weights O S Wmax for some W > 0 independent of the system size n and weights w in the last layer. Assume that G satisfies assumptions [a) (c) and lye -tr(Op(zz)) I E2. Furthermore, suppose we train f0,00 on data {(z,, be)l of size N, where the T (xz) from set with star-discrepane at most D' (d: (r) in each dimension d. Then, we have
o
( Ro(O)= R(()) + + (1WW]I D3 (d'; (dd'="p)))))))))))))"))))) 20 (WW.a//)))))))))) (1))
(C.113)
Moreover, if there exist constants b,, be such that Dir (d) S by / + log(1/0) at least 5, then there exists constant by such that
d N with probability
(x(O)= < ((())) 2 with probability at least 1 - 5.
Ioc (neli) v log ())) +
m 2 (WWolllog(WWmm//ee (C.114)
N
This lemma can be proven in the same fashion Lemma 10 with two minor adjustments. One change is the use of a generalization of the Moksma-Hlawwe inequality, which we discuss in Theorem M in Appendix (A.2 To prove the second part of Lemma [T] we need a technical lemma (Lemma to handle the probability of failure in the bound on the star-discrepancy. We relegate this to the end of the section, as is mainly technicality.
Proof. We proceed in the same way as in Lemma 10 replacing R(O) with RD(O) and replacing Rioe (9) with
Rioc D )
E
(x)) - Σ apfp(z)
(C.115)
DND
P
We follow the proof of Lemma 10 until Equation
C.75).
This gives us
RD(O)= + Paoc + [Roce Pooo (0))
(C.116)
where recall that
1 N
R1o((() = ) - Σ apfp(z))
Σ
(C.117)
N
t=1
as in Equation CC.3 Moreover, we also have the adjusted version of Equation
C.75)
N
(Roo,,D()) (9) < Σ
|wp 1wpp
EIA
E
8r
Br (x)] (x)
1
Σ
f (at)
(zz) (x1)
0r²2
N
Ps
t=1
42

---

N Σ
+ p/ |lapy
E U (x) (x) I
fo (xe)
E aND + lan |a
Σ
fr (mae))) t=1
(C.118)
N
To bound the first term, we use the generalized Koksma-Hlawer inequality (Theorem to obtain
N
EUP
E I fp (x)
(x)
On (xx) (xt).
(C.119)
IND
N
N
(x) (:(0-trr(p)) dG(x)
1
Ar (xt)
(zt)
(C.120)
1-111-
N
Pi
8=1
f (T())
On Or (T(#)) (T(()
II
g (5.)d
(T(E)))
Or (-(ee)
(C.121)
10.1pm
N
N
Jamin f (T(E)) PP (T(E))
Σ
fr (T(E:))
(T(E))
(C.122)
N
S D (UP Sp. ))))
(C.123)
Here, the first equality, we use Assumption [c] on structure of the PDF y and use the variable transformation Txx) 2x 1. In the second equality, similarly to Lemma 10 notice that because the functions in the expectation are local functions that only depend on parameters in Sp,,,, we can replace the expectation over the whole domain [0. 1 with an expectation over just the domain Dr This step also crucially uses Assumption (c) where the factorization of the PDF due to independence is needed. The last line uses the generalized moksma-Hlawke inequality (Theorem 11). The remainder of the proof follows in the same way as Lemma 10
The second part of the statement is direct consequence of Lemma 14 Specifically, following the proof of Lemma 10 we use Lemma 14 to bound the term in Equation (C.88). This necessary because the upper bound on the star-discrepancy only holds probabilistically. so we must show that we can still use this upper bound on the sum of several discreparyy terms. This is more complicated than simple union bound, and relegate the proof and statement of Lemma 14 to the end of this section.
In addition to this lemma, also need result from [8]] adapted to our definitions above. In the following, we use D (wr; d) to denote the discrepancy with respect to the Lebesgue measure of a specific sequence of length N and dimension d, as in Definition 1 Similarly, we D (w;; d: μ)) to denote the discrepancy with respect to a measure of a specific sequence w of length N and dimension d, in Definition
Lemma 12 (Theorem 2 in 88 Let = {xe) be an arbitrary sequence on the open d- dimensional unit cube with discrepancy (x d), and let a = {
|== be the sequence defined by Fi, Fe where defined in Equation (C.106). Moreover, let g be a strictly positive, d-times continuously differentiable PDF, such that g(x) 2
for all x. Let G be the corresponding probability measure (i.e., CDF), Furthermore, let F satisfy
[F(x)) F(v) K| vll-
(C.124)
Then, the discrepancy a with respect to G is bounded as
(x( d; G) S (D)
(C.125)
where e 2d. (d KKK+17 1)d-1
The authors in 88 note that the assumption on F in Equation 12.44 is certainly fulfilled when is continuously differentiable. This where Assumption (b) used, where technically, we only require
this Lipschitz condition on F. With Lemma II and Lemma 12 are ready to prove Corollary 6
43

---

Proof of Corollary 6 We proceed similarly as in the proof of Theorem 14 but this time using
Lemma II instead of Lemma TO First, we bound the nonuniform discrepancy of our training
inputs á = { t=1- Recall that Ty = (x2) for xy generated according to a low-discrepancy
N
Sobol sequence (i.e., low-discrepancy with respect to the Lebesgue measure). By definition of F,
then @ has star-discrepancy D72 (w; d²; p²), By Assumption (b) we can apply Lemma 12 to obtain
(w;; d': :=) S (x(a;d"; ;p") (DNNWW; d= S 2 (W;
(C.126)
Here, the first inequality follows because D2 (d) S (d),), and the second follows by Lemma 12 Finally, the last inequality follows from (d) < 2d D2 (d) (see, e.g.. [93]. Because d' 2m,
can proceed as in the proof of Theorem 14 using the bound above.
By Theorem we know that for Sobol sequences in base with points in [0, 1j"" the star-discrepancy is bounded by
Jog(NN
(dd) < C(d*)
(C.127)
where (id) is constant such that
d
C(d) d! log(2d)
(C.128)
Since C(d) o(1), there exists a constant C, such that C 2 C(d) for all > 0. Using the assumption that the training objective is not larger than ((El + 62)2 + 62) by Lemma 11 we have
RD(0*)=
E 1 (I) tr(Op(z))1
(C.129)
zwD
(EI t22² + + C²
+
2
(C.130)
Nl/d"
< 2(1 + x2) + c3 + (
(C.131)
\1/polylog(//a)
where C' a constant. We also used here that d' < 2m and m = |Pp (polyyog Since the training data has size N = O E1, 63 and independent of the system size n such that
W max can be chosen with respect to
C" log(No))) (2)(NN2)02ppoo) (polylooog /1))
63
S
(C.132)
N //ooyyoog((//c)
4
for some constant C" this way, we obtain
Ro( S 2(a + c2)² + +3--
(C.133)
Finally, prove Case 2 where the training data is sampled i.i.d. according to a distribution D and the prediction error is also measured with respect to D. Note that we can drop the assumption that F-1 is efficiently computable for this case. The key result need for this is bound on the diccreicryyancy for uniformly random points (Lemma
Let 2. Fx,, where F is as in Equation CC106). As stated in 991 92.. F transforms random variables with distribution D into standard uniform random variables. Hence, similarly to the proof of Corollary 6 if w { has star-discrppancy Dÿ (wi d": d("), we can bound it with respect to the discrepancy of @ (
Proof of Corollary 7
(w; d n²) < (x(u,dd;n")
(Dv((;; d') 22 dd))
(C.134)
Here, again we use (d) < (dd I 2d (d) and Lemma 12 Then, by Lemma for uniformly random points, i.e., i ( N. we have
d N
(d) < 5.7 4.9
log(1/0) -
(C.135)
with probability at least 1 - 5. The rest of the proof follows in the same way as Corollary 6 but using the above discrepancy bound. Note that because this discrepancy bound only holds probabilistically.
we need to use the second part of Lemma II
44

---

Our prediction error bounds for Case 1 and Case 2 (in Corollaries 6 and respectively) look rather similar. However, one can verify that Corollary 6 only requires about square root of the number of samples Corollary 7 uses to achieve certain risk bound with small enough but this advantage hidden in the polylogarithmic factors the exponent. Hence, now-discrepancy data yields better theoretical guarantees. However, they did not yield an improvement in our numerical experiments, as discussed in Appendix [ The size N of the training set seems to be very large for low-discrepancy data to have practical effects. In the main text, we present Corollary 7 because it is the more general theoretical statement.
In fact, one can also improve the polylogarithmic factors in Corollary 6 by imposing stronger assumptions on the distribution. In particular, the result in Lemmal [2] seems surprisingly weak at first glance. Multidimensional transformations do, however, constitute a major challenge, since they generally do not preserve properties such as lines remaining straight or parallel. The boxes over which one optimizes in order to compute the discrepancy can thus change severely in shape, which can strongly alter the discrepancy and makes difficult to analyze. This can result in rather poor scaling in terms of the discrepancy with respect to the Lebesgue measure and thus N. However, when g fulfills additional assumptions, we obtain a much better dependence on N by directly applying the Noksma-Hlaw's inequality (with respect to the Lebesgue measure) to f o ø. Unsurprisingly, this is possible when the mixed derivative of F-1 = & is bounded on [0, 1]. This follows, when g '' mixed derivative is bounded [88) We restate this result below.
Lemma 13 (Theorem in (8).. Let +
{xx 12 size N be an arbitrary sequence on the open d-dimensional unit cube with discrepancy D (w. d) and i = {&t) the sequence defined by Fû,- ze, where F is defined in Equation (C.106). Moreover, let be a strictly positive, d-times
continuously differentiable PDF, such that ((x) 2 m > 0 ffror all x. Let G be the corresponding probability measure (i.e. CDF). Furthermore, let F satisfy
alAl Fj
< M
isisd, AL
(C.136)
dx
Then
Veany f())GG()) - N
N Σ f(i)) I 1=1
M
2d-1 Di(w; d)H
(C.137)
On a high level, the proof works via the observation that the Jacobian of F has as its determinant, which is strictly positive. Since F o is the identity, one can write the Jacobian of 6 as a linear system of equations with the derivatives of & as solution. Using Cramer's 's rule and the assumption on F, one can upper bound the derivative of Φb Applying this iteratively, one can show via induction that the mixed derivatives of & are also bounded when the mixed derivatives of F are bounded. Note that (as stated in 88) when D is product of independent distributions, i.e. g(z) II (x,)) and fulfills assumptions (a) (c) the conditions for Lemma 13 are also fulfilled. It is important to emphasize that the additional assumption used in Lemma 13 yield a much better dependence of e on
N. However, this improvement is hidden in the polylogarithmic factors.
We dedicate the last part of this section the proof the following statement, which we used in the proof of Lemma []] At high level, this shows that when we have a probabilistic upper bound on the star-discrepancy, we can still upper bound a sum of star-discrepancies with high probability.
Lemma 14. Suppose there exist constants by, b2 such that D (d) S by / + log(1/0) with
probability 1 - 5. Then, there exists a constant by such that for any L > 0
Pr
Σ
(alar, 1arrs + ca([wr, Ilarsl + |wr, ||rr,
21
(C.138)
N
<exp (eillal) + (2(lw]h [|al [1]1))))
(C.139)
where recall Sp,,P, is the set of parameters with coordinates in Lp, U Up, (Equation (A.2)) ), Ci (0( and 02 = 20t log(W W log(m))) Thus Dj (XPr, PP) denotes the star-discrypancy of this set of parameters in the training data.
45

---

First, we introduce two useful tools for the proof.
Theorem 17 (Azuma's Inequality for Martingales with Subgaussian Tails; Adapted from Theorem 2 in (94). Let Zi, Zz,.... Zn be marlingale difference sequence with respect sequence X1, X2..... Xn.
and suppose there are constants b > 1, cn..... > O, such that for any j and any
t 0 it holds that
1
Pr(Z; > 4X1,,..... XX,1,) S bexp
(C. 1404
Then, it holds that
Pr
Σ
Zz j=1
S exp
(C.141)
28b Σ
2j=1
j=1
Proof of Theorem 17 Following the steps of the proof of Theorem 2 in 94 but taking the sum over Zj instead of the empirical average, we obtain for any
Pr
Zj >
< Se
7
7he
E
II
77 X1
Xn-1
Se stt E3
(C.142)
We refer
194 for further details of this calculation. Choosing t/ (146 e9),
,the the expres-
sion above equals e (286 Eド=1 e,), and get the claim:
Pr Σ Z3 >t
S exp
(C.143)
[28b
28b ΣØ=
We also need the following two small lemmas.
Lemma 15. Let 5 > 0. Let X: Ωx + X and Y : + y be independent random variables and
f: X x y + R4 be a function such that Pxxx (f(,Y) 2 for t >> 0. Then,
t
Elf(X,Y)
< 2
(C.144)
with probability at least 1 25.
Proof. First, we show that Pr(f(X,Y) 2 x(x) 2 1/2 with high probability. Then, we show that this implies the claim by Markov's inequality.
First, suppose for the sake contradiction that Pr(E]](J(X,, Y) 2 H 2 1) > 26. Using the independence of X and Y applying Markov's 's inequality, obtain
1 Pr(f(X,Y) 2 t) [(E]( [|]] 2 Pr (E[L)((X, 2 2 2
1 !)
28 1
5, (C.145)
2
which contradicts initial assumption. Therefore, with probability most 25 (W.rt. X), Pr(J(X, Y) 2 x and hence
1
X
< Pr(f(XX)) ((x)
(C.146)
2
t
by Markov's inequality. The result follows immediately.
Lemma Let j E [m] coordinate of the parameters. Then, I(P ((g60) :j E Tr] tildem. where mn O([pl).
46

---

Proof. Recall that
Tp= (c E (1....,m] dona(h)(e)) P) 5.1..
(C. 14.1
Fixing e instead of also results in set of geometrically local terms in radius 6n around geometrically local term. Hence, the size of the set {P E g(seo) :j E [p} also scales [lp which is at most m.
Now we are able to provide partial proof to Lemma
Lemma 17. Let SP..P be the set of parameters with coordinates in 1p, U Ip, and let & Ht & Sp..Pa AN denote the training data set only for these local parameters. If there exist constants b1, b2 such that (d) S bi bu + log(1/0)/ N with probabiliiy at least 1 ô, then
N
Pr Σ
Japy (ER,, 21) I exp
(C.148)
(m) exp(b1)b2)
PrES(En))
for any P1 E ((PO0) and any > 0.
Proof. Let P1 E S(geo), Define
Xy E E
Σ Pae
Jap, (TP
Yo
(C.149)
where we omit the dependence P 33 .Yi...., Ym) and Y, {(ry)e) and zj param- eterize hy. We consider all increments, which are not contained in Ip, Hence, with slight abuse
of notation, let index = refer to all coordinates Ip, and Yo & {{(x,) : e Ip, Ip Furthermore, let
Xo E Σ aa (2)
(C.150)
PAES(REO)
and 21 A X Xo- Clearly, Xo...., is martingale sequence and Zi, Zm the respective
martingale difference sequence. Furthermore, note that Xm Peeeteo lap, Dy (TP,.Ps) and by definition of Yo. j & Tp, for all j > 0. Now, since D (TP..P 2 0 and aap, D (TPI.P) cancel out if j Ip.-
Zy S
(N 1-111 1-1...., Yo
(C.151)
(P :jEl, Va
Σ
lap; E (i( 1.1....,
(C.152)
P PeeSteo) Va
Σ
lap, E (N(E))))))
(Ya))))))) (Yr)
(C.153)
P.ESS Mpi
Then, for any t > 0, we have
Pr(Z; 2 t) Pr
Σ
Ja E (M(a))))) (Ya) [
2t
(C.154)
PaESimongjEee Vp
1
Pr L D (Kp.))))))
2
(C.155)
app
P,eSt jETP
<2
Σ
Pr (M(E))))
(C.156)
2/pp
47

---

N22
2 PreSiom)yjrr
Σ
exp(bi)exx exp)
(C.157)
12b2m
N12
:j E exp(()) < { E S(800)
4bym Σ PppESioo)yjlln aap
(C.158)
N12
S 2m exp(bi) exp
(C.159)
4b2m E PrEStee) corr
In the second line, we use union bound. third line, we use Lemma 15 with (Yε)a<j.AET)) Uhp, and Y = (Yo....,,y- In the fourth line, we use rearrangement of the probabilistic upper bound on the siarriiccrepancy. the last line, we use the definition of m. Now, by Theorem 17 for any >
12
Pr
Σ
Jap; (
2t S exp
(C.160)
28b' E &7
PrES(
with b' = 2m exp(bi) and c²²
1bam Σ LpsESto):eEl Jarz1
Furthermore,
Σ
lapp
Σ lap
Σ
[ m Σ
lap
1=l PaEStEo Ne
PrES(
PrESlsoo)
(C.161)
The result follows from this.
Now, we are finally able to prove Lemma
Proof of Lemma 14| We need to bound the weighted of the star-discrepancies we consider. This requires an extra step, since the star-discrepancy may vary among the sequences the sum. Note that simply applying the union bound would result in a log(n)) needs to be small, rather than all individual terms needing to be small at once. Recall that we use Sp,,P, to denote the set of parameters with coordinates in Ip, U Ipz. In the following, D2 P.), denote the star star-discrepancy of {I Sp, P. i... the training data points restricted to local parameters in Sp,,Ps. We aim to apply Theorem to L P..Peestemo) (ap, ( Ep,r, Iw pl D2 (TP,,)) .2) and Σr, P3e
Luckily, only the sum
|0p, Wp,, D2 (TP).P))).
For illustrative purposes, we only consider the first term for now. We proceed similarly the proof Define
of Lemma 17
X, E
Σ
Y
(C.162)
P..PeEStemo)
where the expectation is with respect to the inputs Y, {xx))e and x, parametrize h,. Further- more, let
Xo 2 E
Σ
lap 1D
(C.163)
and Z1 X; Xo- Clearly, Xo. Xm is martingale sequence and Zi..... Zm the respective martingale difference sequence. Furthermore, X,, = Er, PPe Jar, |ar, (xr, Now, since (i 2 0 and (up,,//p,,, D cancel out if $ Ip. U Ips.
Z, E
Σ
lap, Iapp Y 1/.....
(C.164)
Pr. Pa. JETP, Ul
Σ
lap lap, E Di (2p
(C.165)
P. P.E :EII UIP
48

---

2 Σ E
(D Y-...... Yi
(C.166)
PEES P2ES(Z0)
In the last step, we used the observation that for j to be contained in Ip, Ips. has be contained in at least one of the two sets. Hence, we can enumerate the admissible coordinate sets by fixing Pt, such that Tp contains j and combine it with //y. The factor two arises from doing the same with Pi when fixing P2.
Now, for any we have
Pr(Zz 21) Pr 2
E
Ten,llan E (M( V,
Vi 26
:EEP,, PaESiOn)
(C.167)
2
Σ
Pr
Σ
De (xF,,))))
(C.168)
4|ag|
Pi (EESBO)) :Eln,
PrESi
Nt
2
exp
(C.169)
16 a0-224/pp::3
1
2 exp((x)bp)
PrES
Nt²
< 21 E S(Ec0)
: 1pp
16 (16.224/alB(() /b2 E ges (C.170)
JETM
aap
Nt
2m exp
(C.171)
16 224 exp(bi E Epeestoo lapp 13
In second line, we use the union bound and Lemma 15 with X (Y*) Ule, and Y (Yi)assAeeIr the third line, we use Lemma 17 In the last line, we use the definition of m.
Applying Theorem 17 and bounding Ej og exactly as in the proof of Lemma 17 yields
Nt2 billa
Pr
Σ Mn 21
S exp
(C.172)
One can similarly repeat this argument for the remaining terms of
Σ (alan, c2(Wwr, ||ap,] |w,, (ER.))
(C.173)
Using that ||al12 < ||all and solving for the appropriate 8 yields the desired result.
C.4 Bound on the mixed derivatives
Let O = EPE[I.XXY.2 P be an observable that can be written as sum of geometrically local observables. In the following, we derive an expression for the mixed partial derivatives of tr(Pp(z)). using tools from the spectral flow formalism [59] 60 61]. This allows us to bound the Hardy-Krand Krause variation (Equation (A.36) in Appendix C.2 Let the spectral gap of H(x) be lower
bounded by some constant for all choices of parameters x E [-1 1, 1 1|"h. Then, by the spectral flow formalism (59] 60 61), the directional derivative of ground state of Hx:)) the direction defined
by the parameter unit vector is given by
Tu p(x) u. v.p(() i(Da(z),
(C.174)
where
+00
OH (,(t)estHes (H(())
Da(x)
Dū (x)e -tH(()) dt,
(C.175)
49

---

and (t) is defined by
2 35e (7140)
0 7/4 S 0, 7/4 > 0.
[W((1) -
(C.176)
The parameter / is chosen to be the largest real solution of 35c (>/t1)* exp (-? 7/t| log"(>(())
1/2.
This allows to us to obtain an expression of the first order derivative of p(z) with respect to some parameter Consider the unit vector û = é - (O.... 0, 1, 0, ...,..),, where the 1 is in the kth
position. Then, the directional derivative in the direction given by ex
0eg p(x) êx VeP(2)
p(x) p(x) = (D)
(C.177)
Ork
Hence, we obtain
8 dr
ir((p(x)) = p()))())) = =itr(P(De De (C.178)
p(x))
In order compute the mixed derivative of second order, now apply the product rule this expression, which yields
0²
8
op (r(Pp()))= = iap tr([P, Da, (x)]p({))
(C.179)
02,002
tr ((P Da, (x)) p(z) - (x)
a
iap
P.
p(x)
Ox2
dxz
(C.180)
Dáy (1)) p(x)) -r[[[ (e,(()))) De, (z))
= ir
(C.181)
Note that the terms of this expression can be treated similarly as the first partial derivative. For each additional partial derivative, obtain terms consisting of the product with nested commutators with p(z) under the trace. The nested commutators contain D2, (x) or partial derivatives of it, for which will later derive explicit form. Hence, partial derivative. In order to formalize this statement, we need to introduce some additional notation.
apply the same scheme until arrive the k-th
Throughout the rest of this section, we use the notation 01 respect to all parameters 2; B for some set B.
to denote the mixed derivative with deg
Definition Let E N. Let C [k] be set ofze |A|= m. Define an ordering l < < < hm the elements 1 12, Im of A. Then, we define
B 8Th tr (II-
P. θ Br a
0 B
2 Bl
Day (x)
Dat,
(x) ...
Deam (2) p(z))
Ox Big
Oz Bi...
LEA
(C.182)
where By C [k). We refer to the nested commutators under the trace as summands. The set and collection {BiJIAA & BA satisfy the following conditions:
1. Each summand contains Dē, (x).
2. The sets A, Bi...,, Bm satisfy A AUU BN [k] and An B, 0, B.n Bj =
3. For each (Bt, I) pair, holds that > I for all E B,.
This notation gives compact way of expressing the terms of the mixed derivative and allows us to address each mixed derivative of the terms D;, individually. Each term OLEA 8 contains the product of m + matrix-valued functions (including p(z),, which depend on æ. The set A denotes the partial derivatives on the factor p(x), which have been differentiated using Equation CC114) when
50

---

applying the product rule. We will address the partial derivatives on De, later in this section, when we derive an upper bound for OleA L..,
The first condition underlines that the first partial derivative on p(z) is necessarily computed via Equation (C.174) and thus contained in each term. The second condition reflects that each partial derivative operates on exactly one factor each summand when applying the product rule. The third condition arises from the order, by which the partial derivatives are computed. For example, when apply & after e_ the @ Bay 0nz" B8y Dey can not occur in any term, since term contained Dæj when the partial derivatives 0zj
were computed.
We can show that the mixed partial derivatives of a o Lr(PP(x)) can be written in terms of
8B. Lemma 18 (Mixed derivative). Let As = {A S [K] : :1 E A} and BA be as Definition The mixed derivative of the ground state property ir(Pp(a)) is given by
2h
dx ap aptr(Pp(z)) ap Σ AEA,, BI.....BAAJEEB,
E
a
(C.183)
Proof. We proceed via induction. First, we verify that a dz 1 B with A E Ak-1 and A U U By [k 1] yield summands which fulfill the criteria for summands of the k-th partial derivative stated in Definition & Then, we show that each summand of the k-th derivative stems from a unique summand from the (A: - 1)-th partial derivative.
For the first part, let |A| m. Furthermore, let
{ {5} 0
if else
1,(1)
(C.184)
Then,
8
Bi, uI 11,00 +
BBL,
(C.185)
Dakk
TEA
j=1(JEA
LEAU(R)
where each summand fulfills the properties, since k > for all / E A.
Next, let A' AA, and let B be the corresponding collection. Then, it is easy to that, if k Bi, it stems from the summand ClEA/ O. with Bi....., Bi, \ (k)...., Bi... If A', stems from OlEA L
With this expression in hand, we can move forward to bounding the mixed derivative, which we need in order to bound the Hardy-Krause variation. First, we will upper bound the number of terms in i [. Then, we derive an upper bound on the individual terms. For the first step, we exploit the conditions on the sets defining the mixed derivative. When we drop the third requirement in definition Definition 8 A corresponds to the number of ways of assigning k m distinct balls to m bins. Thus, we obtain the following result on the number of terms OieA BB in the k-th mixed derivative.
Lemma 19. Let A denote the set of all subsets [k). Then, the number of summands in the expression OLeA gB.l is upper bounded by
BA <
5
(C.186)
Proof. There are |A| E* "
(*) different subsets of [k]. For each set with |A| = 8, there are sets Bj. Dropping the third condition in Definition 8 observe that each of the s elements in
[k] A can be in any of the s sets. Thus, we obtain the claimed upper bound.
In the next step, we aim to bound each individual term of the mixed derivative O B Therefore, crucial step is to bound the spectral norm of each factor. We first derive preliminary result on the
51

---

mixed derivatives of the factors in Dē, (I), which depend on и. This can be done using Duhamel's Formula for the derivative of the exponential map el(s), where exploit that only compute the derivative with respect to one parameter at time, such that we can treat H (x) as a function, which only depends one parameter.
Theorem 18 (Derivative of the exponential map; Theorem 3a in (951). Let A(t) R R- Cnxn, Then,
d
! (2-)))(0)
dA((t)
dsd(t) ds.
(C.187)
di
dl glliny dic
Lemma 20. Let l E [n], B = [n] (k)), such that
< C BU [N).). Then
|
(H(())
Ohg
(L)(()
)|
2 +1 +1 + B|
(C.188)
Orp
0rk
Proof. By Theorem 18 the mixed derivative equals the sum of terms the form
T T= f- L' II [isssdssss..ddd d81,
(C.189)
where f((s)) can be any of e(1-)))(((0) (x(HH((), 0hh, or By our assumption and the Cauchy- Jzn:
Schwartz inequality, each term 7 satisfies ||]| S Furthermore, by the product rule, the number of terms is smaller than II | (2j + 1). Since each term of the ith partial derivative (including k) is
the product of at most 2/ + factors depending on such that the (1 + 1)th derivative contains at most 2/ + 1-times as many factors. Thus, the number of terms bounded above by
B II 1=1
[B+1
(2)+
II 1=1
(2)) = n" s 2 21+ + +1)1B+1 +1,
(C.190)
required.
Now we can bound the terms I 1. Lemma 21 (Bound components of the derivative). Lel OlEA 0B:1 be in Definition g Then
BB:1 < (2C,)14) Al
II
2 B (lBi, 11)+111)1111 11,11
(C.191)
iEA
Proof. Recall that
Da(x) 1 +00
0H W (H)))
Oū (z)e (te-HH(()) dt,
(C.192)
where (1), such that
0 7|4 S 50,
WV <
2
(C.193)
35c (>/1))
7|1| > 0,
where 0 is chosen to be the largest real solution of 35c (r (1) exp ( log 2/1 ()1)) useful to note that sup, [t) = 1/2.
1/2. is also
By definition of the terms OleA L, the
inequality, and [|A B| <
|| Bl we obtain
: aBBi
( (W,(t)dtt)
2/4 II sup
[A]
I B.,1
((H((s))
[ahi Ox.
(HH())
IEA
(C.194)
52

---

We bound each term individually. For the first term, we proceed in similar manner as in 2 (Lemma 3). Namely, by Equation (S32) in [2]. we can bound this integral by
245 (t)(t)ltt - x2n-1
(1t² - (005 & Cj.,
(C.195)
35 log- (ytt)
1
7
by choosing such that yt' = max a, 7(d + 11), 0) some constant a. Here, we use C² to denote a constant that depends only on y. Moreover, since (t) _ 1.4 we can conclude that
[W, di max(5900, a, 7(d+ + 11), +2C, Cy. (W)(t)d < [ de + 21
(C.196)
where Cy is also constant that only depends y. By Lemma 20
obtain the desired statement.
Lemma 22 (Bounding the k-th mixed derivative). The k-th mixed derivative of or tr(pp(x))) is bounded by
Oo, ap tr (r((p(x))) $ |apl 20 log(k))
(C.197)
0z
Proof. First, derive an upper bound on the terms Proceeding from the result of Lemma 21
le 8B.,, which is independent of A and BA.
we obtain
AI II B H+ (lBi,) B1,11 s (2C2)
IAI
(2C,))A1
II
k Bi, 14,1+1 s (Cik)*, (C.198)
where we used |A| S & and C, + 1) = l and Ci = 4Ca. Furthermore, from Lemma easy to see that [Bal < k* Thus, we obtain
ar xptr(pp(z))
s [Balla]((CiM)) s lar|Ch (0r|20(klogtt log(k))
(C.199)
Or ... Dr.
Note that when deriving this result, we do not require that the parameters for the mixed derivatives distinct. Assuming that (H))))l ([-1,)) I bound for any mixed derivative of order k.
induce an order recover the above
Corollary 8. If H (x) ([-.))) $ then ||rr tr(Pp(z))]l I (+tr(2(()))g(()) log(H))
Proof. Note that the bound from Lemma 22 is agnostic to the explicit directions é of the derivatives. Thus, we can choose any mixed derivative À N such that Σ A, k and fix an order o: dom()) [k). Then, we can bound the mixed derivative on o(A) using the same approach as in Lemma to obtain the bound.
D Details of numerical experiments
In this section, we discuss the numerical experiments in detail.
D.1 Experimental setup
As in 2 we consider the two-dimensional antiferromaanetic Heisenberg model with spin-1/2 particles placed on sites in a two-dimensional lattice. The corresponding Hamiltonian is
H =
Σ (X + Y.Y, + 7,7,),
(D.1)
(0)
53

---

where (ij) denotes all pairs of neighboring sites on the lattice. The coupling terms Jey correspond to the parameters a of the Hamiltonian and are sampled uniformly from [0, 2| (and then mapped to lie in 11 for our MI. algorithm). The goal of the numerical experiment is to predict the two-body correlation functions, i.e., the expectation value of
1 [x,x, + Y, + Z,2,) Cij =
(D.2)
for all neighboring sites (iz)-
To this end, we generate data similarly to 0 2), approximating the ground state and corresponding
correlation functions for the Hamiltonian Equation (D.I) of different lattice sizes and choices of coupling parameters Jıy- We consider lattice sizes of 4 x 5 = 20 up to 9 x 5 45. For each lattice size, we generate two datasets of size 4096, one with uniformly randomly distributed J.y and one where the coupling parameters are distributed as a Sobol sequence. We obtained the data by approximating the ground state using the density-matre on maatri-prrducctsffee Nvidia T4 and A40 graphical processing units (GPUs). The former were used for lattice sizes from 4 x 5 up to 7 x 5 while the latter were used for lattice sizes 8 x 5 and 9 x 5. Depending on system size, we required between Rs 50 and 200 hours on the respective hardware component to simulate one dataset of size 4096.
renormalization group (DMRG) [96] based (MPS) [97]. as has been done in 2 The simulations were performed on
Our deep learning model was also trained on Nvidia T4 and A40 GPUs. We trained the models for all respective correlation terms in parallel, by training full model f (we omit the indices for the model's 's parameters) for each term and minimizing the combined loss function
N (2)) - (C
ΣΣ (A3) t=1
(D.3)
for the sake of time efficiency. For each data point, we trained a combined model for 500 epochs. For the terms of the local models ler, as defined in Definition 6 we used fully connected deep neural networks with five hidden layers of width 200. For training. we used the Adam optimization algorithm [83) Depending on the system size and the amount of training data, this took between 0.5 and 20 hours. As a baseline, we compared against the best model from [2. The code can be found at https: wtt.ggtt.........a..ceeeeeeeeeee www.///aarcaamrrcaaaeeeeeeeeeeee wwwprrrrhhaeeeeeeermminnaa learning. .orgggggrroddooooo arroouud_ttttsssse states....... git
D.2 Additional experiments and discussion
In this section, we discuss the results of the numerical experiments and additional experiments performed that are not mentioned in the main text.
First, we perform additional experiments that analyze the scaling of the training/prediction error with respect to various parameters such as system size, local neighborhood size, and training set size (Figures 4 to 6). Importantly, in each of these, we see that the training error is small, as required by Theorem Thus, as discussed in the main text, this assumption is satisfied in practice.
Moreover, shown in Figure 2 (Left), the empirical prediction accuracy (RMSE) of the deep learning model is approximately constant with respect to the size of the lattice. Figure 4 (Right) further underlines this statement. The slight increase in prediction error for 5, 0 (size of the local neighborhood in Equation (A.2)) present in Figure (Right) when increasing the system size from 4 x x 5 may occur due to numerical errors in the data. From system size 5 onwards, rather witness random fluctuations in test errors than a systematic increase.
Furthermore, observe that the deep learning model significantly outperforms the regression model with random Fourier features from [2). On the one hand, we notice that the performance of the latter could be improved, since the hyperparameters considered for hyperparameter tuning were selected for a substantially smaller dataset. This is underlined by the drop in RMSE for the regression model on Figure for ó1 1, whereas a smaller RMSE is possible when choosing 81 0. On the other hand, we think that the vast body of deep learning research also offers room for practical improvement of our deep learning model.
For 5n = 0, we believe that our model achieves the best possible prediction error. For training set size larger than 2048, there is little improvement the prediction error, as opposed to all experiments
54

---

50 5.
0.08
0.08
Average training error
Average prodiction orror
0.06
0.04
0.02
0.00
4%5
5045
635
7x5
8x45
9X5
4x5
5x5
6xc5
7x55
0x5
9
System size (n)
System size (t)
Figure 4: Training/Prediction Error vs. System Size. This figure shows the scaling of the training (left) and prediction (right) RMSE with respect to system size for different values of 6,. All training sets are distributed as Sobol sequences and were trained on N = 3686 samples. The shaded areas denote the I-sigma error bars across the assessed ground state properties.
0.07
0.07
Sperage gradiction errt
0.05
0.05
Avarage Triming
Algorithm
Doeg Learning,
0.04
Regression, LDS
Deep Learning. Random
0.03
Begression, Random
Algorithm
0.02
0.02
Deep Learning, 1.DS
Regression, LDS
0.01
Deep Learning, Random
Regression, Random
0.00
0.00
Figure 5: Training/Prediction Error vs. Local Neighborhood Size. This figure shows the scaling of the training (left) and prediction (right) RMSE with respect to the local neighborhood size ò, All training sets are of size N 3686 with system size 9 x 5. The shaded areas denote the I-sigma error bars across the assessed ground state properties.
with 82 > 0 (see Figure (Center)) Furthermore, the training error remains relatively large compared to other choices of 82 (see Figure Hence, we conclude that the error arising from approximating the ground state property via local functions dominates the prediction error.
When increasing 81, we witness an increase in prediction error, especially for small training sets. This is consistent with Lemma TO which states that the bound on the prediction error is combination of the training error and term proportional dimension of the domain of the local models). Our experimental results underline the balance which must be achieved between the two in order to obtain a small prediction error. This can clearly be observed in Figure 6) The training enror decreases when increasing ó and increases with the size of the training set. Mcanwhile, the test error increases when increasing ò and decreases with the size of the training set.
the discrrccrypancy (and thus increases with the
Another interesting observation is that the ML algorithm's performance on LDS seem to be almost the same as that of uniformly random points. We believe this is due to the dominance of the local approximation error for small 82 and the drastic increase in dimensionality of the local models with increasing ō1 outweighing the benefit of using LDS in practice. The dominance of approximation error is also a possible explanation for the slight decrease prediction error with respect to system size in Figure (Left) and Figure For our concrete choice of lattice shape and ground state properties, the local approximation error may be decreasing with respect to system size. However, do not expect this to be the case in general.
55

---

5.
0.08
0.08
Average trainin error
Average prodiction errar
0.06
0.04
0.02
409
1228
2048
2067
3606
0.00
409
1228
2048
2067
3686
Training set size (N)
Training set size (N)
Figure 6: Training/Prediction Error vs. Training Set Size. This figure shows training (left) and prediction (right) RMSE with respect to training set size for different values of 81. All training sets are distributed as Sobol sequences and the grid size is 9 x 5. The shaded areas denote the I-sigma error bars across the assessed ground state properties.
D.3 Experiments with non-geometricaalyyloaal Hamiltonians
In this section, we assess the necessity of the geometric locality assumption by conducting numerical experiments for non-geomeeticaall--oee systems. We conclude that geometric locality is necessary for our theoretical results.
We conduct experiments on for a Hamiltonian given by
H Σ Jx, + +Y, Z2 j<i
(D.4)
The difference between this Hamiltonian and Equation D.I is that the sites i and j are not required to be neighhoring, thus violating the geomtric locality assumption needed for rigorous guarantees. We predict the same ground state properties as in the previous section, i.c., two-body correlation functions on neighboring sites. Our ML model still uses the local coordinate set 1p from Equa- tion (2.3). However, notice that the non-geometric-locaait of the terms in the Hamiltonian impacts the number of parameters used. other words, larger number of parameters now affects a site in the neighborhood of each local Pauli. Furthermore, our adapted ML model assumes observables with 2-local term. Hence, the adapted ML model reads
Σ
9p P
(D.5)
((
Due to the lack of geometric locality and the larger number of terms of the Hamiltonian, the ground state properties are substantially harder to simulate, compared to the previous ones. We limit ourselves uniformly random parameters and lattice shapes x 5, 5 and 6 5. The former two were simulated on Nvidia T4 GPUs and the latter on Nvidia A40 GPUs, using approximately 100 - 500 hours per data set of size 4096. We also notice that the approximation eтror due to MPS may be larger in this dataset than in the previous one. As for the previous results, we trained the models for each ground state property in parallel, by optimizing the sum of their training objectives. For the local models ffr we used fully connected neural networks with five hidden layers of width 100. This may not be optimal, but sufficient for the purpose of assessing the scaling of the prediciton error. We trained the models for different training set sizes using ò1 0. Since the adapted models consisted substantially more terms than the previous ones, training them for 500 epochs took between and 35 hours on Nvidia T4 GPUs for lattice shapes x and 5 and on Nvidia A40 GPUs on 6 x lalticee.
In Figure (Right), we witness system size-dependent prediction error for the smallest training set size we investigate. Since the respective training error is very small, the respective prediction errors arise due to overfitting. This effect diminishes for larger training sets. This is what one would expect when directly applying the techniques of our theoretical results to this setting. Since the number
2 2oclc in the sense that P does not act more than necessarily neighboring sites.
56

---

0.5
Training set size (N)
4099
0.4
0.4
Avwrage prediction
Average training
0.3
3686
0.2
0.2
Training set size (N)
409
0.1
0.1
+.
3686
485
5x05 System size (n)
6045
4x5
System size (a)
Figure 7: Training/Pediictonn Error vs. System Size for Non-Geometrrially--Loorr Systems. This figure shows training (left) and prediction (right) RMSE with respect the system size for the model given in Equation (D.4), which violates geometric locality. All training sets are of size N 3686 and 0. The shaded areas denote the I-sigma error bars across the assessed ground state properties.
of terms increases quadratically in system size, the norm of the weights in the final layer can not be bounded by a constant anymore. Furthermore, the properties of the local approximation do not hold true anymore. Hence, the predictive capabilities of model with ô 0 may be more limited here than in the geometrically local case. However, the prediction error may also be impacted by possible numerical errors in the training data, as well the architecture of the local deep neural networks. Overall, these experiments illustrate the necessity the geometric locality assumption in our theoretical results.
57

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We state, albeit informally, our results and assumptions in the abstract and instruction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Section 3 includes detailed discussion of the assumptions needed in the paper.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
58

---

Answer: [Yes]
Justification:
The assumptions are detailed in Section 3. The appendices contain the full proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The code and data for the numerical experiments are provided in the supple- mentary material. The details of the numerical experiments are also described in Section D of the appendices.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
59

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The code and data for the numerical experiments is provided in the supple- mental material, and the details regarding the experiments are described the Appendix
D.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttpss//nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ltttlssccc/ubbbc/guiieeee http:/guiiese///eeee
wwaibbmmsssoooooo ssioncl for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
This is detailed in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Error bars are included in the numerical experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
60

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This is detailed in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This research conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There are no societal impacts of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
61

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: When using data or parts of code from previous papers, this is cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
62

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
63


Reviews:
[{"review_id": "17zvwTlzEn", "reviewer": "Reviewer_vDXc", "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.", "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.\nPresumably the results would not apply to standard Neural Network architectures- what specifically would break in the analysis? \nHow does the sample complexity depend on the constant the authors assume the network weights are bounded by?", "limitations": "I believe the authors have adequately adressed the limitations of the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of our paper and their constructive comments.\n\n**Reviewer Comment:** It is unclear to me how the Neural Network generalization result compares to known results in the literature.\\\n**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]. \n\n**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.\\\n**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.\\\nMoreover, we note that this assumption is not something new to our work and was introduced in Ref. [2].\n\nThere are many physically relevant examples where this holds. A few examples are are \n- the 2D random Heisenberg model (as considered in the numerical experiments).\n- the XY model on an $n$-spin chain with a disordered $Z$ field.\n- the Ising model on an $n$-spin chain with with a disordered $Z$ field (see, e.g., [A]) .\n- the Sachdev-Ye-Kitaev (SYK) model, which requires Gaussian parameters. \n\nWe thank the referee for this comment and will add such examples to demonstrate its wide applicability.\n\n[A] Lieb et al., \"Two soluble models of an antiferromagnetic chain.\" Annals of Physics 1961\n\n**Reviewer Question:** Presumably the results would not apply to standard Neural Network architectures- what specifically would break in the analysis?\n\n**Author Response:** \n- 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. \n- 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.\n- 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.\n\n**Reviewer Question:** How does the sample complexity depend on the constant the authors assume the network weights are bounded by?\\\n**Author Response:** One can see this dependence in Eq. (C.93) in the appendices.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cXmmEzhITD", "reviewer": "Reviewer_7tNg", "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.\n\n[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\n[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.", "questions": "Some typos:\n\nline 121: geometrically [local] observable\n\nline 148: || \\omega || -> || w ||", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 1, "presentation": 2, "contribution": 3, "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)$.\n\nOther minor inconsistencies includes: \n\nline 642: $S^{geo}$ not defined\n\nline 660: $h_{c(j)}$ not defined", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Bug** \nThe claim by the reviewer is incorrect, as *our observables satisfy exactly the same conditions* as those considered in [LHT+24].\\\nIn particular, we state throughout the paper that \n- we only consider observables that satisfy $\\lVert O\\rVert_\\infty \\leq 1$, e.g., in lines 122, 225, 301, etc.\n- 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.\n\nWe will clarify this explicitly in the final version.\n\nWe define $S^{(\\mathrm{geo})}$ later in line 654. We will make this change to introduce it earlier.\nThe 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.\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vgJg4NLzGm", "reviewer": "Reviewer_cLpw", "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.", "questions": "How do the parameters or phases of the random Heisenberg model affect the training performance?", "limitations": "Limitations are addressed in the paper.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n- 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.\n\n- 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.\"\n    \nIn 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.\n\n## References\n[A] Yamasaki et al., \"Learning with optimized random features: Exponential speedup by quantum machine learning without sparsity and low-rank assumptions.\" NeurIPS 2020\\\n[B] Aaronson et al., \"Online learning of quantum states.\" NeurIPS 2018\\\n[C] Abbas et al., \"On quantum backpropagation, information reuse, and cheating measurement collapse. NeurIPS 2024\\\n[D] Michaeli et al., \"Exponential Quantum Communication Advantage in Distributed Inference and Learning.\" ICML 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5w5Z4s4zfD", "reviewer": "Reviewer_u4Mp", "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. \n\nThe 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.", "questions": "I included the questions with the weaknesses.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "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.  \n\n1. 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. \n\n2. 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? \n\n3. 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. \n\n4. 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. \n\n5. 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? \n\n6. 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?  \n\n7. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of our paper.\\\nFirst, we would like to clarify some statements made by the reviewer.\nWe 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.\nIn 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.\nNote 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.\nMoreover, given that there are few rigorous guarantees for NNs in the literature, we view our work as a step in this direction.\nIn the following, we will do our best to address each point of criticism by the referee in detail.\n1. 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.\n2. 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$.\nExamples of natural distributions satisfying all conditions simultaneously are uniform and the normal distribution.\nThe latter is important for physical models such as the SYK model.\n3. 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.\nIn 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.\n4. 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.\nNamely, 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.\nWe respectfully disagree with the comment that the numerics do not complement our theorems.\nWe 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].\nThe experiments illustrate that our method outperforms the method from Ref. [2] in practice (Figure 2, left).\nMoreover, 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). \n5. 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].\n6. As discussed in point 3, the only assumption that is truly necessary for the argument is Assumption (c) (component-wise independence).\nAllowing 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].\n7. 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.\nMoreover, our experimental results demonstrate that these claims are satisfied in practice in the setup we tested.\nThe 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).\n\n## References\n\n[A] Huang et al., \"Quantum advantage in learning from experiments.\", Science 2022 \\\n[B] Struchalin et al., \"Experimental estimation of quantum state properties from classical shadows.\" PRX Quantum 2021\\\n[C] Elben et al., \"Mixed-state entanglement from local randomized measurements.\" Physical Review Letters 2020.\\\n[D] Oymak et al., \"Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?\" PMLR 2019", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g4cN13iX2J", "reviewer": "Reviewer_MeLw", "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.", "questions": "No questions", "limitations": "See weakness", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. High-quality paper with rigorous theoretical findings and comprehensive numerical results.\n2. Improved the sampling overhead to constant complexity, independent of the system size.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n- 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. \n\n- 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). \n\nMoreover, 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nKBG9d3cwm", "reviewer": "Reviewer_KHZF", "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.", "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.\n\n2. 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.", "limitations": "The authors have discussed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n\n2. 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.\n\n2. While the paper claims improved computational complexity, the actual implementation details and computational resources required for the deep learning model are not thoroughly discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.\n\n**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.\nFurthermore, the experimental results show that this does not seem to be an issue in practice.\n\n**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.\n\n**Author response:** The computational requirements and implementation details for generating the training data and training are detailed in Appendix D.1.\nMoreover, we provide code for the experiments in https://anonymous.4open.science/r/anonymous-B093, as referenced in Section 4.\n\n\n**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.\n\n**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.\n\n**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.\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their consideration and feedback. We're gratified to see appreciation from most reviewers: several described the work as important and appreciated the novelty of the deep learning approach with both theoretical guarantees and strong practical performance.

We believe that the negative reviews are mainly the result of misunderstanding that we correct and clarify in the detailed rebuttals below:
-  the technical objections of 7tNg and u4Mp are the result of misunderstanding that we have clarified in detail below. Our first result does not make any additional assumptions on the observables nor on the input distribution (but only that the observable of interest is known, which is reasonable, and which can be ameliorated via the use of shadows as we clarify below). Our neural network guarantee holds for natural distributions such as uniform or Gaussian. We extend the tools from Ref. [54] to more general distributions than low-discrepancy sequences. By exploiting physical structure and deriving an explicit bound on its Hardy-Krause variation, we show that our neural network algorithm achieves theoretical improvements over Refs. [1, 2] with respect to sample complexity. Experimentally, in the settings tested in Refs. [1, 2], our neural network algorithm also shows practical improvements. We emphasize that the deep learning approach is the *first* such result on this problem. We believe that our methods apply to broader classes of physical systems. 
- Reviewer cLpw opines that it is a *strong* paper with *mathematically rigorous guarantees* but it comes from physics literature and is not relevant to the wider NeurIPS community. We note that AI for Science is one of the most active areas at premier ML conferences like NeurIPS and ICML today, and our work falls in this area. Our second result is also very practical (code available via anonymous repo) and shows strong empirical performance.

Among the positive reviews,
- Reviewer MeLw opines that the paper is of "high quality" and gives a score of 7, stating the main reason for not giving a higher score is that they consider the result somewhat incremental. Actually the improvement over previous work is significant - reducing sample complexity from logarithmic to constant. In addition, MeLw appears to have missed entirely, our second main result, namely the *first* deep learning approach to the problem which is not only practical and shows strong empirical improvement over previous work, and for which we also give rigorous results using innovative new techniques such as the Hardy-Krause variation with wide applicability.

Meta-review: Regarding the potential impact of this paper on introducing rigorous machine learning techniques to quantum physics research, I recommend accepting it. Predicting ground state properties is a fundamental task in quantum physics. This paper is the first theoretical work on predicting ground state properties using deep learning and, modulo some assumptions that deserve further study, achieves state-of-the-art sample complexity results. Although there are several gaps between theory and practice in the proposed algorithms, potential concerns are explicitly raised and mostly discussed in the paper.

Below are some additional comments. 
- Some discussion is needed to justify the bounded weights assumption in Theorem 5. 
- The claim that "we cannot guarantee a priori that the network will indeed achieve a low training error" in Section 3.2 deserves further consideration. I agree with the claim, but I believe the reason is the agnostic nature of machine learning. 
- Please consider revising the paper to avoid potential concerns and misunderstandings as those raised by Reviewer u4Mp.
Decision: Accept (poster)