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.

arXiv comment10 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 (127)

• Fault-tolerant quantum computation by anyons
• Anyons in an exactly solved model and beyond
• A variational eigenvalue solver on a quantum processor
• The density-matrix renormalization group in the age of matrix product states
• Probing many-body dynamics on a 51-atom quantum simulator
• Machine learning and the physical sciences
• Topological entanglement entropy
• The theory of variational hybrid quantum-classical algorithms
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Detecting topological order in a ground state wave function
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• 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
• Topological quantum chemistry
• Improved Simulation of Stabilizer Circuits
• Quantum Convolutional Neural Networks
• Machine learning phases of matter
• Entanglement spectrum of a topological phase in one dimension
• Symmetry protected topological orders and the group cohomology of their symmetry group
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Many-Body Physics with Individually-Controlled Rydberg Atoms
• Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Classification of Gapped Symmetric Phases in 1D Spin Systems
• Many-body quantum state tomography with neural networks
• Symmetry-based Indicators of Band Topology in the 230 Space Groups
• Realizing quantum Ising models in tunable two-dimensional arrays of single Rydberg atoms
• Learning phase transitions by confusion
• Stochastic series expansion method with operator-loop update
• Power of data in quantum machine learning
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• User-friendly tail bounds for sums of random matrices
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Topological classification of crystalline insulators through band structure combinatorics
• Discovering Phase Transitions with Unsupervised Learning
• Spectral Gap and Exponential Decay of Correlations
• Unsupervised learning of phase transitions: from principal component analysis to variational autoencoders
• Quasi-adiabatic Continuation of Quantum States: The Stability of Topological Ground State Degeneracy and Emergent Gauge Invariance
• Quantum Entanglement in Neural Network States
• Studying Two Dimensional Systems With the Density Matrix Renormalization Group
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems
• Detection of Symmetry Protected Topological Phases in 1D
• Reconstructing quantum states with generative models
• Mixed-state entanglement from local randomized measurements
• Dynamical crystallization in a low-dimensional Rydberg gas
• Machine Learning Topological States
• Identifying topological order through unsupervised machine learning
• Quantum Loop Topography for Machine Learning
• The Loop Algorithm
• Information-theoretic bounds on quantum advantage in machine learning
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Competing density-wave orders in a one-dimensional hard-boson model
• Recurrent Neural Network Wave Functions
• Learning Thermodynamics with Boltzmann Machines
• Symmetries and many-body excited states with neural-network quantum states
• Fermionic neural-network states for ab-initio electronic structure
• OrbNet: Deep Learning for Quantum Chemistry Using Symmetry-Adapted Atomic-Orbital Features
• Provably efficient machine learning for quantum many-body problems
• Identifying Quantum Phase Transitions using Artificial Neural Networks on Experimental Data
• Variational optimization with infinite projected entangled-pair states
• Neural-Network Quantum States, String-Bond States, and Chiral Topological States
• Gradient methods for variational optimization of projected entangled-pair states
• Chiral spin liquid phase of the triangular lattice Hubbard model: a density matrix renormalization group study
• Efficient estimation of Pauli observables by derandomization
• Sample-optimal tomography of quantum states
• Machine learning vortices at the Kosterlitz-Thouless transition
• Statistical correlations between locally randomized measurements: a toolbox for probing entanglement in many-body quantum states
• Unsupervised machine learning and band topology
• Fermionic partial tomography via classical shadows
• The power of random measurements: measuring Tr(ρ^n) on single copies of ρ
• Automorphic Equivalence within Gapped Phases of Quantum Lattice Systems
• Robust shadow estimation
• Machine Learning for Quantum Matter
• Probing many-body localization with neural networks
• Integrating Neural Networks with a Quantum Simulator for State Reconstruction
• Isometric Tensor Network States in Two Dimensions
• Perfect Sampling with Unitary Tensor Networks
• Quantum Overlapping Tomography
• Sample-efficient learning of quantum many-body systems
• Bridging lattice-scale physics and continuum field theory with quantum Monte Carlo simulations
• Band Representations and Topological Quantum Chemistry
• Machine Learning ${\mathbb{Z}}_2$ Quantum Spin Liquids with Quasi-particle Statistics
• Finite speed of quantum scrambling with long range interactions
• Classifying Snapshots of the Doped Hubbard Model with Machine Learning
• Strictly linear light cones in long-range interacting systems of arbitrary dimensions
• Order Parameter to Characterize Valence-Bond-Solid States in Quantum Spin Chains
• Unitary $n$-designs via random quenches in atomic Hubbard and Spin models: Application to the measurement of Rényi entropies
• Restricted Boltzmann Machines for Quantum States with Nonabelian or Anyonic Symmetries
• Many-body topological invariants for fermionic symmetry-protected topological phases
• Topological quantum phase transitions retrieved through unsupervised machine learning
• Experimental Estimation of Quantum State Properties from Classical Shadows
• An order parameter for symmetry-protected phases in one dimension
• Many-body topological invariants from randomized measurements
• Neural Gutzwiller-projected variational wave functions
• Quantization of Hall Conductance For Interacting Electrons on a Torus
• Semidefinite approximations of the matrix logarithm
• Hierarchy of linear light cones with long-range interactions
• Simulating adiabatic evolution of gapped spin systems
• Efficient and feasible state tomography of quantum many-body systems
• Deep Learning Topological Invariants of Band Insulators
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Deep learning the Hohenberg-Kohn maps of Density Functional Theory
• Extrapolating quantum observables with machine learning: Inferring multiple phase transitions from properties of a single phase
• Symmetry indicators of band topology
• Unsupervised identification of topological order using predictive models
• A many-body index for quantum charge transport
• Detection of Topological Materials with Machine Learning
• Extraction of many-body Chern number from a single wave function
• Hamiltonian-Driven Shadow Tomography of Quantum States
• Interpreting machine learning of topological quantum phase transitions
• Randomness induced spin-liquid-like phase in the spin-$1/2$ $J_1-J_2$ triangular Heisenberg model
• The Local Density Approximation in Density Functional Theory
• Conversion of projected entangled pair states into a canonical form
• U(1) symmetric recurrent neural networks for quantum state reconstruction
• Quantum topology identification with deep neural networks and quantum walks
• Topological phase transition and ${\mathbb{Z}}_2$ index for $S=1$ quantum spin chains
• On gapped phases with a continuous symmetry and boundary operators
• Hall conductance and the statistics of flux insertions in gapped interacting lattice systems
• Estimating expectation values using approximate quantum states
• Rapid Exploration of Topological Band Structures using Deep Learning
• Predicting excited states from ground state wavefunction by supervised quantum machine learning
• 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
• Unsupervised interpretable learning of topological indices invariant under permutations of atomic bands

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