PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably efficient machine learning for quantum many-body problems

Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V. Albert, John Preskill

arXiv:2106.12627v4quant-phcs.ITcs.LG

TL;DR

Classical ML for quantum many-body problems lacks firmly established advantages over traditional methods. The paper combines classical shadows with learning algorithms to prove efficient prediction and classification results. It establishes rigorous guarantees for gapped Hamiltonians and shows that comparable guarantees are unavailable to data-free classical algorithms under standard complexity assumptions.

  • Problem

    Classical ML methods for quantum many-body problems have shown promising results, but their advantages and performance guarantees remain insufficiently established.

  • Method

    The paper uses classical shadows as training representations and derives rigorous ML guarantees for ground-state property prediction and supervised quantum-phase classification.

  • Results

    The paper proves efficient ground-state prediction for gapped finite-dimensional Hamiltonians and shows that data-free classical algorithms cannot match the guarantee under widely accepted complexity assumptions.

  • Takeaways & Limitations

    Classical shadows enable classical ML to generalize quantum-state properties from experimental or simulation data with rigorous guarantees in the studied settings.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses limited rigorous evidence for classical ML in quantum many-body problems by combining classical shadows with learning theory. It proves efficient ground-state prediction and phase classification under stated conditions, and supports these results numerically.

  • Classical ML approaches to quantum many-body physics have shown promise but are mostly heuristic and lack convincing guarantees of good performance.
  • Classical shadows provide succinct classical descriptions of many-body states that can predict a wide range of properties with rigorous guarantees and feasible experimental implementation.
  • For smoothly parameterized Hamiltonians, ML trains on classical shadows of sampled ground states and predicts representations for new parameter values.
  • For gapped finite-dimensional systems, few-body ground-state properties can be predicted with small average error using training data and computation polynomial in the parameter count and linear in system size.
  • Classical algorithms without data cannot provide the same rigorous guarantee under widely accepted complexity-theoretic conjectures.
  • ML generalization can be more convenient than repeated experiments or simulations when changing Hamiltonian parameters is costly or computationally demanding.
  • The second application is supervised phase classification from classical shadows, assuming phases are distinguishable by a nonlinear function of constant-size subsystem marginals.

II. CONSTRUCTING EFFICIENT CLASSICAL REPRESENTATIONS OF QUANTUM SYSTEMS

The classical-shadow formalism converts quantum states into compact randomized-measurement data. These snapshots support efficient, reliable estimation of subsystem-dependent properties.

  • An n-qubit state is measured in random single-qubit Pauli bases across T copies, producing random product-state snapshots.
  • The complete collection of snapshots requires only 3nT bits of classical storage.
  • Randomized measurements can be performed in physical experiments or classical simulations, while storage and postprocessing remain tractable in the stated regime.
  • The classical-shadow representation reproduces the global density matrix as T→∞ and approximates all reduced r-body density matrices with T = O(constr log(n)/ε^2).
  • These approximations enable prediction of functions depending on reduced density matrices, including local observables and entanglement entropies of small subsystems.

III. PREDICTING GROUND STATES OF QUANTUM MANY-BODY SYSTEMS

The paper studies prediction of ground-state representations for smoothly parameterized, geometrically local n-qubit Hamiltonians in finite spatial dimensions. The Hamiltonian family is indexed by a bounded m-dimensional classical parameter.

  • The considered family consists of geometrically local n-qubit Hamiltonians H(x) parametrized by x ∈ [−1, 1]^m.
  • The mapping from the bounded parameter vector x to the 2^n × 2^n Hermitian Hamiltonian is smooth and is not assumed to have additional structure.
  • The target is a classical representation of the quantum many-body ground state associated with each Hamiltonian in the family.

A. An ML algorithm with rigorous guarantee

The proposed ML algorithm predicts classical-shadow representations from Hamiltonian parameters, then estimates few-body ground-state properties from those predictions. A Fourier-kernel analysis supplies rigorous efficiency and accuracy guarantees.

  • A. An ML algorithm with rigorous guarantee: Training uses sampled parameter values and classical shadows of their ground states, while prediction produces a shadow representation for new parameter values.
  • A. An ML algorithm with rigorous guarantee: The predicted representations may encode exponentially large density matrices, yet training and prediction can remain efficient on a classical computer.
  • A. An ML algorithm with rigorous guarantee: The l2-Dirichlet kernel makes the model equivalent to learning a truncated Fourier series for f_O(x) = tr(Oρ(x)).
  • A. An ML algorithm with rigorous guarantee: The prediction guarantee applies when the target property varies sufficiently slowly with x, with gradient bounds derived using quasi-adiabatic continuation.
  • A. An ML algorithm with rigorous guarantee: Theorem 1 guarantees constant-error approximation of few-body reduced density matrices with training data and computation polynomial in m and linear in n.
  • A. An ML algorithm with rigorous guarantee: The required training-data size scales badly with approximation error ε, and improved scaling for restricted Hamiltonian classes remains future work.

B. Computational hardness for non-ML algorithms

The paper argues that non-learning classical algorithms cannot match the ground-state estimation guarantee without contradicting standard complexity assumptions, while training data may itself be difficult to obtain.

  • The hardness result relies on the widely believed conjecture that NP-complete problems cannot be solved in randomized polynomial time.
  • A randomized polynomial-time algorithm without data achieving the stated guarantee would imply a randomized polynomial-time solution for NP-complete problems.The implication applies to smooth families of two-dimensional constant-gap Hamiltonians and one-body observables averaged over parameters.
  • Obtaining training data can itself be challenging, although data efficiently generated by quantum processes may still enable a classical ML advantage.

IV. CLASSIFYING QUANTUM PHASES OF MATTER

The paper formulates quantum-phase classification as learning labels of classical-shadow representations, initially considering two phases and allowing generalization beyond training examples.

  • The proposed learner uses classical shadows of quantum states as its input representation.
  • The analysis for two phases naturally generalizes to classification among any number of phases.

A. ML algorithms

The ML construction maps classical shadows into expressive feature spaces, learns separating hyperplanes, and supports classification from local reduced-density-matrix information and nonlinear features.

  • The learner maps each labeled classical shadow to a feature representation and predicts phases for previously unseen shadows.
  • For symmetry-breaking phases, a local order parameter yields a separating hyperplane that can be learned using reconstructed reduced density matrices and a soft-margin support vector machine.
  • Linear observables cannot distinguish distinct topological phases, motivating nonlinear functions such as topological entanglement entropy.
  • The feature map includes arbitrarily large r-body reduced density matrices and arbitrarily high-degree polynomial expansions.
  • Inner products between feature vectors can be computed analytically in O(nT^2), linear in system size n and quadratic in measured copies T.

B. Rigorous guarantee

The paper gives polynomial-efficiency guarantees for phase classification under local-information assumptions and reports numerical evidence that the approach works in several settings, including a 51-atom Rydberg chain.

  • B. Rigorous guarantee: If phases are classifiable by a nonlinear function of few-body reduced density matrices, the ML algorithm learns an accurate classifier with polynomial data and computation.
  • B. Rigorous guarantee: The guarantee covers local order parameters for symmetry breaking and sufficiently local topological-entanglement-entropy classifiers, while larger correlation lengths increase required subsystem size and resources.
  • B. Rigorous guarantee: The model is guaranteed to efficiently classify a class of gapped one-dimensional spin-1 SPT chains.
  • B. Rigorous guarantee: In a 51-atom Rydberg experiment, ML predictions of local Pauli expectation values agreed well with DMRG values, whereas nearest-training-point predictions performed poorly.
  • B. Rigorous guarantee: Numerical experiments demonstrated that the theoretical claims carried over to practice, sometimes outperforming the stated guarantees.

A. Predicting ground state properties

The paper evaluates classical ML for predicting ground-state representations and observables across Rydberg and 2D Heisenberg systems. Predictions agree well with exact or directly measured-shadow estimates, while the Rydberg example also highlights a scope caveat in the theorem.

  • Method: Classical ML models are selected by validation RMSE to predict ground-state representations from Hamiltonian parameters and classical-shadow training data.The models include kernels equivalent to large-hidden-layer neural networks and kernel methods.
  • Rydberg atom chain: Rydberg-chain predictions for Z_i and X_i agree well with exact DMRG values and outperform the nearest-training-point procedure.The experiment uses 20 training parameter values and T=500 randomized Pauli measurements per state.
  • Scope: The rigorous ground-state guarantee applies only when training and testing points are sampled from the same phase, unlike the three-phase Rydberg training example.Despite this mismatch, the Rydberg numerics still show good prediction performance.
  • 2D antiferromagnetic Heisenberg model: The 2D Heisenberg experiment predicts two-body correlators C_ij for new coupling configurations using classical-shadow representations.The study uses 90 training configurations and T=500 randomized Pauli measurements for each ground state.
  • 2D antiferromagnetic Heisenberg model: The predicted Heisenberg correlators show reasonable agreement with exact values for a representative Hamiltonian instance.Figure 3(b) displays predictions for all spin pairs in that instance.
  • 2D antiferromagnetic Heisenberg model: For most Heisenberg correlators, ML prediction error is comparable to estimating the correlators from T=500 randomized measurements of the true ground state.Figure 3(c) compares red ML RMSE points with blue classical-shadow RMSE points across spin pairs and system sizes.

B. Classifying quantum phases of matter

The paper uses unsupervised nonlinear PCA with a shadow kernel to classify quantum phases without phase labels. In the XXZ and toric-code experiments, phase structure is visible in the learned feature space, although deeper circuits make topological phases harder to distinguish.

  • Method: Unsupervised nonlinear PCA maps classical shadows into a low-dimensional feature space for phase classification without supplied phase labels.The method constructs an infinite-dimensional nonlinear feature vector before applying PCA.
  • Bond-alternating XXZ model: The bond-alternating XXZ model contains trivial, symmetry-protected topological, and symmetry-broken phases identified by a many-body topological invariant.The experiment uses n=300 spins and examines cross sections at δ=0.5 and δ=3.0.
  • Bond-alternating XXZ model: The XXZ phases are well separated in the principal subspace, and the phases naturally cluster in the expressive feature space.The phase diagram colors correspond to invariant values 1, −1, and approximately 0.
  • Trivial versus topological phases: The toric-code experiment distinguishes topological and trivial states generated by low-depth local random circuits from different initial states.The system has n=200 qubits, and the topological construction uses code distance 10.
  • Trivial versus topological phases: As circuit depth increases, the topological and trivial phases become harder to distinguish in the unsupervised feature-space projection.The projection is shown versus depth divided by the code distance 10.
  • Trivial versus topological phases: A CNN using Pauli-6 POVM outcomes cannot classify these topological phases, whereas a CNN using classical-shadow representations can learn nonlinear classification functions successfully.The comparison follows the result that no observable, even a global one, can classify the topological phases.

VI. OUTLOOK

The outlook connects classical shadows and ML to scalable quantum-data analysis, while noting that alternative measurement schemes remain an open direction. The broader aim is to use experimental data to predict unmeasured properties and support applications in materials science and chemistry.

  • Outlook: The paper argues that classical ML informed by physical-experiment data can address some quantum many-body problems.It identifies potential applications in chemistry and materials science that are difficult for classical processing alone.
  • Future directions: Future work must determine how to use measurement data from platforms that cannot perform arbitrary single-qubit Pauli measurements.One proposed setting switches Hamiltonians, allows short evolution, and then measures in the computational basis.
  • Classical shadows: Randomized single-qubit Pauli measurements produce classical-shadow data that can be stored cheaply and used to approximate the underlying quantum state.The construction collects nT single-qubit states after T repetitions and reproduces the state in expectation.
  • Classical shadows: Classical shadows provide succinct state representations whose reduced-density-matrix approximation cost is exponential in subsystem size but independent of total qubit number.This subsystem scaling motivates their use for many-body states.
  • Ground-state prediction: The work’s ground-state ML contribution addresses a setting where direct neural-network approaches lacked rigorous guarantees and establishes an advantage over non-data-learning classical algorithms.The model uses an l2-Dirichlet kernel and is trained with experimental data.
  • Phase classification: The paper uses nonlinear feature maps and PCA on classical shadows to support phase classification, with rigorous accuracy guarantees under specified conditions.The classification analysis assumes the phases are distinguishable by a nonlinear function of constant-size marginal density operators.

D.1. Additional numerical experiments

Additional experiments apply classical-shadow-based ML to predict Rydberg-chain observables and distinguish symmetry-protected and topologically ordered phases. The results compare learned predictions with DMRG, interpolation baselines, and kernel-based phase representations.

  • Distinguishing quantum phases: In phase-classification experiments, low-depth random circuits generate representatives of SPT, topologically ordered, and trivial phases from cluster, toric-code, or product states.The SPT experiment uses a 50-qubit chain with Z2 × Z2 symmetry, while the topological-order experiment uses 200 qubits.
  • Distinguishing quantum phases: With T=500 randomized Pauli measurements, classical-shadow feature vectors and their kernel representations separate distinct phases in the SPT/trivial and topologically ordered/trivial tasks.Kernel matrices and nonlinear PCA projections visualize the separation, and the accompanying text reports that the phases can be distinguished easily.
  • Rydberg atom chain: For a 51-atom Rydberg chain, ML predicts Pauli-Z and Pauli-X expectation values at three testing points, with DMRG providing exact reference curves.Nearest-training-point predictions and learned predictions are shown alongside the DMRG results.
  • Rydberg atom chain: Bivariate B-spline interpolation provides an additional baseline for predicting Rydberg-chain observables from the training data.The interpolated markers are compared with exact values obtained from DMRG.
  • Rydberg atom chain: The Rydberg-chain experiments use DMRG-based matrix-product-state ground-state approximations and characterize phase regions using Z2 and Z3 order parameters.The numerical setup starts from a random MPS and converges it using specified SVD and energy-change thresholds.
  • Rydberg atom chain: Increasing the Rydberg training-set size improves prediction, while the RMSE-versus-N slope flattens; the authors identify guarantees for other ML models as future work.The stated theorem gives N=m O(1/epsilon) as an upper-bound scaling under its assumptions.

E.1. Main result

The paper develops classical ML methods for predicting ground-state properties and representations from sampled Hamiltonian data. Under smoothness and locality conditions, these methods achieve polynomial data and computation requirements, with extensions to alternative measurements, variable parameter dimensions, long-range interactions, and fermionic systems.

  • Ground-state prediction: The l2-Dirichlet-kernel model learns a truncated Fourier approximation to tr(Oρ(x)) from sampled Hamiltonian parameters.The cutoff depends on an upper bound for the function gradient.
  • Ground-state prediction: N = m^O(1/ϵ) training examples suffice for small constant average prediction error when estimating a local ground-state property.The result follows from statistical analysis of the truncated Fourier model.
  • Ground-state representations: The same approach predicts classical-shadow representations whose expectation values reproduce a wide range of observables.Only one randomized-measurement snapshot per parameter point is required in the stated protocol, while multiple snapshots may improve estimates.
  • Generalizations: Alternative measurement procedures can still support accurate prediction of specified observables, although they may not support prediction of a full classical representation.The extension includes other random-unitary ensembles and lists of observable properties.
  • Generalizations: The theorem extends to variable parameter dimensions by training a distinct model for each m, increasing the data size by m_max − m_min + 1.The direct construction applies when the input includes both a discrete parameter count and a continuous vector.
  • Generalizations: Long-range systems are covered when ground-state dynamics have bounded information-spreading speed, while the argument applies to tight-binding fermionic models but fails for some all-to-all systems.The long-range guarantee assumes a constant Lieb–Robinson velocity.

APPENDIX F: Proof of efficiency for predicting ground states

The appendix proves efficiency by approximating the parameter-dependent ground-state function with a truncated Fourier series and controlling truncation and generalization errors. It also establishes computational bounds and a lower-bound argument showing that the favorable scaling depends on learning from data.

  • Theorem and setup: Theorem 3 assumes smooth, geometrically local n-qubit Hamiltonians in finite dimensions with constant spectral gap γ ≥ Ω(1).The target is a ground-state prediction model for sums of few-body observables.
  • Efficiency guarantees: With high probability, classical shadow data suffice to construct the prediction model, with training and prediction costs bounded by the stated polynomial expressions.The bounds depend on n, observable count L, norm bound B, parameter dimension m, and error tolerance ϵ.
  • Fourier approximation: The intermediate model is a truncated Fourier series of the matrix-valued quantum-state function ρ(x), with cutoff Λ controlling retained wavevectors.The observable prediction theorem follows by applying this state-function construction to sums of local observables.
  • Proof strategy: The proof separates the error into truncation error between ρ_Λ(x) and ρ(x), and generalization error between the ML model and ρ_Λ(x).The two bounds combine through a triangle inequality.
  • Classical-shadow data: A single-shot randomized measurement produces an unbiased classical-shadow approximation, and averaging over training data makes its expected model equal the truncated Fourier series.The proof controls the resulting finite collection of Fourier-mode deviations using concentration bounds.
  • Computational limitations: Prediction time becomes problematic when an observable’s support is no longer a small constant because computation scales exponentially with support size.For constant-size supports, each local contribution can be computed in constant time after storage.
  • Lower bounds: The required scaling in ϵ is necessary for general gapped local Hamiltonians unless additional structure, such as translational invariance or graph restrictions, is assumed.The lower-bound argument uses quantum-data sample complexity that becomes exponential in a fractional power of m for sufficiently small error.

G.3. Information-theoretic analysis

The information-theoretic analysis bounds how much information quantum training data can convey about encoded parameters. This supports lower bounds on the data and runtime required by quantum ML procedures that achieve accurate ground-state prediction.

  • Communication reduction: The analysis encodes a parameter message a and studies a decoded estimate ā produced from quantum training states.A successful learner would recover a up to a specified Hamming-distance resolution.
  • Information bound: Because the sampled parameters are independent of the message, the mutual-information bound reduces to conditional information in the decoded output given those parameters.The chain-rule decomposition is applied after conditioning on the sampled inputs.
  • Information bound: Holevo information bounds the correlations between the encoded message and the learner’s decoded signal.The quantum training procedure is treated as a measurement of the joint training-state ensemble.
  • Lower bound: Combining the decoding requirement with the information bound yields the quantum training-data lower bound and the corresponding runtime lower bound.The runtime must be at least as large as the time needed to process the required quantum training data.
  • Fourier-mode counting: The available Fourier-mode count satisfies K_Λ = m^Ω(C/ϵ) under the stated parameter regime, providing a large message dictionary for the reduction.The lower bound follows by counting binary wavevectors of fixed Hamming weight.

H.1. NP-hardness for estimating one-body observables in the ground state of 2D Hamiltonians

The appendix proves that estimating one-body ground-state observables for smooth, gapped, geometrically local 2D Hamiltonians is NP-hard. The reduction encodes a uniquely solvable planar rectilinear 3SAT instance into a 2D Hamiltonian whose ground-state bits can be recovered from local observables.

  • Hardness result: Estimating one-body observables with small average error for smooth, constant-gap 2D Hamiltonians is NP-hard.The hardness applies even when the error is averaged over the smooth Hamiltonian class.
  • Reduction construction: The reduction embeds planar rectilinear 3SAT into a two-dimensional qubit grid using local two-body path terms and three-body clause terms.Irrelevant grid qubits receive -Z_i terms that fix them to |0⟩ in the ground state.
  • Complexity consequence: Therefore, such a randomized polynomial-time classical estimator would imply RP = NP.The conclusion follows from the standard complexity-theoretic consequence of efficiently solving uniquely satisfiable planar rectilinear 3SAT.
  • Ground state: The constructed Hamiltonian has a unique computational-basis ground state |b⟩⟨b| encoding the unique satisfying assignment, with spectral gap at least one.All local terms are diagonal in the Z-basis, and the eigenvalues are integers.
  • Data-dependent learning: The result also supports a data-dependent separation: ML can efficiently learn one-local observables for RSA-based Hamiltonian classes, whereas data-free classical estimation is hard under RSA assumptions.Quantum experiments can efficiently generate the training data for these classes.

APPENDIX I: No observable can classify topological phases

The appendix proves that no single observable can linearly distinguish two distinct topological phases, even when the observable acts on the entire system. It explains why phase classification therefore requires nonlinear functions or classical-ML procedures beyond a single linear order parameter.

  • No linear observable: No observable can distinguish two distinct topological phases after arbitrary local single-qubit unitaries.The claim includes cases where one phase is trivial.
  • Implication for classification: Because any linear classifier based on tr(Oρ) is an observable expectation, linear functions cannot classify topologically ordered phases.This limitation applies even to observables acting globally on the system.
  • Proof strategy: The proof uses Haar-random single-qubit unitaries and compactness of U(2) to show that the assumed positive and nonpositive expectations are incompatible.The contradiction establishes the nonexistence of the proposed observable.
  • SVM background: The SVM framework separates labeled data with a maximum-margin hyperplane, while the representer theorem restricts the learned vector to the span of the training feature points.This reduces dependence on the ambient feature-space dimension to dependence on the training-set size.
  • Kernel limitation: The shadow kernel may require approximation by finite-dimensional kernels because its associated feature space is not finite-dimensional.Finite cutoffs introduce approximation error that can be reduced by increasing the cutoffs.

J.5. Training with shadow kernels

The shadow-kernel construction turns phase-separating nonlinear functions into linear classifiers on finite-dimensional shadow features. With sufficiently large shadows and margin, the resulting SVM can achieve zero training error while retaining polynomial resource scaling under the stated assumptions.

  • Kernel formulation: The shadow-kernel matrix evaluates similarities between classical shadows and supports the finite-dimensional feature-space formulation used for training.The finite approximation is analyzed rather than the infinite shadow kernel directly.
  • Constructing the classifier: A finite power-series approximation converts the nonlinear phase classifier into a linear function in shadow feature space.The corresponding dual vector defines a candidate separating hyperplane for SVM training.
  • Shadow approximation: Classical shadows of sufficient size approximate the truncated classifier uniformly over the training states with probability at least 1 − 𝛿.The approximation bound controls the error simultaneously across all N training examples.
  • Zero training error: The approximating hyperplane has the correct labels and margin on every training example, yielding zero training error when the cutoff conditions hold.The proof uses the uniform approximation error and assumes D ≥ d_p and R ≥ r.
  • SVM feasibility: Choosing the squared margin constant above the stated bound makes the candidate hyperplane feasible, so the original training problem also attains zero error.The feasibility condition is enforced by taking Λ^2 sufficiently large.
  • Efficiency and separation: When r, C, and d_p are constant, the required shadow size and training costs scale favorably with system size, while classical algorithms without data lack the same guarantee under complexity assumptions.Storage, training, and prediction remain polynomially tractable in the system size under the stated setting.
Loading 2106.12627v4…