Provably efficient machine learning for quantum many-body problems

Motivation

• The work addresses the difficulty of classically simulating general quantum many-body systems, for which exact descriptions may require data exponential in the number of qubits.Existing methods solve restricted instances, while scalable fault-tolerant quantum computers are not expected to be available for years.Source: §I · p. 1

Contributions

• Classical shadows enable polynomial-time machine-learning algorithms with rigorous guarantees for predicting ground-state properties and classifying quantum phases.The shadows are succinct classical descriptions constructed from measurements or classical simulations and support prediction of many state properties.Source: §I · pp. 1, 3

Ground-state prediction

• For gapped geometrically local Hamiltonians in finite spatial dimensions, ML predicts slowly varying few-body-observable expectations with small average error using polynomial data and linear system-size computation.The training data pair sampled Hamiltonian parameters with classical shadows of their ground states, after which the model predicts representations for new parameters.Source: §I · pp. 1–2
• Classical algorithms without learning from data cannot provide the same rigorous ground-state guarantee without violating widely accepted complexity-theoretic conjectures.This establishes a data-assisted advantage for ML over non-ML classical algorithms.Source: §I · p. 2

Data sources and motivation

• The guarantees apply whether training data come from quantum experiments or classical simulations, making ML useful when new measurements or simulations are costly or unreliable.Generalization can avoid re-engineering experiments or performing computationally demanding new simulations.Source: §I · p. 2

Quantum-phase classification

• Supervised ML can classify new quantum states into phases using polynomial training data and processing when phase labels are determined by a nonlinear function of constant-size subsystem marginals.The function need not be known in advance, and classical shadows may come from experiments or classical computations.Source: §I · pp. 2–3

• Randomized Pauli measurements on T copies produce classical access to a collection of random pure product-state snapshots of the unknown n-qubit state.Each qubit is measured in a randomly selected X, Y, or Z basis, yielding outcomes ±1.Source: §II · p. 3
• The snapshot collection requires only 3^nT bits of classical storage and can be generated through physical experiments or classical simulations.Source: §II · p. 3
• T = O(const^r log(n)/ε^2) randomized measurements provide an ε-accurate approximation of every reduced r-body density matrix in trace distance.The classical shadow exactly reproduces the global density matrix as T approaches infinity.Source: §II · p. 3
• The resulting classical shadow enables efficient and reliable prediction of expectation values of local observables and entanglement entropies for small subsystems.Classical storage and postprocessing remain tractable in this regime.Source: §II · p. 3

Problem formulation

• The task is to learn a model that predicts properties of ground states for geometrically local n-qubit Hamiltonians parametrized by bounded classical variables.The Hamiltonian family H(x) is smoothly parameterized by x ∈ [−1, 1]^m, without assuming knowledge of the physical parameter-to-Hamiltonian mapping.Source: §III · p. 3

Algorithm

• The method trains on classical-shadow snapshots at sampled parameters and efficiently predicts classical ground-state representations at new parameters using neural networks or kernel methods.Although the represented density matrices are exponentially large, training and prediction remain efficient classically.Source: A. An ML algorithm with rigorous… · pp. 3–4

Proof strategy

• For few-body observables, predicted representations efficiently estimate f_O(x)=tr(Oρ(x)); the proof uses an l2-Dirichlet kernel, truncated Fourier approximation, and gradient bounds from quasi-adiabatic continuation.The kernel cutoff is determined by upper bounds on how rapidly the observable function varies with Hamiltonian parameters.Source: A. An ML algorithm with rigorous… · p. 4

Resource scaling

• The guarantee requires N=m^O(1/ε) training data in the m→∞ limit, with only one classical-shadow snapshot per parameter point (T=1), while computation remains at most linear in n.The resulting average squared prediction error is bounded by ε.Source: A. An ML algorithm with rigorous… · p. 4

Guarantee

• Theorem 1 guarantees that, for smooth finite-dimensional Hamiltonian families with a constant gap, ML predicts few-body ground-state reduced density matrices to constant average error using resources polynomial in m and linear in n.Training data consist of classical shadows from sampled Hamiltonian parameters in the same phase.Source: A. An ML algorithm with rigorous… · pp. 3–4

Limitations

• The ε-dependent data scaling is necessary for general gapped local Hamiltonians, although structural restrictions such as translation invariance or graph structure may enable improved performance with specialized kernels.Rigorously proving such neural-network improvements for specific Hamiltonian classes remains future work.Source: A. An ML algorithm with rigorous… · p. 4

Hardness proposition

• Classical algorithms without data cannot achieve the same guarantee without violating the widely believed conjecture that NP-complete problems lack randomized polynomial-time algorithms [122, 182].This result is presented as a corollary of standard complexity-theoretic results.Source: B. Computational hardness for non-ML… · p. 4
• Proposition 1 shows that efficiently estimating one-body ground-state observables for smooth, gapped two-dimensional Hamiltonian families would enable randomized polynomial-time solutions to NP-complete problems.The guarantee requires constant-error estimates averaged over Hamiltonian parameters and applies to algorithms that do not learn from data.Source: B. Computational hardness for non-ML… · p. 4

Data-enabled computational power

• Learning from data can yield computational capabilities beyond data-free classical algorithms, and this separation may persist for data efficiently generated by quantum processes.The paper relates the data to restricted randomized advice and gives a contrived factoring-based Hamiltonian family establishing the possibility.Source: B. Computational hardness for non-ML… · p. 5

IV. CLASSIFYING QUANTUM PHASES OF MATTER

• The classification framework represents quantum states by classical shadows and distinguishes two phases, A and B, with a natural extension to multiple phases.The analysis is presented for two phases for simplicity but is stated to generalize to any number of phases.Source: §IV · p. 5

General framework

• Classical-shadow classifiers map measured states to expressive feature vectors and learn a separating hyperplane that generalizes to unseen states.The hyperplane can be found by soft-margin support vector machine optimization and may encode an interpretable order parameter.Source: A. ML algorithms · p. 5

Symmetry-breaking phases

• Symmetry-breaking phases can be classified by separating states using all r-body reduced density matrices, which reconstruct the local order parameter from sufficiently large classical shadows.The classifier is y(ρ) = sign(tr(Oρ)), where O is a sum of r-body observables.Source: A. ML algorithms · p. 5

Topological phases

• Distinct topological phases cannot be separated by any linear observable, so classification requires nonlinear functions such as topological entanglement entropy and richer feature maps.The proposed map includes arbitrarily large r-body reduced density matrices and arbitrarily high-degree polynomial expansions.Source: A. ML algorithms · pp. 5–6

Computational cost

• Feature-vector inner products are computed analytically, giving a classical-shadow ML computation time of O(nT^2), linear in system size n and quadratic in measured copies T.The calculation reorganizes direct sums into a double series and wraps the series into an exponential.Source: A. ML algorithms · p. 6

• If phases are classifiable by a nonlinear function of few-body reduced density matrices, classical ML learns an accurate classifier with polynomial training data and computation in system size.The result is established for the model ⟨𝛼, 𝜑(shadow)(𝑆𝑇(𝜌))⟩, where 𝛼 defines the classifying hyperplane.Source: B. Rigorous guarantee · p. 6
• The algorithm efficiently discovers and explicitly constructs classifiers based on efficient reduced-density-matrix procedures, including local order parameters and topological entanglement entropy.Accurate topological classification may require regions larger than the correlation length, increasing subsystem size, training data, and computation near phase boundaries.Source: B. Rigorous guarantee · p. 6
• For SPT phases, the algorithm is rigorously guaranteed to classify a class of gapped one-dimensional spin-1 chains and may help develop compact classifiers for more general interacting systems.SPT classification requires structures to respect the relevant symmetry, and constant-size regions are expected to suffice when they exceed the correlation length.Source: B. Rigorous guarantee · p. 6
• The guarantee may extend to gapless phases recognizable from constant-size regions, while failure to distinguish two such phases implies that nonlocal data is required for at least one.Constant-size recognition is especially plausible for gapped phases but may also apply to some gapless phases.Source: B. Rigorous guarantee · p. 6
• Numerical experiments show that the theoretical claims carry over to practical settings, with performance sometimes exceeding the formal guarantees.Experiments include predicting local Pauli-operator expectation values in a 51-atom one-dimensional Rydberg system against exact DMRG results and nearest-training-point predictions.Source: §V · p. 7, Figure 2 · p. 7

Method

• The method trains kernel- or wide-neural-network-equivalent models by selecting hyperparameters on validation RMSE and evaluating predictions on a test set.The models predict classical representations, which are then used to estimate observables.Source: A. Predicting ground state properties · p. 7

Rydberg atom chain

• For the Rydberg chain, 20 parameter points supplied DMRG ground states and 500 randomized Pauli measurements per state to construct classical shadows for prediction.The system contains 51 atoms, and predicted representations are evaluated at new parameter-space testing points.Source: A. Predicting ground state properties · p. 7
• In the Rydberg chain, predicted local Pauli expectation values agree well with exact DMRG values, while nearest-training-point prediction performs poorly.The result shows that the ML model leverages data from multiple training points; the training set contains points from three phases, beyond Theorem 1’s same-phase guarantee.Source: A. Predicting ground state properties · pp. 7–8

2D antiferromagnetic Heisenberg model

• For the 5 × 5 Heisenberg lattice, 90 randomly chosen coupling configurations and 500 randomized Pauli measurements per ground state supported predictions of two-body correlations.The couplings are uniformly sampled from [0, 2], and the parameter dimension scales as O(n).Source: A. Predicting ground state properties · p. 8
• For most two-body correlators in random 2D Heisenberg models, ML prediction RMSE is comparable to estimating them from 500 measurements of the actual ground state.The comparison covers all spin pairs and variable system sizes, averaged over sampled Hamiltonian parameters.Source: A. Predicting ground state properties · p. 8, Figure 3 · p. 8

Method

• Unsupervised kernel PCA on classical-shadow feature vectors efficiently identifies low-dimensional manifolds corresponding to distinct quantum phases.The method applies an infinite-dimensional nonlinear feature map to each shadow and uses the shadow kernel with kernel PCA.Source: B. Classifying quantum phases of matter · p. 8

Bond-alternating XXZ model

• In the bond-alternating XXZ model, different phases are well separated without phase labels, enabling accurate classification with only a small amount of labeled data as guaranteed by Theorem 2.The experiment uses n=300 spins and T=500 randomized Pauli measurements; the model includes trivial, symmetry-protected topological, and symmetry-broken phases.Source: B. Classifying quantum phases of matter · pp. 8–9, Figure 4 · p. 9

Toric-code topological phase

• In toric-code versus trivial-phase classification, the shadow-based model successfully distinguishes phases, whereas a CNN using Pauli-6 POVM outcomes fails because no observable can classify topological phases.The study uses n=200 qubits and T=500 randomized Pauli measurements; increasing circuit depth makes the phases harder to distinguish.Source: B. Classifying quantum phases of matter · p. 9

APPENDIX A: Background on classical shadows

• Classical shadows use randomized single-qubit Pauli measurements whose stored post-measurement states reproduce the unknown quantum state in expectation.Each repetition selects X, Y, or Z independently and records classical measurement outcomes alongside one of six possible single-qubit states.Source: Appendix A · p. 12
• Classical shadows efficiently represent local quantum information: approximating all reduced r-body density matrices requires resources exponential in r but independent of total qubit number n.Global trace-distance approximation instead requires exponential shadow size, making full-state reconstruction intractable.Source: Appendix A · p. 13

B.1. Estimating ground state properties

• ML trained on experimental data can predict ground-state representations more accurately than any classical algorithm that does not learn from data, under the paper’s guarantees.Existing methods often lack rigorous guarantees or scale exponentially, while the proposed model uses an l2-Dirichlet kernel.Source: §B.1 · pp. 14–15

B.2. Classifying quantum phases of matter

• The work provides rigorous ML approaches guaranteed to classify quantum phases accurately under the conditions of Theorem 2.This addresses limitations of prior models, which lack guarantees and can misclassify phases after slight noise.Source: §B.2 · p. 15

B.3. Classical representations of quantum systems

• Classical representations determine which functions ML can learn, and classical shadows offer a versatile framework extendable to fermionic systems and other efficient representations.The techniques may also help certify ML methods for band-insulator characterization.Source: §B.3 · p. 15

APPENDIX C: Neural networks with classical shadow for quantum many-body problems

• Neural-network enhancements could impose inductive biases and reduce data requirements, but proving improved prediction performance remains future work.Infinite-width neural networks can nevertheless be trained efficiently through neural tangent kernels when those kernels are efficiently evaluable.Source: Appendix C · pp. 15–16

C.1. Predicting ground state representation

• For ground-state representation prediction, an infinite-width neural network can efficiently learn an exponential-size density-matrix output from classical-shadow inputs using a computable neural tangent kernel.Predicted properties are obtained by evaluating observables on the learned representation.Source: §C.1 · p. 16

C.2. Classifying phases of matter

• Phase-classification training uses classical shadows rather than perfect state knowledge, because each labeled quantum state is impractical to characterize exactly.The raw shadow data is organized as a two-dimensional array.Source: §C.2 · p. 17
• The proposed phase-classification method trains a support vector machine using the shadow kernel.The deterministic kernel enables a thorough theoretical analysis of the entire learning procedure in Appendix J.Source: §C.2 · p. 17
• Alternative kernels, including the neural tangent kernel from infinite-width convolutional neural networks, could perform better in practice.The neural tangent kernel is positive-semidefinite and represents similarity induced by the trained neural network [96], with Mercer’s theorem [126] relating it to a Gram matrix in feature space.Source: §C.2 · p. 17
• Infinite-width neural networks using the input array S_T(ρ) induce a feature map that can replace the shadow-kernel feature map.This provides an alternative to the doubly-infinite feature map φ(shadow) associated with the shadow kernel.Source: §C.2 · p. 17

APPENDIX D: Details regarding numerical experiments

• Appendix D supplies additional numerical experiments and further details about the experiments described in the main text.Source: Appendix D · p. 17

D.1. Additional numerical experiments

• Rydberg experiments extend predictions to Pauli-Z_i and Pauli-X_i on all 51 atoms, while bivariate B-spline interpolation provides an additional baseline.Figures 6 and 7 compare machine-learning predictions and nearest-training-point predictions with DMRG exact values; Figure 8 shows spline interpolations against DMRG.Source: §D.1 · p. 17, Figure 6 · p. 18, Figure 7 · p. 18
• Classical-shadow feature vectors clearly separate SPT/trivial and topologically ordered/trivial phases, enabling accurate classification even with unlabeled training data.Both experiments use T=500 randomized Pauli measurements; the SPT/trivial system has 50 qubits, while the toric-code/trivial system has 200 qubits.Source: §D.1 · pp. 17–18, Figure 9 · p. 19

D.2. Ground state properties of the Rydberg atom chain

• Rydberg model performance varies moderately across kernels and regularization settings, but with small training sets the best λ can differ substantially between predicted properties.The study selects models using 80 validation inputs after choosing 20 training points from 100 parameter-space points, then tests on three held-out points.Source: §D.2 · p. 21
• As training size N increases, Rydberg prediction RMSE improves but its decrease flattens, consistent with the theorem’s N = m𝒪(1/ε) training-size scaling.The evaluation covers 102 single-site Pauli-X and Pauli-Z properties across a 1D chain of 51 atoms; the same experiments vary shadow size T.Source: §D.2 · pp. 21–22, Figure 10 · p. 22

D.3. Ground state properties of the 2D antiferromagnetic Heisenberg model

• For 2D Heisenberg correlation-function prediction, neural-network and Gaussian kernels perform better in most cases, while no single regularization λ is uniformly best.The test set contains 6250 instances from a 5 × 5 lattice; kernels perform similarly at larger N and T, with the Dirichlet kernel not matching its best large-T Rydberg performance.Source: §D.3 · pp. 22–23, Figure 11 · p. 23

D.4. Classifying phases of the bond-alternating XXZ model

• In the bond-alternating XXZ classification experiment, modifying diagonal shadow-kernel terms improves numerical stability and slightly improves classification performance.The kernel modification counteracts a large diagonal contribution before standardizing the kernel matrix.Source: §D.4 · p. 24
• Kernel PCA produces low-dimensional vectors that cluster states into distinct quantum phases of matter.The experiment uses two-dimensional representations, with one vector corresponding to each quantum state.Source: §D.4 · p. 24
• For the SPT-versus-trivial setting, symmetric low-depth local random circuits generate representatives while preserving Z2 × Z2 symmetry.The nontrivial phase starts from the one-dimensional cluster state, whereas the trivial phase starts from a product state.Source: §D.4 · p. 24

D.5. Distinguishing a topological phase from a trivial phase

• For 200-qubit toric-code systems, states are generated in topologically ordered and trivial phases using low-depth local random Clifford circuits.The toric-code state has code distance 10, and Clifford circuits enable efficient simulation up to depth 9 via the Gottesman–Knill theorem.Source: §D.5 · p. 24
• The standard supervised CNN’s performance is not substantially different from random guessing on the toric-code phase-classification task.It is trained on 100 labeled points, selected using a 100-point validation set, and evaluated on a 100-point test set.Source: §D.5 · p. 25
• The enhanced CNN represents each qubit using local reduced density matrices estimated from classical shadows obtained with T=500 randomized Pauli measurements.Each state is encoded as a tensor of size 2L × L × 16 before CNN evaluation.Source: §D.4 · p. 24, §D.5 · p. 25

E.1. Main result

• Under a nonzero spectral gap, an l2-Dirichlet-kernel model predicts local ground-state properties with error at most epsilon using N = mO(1/epsilon) training data and polynomial computation.The polynomial scaling follows from a combinatorial bound showing the number of lattice points is mO(1/epsilon), rather than exponential in m.Source: §E.1 · p. 26
• The same approach predicts classical-shadow representations from one randomized Pauli snapshot per parameter point, enabling expectation-value estimates for a wide range of observables.Using multiple snapshots could improve the estimate, but corresponding improved bounds are left for future work.Source: §E.1 · p. 27

E.2. Generalization to other systems and settings

• Theorem 1’s proof can be generalized across measurement procedures, parameter structures, interaction ranges, and fermionic systems.Each extension preserves the learning strategy only under the measurement, parameter, locality, or information-spreading conditions described below.Source: §E.2 · p. 27

a. Prediction based on other quantum measurements

• With alternative measurements or classical representations, the model predicts one observable or a finite collection of observables accurately for new Hamiltonian parameters.The representation may use another random-unitary ensemble or a list of ground-state properties, rather than randomized Pauli shadows.Source: a. Prediction based on other quantum… · p. 27

b. A variable number of parameters

• For a variable number of parameters m ranging from m_min to m_max, training distinct models for each m requires a dataset at most (m_max − m_min + 1) times larger.The input is treated as xi = (m, x), combining a discrete parameter count with an m-dimensional continuous vector.Source: b. A variable number of parameters · pp. 27–28

c. Systems with long-range interactions

• Long-range systems are covered when ground-state dynamics have a bounded Lieb-Robinson velocity and sufficiently suppressed distant commutators, yielding a guarantee similar to Theorem 1.The argument applies when the interaction-dependent decay exponents satisfy the required condition that alpha is sufficiently large compared with beta.Source: c. Systems with long-range interactions · p. 28

d. Fermionic systems

• For fermionic systems, replacing Pauli shadows with fermionic partial tomography and assuming a bounded information-spreading speed extends the theorem to sparse-interaction models.The result applies to tight-binding models including the Fermi-Hubbard model, while the velocity argument fails for some all-to-all-connected systems.Source: d. Fermionic systems · p. 29

APPENDIX F: Proof of efficiency for predicting ground states

• For geometrically local n-qubit Hamiltonians with smoothly parameterized local terms and gap γ≥Ω(1), classical-shadow data suffices to learn predictions for bounded-norm observables with high probability.The theorem concerns observables O=∑ᵢOᵢ with ∑ᵢ‖Oᵢ‖≤B and ground states ρ(x).Source: Appendix F · pp. 29–30
• Both classical training and prediction take time at most 𝒪((n+L)B^2m𝒪(B^2/ϵ)) for the ground-state model.The prediction computes tr(Oσ̂(x)) for a sum of L observable terms.Source: Appendix F · p. 30

F.1. Overview for sample complexity upper bound

• The sample-complexity proof combines Fourier truncation error with machine-learning generalization error and then applies a triangle inequality.The resulting bound establishes the sample-complexity upper bound used for the theorem.Source: §F.1 · p. 31

F.2. Controlling the truncation error

• Truncating the Fourier representation controls approximation error through bounds on parameter derivatives of observable expectation values.The appendix derives the truncation inequality using harmonic-analysis orthogonality and the condition E_x‖∇_x tr(Oρ(x))‖_2^2≤C.Source: §F.2 · p. 32

F.3. Controlling generalization errors from using the training data

• Classical-shadow labels are unbiased, and for observables decomposing into local terms, concentration over sampled parameters controls the generalization error with high probability.The proof uses bounded random variables, Hoeffding-type concentration, and a union bound over finitely many Fourier wave-vectors.Source: §F.3 · pp. 32, 33, 35

F.4. Computational time for training and prediction

• The Fourier-kernel predictor evaluates in time 𝒪(K_Λ), with K_Λ≤(2m+1)^Λ^2 and Λ=Θ(√(C/ϵ)), while local observable contractions are constant-time for fixed locality.Runtime becomes problematic when an observable’s support is no longer a small constant because the contraction cost scales exponentially with support size.Source: §F.4 · p. 36

F.5. Spectral gap implies smooth parametrizations

• Physically meaningful assumptions on finite-dimensional systems, geometrically local bounded Hamiltonian terms, and gapped ground-state subspaces provide the smoothness bound needed to set C=𝒪(B^2).Applying the general state-learning theorem with this bound yields the ground-state theorem.Source: §F.5 · p. 36
• A constant lower-bounded spectral gap implies a uniform smoothness bound for few-body observables along local-Hamiltonian parameter paths.The proof combines Lieb–Robinson bounds with spectral flow, with constants depending on spatial dimension, gap, and Lieb–Robinson velocities.Source: §F.5 · pp. 37, 39

G.1. Learning problem formulation

• The sample-complexity lower bound is established by encoding a hidden sign vector in a family of single-qubit Hamiltonians whose observable expectation reproduces a truncated Fourier function.Each sign choice defines a Hamiltonian over x ∈ [−1,1]^m, and predicting the scaled Pauli-Y expectation is equivalent to learning the corresponding function.Source: Appendix G · p. 39, §G.1 · p. 40

G.2. Communication protocol

• Prediction accuracy worsens when a candidate sign vector differs from the true one by more than K_Λ/18 in Hamming distance, enabling recovery of the hidden parameter at that resolution.A dictionary of sign vectors separated by more than K_Λ/18 lets the learned predictor serve as a decoding procedure.Source: §G.2 · pp. 41–42
• The protocol has Alice encode a dictionary index in quantum training data and Bob decode it by checking prediction error for every dictionary element, exposing information-theoretic limits on training-data size.The dataset uses uniformly sampled inputs and ground states generated from Alice’s selected sign vector; successful prediction retrieves the correct message with high probability.Source: §G.2 · p. 42

G.3. Information-theoretic analysis

• A large message dictionary, M = ⌊exp(KΛ/32)⌋, can nevertheless be decoded with high probability by the promised quantum ML procedure.This establishes the communication setting used for the hardness argument.Source: §G.3 · p. 42
• Mutual information between Alice’s message a and Bob’s decoded signal ā is lower-bounded via Fano’s inequality and upper-bounded through Holevo information.Bob measures the tensor-product training state and reconstructs ā, so the classical correlation is bounded by the Holevo information of the associated quantum-state ensemble [89][197, Sec. 11.6.1].Source: §G.3 · p. 42
• Independent training parameters imply I(a:x₁,…,x_N)=0, reducing I(a:ā) to conditional mutual information averaged over the sampled instances.The chain-rule reduction is given explicitly in Eqs. (G18a)–(G18d).Source: §G.3 · p. 42
• The correlation problem reduces to bounding the Holevo information of the two-by-two states ρ_a, which is evaluated using entropy identities and the ground-state representations from Lemma 6.The resulting bound is stated in Lemma 8 and completed using eigenvalue, binary-entropy, Jensen, and Fourier-orthogonality arguments.Source: §G.3 · pp. 43–44
• The first claim of Theorem 5 follows once the allowed Fourier-mode count satisfies the required assumption, with the lower bound KΛ = m^Ω(C/ϵ) obtained by counting binary wavevectors.Restricting to wavevectors with exactly ⌊C/(9ϵ)⌋ ones yields KΛ ≥ m^0.01⌊C/(9ϵ)⌋ = m^Ω(C/ϵ).Source: §G.3 · p. 43
• Because quantum ML must process N ≥ B^2m^Ω(C/ϵ)/log(B) quantum training data, its runtime is lower-bounded by the same quantity.This connects the information-theoretic constraint to the computational lower bound.Source: §G.3 · p. 43

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

• For any smooth class of 2D Hamiltonians with a constant spectral gap and unique ground state, estimating one-body Pauli-Z observables to average error 1/4 implies RP = NP.The guarantee holds even when the error is averaged over the Hamiltonian class.Source: §H.1 · pp. 44–45
• The reduction embeds planar rectilinear 3SAT into a 2D qubit grid using local path constraints, clause terms, and fields fixing irrelevant qubits.The resulting Hamiltonian is diagonal, has a unique ground state encoding the satisfying assignment, and has spectral gap at least one.Source: §H.1 · pp. 45–46
• If such observable estimates were available, O(log(n)) randomized repetitions would recover every assignment bit with probability at least 1/2, solving unique planar rectilinear 3SAT.Because the Pauli-Z expectation values are in {−1, 1}, additive error 1/2 suffices to decode the encoded solution.Source: §H.1 · p. 46
• The hardness argument extends from the constant Hamiltonian class to suitably chosen smooth, nonconstant classes with parameter-dependent local single-qubit rotations.The rotated Hamiltonians remain geometrically local, and predicting averaged ground-state properties remains hard.Source: §H.1 · p. 46

H.2. Computational hardness for a class of Hamiltonians based on factoring

• Combining Theorem 1 with Proposition 3 shows that preparing ground states of hard 2D local Hamiltonians is itself NP-hard, even when followed by single-qubit measurements and efficient classical processing.The authors note that this does not model realistic laboratory conditions because physically realizing an NP-hard preparation is not expected to be efficient.Source: §H.2 · pp. 46–47
• The factoring construction maps a unique factoring solution through SAT, 3SAT, planar rectilinear 3SAT, and finally a gapped 2D 3-local Hamiltonian whose one-local observables reveal the solution.Factoring large semiprimes is assumed classically hard and suffices to break RSA encryption.Source: §H.2 · p. 47
• For RSA-based gapped Hamiltonian classes, Shor’s algorithm and adiabatic evolution provide quantum training data, enabling efficient classical prediction of one-local observables that data-free classical algorithms cannot efficiently estimate if RSA remains unbreakable.The adiabatic evolution is efficient because the Hamiltonian class has a constant spectral gap.Source: §H.2 · p. 47

APPENDIX I: No observable can classify topological phases

• For any two distinct topological phases A and B, including when one phase is trivial, no observable O exists that can classify the phases.Source: Appendix I · pp. 47–48

APPENDIX J: Proof of efficiency for classifying phases of matter

• The phase-classification guarantee is developed using supervised-learning tools, specifically support vector machines and their generalization analysis.The appendix introduces this section as a proof of a rigorous performance guarantee for learning to predict quantum phases of matter.Source: Appendix J · p. 49

J.1. Training support vector machines

• SVM training separates labeled data with a margin-maximizing hyperplane, and kernel feature maps make nonlinear separation tractable through an N × N Gram matrix.The representer theorem restricts the classifier to the span of transformed training points, while the resulting convex QCQP is solvable in polynomial time in N.Source: §J.1 · pp. 49–51, Figure 13 · p. 50

J.2. Prediction using support vector machines

• The trained SVM exactly reproduces training labels when the training error is zero, then predicts new labels by evaluating the classifier’s kernel expansion.Prediction cost is dominated by evaluating N kernel functions, so small training sets yield fast prediction when the kernel is efficiently computable.Source: §J.2 · p. 51
• Theorem 6 bounds average prediction error by the training error plus a term decaying with training size N, assuming bounded kernels and iid training and prediction data.The bound holds with probability at least 1 − δ and uses the kernel bound k(x, x) ≤ R^2, minimal margin 2/Λ, and training size N.Source: §J.2 · p. 52
• The support vector machine obtains the tightest available bound by minimizing a hinge-loss upper bound on classification error over bounded hyperplane vectors.The resulting optimizer simultaneously defines the classifier and minimizes the training error.Source: §J.2 · pp. 53–54

J.3. Kernel functions for classical shadows

• The shadow kernel is efficiently computable from classical shadows and remains bounded, despite representing states with potentially exponentially many degrees of freedom.Its evaluation requires nT^2 trace inner products, while finite-dimensional approximations provide theoretical guarantees with arbitrarily small additional error.Source: §J.3 · p. 55

J.4. Physical assumptions about classifying quantum phases of matter

• Phase classification assumes a reduced-density-matrix function separates phases by margins exceeding 1 and admits a degree-d_p polynomial approximation with error at most 0.25.Exact classical-shadow representations would require T≥exp(Ω(n)), so the framework instead uses coarser resolutions when this analytic condition holds.Source: §J.4 · p. 56
• Subsystem purity is exactly quadratic, while order-two Rényi entropy reaches constant approximation error with d_p=𝒪(log(r)2^r), independent of total system size.The same approximation strategy extends to higher-order Rényi entropies and averages over multiple subsystems.Source: §J.4 · p. 57
• For an r-qubit subsystem, entanglement entropy admits a polynomial approximation with d_p=2^r+2, which is constant when r is independent of n.The normalization constant is likewise constant, and the construction extends to averages of multiple entanglement entropies.Source: §J.4 · pp. 57–58

J.5. Training with shadow kernels

• A shadow-kernel feature map approximates the analytic phase classifier by a finite power series, yielding a separating hyperplane and zero SVM training error with high probability.Proposition 5 gives a sufficient joint shadow size T and requires a sufficiently large squared margin constant so the ideal hyperplane remains feasible.Source: §J.5 · pp. 58–59

J.6. Prediction based on shadow kernels

• Shadow-kernel SVMs generalize from labeled classical shadows when phases are distinguished by a bounded analytic function of reduced r-body density matrices, with polynomial costs in system size.The required shadow size is polylogarithmic in n for constant r, C, and d_p, while training-data size and storage, training, and prediction costs scale polynomially.Source: §J.6 · pp. 60–61

K.1. Symmetry-protected topological phases

• Gapped Hamiltonian families remain in the same SPT phase under continuous parameter changes, with transitions requiring gap closure; local classification is rigorously established only in selected cases,, [15, 173, 174].One-dimensional spin-chain SPT phases with unique ground states correspond to projective representations of the protecting symmetry group.Source: §K.1 · p. 62

K.2. O(2)-symmetric qutrit spin chains

• The two O(2)-symmetric qutrit-chain phases are represented by the trivial product state and the Haldane valence-bond-solid state, distinguished by the twist expectation sign.The product state has sign +1, whereas the VBS state has sign −1; continuity preserves this sign within each phase.Source: §K.2 · pp. 62–63
• For O(2)-symmetric qutrit spin chains, a few-body observable A matches the nonlocal twist invariant’s sign and satisfies |⟨A⟩| ≥ 1/2 across the family.This local observable supplies the margin needed for accurate classical-shadow classification of the two SPT phases.Source: §K.2 · pp. 62–63

K.2. 𝑂(2)-symmetric qutrit spin chains

• The proof uses a twist whose conjugation assigns each operator component a phase that is an integer multiple of 2π/(2ℓ+1).Terms with the same phase are grouped into components h_j,μ, which transform by the corresponding phase under conjugation.Source: §K.2 · p. 64
• Because the spin-operator products form a complete matrix-unit basis, each phase component h_j,μ is obtained by removing entries from h_j and retains norm at most R.The resulting norm bound is used together with the spectral-gap inequality to derive the energy estimate.Source: §K.2 · pp. 64–65
• For ℓ≥C0, the ground-state and twisted-ground-state energies differ by at most C1/ℓ, with constants depending on interaction range r and term-norm bound R.This result is stated as Lemma 13 (High overlap; Eq. (K7)).Source: §K.2 · p. 64