Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Natsuto Isogai; Satoshi Yoshida; Mio Murao

quant-phSep 29, 2026

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Authors: Natsuto Isogai, Satoshi Yoshida, Mio Murao

Organizations: Department of Physics, Graduate School of Science, The University of Tokyo, Tokyo, Japan

Abstract

Whether quantum computation can reduce the amount of data sampled from an unknown probability distribution required to learn a prediction rule is a fundamental question in quantum machine learning. Quantum PAC learning studies this question using quantum data as a quantum state whose squared amplitudes encode the unknown distribution from which classical learning data are sampled. With only copies of such quantum data, the optimal worst-case sample complexity asymptotically matches that of classical PAC learning. In contrast, access to both a state-preparation unitary for this state and its inverse can improve the query-complexity dependence on the accuracy parameter in realizable learning. However, it has remained unclear whether forward-only access allows such an improvement. In this work, taking the worst case over compatible state-preparation unitaries and their finite ambient dimensions, we show that the optimal forward-only query complexities of realizable and agnostic learning are, respectively, $Θ((d+\log(1/δ))/\varepsilon)$ and $Θ((d+\log(1/δ))/\varepsilon^2)$ , where $d$ is the VC dimension of the concept class, $\varepsilon$ the accuracy parameter, and $δ$ the failure probability. These bounds match the optimal sample complexities with classical data or quantum data copies. To prove them, we establish a reduction using $q$ copies of the prepared state to approximate the Haar-averaged output of any $q$ -query forward-only algorithm. These results show that forward-only access cannot provide an asymptotic query-complexity advantage over learning from classical data or quantum data copies in this worst-case setting, and establish the essential role of inverse access in the known realizable-setting improvement. Our reduction also provides a new framework for analyzing limitations of forward state-preparation access via state-copy lower bounds.

Figures & tables

Setting	Oracle	Upper bound	Lower bound	Reference
Realizable	$\mathrm{PEX}$	$O\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon}\right)$	$\Omega\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon}\right)$	[ 25 , 26 , 23 ]
	$\mathrm{QPEX}$	$O\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon}\right)$	$\Omega\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon}\right)$	[ 14 ]
	$U$	$O\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon}\right)$	$\Omega\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon}\right)$	Theorem 4.1
	$U,\ U^{\dagger}$	$O\!\left(\dfrac{(d+\log(1/\delta))\log^{9}(1/\varepsilon)}{\sqrt{\varepsilon}}\right)$	$\Omega(d/\sqrt{\varepsilon})$	[ 16 ]
Agnostic	$\mathrm{AEX}$	$O\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon^{2}}\right)$	$\Omega\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon^{2}}\right)$	[ 24 , 27 ]
	$\mathrm{QAEX}$	$O\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon^{2}}\right)$	$\Omega\!\left(\dfrac{d+\log(1/\delta)}{\varepsilon^{2}}\right)$	[ 14 ]

Table 1: PAC learning complexity in each access model. Let

d=\operatorname{VCdim}(\mathcal{C})

. For the sample-access and forward-only bounds, the realizable setting assumes

d\geq 2

0<\varepsilon\leq 1/32

, and

0<\delta\leq 1/4

, and the agnostic setting assumes

d\geq 1

0<\varepsilon\leq 1/16

, and

0<\delta\leq 1/4

. The forward-only lower bounds take the worst case over permitted ambient dimensions and compatible unitary completions. Bold entries indicate the new lower bounds established in this paper.

Explore similar work

Jun 10, 2026quant-ph

Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning

A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, the expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. In this work, we develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits. For the class

S_{n,G}

n

-qubit pure states preparable with at most

G

two-qubit gates, a metric-entropy argument gives the realizable sample law

\widetildeΘ(G/ε^2)

in the circuit-limited regime. For an arbitrary source

\hatρ

, we introduce the best

G

-gate approximation error

d_G(\hatρ)

and the approximate circuit complexity

C_η(\hatρ)

. We prove an agnostic quantum Occam theorem: with

M

copies, one can learn up to the best

G

-gate approximation error plus a statistical penalty

\widetilde{O}(\sqrt{G/M})

. We then remove the need to know

G

in advance through an adaptive model-selection theorem whose oracle inequality selects the circuit complexity justified by the data. Matching lower bounds yield a sample-supported expressibility law: at trace-distance accuracy

ε

M

samples can support only

G_{\rm supported} \simeq Mε^2

gates, up to logarithmic factors and tomography saturation at

2^n

. Thus, the circuit complexity becomes an adaptive statistical resource rather than a static promise. Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.

Jeongho Bang, Kyoungho Cho, Jeongwoo Jae

Institute for Convergence Research and Education in Advanced Technology, Yonsei University, Seoul 03722, Republic of Korea · Department of Quantum Information, Yonsei University, Incheon 21983, Republic of Korea · Department of Statistics and Data Science, Yonsei University, Seoul 03722, Republic of Korea +1

Quantum Learning Quantum Machine Learning Quantum Circuits Model Selection Expressivity

Ask PDF

Aug 12, 2026quant-ph

A Quantum/Classical Example Oracle Separation for Making Things Up

Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.

Kenny Chen

The University of Sydney

Quantum Learning Quantum Processor First Order Oracle Complexity Oracles Separation

Ask PDF

Jul 7, 2026quant-ph

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

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.

Rahul Bandyopadhyay, Riccardo Molteni, Jens Eisert +2

⟨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 Learning Quantum Machine Learning Many-Body Physics Learnability

Ask PDF