## Appendix A VC Dimension of Ising Predictor  
In this appendix, we provide the derivation for the VC dimension of the Ising classifier toy models. First, we show a simple result that one test datum can always be shattered by one support vector; hence, there is a general lower bound \(d_{VC}\geq 1\). If there is only one support vector \(s_{1}\) and one test datum \(s_{2}\), the Hamiltonian is \(H=-Js_{1}s_{2}-h_{1}s_{1}=-s_{1}(Js_{2}+h_{1})\). Given any \(s_{2}\), we can choose \(s_{1}=s_{2}\) to produce the desired ground state. Hence, one point can always be shattered by one support vector. Hence, \(d_{VC}\geq 1\).  
Then, we consider the fully connected Ising model \(H=-\int\sum_{i<j}s_{i}s_{j}\). The eigenenergy \(E_{m}=\int(-\frac{1}{2}N(N-1)+2m(N-m))\) for eigenstates with \(m\) spin-up and \((N-m)\) spin-down. The spectrum is a parabolic curve concave downward as a function of \(m\). The doubly degenerated ground states are all spin-up and all spin-down states with energy \(E_{0}=-\frac{1}{2}N(N-1)\). The highest energy state occurs at \(m=\lfloor\frac{N}{2}\rfloor\) with half spin-up and half spin-down and the energy is \(E_{max}=\int\lfloor\frac{N}{2}\rfloor\).  
Now, we can consider the first prediction model defined in Equation (16). Let us consider two configurations of prediction data: (A) half spin-up and half spin-down; (B) all spins aligned in the same direction. To shatter the prediction data, the model has to be able to achieve a ground state when the given test data are in the highest energy state \(E^{A}_{t}=\int\lfloor\frac{h_{t}}{2}\rfloor\). The best possible choice of the support vectors is that all spins are aligned in the same direction with some energy \(E_{sv}\). The interaction between support vectors and test data gives the energy \(E^{A}_{int}=-\frac{1}{2}(n_{t}\bmod 2)\). The resulting total energy is \(E^{A}_{total}=E^{A}_{t}+E^{A}_{int}+E_{sv}=\int\lfloor\frac{n_{t}}{2}\rfloor- \frac{1}{2}(n_{t}\bmod 2)+E_{sv}\). To predict configuration (A), \(E^{A}_{total}\) must be lower than the state \(E^{B}_{total}\), where all prediction spins are aligned with all support vectors. The total energy in the second case is \(E^{B}_{total}=-\frac{1}{2}n_{t}(n_{t}-1)-Jn_{t}n_{sv}+E_{sv}\). The requirement \(E^{A}_{total}\leq E^{B}_{total}\) means \(\int\lfloor\frac{n_{t}}{2}\rfloor-\frac{1}{2}(n_{t}\bmod 2)+\frac{1}{2}n_{t}(n_{t}-1)+Jn _{t}n_{sv}\leq 0\). Since only the second term is negative, this condition can never be satisfied for any \(n_{t}\geq 2\). Hence, the model can never shatter two points, so \(d_{VC}\leq 1\). Since we also have \(d_{VC}\geq 1\), we conclude that \(d_{VC}=1\).  
Then, we consider the second relaxed model defined in Equation (18). To simplify the derivation, we assume that \(n_{sv}\) and \(n_{t}\) are both even numbers. The support vectors can be in the configuration of half spin-up and half spin-down. The spin-up support vectors are one-to-one-coupled to the spin-up test data. The interaction energy is \(E^{A}_{int}=-J_{int}n_{sv}\) and the total energy is \(E^{A}_{total}=E^{A}_{t}+E^{A}_{int}+E_{sv}=\int_{t}\frac{n_{t}}{2}-J_{int}n_{sv }+E_{sv}\). We also have \(E^{B}_{total}=E^{B}_{t}+E^{B}_{int}+E_{sv}=\frac{-1}{2}I_{t}n_{t}(n_{t}-1)+0+E _{sv}\). The requirement \(E^{A}_{total}\leq E^{B}_{total}\) then implies \(n_{p}\leq\sqrt{\frac{2|\mu_{t}}{J_{t}}}n_{sv}\). Hence, \(d_{VC}\leq\sqrt{\frac{2|\mu_{t}}{J_{t}}}n_{sv}\). We may also consider that all support vectors are aligned in the same direction. In this case, we have \(E^{A}_{total}=E^{A}_{t}+E^{A}_{int}+E_{sv}=I_{t}\frac{n_{t}}{2}+0+E_{sv}\) and \(E^{B}_{total}=E^{B}_{t}+E^{B}_{int}+E_{sv}=\frac{-1}{2}I_{t}n_{t}(n_{t}-1)+J_{ int}n_{sv}+E_{sv}\); therefore, the upper bound remains the same.