Provably scalable learning from quantum many-body data via locality

Koki Chinzei; Quoc Hoan Tran; Norifumi Matsumoto; Yasuhiro Endo; Hirotaka Oshima

quant-phSep 17, 2025

Provably scalable learning from quantum many-body data via locality

Authors: Koki Chinzei, Quoc Hoan Tran, Norifumi Matsumoto, Yasuhiro Endo, Hirotaka Oshima

Organizations: Quantum Laboratory, Fujitsu Research, Fujitsu Limited, 4-1-1 Kawasaki, Kanagawa 211-8588, Japan

Abstract

Machine learning (ML) holds great promise for extracting insights from complex quantum many-body data obtained in quantum experiments, potentially solving certain classically intractable problems. However, addressing large-scale problems still requires significant amounts of data that exceed the capabilities of near-term quantum devices. We propose a scalable ML framework, the Geometrically Local Quantum Kernel (GLQK), that efficiently learns from quantum many-body data by leveraging the exponential decay of correlations prevalent in noncritical systems. For learning an unknown polynomial of quantum expectation values, we rigorously prove that the GLQK substantially improves the sample complexity in the system size $n$ over the existing shadow kernel, by constructing a feature space from local quantum information at the correlation length scale. This improvement is particularly notable when each term of the target polynomial involves few local subsystems. Remarkably, for translationally symmetric data, the GLQK achieves constant sample complexity, independent of $n$ . Numerical experiments on two quantum many-body tasks corroborate these theoretical results, demonstrating the high scalability of the GLQK. Beyond the polynomial setting, we further show that it can efficiently learn certain non-polynomial functions. Our framework establishes new avenues for utilizing experimental data to advance the understanding of quantum many-body physics.

Figures & tables

Figure 1: Overview of our ML framework and its mechanism. (Top) Our ML framework comprises the quantum experiment phase and the classical learning phase. In the quantum experiment phase, quantum data

\rho_{i}^{\otimes T}

is prepared on quantum hardware (e.g., digital quantum computers, analog quantum simulators) and then measured in several bases. This process extracts quantum features

S_{T}(\rho_{i})

, which record the measurement bases and outcomes. In the subsequent learning phase, the extracted quantum features are learned on a classical computer. In this work, we propose the GLQK to leverage the ECP of quantum data, thereby enhancing learning efficiency. Specifically, the GLQK is calculated from the quantum features by incorporating local quantum kernels

k_{A}

on subsystems of size

\mathcal{O}(\xi)

into a polynomial

f

. Based on the calculated kernel functions, we optimize the kernel model

h_{\bm{\alpha}}(S_{T}(\rho))

to approximate

g(\rho)

. Hyperparameters (e.g., subsystem size, kernel exponent) can be tuned adaptively for a given data distribution using a validation dataset, without requiring additional quantum computational resources, providing a flexible learning framework. (Bottom) The validity of the GLQK is guaranteed by the ECP, which enables the approximation of the polynomial

g(\rho)

by an alternative polynomial

g_{\rm CA}(\rho)

in local features. Given the kernel construction, the GLQK can represent

g_{\rm CA}(\rho)

as a linear function within its feature space, which is composed of polynomials in local features, thereby enabling efficient learning.

	Trans. sym.	Training ( $N_{z}$ )	Validation ( $N_{v}$ )	Shadow ( $T$ )
Shadow kernel	No	$\tilde{\mathcal{O}}(n^{mp}/\epsilon^{4})$	$\tilde{\mathcal{O}}(\log(\|\mathcal{P}\|)/\epsilon^{2})$	$\mathcal{O}(1/\epsilon^{2})$
GLQK	No	$\tilde{\mathcal{O}}(n^{\alpha_{g}}\xi^{mpD}/\epsilon^{4})$	$\tilde{\mathcal{O}}(\log(\|\mathcal{P}\|)/\epsilon^{2})$	$\mathcal{O}(1/\epsilon^{2})$
Shadow kernel	Yes	$\tilde{\mathcal{O}}(n^{mp-\beta_{g}}/\epsilon^{4})$	$\tilde{\mathcal{O}}(\log(\|\mathcal{P}\|)/\epsilon^{2})$	$\mathcal{O}(1/\epsilon^{2})$
GLQK	Yes	$\tilde{\mathcal{O}}(\xi^{mpD}/\epsilon^{4})$	$\tilde{\mathcal{O}}(\log(\|\mathcal{P}\|)/\epsilon^{2})$	$\mathcal{O}(1/\epsilon^{2})$

Table 1: Learning costs for shadow kernel [ 15 ] and GLQK. The task here is to learn an unknown

m

-body, degree-

p

polynomial

g(\rho)

in an

n

-qubit quantum state

\rho

with correlation length bounded by

\xi

on a

D

-dimensional hypercubic lattice. The table shows the scaling of the sufficient number of training and validation data points

N_{z}

and

N_{v}

, and shadow size

T

with respect to the system size

n

, correlation length

\xi

, error

\epsilon

, failure probability

\delta

, and the number of candidate hyperparameter values

|\mathcal{P}|

, with and without translation symmetry of quantum data. This scaling assumes that the weight

m

, degree

p

, norm

g_{1}

, and upper bound

C

of the target polynomial are fixed. The quantity

\alpha_{g}(\leq mp)

represents the local-cover number of

g

, characterizing the minimum number of local subsystems required to encompass the support of each term of

g

. The quantity

\beta_{g}(p\leq\beta_{g}\leq mp)

denotes the local-factor count of

g

, characterizing the number of local factors when each term of

g

is decomposed into the product of local expectation values. These quantities take small values when

g(\rho)

is local relative to

\mathcal{O}(\xi)

. For instance, if

g(\rho)

is a sum of local linear/nonlinear quantities (e.g., local Hamiltonian, local purity, local entanglement entropy),

\alpha_{g}=1

and

\beta_{g}=p

. See Eqs. ( 18 ) and ( 21 ) in Sec. IV.1 for the detailed definitions of

\alpha_{g}

and

\beta_{g}

. The tilde in

\tilde{\mathcal{O}}(\cdot)

hides logarithmic factors in

\delta

Figure 2: An example of cluster approximation. Here, we consider

g(\rho)=\braket{P}\braket{Q}

, where

P

and

Q

are Pauli strings acting on qubits denoted as yellow and green circles, respectively. The weight

m

and degree

p

of this polynomial are

6

and

2

, respectively, since the number of qubits on which

P

and

Q

act is bounded by six, and

g(\rho)

is the product of two quantum expectation values. The cluster approximation decomposes the support of each Pauli string into clusters by grouping qubits within a distance

\Delta

and partitioning qubits separated by distances greater than

\Delta

into distinct clusters. Based on this decomposition, we define

P_{1},P_{2},P_{3},Q_{1}

, and

Q_{2}

as Pauli strings acting on each cluster such that

P=P_{1}\otimes P_{2}\otimes P_{3}

and

Q=Q_{1}\otimes Q_{2}

. The

\Delta

-cluster approximation of

g(\rho)

is given by

g_{\rm CA}(\rho)=\braket{P_{1}}\braket{P_{2}}\braket{P_{3}}\braket{Q_{1}}\braket{Q_{2}}

. The local-cover number

\alpha_{g}

is defined as the minimum number of local subsystems in

\mathcal{A}_{\rm GL}(\zeta)

required to encompass the support of all Pauli strings (i.e., the number of red boxes), and the local-factor count

\beta_{g}

is defined as the number of factors (i.e., degree) of

g_{\rm CA}(\rho)

. Then,

g_{\rm CA}(\rho)

is represented as the product of

\alpha_{g}=3

local linear/nonlinear quantities:

\braket{P_{1}}\braket{Q_{1}}

\braket{P_{2}}\braket{Q_{2}}

, and

\braket{P_{3}}

Figure 3: Numerical results of the regression task involving random quantum dynamics. Results are shown for (a) translationally symmetric and (b) general data distributions, comparing the shadow kernel (SK, orange squares) and GLQK (blue circles). The top panels show the coefficient of determination $R^{2}=1-\sum_{i=1}^{M}(y_{i}-f_{i})^{2}/\sum_{i=1}^{M}(y_{i}-\bar{y})^{2}$ , where $y_{i}=g(\rho_{i})$ and $f_{i}$ are the true and predicted values for the $i$ th test data $\rho_{i}$ , and $\bar{y}=\sum_{i=1}^{M}y_{i}/M$ . A larger $R^{2}$ indicates better accuracy, with $R^{2}=1$ denoting perfect prediction. Data points represent the mean value of $R^{2}$ across 10 randomly sampled training and test datasets, and error bars represent the corresponding standard deviation. The bottom panels display scatter plots for $n=80$ . The horizontal and vertical axes represent the true and predicted values of $g(\rho_{i})$ , respectively. The green shaded areas depict $[\sum_{i=1}^{M}(g(\rho_{i})-g(\sigma_{i}))^{2}/M]^{1/2}$ , the statistical error originating from the finite shadow size $T$ , independent of the kernel ridge regression. Here, $\sigma_{i}$ is the density matrix estimated from the classical shadow for test data $\rho_{i}$ . The number of training data points is $N$ , and the shadow size is fixed at $T=500$ .

Figure 4: Numerical results of quantum phase recognition. (a) The support vector machine classifies data points using a hyperplane within the feature space. (b) Topological order parameter defined on a local subsystem

I

of size

\mathcal{O}(\xi)

(see Sec. IV.6 for details). (c) Test accuracy for the shadow kernel (SK, orange squares) and the GLQK (blue circles) as the system size

n

varies. Data points represent the mean value of test accuracy across 10 randomly sampled training and test datasets, and error bars represent the corresponding standard deviation. (d)–(e) Kernel PCA results obtained with the shadow kernel and the GLQK for 500 data points at

n=80

. In (e), we set

\kappa=1

and

\zeta=2

. The number of training data is denoted by

N

, and the shadow size is fixed at

T=500

Figure S1: Translation of Pauli strings. The left and right panels illustrate the

D=1

and

2

cases, respectively. Given a Pauli string

P

and a local subsystem

A^{\ast}

, we translate

P

A^{\ast}(P)

such that

\operatorname{supp}(A^{\ast}(P))\subseteq A^{\ast}

and

\operatorname{supp}(A^{\ast}(P))

touches the left side of

A^{\ast}

(the left and bottom sides of

A^{\ast}

) for

D=1

(

D=2

Figure S2: Regression performance as a function of the shadow size

T

. Panels (a)–(c) show the regression accuracy

R^{2}

as a function of the shadow size

T

, while panels (d)–(f) show log-log plots of the regression error

1-R^{2}

as a function of

T

. The black dotted lines in panels (d)–(f) indicate the reference scaling

1-R^{2}=1/T

for ease of comparison. Here,

N

denotes the number of training samples. Error bars indicate the standard deviation over 10 independently and randomly sampled training and test datasets.

Figure S3: Regression accuracy

R^{2}

as a function of the system size

n

for various disorder strengths

w

. The number of training samples is

N=100

in (a) and (c), and

N=500

in (b). Error bars indicate the standard deviation over 10 independently and randomly sampled training and test datasets.

Quantum Machine Learning

Quantum machine learning uses quantum circuits and quantum data to build learning algorithms and study their computational and statistical limits.

See all 256 papers

Provable learning separation for predicting time-evolution of quantum many-body systems
Jul 7, 2026Rahul Bandyopadhyay, Riccardo Molteni, Jens Eisert +2Quantum Machine Learning Quantum Many-Body Physics
⟨aQaL⟩, Applied Quantum Algorithms, Leiden University, The Netherlands · Leiden Institute of Advanced Computer Science (LIACS), Leiden University, Einsteinweg 55, 2333 CC, Leiden, The Netherlands · Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany +2
Provable and scalable quantum Gaussian processes for quantum learning
Apr 30, 2026Jonas Jäger, Paolo Braccia, Pablo Bermejo +3Quantum Machine Learning Quantum Kernel Methods
Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA · Department of Computer Science and Institute of Applied Mathematics, University of British Columbia, Vancouver, V6T 1Z4 B.C., Canada · Stewart Blusson Quantum Matter Institute, Vancouver, V6T 1Z4 B.C., Canada +8
Learning ground state observables from quantum computing experiments
Jun 14, 2026Ben Jaderberg, Freya Shah, Minjun Jeon +3Quantum Machine Learning Quantum Many-Body Physics
IBM Quantum, IBM Research Europe, Hursley, Winchester, SO21 2JN, United Kingdom · Department of Engineering Science, University of Oxford, Parks Road, Oxford OX1 3PJ, United Kingdom · IBM Quantum, T. J. Watson Research Center, Yorktown Heights, NY 10598, USA +4

Jul 7, 2026J/K move · Enter open · S save

Provable learning separation for predicting time-evolution of quantum many-body systems

Rahul Bandyopadhyay, Riccardo Molteni, Jens Eisert, Vedran Dunjko+1

⟨aQaL⟩, Applied Quantum Algorithms, Leiden University, The Netherlands · Leiden Institute of Advanced Computer Science (LIACS), Leiden University, Einsteinweg 55, 2333 CC, Leiden, The Netherlands · Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany+2

Quantum Machine Learning Quantum Many-Body Physics

Open paper AskPDF arXiv

Given that quantum computers are naturally suited to simulate the behavior of quantum many-body systems, an immediate question arises: can one formulate physically motivated quantum machine learning (QML) tasks that exhibit learning separations? We address this problem by studying the learnability of quantum many-body dynamics from the perspective of probably approximately correct (PAC)-learning. Concretely, we devise a supervised learning problem where the training set consists of specifications of randomized stabilizer probe states, evolution times sampled uniformly from a polynomially large time interval

[0,T]

, coupled with expectation values of certain observables evaluated on the resulting time-evolved state under an unknown Hamiltonian. For this learning task, we provide an efficient quantum procedure whose training phase learns the underlying Hamiltonian from short-time training samples, and whose deployment phase combines Hamiltonian simulation with the classical shadows protocol to perform inference on a newly given data point. By contrast, the existence of

O(\mathsf{poly}(n))

-time instances ensures classical hardness: by embedding a

\mathsf{BQP}

-complete computation into the polynomially long time-dynamics of a low-intersection variant of the Feynman-Kitaev clock Hamiltonian construction, we show that, for a certain family of input distributions, no randomized classical polynomial-time algorithm can fulfill our learning condition, unless

\mathsf{BQP}\subseteq\mathsf{P/poly}

. Furthermore, we show that the classically hard instance maintains quantum learnability. We also give an interpretation of our results in learning-assisted certified quantum simulation. Taken together, our results demonstrate a rigorous learning separation for a natural ML task based on Hamiltonian evolution, while building connections between quantum learning theory, quantum simulation, and QML.

Abstract

Quantum Machine Learning

Explore similar work

Provable learning separation for predicting time-evolution of quantum many-body systems

Provable and scalable quantum Gaussian processes for quantum learning

Learning ground state observables from quantum computing experiments