Provably efficient machine learning for quantum many-body problems

Abstract

Classical machine learning (ML) provides a potentially powerful approach to solving challenging quantum many-body problems in physics and chemistry. However, the advantages of ML over more traditional methods have not been firmly established. In this work, we prove that classical ML algorithms can efficiently predict ground state properties of gapped Hamiltonians in finite spatial dimensions, after learning from data obtained by measuring other Hamiltonians in the same quantum phase of matter. In contrast, under widely accepted complexity theory assumptions, classical algorithms that do not learn from data cannot achieve the same guarantee. We also prove that classical ML algorithms can efficiently classify a wide range of quantum phases of matter. Our arguments are based on the concept of a classical shadow, a succinct classical description of a many-body quantum state that can be constructed in feasible quantum experiments and be used to predict many properties of the state. Extensive numerical experiments corroborate our theoretical results in a variety of scenarios, including Rydberg atom systems, 2D random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases.

10 pages, 13 figures + 60-page appendix; v4: Fixed a minor formatting issue; open-source code available at https://github.com/hsinyuan-huang/provable-ml-quantum

References in corpus (21)

• The density-matrix renormalization group in the age of matrix product states
• Probing many-body dynamics on a 51-atom quantum simulator
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Entanglement Spectrum as a Generalization of Entanglement Entropy: Identification of Topological Order in Non-Abelian Fractional Quantum Hall Effect States
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Many-Body Physics with Individually-Controlled Rydberg Atoms
• Learning phase transitions by confusion
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems
• Dynamical crystallization in a low-dimensional Rydberg gas
• Competing density-wave orders in a one-dimensional hard-boson model
• Provably efficient machine learning for quantum many-body problems
• Efficient estimation of Pauli observables by derandomization
• Machine learning vortices at the Kosterlitz-Thouless transition
• Bridging lattice-scale physics and continuum field theory with quantum Monte Carlo simulations
• Hamiltonian-Driven Shadow Tomography of Quantum States
• Estimating expectation values using approximate quantum states
• Summability of Multi-Dimensional Trigonometric Fourier Series
• Unsupervised mapping of phase diagrams of 2D systems from infinite projected entangled-pair states via deep anomaly detection

Cited by in corpus (134)

• Challenges and Opportunities in Quantum Machine Learning
• Quantum advantage in learning from experiments
• Generalization in quantum machine learning from few training data
• The randomized measurement toolbox
• Provably efficient machine learning for quantum many-body problems
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Learning Quantum Systems
• Many-Body Localization in the Age of Classical Computing
• Theory for Equivariant Quantum Neural Networks
• Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Out-of-distribution generalization for learning quantum dynamics
• On the practical usefulness of the Hardware Efficient Ansatz
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Machine Learning for Practical Quantum Error Mitigation
• Quantum machine learning of large datasets using randomized measurements
• Shadow process tomography of quantum channels
• Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers
• The MQT Handbook: A Summary of Design Automation Tools and Software for Quantum Computing
• Quantum phase detection generalisation from marginal quantum neural network models
• Operator relaxation and the optimal depth of classical shadows
• Classical shadows with Pauli-invariant unitary ensembles
• Quantum Phase Recognition via Quantum Kernel Methods
• Improved machine learning algorithm for predicting ground state properties
• Cross-Platform Comparison of Arbitrary Quantum Computations
• Quantum Simulations in Effective Model Spaces (I): Hamiltonian Learning-VQE using Digital Quantum Computers and Application to the Lipkin-Meshkov-Glick Model
• Model-Independent Learning of Quantum Phases of Matter with Quantum Convolutional Neural Networks
• Quantum Error Mitigated Classical Shadows
• Feedback-driven quantum reservoir computing for time-series analysis
• Non-IID Quantum Federated Learning with One-shot Communication Complexity
• Classical shadow tomography for continuous variables quantum systems
• Flexible learning of quantum states with generative query neural networks
• Quantum Mixed State Compiling
• Performance analysis of multi-shot shadow estimation
• Revealing the nature of hidden charm pentaquarks with machine learning
• Robust estimation of the Quantum Fisher Information on a quantum processor
• Quantum kernels to learn the phases of quantum matter
• Estimating gate-set properties from random sequences
• Effects of noise on the overparametrization of quantum neural networks
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Equivalence Checking of Parameterized Quantum Circuits: Verifying the Compilation of Variational Quantum Algorithms
• Enhancing Detection of Topological Order by Local Error Correction
• Classically estimating observables of noiseless quantum circuits
• Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
• Demonstration of Robust and Efficient Quantum Property Learning with Shallow Shadows
• Neural network encoded variational quantum algorithms
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Entanglement accelerates quantum simulation
• Certification of quantum states with hidden structure of their bitstrings
• Machine learning on quantum experimental data toward solving quantum many-body problems
• Enhanced estimation of quantum properties with common randomized measurements
• On the expressivity of embedding quantum kernels
• Computing exact moments of local random quantum circuits via tensor networks
• Foundation Neural-Networks Quantum States as a Unified Ansatz for Multiple Hamiltonians
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Atomic Quantum Technologies for Quantum Matter and Fundamental Physics Applications
• Local minima in quantum systems
• Filtering crosstalk from bath non-Markovianity via spacetime classical shadows
• Randomness-enhanced expressivity of quantum neural networks
• Statistical Complexity of Quantum Learning
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Variational optimization of the amplitude of neural-network quantum many-body ground states
• EHA: Entanglement-variational Hardware-efficient Ansatz for Eigensolvers
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Estimating the Euclidean quantum propagator with deep generative modeling of Feynman paths
• The role of data embedding in equivariant quantum convolutional neural networks
• Continuous-variable quantum state designs: theory and applications
• Supervised learning of random quantum circuits via scalable neural networks
• Implementation of quantum stochastic walks for function approximation, two-dimensional data classification, and sequence classification
• Entanglement-induced provable and robust quantum learning advantages
• Unified Quantum State Tomography and Hamiltonian Learning Using Transformer Models: A Language-Translation-Like Approach for Quantum Systems
• Stability of classical shadows under gate-dependent noise
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus
• Investigating the Effect of Noise on the Training Performance of Hybrid Quantum Neural Networks
• Error-tolerant quantum convolutional neural networks for symmetry-protected topological phases
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Exponentially improved efficient machine learning for quantum many-body states with provable guarantees
• Unsupervised Interpretable Learning of Phases From Many-Qubit Systems
• Simulating 2D topological quantum phase transitions on a digital quantum computer
• Quantum-enhanced neural networks in the neural tangent kernel framework
• Unveiling quantum phase transitions from traps in variational quantum algorithms
• Efficient Classical Shadow Tomography through Many-body Localization Dynamics
• Projective toric designs, quantum state designs, and mutually unbiased bases
• Efficient and quantum-adaptive machine learning with fermion neural networks
• Observing Schrödinger's Cat with Artificial Intelligence: Emergent Classicality from Information Bottleneck
• Machine learning reveals features of spinon Fermi surface
• Universal adversarial perturbations for multiple classification tasks with quantum classifiers
• Quantum contextual bandits and recommender systems for quantum data
• Entanglement Detection with Quantum-inspired Kernels and SVMs
• Learning topological states from randomized measurements using variational tensor network tomography
• Synergy between noisy quantum computers and scalable classical deep learning
• Predicting topological invariants and unconventional superconducting pairing from density of states and machine learning
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Hacking Cryptographic Protocols with Advanced Variational Quantum Attacks
• Learning of error statistics for the detection of quantum phases
• Estimating many properties of a quantum state via quantum reservoir processing
• Quantum Convolutional Neural Network for Phase Recognition in Two Dimensions
• Learning Quantum Processes with Quantum Statistical Queries
• Exact spectral gaps of random one-dimensional quantum circuits
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Efficient learning of ground & thermal states within phases of matter
• Machine learning the Ising transition: A comparison between discriminative and generative approaches
• Variational quantum algorithm for Gaussian discrete solitons and their boson sampling
• Classifying topological neural network quantum states via diffusion maps
• Machine-learning-inspired quantum control in many-body dynamics
• Quantum circuit complexity and unsupervised machine learning of topological order
• Learning Density Functionals from Noisy Quantum Data
• Sub-ballistic operator growth in spin chains with heavy-tailed random fields
• Tomography of parametrized quantum states
• Quantum Curriculum Learning
• Holographic Classical Shadow Tomography
• Quantum Active Learning
• Efficient Learning of Long-Range and Equivariant Quantum Systems
• Learning quantum symmetries with interactive quantum-classical variational algorithms
• Efficiency of neural-network state representations of one-dimensional quantum spin systems
• Attention to Quantum Complexity
• Unified Architecture for Quantum Lookup Tables
• Protecting entanglement witnesses with randomized measurements
• Learning the dynamics of Markovian open quantum systems from experimental data
• Model-Independent Quantum Phases Classifier
• Quantum-Classical Auxiliary Field Quantum Monte Carlo with Matchgate Shadows on Trapped Ion Quantum Computers
• Fourier Neural Operators for Time-Periodic Quantum Systems: Learning Floquet Hamiltonians, Observable Dynamics, and Operator Growth
• Machine-learning-enabled characterization of individual ring resonators in integrated photonic lattices
• A Study on Stabilizer Rényi Entropy Estimation using Machine Learning
• Quantum phase classification via partial tomography-based quantum hypothesis testing
• Challenges and opportunities in the supervised learning of quantum circuit outputs
• Moments of Quantum Channel Ensembles
• Learning mixed quantum states in large-scale experiments
• A Unsupervised Framework for Identifying Diverse Quantum Phase Transitions Using Classical Shadow Tomography
• Diagnosing crosstalk in large-scale QPUs using zero-entropy classical shadows
• Quantum Phase Recognition via Quantum Attention Mechanism
• Classical Shadows with Improved Median-of-Means Estimation
• Critical Scaling of the Quantum Wasserstein Distance