Research map / Learning theory and algorithms / Sample complexity
Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that a ridge-regression variant of the Lewis et al. geometric-feature method achieves system-size-independent sample complexity for ground-state property prediction, and that a tanh neural network trained on low-discrepancy/quasi-Monte Carlo data gives a rigorous 2^polylog(1/eps) sample bound, with experiments up to 45 qubits.
Problem
Reducing the number of training samples needed to predict ground-state properties of gapped geometrically local Hamiltonians below O(log n) and providing rigorous sample-complexity guarantees for neural-network ML models in this setting.
Approach
Modify the Lewis et al. feature map by weighting features with square roots of Pauli coefficients and replace LASSO with ridge regression to get n-independent sample complexity; for neural networks, combine Koksma-Hlawka quasi-Monte Carlo bounds with spectral flow to bound prediction error for local tanh sub-networks trained on low-discrepancy data.
Key results
- Neural network model achieves approximately half the prediction error of the Lewis et al. regression model on the same training data (N = 3686) for 20 to 45 qubit Heisenberg systems.
- Prediction error of both methods is roughly constant with system size, consistent with the system-size-independent guarantee.
- Theory gives constant sample complexity 2^polylog(1/eps) for ridge regression with known observable, and a neural network bound N = O(2^polylog(1/eps)) without requiring knowledge of the observable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the previous regression method with the deep learning model | Prediction of two-body correlations in the random Heisenberg model · Two-dimensional random Heisenberg model, 20–45 qubits | prediction RMSE: approximately half the prediction error | Helped |
| Train on low-discrepancy sequence points instead of uniformly random points (ablation) | Deep learning model and regression model · Two-dimensional random Heisenberg model, 20–45 qubits | prediction RMSE | No clear effect |
| Increase the local neighborhood size δ1 above 0 (ablation) | Deep learning model · Two-dimensional random Heisenberg model, 20–45 qubits | prediction RMSE | Mixed |
Surprising findings
- Training on low-discrepancy (Sobol) points versus uniform random points gives nearly identical performance for both methods.
Limitations
- Neural network guarantee requires training data from a distribution with product-form, full-support density and assumes the training objective reaches O(eps) which is non-convex and not guaranteed.
- Sample complexity scales quasi-polynomially in 1/eps unless the number of Hamiltonian parameters is constant.
- Ridge approach requires knowing the observable's Pauli decomposition in advance.
Experimental setup
Datasets: DMRG-generated ground-state correlation data for 2D random Heisenberg model
Benchmarks: 2D random antiferromagnetic Heisenberg model (20 to 45 qubits)
Metrics: RMSE
Baselines: Lewis et al. LASSO-based geometric learning
Builds on: Lewis et al. ground state property learning (LASSO) Huang et al. 2022 learning ground state properties Koksma-Hlawka inequality spectral flow formalism
Closest papers by meaning
- Rethink the Role of Deep Learning towards Large-scale Quantum Systems (ICML 2025 · similarity 0.89)
- One More Time: Revisiting Neural Quantum States from a Reinforcement Learning Perspective (NeurIPS 2026 · similarity 0.86)
- Learning the Electronic Hamiltonian of Large Atomic Structures (ICML 2025 · similarity 0.85)
- Reinforced Learning Explicit Circuit Representations for Quantum State Characterization from Local Measurements (ICML 2025 · similarity 0.85)
- From Density Matrices to Phase Transitions in Deep Learning: Spectral Early Warnings and Interpretability (NeurIPS 2026 · similarity 0.85)
- PALQO: Physics-informed model for Accelerating Large-scale Quantum Optimization (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.