Quantum machine learning advantages beyond hardness of evaluation
Authors: Riccardo Molteni
Simon Callum Marshall
Vedran Dunjko
Venue: ICLR 2026 Poster (2026)
Keywords: Quantum machine learning
Quantum-classical learning separations
Learning theory
Primary area: learning theory
TL;DR: We establish a quantum-classical separation in supervised learning for identifying the target labeling function, without the need for direct evaluation, when the target function is quantum.

Abstract: Recent years have seen rigorous proofs of quantum advantages in machine learning, particularly when data is labeled by cryptographic or inherently quantum functions. These results typically rely on the infeasibility of classical polynomial-sized circuits to evaluate the true labeling function. While broad in scope, these results however reveal little about advantages stemming from the actual learning process itself. This motivates the study of the so-called identification task, where the goal is to ``just'' identify the labeling function behind a dataset, making the learning step the only possible source of advantage. The identification task also has natural applications, which we discuss. Yet, such identification advantages remain poorly understood. So far they have only been proven in cryptographic settings by leveraging random-generatability, the ability to efficiently generate labeled data. However, for quantum functions this property is conjectured not to hold, leaving identification advantages unexplored. In this work, we provide the first proofs of identification learning advantages for quantum functions under complexity-theoretic assumptions. Our main result relies on a new proof strategy, allowing us to show that for a broad class of quantum identification tasks there exists an exponential quantum advantage unless BQP is in a low level of the polynomial hierarchy. Along the way we prove a number of more technical results including the aforementioned conjecture that quantum functions are not random generatable (subject to plausible complexity-theoretic assumptions), which shows a new proof strategy was necessary. These findings suggest that for many quantum-related learning tasks, the entire learning process—not just final evaluation—gains significant advantages from quantum computation

Published as a conference paper at ICLR 2026
QUANTUM MACHINE LEARNING ADVANTAGES BEYOND HARDNESS OF EVALUATION
Riccardo Molteni*:1.2 Simon C. Marshall Vedran Dunjko'
1 (aQa") Applied Quantum Algorithms, Universiteit Leiden
2 LIACS, Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, Netherlands momleeniee liacs. leidenuniv.nl
ABSTRACT
Recent years have seen rigorous proofs of quantum advantages in machine learning, particularly when data is labeled by cryptographic or inherently quantum functions. These results typically rely on the infeasibility of classical polynomial-sized circuits to evaluate the true labeling function. While broad in scope, these results however reveal little about advantages stemming from the actual learning process itself. This motivates the study of the so-called identification task, where the goal is to "just" identify the labeling function behind a dataset, making the learning step the only possible source of advantage. The identification task also has natural applications, which we discuss. Yet, such identification advantages remain poorly understood. So far they have only been proven in cryptographic settings by leveraging random- generatability, the ability to efficiently generate labeled data. However, for quantum functions this property is conjectured not to hold, leaving identification advantages unexplored. In this work, we provide the first proofs of identification learning advantages for quantum functions under complexity-hheoretic -theoretic assumptions. Our main result relies on a new proof strategy. allowing us to show that for a broad class of quantum identification tasks there exists an exponential quantum advantage unless BQP is in a low level of the polynomial hierarchy. Along the way we prove a number of more technical results including the aforementioned conjecture that quantum functions are not random generatable (subject to plausible complexity- theoretic assumptions), which shows a new proof strategy was necessary. These findings suggest that for many quantum-related learning tasks, the entire learning process not just final evaluation gains significant advantages from quantum computation.
INTRODUCTION
central question in quantum machine learning (QML) is understanding which learning problems inherently require quantum computer for efficient solutions. As shown in (Huang et al.) [021). access to data enables classical learners to efficiently evaluate some hard-to-compute functions that are otherwise intractable for polynomial time classical randomized algorithms. Most of the known examples of learning problems where data does not aid in computing the target function involve cryptographic functions, for which random labeled samples can be generated efficiently using classical algorithms. While the proofs may be more involved, the intuition remains simple: if classical machine could generate the data, then the data itself cannot be what makes hard problem easy. In the context of QML, where the greatest advantages are intuitively expected for "fully quantum" functions (i.e., functions that are BQP-complete the focus on cryptographic tasks was somewhat unsatisfactory. This limitation was addressed in (Gyurik & Dunjko, 2023) by employing stronger computational complexity assumptions and, crucially, by leveraging the fact that standard learning definitions require the learned model to evaluate new data points.
However, different learning condition could be considered where the learning algorithm is solely required to identify the target labeling function from a set of labeled data. In other words, we
Moore precisely, the class BQP does not contain complete problems. Throughout this paper, whenever refer complete problems, we will instead consider the class PromiseBQP.

---

Published as a conference paper at ICLR 2026
consider supervised learning problems where the learner receives labeled examples (x,, fx)) and it is required to output a description of a consistent f. up to PAC error. In this scenario, the classical learner would only need to recover the description of the unknown target function, without needing to also evaluate it on new input points. From a fundamental standpoint, analyzing the hardness of the identification task in learning problems involving quantum functions helps clarify the source of learning separations. From a practical viewpoint, particularly in expected applications of quantum machine learning, identifying the data-generating function can in fact be the primary goal, such as in Hamiltonian learning or in tasks related to finding order parameters (Gyurik & Dunjko, 2023), as we will comment in Appendix G Crucially, as was proved in (Gyurik & [ separations for the identification problem cannot exist without assumptions on the hypothesis class (intuitively, the classical learner can always outputs the circuit for the whole quantum learner with hardwired data as the output). The main goal of this paper is then to determine the conditions under which a learning separation for fully quantum functions can already emerge from the identification step.
Classical hardness of the identification problem has already been established for certain learning tasks, such as the learnability of DNF formulas (Kearns & Vazirani 1994) and cryptographic functions (Gyurik & Dunjko| 2023 Jerbi et al., 2024). The key components in these hardness proofs are: (1) the existence of a succinct representation of the target function that enables efficient extraction of the relevant property, and (2) the property of "random generatability". In this paper, we use the term "random generatability" to refer to the ability to efficiently generate labeled samples (a, ((x)) for random inputs r. We also refer to the characteristic functions of BQP languages as "quantum functiinn" (informally, these are functions whose values can be estimated efficiently by a quantum circuit, but not by any classical algorithm, see Def. TTP. In Appendix G we list a series of practical scenarios where quantum functions naturally arise. Crucially, for learning tasks involving quantum functions, we cannot rely on a simple representation of the target function, and we also show that these functions are not randomly generatable. Consequently, our hardness result for the identification task requires a fundamentally different proof strategy from those used in prior works. We discuss this in more detail in Appendix A The main contributions of the paper the following.
1. We show that quantum functions are not random generatable unless BQP is in the second level of the polynomial hierarchy. This result has consequences on quantum generative modelling well, see Corollary 2
2. We introduce the task of veriffableidentiffattiin where the algorithm must reject in- valid datasets, and solve identification correctly otherwise, and prove classical verifiable- identification for quantum target function is impossible, unless BQP is in BPPNP
3. We identify sufficient conditions on learning algorithm and concept class such that "mere" classical identification implies approximate-verfiatl reject datasets unless most of the samples are labeled according to the same concept) within the polynomial hierarchy. This implies identification is classically intractable unless BQP is in BPpN (two levels "up" in the hierarchy compared to the verifiable case in the point above).
identification (the algorithm must
4. We provide examples of physically motivated learning tasks that satisfy the above condition and for which there exists a quantum learning algorithm that solves the identification task, thereby yielding formal quantum-classical separation (see Corollary I
The relationship between our proofs illustrated in Figure 1 in Section 5 We note that the results in the main text are presented under the heuristic form of the complexity-theoree since our analysis follows a distribution specific scenario. In Appendix C we describe how classical
assumptions,
hardness can be obtained under the exact assumption BQP g BPP in the case learnability is required under every distribution.
2
PRELIMINARIES
We now provide here the precise definitions of the two tasks we are addressing in this work. Ap- pendix [B provides the definitions of quantum functions and the complexity-theom thhorrtic background relevant hardness results, along with a glossary of the most frequently used symbols in Table 1
2

---

Published as a conference paper at ICLR 2026
2.1 DEFINITION OF RANDOM GENERATABILITY
Given a uniform family of functions f = (n JnNN, with fn {0, - {0,1], we say that f is "random-generable" under a distribution D if there exists a uniform (randomized) algorithm capable of producing samples (a, (x)) with x sampled from D efficiently for any The concept of functions that permit an efficient procedure to generate random samples (z, f(x)) was introduced in (Arrighi & Salvail 2006) under the term "random verifiability". In this paper, we refer to the same property as "random generatability" to avoid potential confusion with the "verifiable case" of the identification task described in Def. 7 Specifically, we consider two cases: exact random generatability in Def. [] where the algorithm is not allowed to make any errors, and approximate random generatability in Def. where the algorithm outputs samples from distribution only close to the true target distribution.
Definition 1 (Exact random generatabilityy) Let f = (Jn Jne be uniform family of functions P with fn= : {0, 11th + {0, 1). f is exact random generatable under the input distribution D if there exists an efficient uniform (randomized) algorithm Ap such that given input description of fn for any n and a random string r is such that with probability I:
AD(fn, r) (Ir, fn(2z))
(I)
When r is chosen uniformly at random from the set of all random strings with length polynomial in n, then (3r, Jn (x ~ x/ (D), where (D) samples x from the target distribution D over x: E {0, 1)
and assigns the corresponding label (2,) E {0,
Definition 2 (Approximate random generatability). Let f = {fa)EE be a uniform family of functions, with fn : f0, 1}" {0, 1). is approximately random generatable under the distribution DD if there exists an efficient uniform (randomized) algorithm Ap such that given as input a description of fa for any n, random string and an error value outputs:
AD(fn 0 .r) (zr, (zx))
(2)
with (Iy. (m(z)) ~ (D) when r is sampled uniformly at random from the distribution of all the random strings (with polynomial size). In particular, o/ (D) is probability distribution over {0, 13" x {0, 13 which satisfies: || (D) - x² (D)llrv $ e, where nt (D) is the same distribution defined in Def.
As the total variation distance between two distributions p and g over x E {0, 13" is defined as gly-gl = 1/2 E. [p(z) - q(x)), the algorithm A in Def. is allowed to make mistakes both with respect to the probability distribution of the outputted æs (c.g. they may not be generated from the uniform distribution) and with respect to the assigned labels.
2.2 PAC FRAMEWORK
The results in this paper are expressed in the standard terms of the efficient probably approximately correct (PAC) learning framework (Kearns & Vazirani 1994; Mohri 2018). In the case of supervised learning, a learning problem in the PAC framework is defined by a concept class F = {Fal )ne,, where each F,, is a of concepts, which are functions from some input space Xx, (in this paper we assume Xr is a subset of {0, 13"h ) to some label set Vn (in this paper we assume Vn, is (0, 1}. unless stated otherwise). The learning algorithm receives on input samples of the target concepts T == {ZTee f (xx))),, where Xe E Xn are drawn according to largel distributions D {Dn}neN- Finally, the learning algorithm has a hypothesis class H. ] associated to it, and the learning algorithm should output a hypothesis h E H., which is another function from Xr to Dr-- that is in some sense "close" (see Eq. (3) below) to the concept E Fn, generating the samples in T.
Definition (Efficient probably approximately correct Icarnability). A concept class F = (Fr is efficiently PAC learnable under target distributions D = {Dn) bee if there exists hypothesis class H. = (H ) new and a (randomized) learning algorithm L with the following property: for every E F.. and for all 0 < < 1/2 and < 8 < 1/2, if L receives in input training set T of size greater than M E (ppoly(n)), then with probability at least - 5 over the random samples in T
Committing slight abuse of notation, we will use fa to denote both the function itself and its description.
3

---

Published as a conference paper at ICLR 2026
and over the internal randomization of C, the learning algorithm & outputs specification of some E Hn that satisfies:
Pra.D.. [M(x) * [(a)) S.
Moreover, the learning algorithm & must run in time (ppol((n, 1/8). the learning algorithm runs in classical (or quantum) polynomial time, and the hypothesis functions can be evaluated efficiently on a classical (or quantum) computer, we refer to the concept class as classically learnable (or quantumly learnable, respectively).
In classical machine learning literature, hypothesis functions are generally assumed to be efficiently evaluable by classical algorithms, as the primary goal is to accurately label new data points. In this paper, however, focus on learning separations that arise from the inability of classical algorithm to identify the target concept that labels the data, rather than from the hardness of evaluating the concept itself. Therefore, for our purposes we consider hypothesis functions that may be computationally hard to evaluate classically. Specifically, we will consider target concept functions, as defined in Def. [0] that are related to (Promise) BQP complete languages. As discussed in (Gyurik & Dunjko 2023). obtaining learning separation for the identification problem in this case requires restricting the hypothesis class available to the classical learning algorithm. Otherwise, a classical learner can always outputs the circuit for the whole quantum learner with hardwired data as the output. A common approach is then to define the hypothesis class as exactly the same set of functions contained in the concept class that label the data. The classical learning algorithm will then have to correctly identify which is the concept, among the ones in the concept class, that labeled the data. As we will make clear later, the task is close variant of the PAC learning framework in Def. called proper PAC learning.
Definition 4 (Proper PAC learning (earns& & Vazirani 1994)). A concept class F (Fn Men is efficiently proper PAC learnable under the distribution D =, hneN if it satisfies the definition of PAC learnability given in Def. [3] with the additional requirement that the learning algorithm L uses a hypothesis class H identical to the concept class, i.e., H F.
We provide now the definition of the two types of concept classes considered in our main Theorem 10
c-distinct concept class In the first scenario, we require the concept class to consist of com-ceeee functions, as defined in Def. 10, that disagree on a sufficiently large fraction of inputs. More specifically, we define c-distinct concept class as follows.
Definition 5 (c-distinct concept class). Let F = {ffa 10, + (0.1) la E 13,11"M be concept class. We say F is c-distinct concept class if
Va1.02 a2 10, an # 02 ES c [0, |81/2" 2 s.t. E fo + (T) (4)
We note that in the case of concept classes containing PromiseBQP functions defined in Def. 13 for the definition of c-distinct concepts to be meaningful, we require that the set S is subset of the inputs specified in the promise. In the Appendix F.2] we provide an example of a 0.5-distinct concept class where the concepts are all (Promise) functions.
Average-case-smooth concept class We now consider concept classes where the label space is equipped with a metric such that two concepts are close under the PAC conditions, then their corresponding labels on and 02 are also close with respect to the metric the label space. We formalize this notion of closeness in the definition below.
Definition 6 (Average-case-smie smotsoo concept class). Let = (f : {0, + [0, a E {0, 13"3 be concept class. We say that F is : {0, 13 x {0, 13.m > RR+ defined over the labels a E {0, 11mm and a C 2 0 such that Van, 02 [0,
if there exists distance function
E Enw.Uit((,11)1 (x) (x) > C d(a),az).
(5)
'The hypotheses (and concepts) are specified according to some enumeration R UneN(0, 1 + Un (or, C,) and by "specification of E Hr we mean string E {0, 1)" such that R(a) h (see (Kearns) & Vazirani 1994) for more details).
4

---

Published as a conference paper at ICLR 2026
We note that in machine learning, it is often the case that closeness of functions in parameter space implies closeness in the PAC sense. However, in Def. 6 we require the reverse: that closeness at the function level implies closeness in parameter space. Nevertheless, in the Appendix F22 we provide an example of an average-case-smoothi concept class of quantum implementable functions.
2.3 DEFINITIONS OF THE IDENTIFICATION TASKS
Imagine we are given a machine learning task defined by a concept class F composed of 2n target functions f E F, each one specified by a vector alpha E {0, 1)ThM with m scaling polynomially with input size n. Formally, that means that there exists a function e S [ {0, 1 - J which is bijective and such that e(a) = o E F. By abuse of notation, in this paper we often use to refer to e(a) when it is clear from the context that we mean the function fa; rather than the vector E {0, 1).m. Given training set of inputs labeled by one of these concepts, the goal of the identification learning algorithm is to "recognize" the target concept which labeled the data and output the corresponding a. We address two closely related but subtly different versions of identification tasks, for which we provide precise definitions below. In the first one, we assume the learning algorithm can decide if dataset is invalid, i.e. if it is consistent with any of the concepts in the concept class. In particular, we adopt the notion of consistency as defined in Definition of (Kearns& & Vazirani 1994) and regard a dataset as valid if every point is labeled in accordance with a concept. In Appendix [.44] we explain that this version of the task is closely related to the learning framework of the so-called consistency model found in the literature (Kearns & Vazirani
1994 Mohri 2018, [Schapire 1990).
Definition 7 (Identification task verifiable case). Let F= (z)()) e (0,1) | a E {0, 13mh be concept class] A verifiable identification algorithm is (randomized) algorithm Ag such that when given as input a set T = {(re, 1 of at least B pairs (x,y) E {0, x {0, 1], an error parameter 0 and random string E R, it satisfies:
If E {0, 13 such that yr- (xx)) holds for all (ate, 31) E T, then Ap outputs "imvalid dataset".
If the samples in T' come from the distribution D. i.c. ze ~ D, and there exists an
a E (0. 13th such that ye f" (xz) E {0, holds for all (IZ, ve) E T = {(x2, ve
then with probability 8 outputs:
An(T,e,r) = a, a {0,11)
(6)
satisfying -o)
We say that Ag solves the identification task for a concept class F under the input distribu- tion D if the algorithm works for any values of c, 2 0. The success probability 1 5 is over the training sets where the input points are sampled from the distribution D and the internal randomization of the algorithm. The required minimum size B of the input T scales as poly(n,1/e../66) while the running time of the algorithm scales as poly(B, m).
It will be instructive to think about the algorithm Ag as a mapping that, once e and r are fixed, takes datasets T C {(x, y) x E {0. 13". E 1), with (T) 2 B, and outputs labels E {0, 1)m The verifiability condition will play a crucial role in our hardness result for the verifiable case of the identification task. Nevertheless, in our main hardness result, we will show how to relax the verifiability condition on the learning algorithm and provide hardness result for the existence of a proper PAC learner algorithm which does not reject any input dataset but satisfies the following additional assumptions. We call such learning algorithm an approximate-corres identification algorithm.
Definition 8 (Identification task non verifiable case ). Fet {0, 13m} be a concept class. An approximate-correct identification algorithm a (randomized) algorithm Ag such that when given as input a set T = {(1,, ) of at least B pairs (z, v) E
10. - (0, a
Moore precisely, the algorithm is allowed to output any ā which is close in PAC condition with See Def. and 8
Here and throughout the paper. we assume that the concepts are labeled by a vector a in (0, 17mh. However, it is not required that spans the entire set of bitstrings in {0, 1) 1 The key requirement is that m is sufficiently
large to ensure that every concept in the concept class can be assigned a unique vector in {0, 1)"
5

---

Published as a conference paper at ICLR 2026
{0, 1)"h x 10, an error parameter 0 and random string R. satisfies the definition of proper PAC learner (see Def. [4 along with the following additional properties:
1. If for any a all the (mg, Me) T such that ve for all $ and all r R:
f (xre) then there exists an 61 such that
(T r.. *
In other words, the algorithm will never output totally incorrect a, i.c. inconsistent with all the inputs in the dataset.
2. If = (2x, we) E is composed of different inputs xy and if there exists an a such that yr = (xx) for all (r) E T, then there exists a threshold e2 such that for any 62 there exists at least one E R for which:
e2) = a2
(8)
With the condition: Un-t (0.1)") (z)
Therefore, the dataset is fully consistent with one of the concept a, then there at least one random string for which the identification algorithm will output ā closer than 3 in PAC condition to the true labelling a.
We say that As solves the identification task for concept class F under the input distribution D if the algorithm works for any value of e, 5 2 0. The required minimum size B of the input set T' is assumed to scale poly(n.1/e.1/0 while the running time of the algorithm scales as poly(B, n)). Moreover, the and required values scale at most inverse polynomially with n.
Appendix H examines the two assumptions made about the approximately correct algorithm and presents concept class where just standard proper PAC learner meets both conditions.
3 HARDNESS RESULTS FOR RANDOM GENERATABILITY OF QUANTUM FUNCTIONS
We now show our results on the hardness of random generability of quantum functions based on the assumptions that BQP is not contained in the second level of the PH, in case of approximate random generability, heuristically decided within HeurBPP by an efficient classical machine with a NP oracle. Classical hardness for exact random generatability of quantum functions also based on different complexity-therreeee theoretic assumption, i.e. BPP SPP/sand /smmp BQP & BPP (we refer to Appendix B and the works in Marshall al. (2024); Huang al. (2021) for the precise definition of the class BPP Ppp/ssmp80P but roughly speaking, this class requires the sample generator to be polynomial-tin quantum computer). For completeness, we also prove this latter result in the Appendix(1 D
be proved
In words, Theorem and 2 state that are labeled by BQP function f. then even classically generating random correctly labeled examples (æ, fx)) is hard. It is important to note that, in general, the hardness of computing function does not imply the hardness of generating random labeled samples from it. For instance, while computing the discrete logarithm modulo a large prime is believed to be classically intractable, is nevertheless possible to efficienlly generate evaluations of this function uniformly random inputs classically. In this sense, our result does not follow trivially from the classical intractability of the target quantum functions.
Theorem (Exact Random generatability implies BQP C PNP). [et (Jn be a family of BQP functions as in Def. 10 If there exists a classical randomized poly-time uniform algorithm that generates samples (z, fu fx(x) correctly with probability in Defl] with x Unif 1)"), then
PNP contains BQP.
Proof sketch. The whole proof can be found in the Appendix D.2.1 here we give the main idea.
Suppose there exists algorithm A which satisfies Def. [or a BQP family of function f and for the uniform distribution over the inputs x E (0, 1)" For a fixed function fn (0, 1)" + (0, 1}. the algorithm A maps a random string r E {0, (ppoly(n) to tuple of fn(x)), ie.. A(fm..) {0, 1 p)ly((()) + {o, 1]" x (0, 13. Then, in order to prove Theorem we construct an algorithm A'' which can decide the BQP language associated to fa by using A and NP oracle. Such algorithm

---

Published as a conference paper at ICLR 2026
A' will essentially invert A on given input 2,. to find a corresponding valid random string F and then computes (z++) using A(fn: F). Specifically, by using the NP oracle, AA' can find the random string i associated to 2, for which A(f (zz, fn (z+)) in polynomial time. Importantly, finding the string i can be achieved using an NP oracle since A operates in classical polynomial time, and thus it
can efficiently verify the correct string F. This concludes the proof as, by Def. [T] f correctly decides
an arbitrary BQP language and A' can evaluate any fn on every x by just running A(fn, O
In the next theorem, we allow the algorithm A to make mistakes both on the distribution followed by the outputted æ and we also allow errors on some of the outputted (z. (z))
Theorem 2 (Approximate Random generatability implies (BQP, Unif) E HeurBPpNP), Let f [JnJnen be family of BQP functions which is the characteristic function of a language L E BQP funnctioissiiicciiii
as in Def. TO, and let Unif be the uniform distribution over {0,1)", 1)", If there exists a polynomial time algorithm A which satisfies Def. for the uniform input distribution Unif, then (L, Unif) E HeurBPpNP
Proof sketch. The full proof can be found in Appendix D.2.2 here we outline the main idea. We present an algorithm A' E HeurBPpNP which can heuristically decide the language L with respect to the uniform distribution over the inputs, i.e. it satisfies Eq. (TO) for the input distribution D Unif. Let f = {fr hn be the family of functions associated to the BQP language as in Def. 10 The algorithm A' follows directly from the one described in the proof of Theorem [ For a fixed function fn and error parameter e, the algorithm A(Jn, 02/=, in Def. Def..2stt Still maps random strings E (0, 1)0ol((m) to tuples (Ir, (xx)) E {0, 13" x {0, 1). Then, on an input 27, A' still inverts the algorithm A in order to obtain random string F such that A(fn, 0'/,, .)) (æz, fx(x)). This time however, it samples multiple such random strings uniformly at random (this can be done in polynomial time using the result from Bellare et al. 20000). By doing so, can guarantee that taking the average of the corresponding fr (z ). obtained from A(fn, 0'//,
( (xxx) )) for different i. will correctly classify the input point Ty with high probability. More precisely, as stated in Def. 2 the algorithm A outputs samples (z, (x)) which follow distribution Le c-close in total variation with the exactly labeled, uniformly sampled over I E {0, 1 one. It follows (see full proof in the Appendix D.2.2) that the maximum fraction of point which A' may misclassify is upper bounded by a linear function of e.
Although this is tangential to our present discussion, in Appendix D.2.2 we present Corollary of the last theorem, which proves that certain class of quantum generative models called expectation value samplers (introduced in Romero & Aspuru- Guzik (202T), and proven universal in Barthe et al. (2024) and generalized in (Shen et al. (2024)) is classically intractable.
Additionally, our result exhibits family of distributions that is classically hard to approximate to within nontrivial error. Previous hardness results obtain strong conclusions under widely accepted, purely classical complexity assumptions, such as the non-collapse of PH. Under these widely accepted assumptions, these results rule out efficient classical algorithms for either exact Huang ct al. (222) simulation or approximation beyond an exponentially small additive error [Bolladd et al. (018); Movassagh (2019): Bouland et al. (2022). It is important to note that Huang et al. (2025) constructs, for each input size, single distribution from an explicit family that is provably hard to sample from, whereas Bouland et al. (2018) Movassagh (2019); Bouland et al. (2022) study conditional settings in which each input instance specifies a different output distribution. Our work instead relies on comparatively less explored assumption, namely that BQP is heuristically not contained in PH and, under this premise, we obtain a correspondingly stronger conclusion: no efficient classical algorithm can approximate the joint distribution (z. f()) for uniformly random x within pnvers-poolnoomee total variation distance e (similar to Huang et al. (2025). we construct one hard distribution per input size), whenever f is a BQP function.
HARDNESS RESULTS FOR THE VERIFIABLE IDENTIFICATION PROBLEM
We now address the second problem studied in this paper, specifically the hardness of the identification task defined in Def. 7
7

---

Published as a conference paper at ICLR 2026
Theorem 3 (Identification hardness for the verifiable case ). Let : (0.1) a {0, 1mm, m = poly(n)} be a concept class such that there exists a f E which is the characteristic function of language C BQP as in Def. 70, and let Unif be the uniform distribution over the I E {0, 1)". there exists a verifiable identification algorithm An for the uniform input distribution Unif given in Def. 7 then (c, Unif) HeurBPpNP.
Proof sketch. The full proof can be found the Appendix E.I here we outline the proof sketch. The core idea is to show that if there exists algorithm An that satisfies Def. 7 for the concept class F in the theorem, then there exists a polynomial time algorithm A'' which, using Ag and an NP oracle. takes as input any a E {0, 1)Th (which uniquely specifies concep and outputs dataset of B-many inputs labeled by a concept f in agreement with f under the PAC condition of Eq. 3 We recall here that, given error parameter and random string r, the algorithm As takes as input any set T of B pairs (æ. y) E {0, 1)" x {0, 1 and, if and only if the set is consistent with one of the target concepts a, outputs with high probability a E 10" close in PAC condition to a. Note that the crucial "if and only if" condition stems directly from the ability of A to detect invalid datasets, as described in Def. 7 which correctly classifies the L language associated to f Specifically, on any input E {0, 1}"" the algorithm A' first inverts AB on the target a in order to obtaín a dataset T = {(re, (t)) of B input points such that An An(T, dataset 7 such that Ag(T, input based on consistency with the training set II' generated in the previous step. By selecting an appropriate number of inputs B, it is possible to bound the probability that the dataset T is consistent with concept f heuristically close to the target f", thereby bounding the probability that the label assigned to x corresponds to (I)).
We can then leverage this to construct the algorithm A''
a. This is possible by using an NP oracle to search for at leveraging the efficiency of the algorithm Ag. then labels the
In Appendix A..4, we observe that the verifiable identification task effectively captures the consistency learning model commonly used in the literature. Another compelling reason to consider learning algorithms within the verifiable case is that quantum learners can verify whether a dataset is valid for a given Specifically, given an input dataset T, the quantum learning algorithm outputs the guessed a and then can check whether every point in the dataset are correctly labeled by f similar to the process for efficiently evaluable hypotheses. Assuming f is quantum evaluable, and the dataset is polynomial in size, the verification procedure runs in polynomial time. A following question is then whether in order verify dataset we necessarily need quantum computer for the BQP functions defined in Def. singleton concept c determining whether dataset is valid is possible if the concept can be evaluated in the class P/poly (see Def. 15 in Appendix B for a definition of P/poly).
Def.[TO] TO] We address this question in the following proposition, which asserts that for a
Proposition 1 (Hardness of verification singleton case). Let F = {f 10, + {0,1} be singleton concept class. If there exists an efficient algorithm Ag such that for every set T = { [[rg, (r)), with B polynomial in n, E 1). such that x; + x; V v E {1, B} and ye E (0,1), satisfies the following:
If ve) ET, yE # (ze). (T( outputs "invalid dataset".
Then there exists a polynomial time non-uniform algorithm which computes f(x) for every v. In particular, there exists algorithm in P/poly which computes f(x).
Proof. For every input size n, let us take as polynomial advice the B samples TB-1 {(x,, f(x))) B-1 for any sequence of different æe {0, 1]"h Then, on any input x E (0, 1)", the algorithm in P/ P/poly would run Ag on the dataset Tg {(x 0)) BTB- and decide based on the corresponding output of An-
We assume that each & provides an unambiguous specification of the concept f (possibly as a quantum circuit, i.c. that quantum circuit can, given o, evaluate fo in polynomial time). "A singleton concept class is concept class that consists of only one concept.
8

---

Published as a conference paper at ICLR 2026
We specify that require the inputs 2ς to be distinct in the training set T to strengthen the result in Proposition T Without this condition, the result would be trivial, as one could provide Ag with B identical copies of (a, 0) input and correctly decide each using polynomial uniform algorithm by simply examining the corresponding output. In case of exponentia--sized concept classes containing BQP function which uniquely labels set of polynomial number of inputs, the verifiability property of the identification algorithm can be used to prove that BQP is contained in the class P/ poly.
Theorem 4. =f
{0, 13 a (0, . poly(n)3 be a concept class such that there exists at least one function f E F that decides language L E BQP, and for which there exists a polynomial sized subset C {0,1]" such that f is uniquely determined by its labels on S. If there exists a verifiable identification algorithm Ag as given in Def. 7 then BQP S P/poly.
Proof. For every input size n, let us take as polynomial advice the samples from the subset S
which uniquely determine f and the corresponding labels, i.e. 7 = f (xx)) such that y/ = (xxr for every Fe E S. We then consider exactly that dataset as advice and we label any new input 2 E {0, 1)" selecting the y {0, 1} which keeps the dataset valid. More precisely, on any input z E {0, 1)", the algorithm in P/poly would run AB on the dataset T₂ = [xx UT$ and
label so that the algorithm AB accepts the dataset.
5 HARDNESS RESULT FOR THE NON-VERIFIABLE IDENTIFICATION PROBLEM
We now present the main result of our paper, which establishes hardness for the verifiaie identification task under the assumption that it is solvable by an approximately correct algorithm. The theorem states that, assuming BQP is not contained in low level of PH, then efficient classical learner can solve the identification problem for a broad class of concept classes. In particular, the result applies to concept classes that either include c-distinct concepts, as defined in Def. 8 with 2 3. or satisfy the average-case smoothness property given in Def.
Theorem 5 (Hardness of the identification task non verifiable case). Let == {0, 13 (0. 13
E {0, 1)"" be a concept class containing at least a BQP function f as in Def. TO associated to a language L E BQP. Assume further that F is either a c-distinct concept class with c e2 or an average-case cetogge-case-mmoeeee smooth concept class. If the non-verifiable identification task for F, as defined in Def. g is solvable by classicully efficient approximate-correc identificution algorithm
Ag. then it follows that (C, Unif)= HeurBppNp NOMP
Proof sketch. The proof can be found in the Appendix F The proof combines the intermediate result in Theorem I with the result Theorem 13 for the c-distinct concept classes or in Theorem 14 for average- cannge-case-smann mmoth concept classes. The intuition is the following. In Theorem 13 and Theorem 14] we show that for c-dinstict or serrage-case-mmolde concept classes the existence of an approximate- correct identification algorithm in Def. 8 allows for the construction of an identification algorithm in the first level of the PH which is able to reject any dataset which contains a fraction of inputs greater than not labeled by fa. Then in Theorem 11 we prove that if such an algorithm exists, then on given
invert it climbing up more layers in the PH in order obtain dataset of inputs mostly consistent with fa. Because each of these datasets will contain only a fraction of inputs incorrectly labeled, we can guarantee that the fraction of misclassified inputs can be made
polynomially small. Thus we can evaluate S in HeurBpp
A full scheme of the proof overview can be found in Figure
Finally, we show that there exists a concrete learning problem for which a quantum learner can successfully identify the unknown label function, while any efficient classical method would fail. In particular, in Appendix G.1 we provide an example of a natural c-distinct concept class with 2 4 which then satisfies the assumption of Theorem 10 and lead to the following final result.

---

Published as a conference paper at ICLR 2026
Hardiness the identification task
Verifable case Det. 7
Non verifiable case Del. (koorodimatlecoomo coniil--cccctccc algorthhn
Theorem concepts
Theorem average case concopts
Theoram
algorthm then BQP E HeurBPpph
Construct an approdmaae- Del.19
Theorem
If approsimate cornect sigonthr
HQP Heurtpp
Figure 1: An overview of our proof strategy for the identification task.
Corollary 1 (Informal, see Theorem [5 a formal version). There exists a natural learning problem involving quantum functions for which there exist a quantum learning advantage for the identification task (i.e. the target concepts are efficiently identifiahle on a quantum computer but not on classical computer) unless BQP is in the (Heuristic) polynomial hierarchy.
The proof, along with the specific instance of the learning task that demonstrates the advantage, is provided in Appendix G.I
DISCUSSION
In this paper, have demonstrated learning separations for the identification task in the case of quantum target functions. In the case concept classes consisting purely of quantum functions, provable quantum advantages in the PAC framework have far been established only the level of the evaluation step, i.e., when the learning algorithm is also required to efficiently evaluate the learned hypothesis. In this work, we instead analyze the hardness for classical algorithm identify a correct hypothesis within the given concept class itself (noting that, if no restriction is placed on the hypothesis class, a classical learner can always solve the task by outputting the circuit of the quantum learner with hardwired data, as shown in Gyurik & Dunjko (2023). In this sense, our results provide a first quantum classical separation for learning concept classes of quantum functions in the setting of proper PAC learning.
natural question is whether our results extend to existing, well-studied learning tasks. Ap- pendix G we examine in detail three scenarios where our results may be applicable. First, we show that our theorems directly apply to the task of learning observables introduced in (Molteni et al., 2024 for which learning separation had previously been established only at the evaluation stage and we outline a potential benchmark against a classical dequantized algorithm. We then consider two physically relevant tasks, such as Hamiltonian learning and learning the order parameter, that can naturally be formulated as identification problems. In one common formulation of Hamiltonian learning, one given access measurements on the Gibbs state of an unknown Hamiltonian fixed temperature and asked to recover the Hamiltonian. This can be cast as an identification problem by defining concept class whose elements are functions mapping measurement settings expectation values on the Gibbs state of the target Hamiltonian. In this sense, Hamiltonian learning is closely related to our identification task, although there are several important differences, which we spell out in Appendix G Importantly, since Hamiltonian learning is known to be classically solvable aalvable/Anshu Anshu et al. (2020); Haah et al. (2024), this suggests that the additional structural assumptions we impose on concept classes for our hardness theorems (c-distinctness average-case smoothness) are not easily relaxed. As a consequence of our results, a general hardness theorem for identification without such constraints, together with the classical tractability of Hamiltonian learning, would lead to unexpected consequences in complexity theory. We further elaborate on this, as well as on the connection to learning unknown order parameter, in Appendix G
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
The authors are thankful to Sofiene Jerbi for numerous discussions and suggestions to look into Reed-Solomon codes, and to Matthias Caro for discussions involving the packing numbers of certain quantum concept classes. This publication part of the project Divide & Quantum (with project number 1389. 20.221) of the research programme NWA-ORC which is (partly) financed by the Dutch Research Council (NWO). This work was also supported by the Dutch National Growth Fund (NGF), as part of the Quantum Delta NL programme. This work was also supported by the European Union's Horizon Europe program through the ERC CoG BeMAIQuantum (Grant No. 101124342).
REPRODUCIBILITY STATEMENT
This manuscript presents exclusively theoretical results. To ensure reproducibility, we provide fully detailed proofs of all theorems claimed in the main text, which are included in the Appendix. Additionally, key proof ideas are outlined within the main body of the paper for further clarity.
REFERENCES
Scott Aaronson. Bqp and the polynomial hierarchy. In Proceedings of the forty-second ACM symposium Theeory of computing, pp. 141-150, 2010.
Scott Aaronson. The equivalence of sampling and searching. Theory of Computing Systems, 55(2):
281-298, 2014.
Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forry-Third Annual ACM Symposium Theory of Computing, STOC 11, pp. 333 342, New York, NY, USA. 2011. Association for Computing Machinery. ISBN 45034599 doi: 10.1 145/1993636. 1993682. URL htt.hhtttt://oott org/10. 1 4 / 9939969369... 1993682
Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. Sample- efficient learning of quantum many-body systems. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pp. 685-691. IEEE, 2020.
Sanjeev Arora and Boaz Barak. Computational complexity: modern approach. Cambridge
University Press, 2009.
Pablo Arrighi and Louis Salvail. Blind quantum computation. International Journal of Quantum Information, 4(05):883-898, 2006.
Maria-Florina Balcan. Lecture notes in foundations of machine learning and data science, September 2015.
Alice Barthe, Michele Grossi, Sofia Vallecorsa, Jordi Tura, and Vedran Dunjko. Parameterized quantum eircuits universal generative models for continuous multivariate distributions, 2024.
Mihir Bellare, Oded Goldreich, and Erez Petrank. Uniform generation of np- witnesses using np-oracle. Information and Computation, 163(2):510-526, 2000.
Andrej Bogdanov, Luca Trevisan, et al. Average-case complexity. Foundations and Trends@ in Theoretical Computer Science, 2(1):1-106, 2006.
Adam Bouland, Bill Fefferman. Chinmay Nirkhe, and Umesh Vazirani. Quantum supremacy and the complexity of random circuit sampling. arXiv preprint /00.://80000400 2018.
Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. Noise and the frontier of quantum supremacy. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 1308-1317. IEEE, 2022.
Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojt éch Havlfček, and Guanyu Zhu. Quantum complexity of the kronecker coefficients. PRX Quantum, 5:010329, Feb 2024. doi: 1003/ PRXQuantum.50011 5.01039. URL http:tt::: :ttp::://nnnin//..ee aps org/ http:///..........///AAaAaua
5. 01339
11

---

Published as a conference paper at ICLR 2026
Andrew M Childs, David Gosset, and Zak Webb. Universal computation by multiparticle quantum walk. Science, 33966121);791-794, 2013.
Richard Feynman. Quantum mechanical computers. Optics news, 11(2):11-20, 1985.
Michael H Freedman, Alexei Kitaev, and Zhenghan Wang. Simulation of topological field theories by quantum computers. Communications in Mathematical Physics, 227:587-603, 2002.
Carlos E. Guilll and Toby S. Cubitt. History-state hamiltonians are critical, 2018.
Casper Gyurik and Vedran Dunjko. Exponential separations between classical and quantum learners. arXiv preprint (rXiv:2306.16026 2023.
Casper Gyurik, Alexander Schmidhuber, Robbie King, Vedran Dunjko, and Ryu Hayakawa, Quantum computing and persistence in topological data analysis. arXiv preprint arXiv:2410.22558, 2024.
Jeongwan Haah, Robin Kothari, and Ewin Tang. Learning quantum hamiltonians from high- temperature gibbs states and real-time evolutions. Nature Physics, pp. 1-5, 2024.
Hsin- Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. Power of data in quantum machine learning. Nature communica- tions, 1261):2631, 2021.
Hsin-Yuse Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 37766613)eebbk3333, 2022.
Hsin-Yuan Huang, Michael Broughton, Norhan Eassa, Hartmut Neven, Ryan Babbush, and Jarrod R McClean, Generative quantum advantage for classical and quantum problems. arXiv preprint MXXi:2500900033, 2025.
Dominik Janzing and Pawel Woejan. Bqp-complete problems concerning mixing properties of classical random walks on sparse graphs. arXiv preprint quant-ph/0611223,, 2006.
Sofiene Jerbi, Casper Gyurik, Simon C Marshall, Riccardo Molteni, and Vedran Dunjko. Shadows of quantum machine learning. Nature Communications, 15(1):5676, 2024.
Stephen P Jordan, Hari Krovi, Keith SM Lee, and John Preskill. Bep-coomleeennes of scattering in scalar quantum field theory. Quantum, 2:44, 2018.
Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), (1(1:677- 1994.
Michael J Kearns and Umesh Vazirani. An introduction computational learning theory. MIT press, 1994.
Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation. Number 47, American Mathematical Soc., 2002.
Luis and Luis Lorenzo Sánchez-Soto. Complete characterization of arbitrary quantum measurement processes. Physical review letters, 83( 83(18):3573, 1999.
Jeff S Lundeen, Alvaro Feito, Hendrik Coldenstrodt-Rowd Timothy C Ralph, Jens Eisert, Martin B Plenio, and lan A Walmsley. Tomography of quantum detectors. Nature Physics, 5(1):27-30, 2009.
Kenny L Pregnell, Ch Silberhorn,
Simon Marshall, Casper Gyurik, and Vedran Dunjko. On bounded advice classes. arXiv preprint 1.Xiv:2405.18/53 2024.
Mehryar Mohri. Foundations of machine learning, 2018.
Riccardo Molteni, Casper Gyurik, and Vedran Dunjko. Exponential quantum advantages in learning quantum observables from classical data. arXiv preprint rrXiv:2405.02027 2024.
Ramis Movassagh. Quantum supremacy and random circuits. arXiv preprint arXiv: arXiv:1909.00 1909.06210 2019.
12

---

Published as a conference paper at ICLR 2026
Bryan O'Gorma,, Sandy Irani, James Whitfield, and Bill Fefferman. Electronic structure in fixed basis is qma-complete. arXiv preprint arXiv:2103.08215, 2021.
Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2d lattices, arXiv preprint arXiv:1506.044 2015.
Ran Raz and Avishay Tal. Oracle separation of bqp and ph. ACM Journal of the ACM (JACM), 69(4): 1-21, 2022.
Jonathan Romero and Alán Aspuru-Guzik. Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions. Advanced Quantum Technologies, (1):2000003, 2021. doi: http:://ooo..orr///1000//////200
URL https: /ttpe:://ddvanne /advanced onlinelibrary amn.ineiibrrry.wleey.cco htw.ley.ccmm//////////a////////a wwt.//yccco////////////oooooooo. 200000/00 202000003
Rob Schapire. Lecture notes in theoretical machine learning, February 2008
Robert E Schapire. The strength of weak learnability. Machine learning, 5:197-223 1990.
Kevin Shen, Andrii Kurkin, Adrián Pérez Salinas, Elvira Shishenina, Vedran Dunjko, and Hao Wang. Shadow-frugal expeccaion--alle-saampii variational quantum generative model, 2024.
Stephen Wicker and Vijay K Bhargava. Reed-Solomon codes and their applications. John Wiley & Sons, 1999.
Hayata Yamasaki, Natsuto Isogai, and Mio Murao. Advantage of quantum machine learning from general computational advantages. arXiv preprint arXiv:2312.03057, 2023.
13

---

Published as a conference paper at ICLR 2026
A RELATED WORKS
A.1 PREVIOUS RESULTS ON LEARNING SEPARATIONS FOR QUANTUM FUNCTIONS
The study of different types of learning separations in quantum machine learning was initiated in Gyurik& & Dunjko 2023), distinguishing between advantages in the identification step and those arising solely from the evaluation of the target function. For BQP-complete functions, the authors showed that learning separations straightforwardly follow under the assumption that there exists an input distribution D and a BQP language L such that (L. D) & HeurP/ /poly. This separation relied on requiring the learning algorithm to evaluate the learned function on new inputs, thus considering the evaluation step only. The paper left open the question of whether a stronger result could be established by proving that even identifying the correct target function is classically hard for BQP-complete concepts, which we address in this paper. In Molteni et al. (2024), stronger learning separations were established for BQP functions under the widely studied assumption that BQP I P/poly (exactly, not with respect to heuristic conditions as in Gyurik & Dunjko (2023), by reverting to standard PAC learning where the learning process must be successful for all input distributions (as opposed to settings where the distribution is fixed). Additionally, there the authors proposed a quantum algorithm capable of correctly identifying and evaluating the target concept in the nontrivial case of a superpolynomially large concept class, as opposed to Gyurik & Dunjko (2023) where only polynomially large classes were studied. However, even in this case, the learning separation was demonstrated only for the evaluation step. Learning separations for superpolynomially large concept classes were also presented in Yamasaki et al. (202)), though they are based on assumptions about heuristic classes similar to Gyurik & Dunjko (2023) and were not focused on finding physically motivated problems, which was instead the goal in Molteni et al. (2024). In Appendix [..| we show that our result directly applies to the physically relevant learning problem considered in Molteni et al. (2024).
A.2 PREVIOUS RESULTS ON HARDNESS OF THE IDENTIFICATION TASK
Hardness results for the identification step are already known for certain tasks and it is important to highlight why the proof strategies used in those cases do not apply to the learning task considered in this paper, which involves quantum functions. In particular, hardness results for identification are already known in the context of learning DNF formulas (Kearns & Vazirani 1994) and for specific cryptographic functions, such as modular exponentiation (Gyurik & Dunjko (003) and discrete cube root (Jerbi et al., 2024). In all of these examples, a key element underlying the hardness proofs is the existence of a representation of the target functions that allows efficient computation of properties of interest. In the case of learning DNF formulas, (Kearns & Vazirani 1994) showed that DNF formulas cannot be learned in the proper PAC setting that is, given samples of variable assignments along with their evaluations under DNF formula, it is not possible to reconstruct the original formula. While the proof in (Kearns & Vazirani 1994) reduces the problem of learning DNF formulas to the NP-complete problem of graph coloring, the following argument provides what see as intuitive explanation of how the key element mentioned above plays a role in the proof. It is well known that checking the satisfiability of CNF formulas is NP-hard, whereas for DNF formulas this task is classically easy. Moreover, since DNF formulas are universal for Boolean functions, any CNF formula be equivalently expressed as D Of course, the transformation from CNF to DNF is itself NP-hard. However, if DNF formulas were learnable in the proper PAC sense, then a classical learner could, given samples from any target CNF, reconstruct the equivalent DNF representation and thereby decide satisfiability efficiently.
In the case of cryptographic functions the existence of an commpue representation implies a mapping between two representations of the same set of functions: one that is computationally intractable and another that classically efficient to compute. identifying the target concept in the second representation were classically efficient, it would also allow the evaluation of the target function in its hard-to-oa cone-to-compute representation. Examples of this are provided in (Kearns & Valiant 1994. Gyurik& & Dunjko 2023) based around the discrete cube root function which is intractable given the input, but has an equivalent representation as modular exponentiation by some (hard-to-compute) exponent. Furthermore, in the case of cryptographic functions, thanks to the additional property
'Note that in general the conversion requires exponential size DNF. This is the reason why our intuition cannot be trivially sharpened into proof.
14

---

Published as a conference paper at ICLR 2026
of random generatability, a classical algorithm could easily generate labeled data and solve the identification problem using the hypothesis class corresponding to the easy-to-com to--mputte representation of the function. Once the correct concept is identified, the algorithm could then evaluate it, thereby violating the cryptographic assumptions of the considered set of functions.
For the BQP-complete functions analyzed in this paper, our findings the hardness of random generatability already rule out the possibility of employing similar proof techniques to establish the hardness of identification. Finally, we observe that our proof does not rely on the existence of simple representation for the target BQP functions. Rather, in our case, we directly tackle the property of the learning algorithm to find the label from data, by exploiting the fact this can be "inverted" in the PH. This approach is then really relying on the strongest properties of quantum functions as it could not work for cryptographic functions which typically are the PH.
A.3 RELATION TO PREVIOUS WORKS ON HARDNESS OF SAMPLING
In the work Aaronson (2014) the authors showed an equivalence between sampling and searching problem. In particular, they showed that if classical computers could solve every search problem quantum solvable, then classical computer could also sample from the output distribution of any quan- tum circuit. While this might seem related to our results about the hardness of random generability of quantum functions Section 3 we note that the problems addressed are fundamentally different. In particular, our results classical intractability do not regard the whole class of distribution realizable by quantum circuits (i.e, SampBQP), nor do we make claims about the hardness of that class. We only consider the distributions given by the tuple (z, fxx) with the characteristic function of BQP language. Such distributions do not constitute the whole of the class SampBQP, and thus the capacity classically sample from them does not straightforwardly imply the capacity to compute (all) quantum functions. Indeed, because we are considering a much more restricted sampling capa- bility, our results are in fact weaker. We do not claim that sampling from these distributions would imply FBQP FBPP. Instead, we show weaker result: if a classical algorithm could sample pairs (ar, (x)). then it would imply that BQP C HeurBPpNP.
A.4 CONSISTENCY MODEL LEARNING
As argued in the text, the ability of the learning algorithm to detect invalid dataset is crucial in the construction of proof of Theorem 9 for the verifiable identication task. Although it is a strong assumption (which we will remove in Section 5 certain families of concept classes) argue that the verifiable case of Def. is of interest. An important reason is that Def. 7 perfectly captures the framework of learning the consistency model present in the literature Balcan (2015);
still
Schapire (2008); Mohri (2018): Kearns & Vazirani (1994). In Kearns & Vazirani ( (1994), a concept f defined to be consistent with a dataset 7 [1r, ye 12_ 1 if ye = (((e)) for every = 1,.... B. Based on that, we give the following definition of learning in the consistency model framework, which includes the ability the learning model to distinguish invalid datasets. As we explain below, this assumption aligns with the general case found in the literature Kearns & Vazirani (1994) ) SShhapire (1990): Mohri 2018), where only efficient hypothesis classes are considered.
Definition 9 (Consistency model learning Balcan (2015); Schapire (2008)). We say that an algorithm A learns the class F = {f" : {0. 1) {0, 1 a E (0. 10 m poly (n)} in the consistency model if, given any of labeled examples T, the algorithm produces concept f E F that is consistent with T, if such a concept exists, and outputs "there is no consistent concept" otherwise. The algorithm runs in polynomial time (in the size of T and the size of the examples).
Given the definition of learning in the consistency model in Def. 9 it is clear that an algorithm AB solves the identification task in Def. 7 for given concept class F if and only if it learns F in the consistency model.
B DEFINITIONS FROM COMPLEXITY THEORY
To enhance readability, we provide glossary of the most commonly used symbols in this paper.
15

---

Published as a conference paper at ICLR 2026
Symbol
Meaning
(x)
Concept function parameterized by
F
Concept class (set of labeling functions F= (f a E {0,1}²}) (0, 1)"
D
Distribution over input space of bitstrings
Unif
Uniform distribution over input space of bitstrings x E {0,
BQP
Class of decision problems solvable by a quamtum computer in polynomial time with bounded error Class of decision problems verifiable in polynomial time Polynomial Hierarchy
NP
PH
PNP
Class of problems solvable in P with access to NP oracle
HeurBPP
Class of problems heuristically solvable in BPP
HeurBPpNP
Class problems solvable in HeurBPP with access to an NP oracle
Heur NPppBpp
Class problems solvable in HeurBPP with access to an Np oracle
Table I: Glossary of commonly used symbols and complexity classes.
B. TOOLS FROM COMPLEXITY THEORY
All our hardness results are based on the assumption that the class BQP is not contained in (a low level of) the polynomial hierarchy (PH). See Appendix [ for arguments supporting this assumptions. Specifically, given a BQP language L, we define function f' which "correctly decides" L as follows.
Definition 10 (BQP function f). We refer to function f (0, 13 - {0, 1} as a BQP function there exists language L E BQP such that f is its characteristic function. In particular:
f(x) 0f L ((x) (f(z) =
Where, as previously said, we use f refer to a uniform family of functions, one for each input size. In our hardness results, we assume the existence of BQP language L such that, under the uniform distribution Unif over inputs x E f0, 1)",, the pair (c, Unif) not contained in HeurBPP with access to NP oracles in the PH. We next provide a precise definition for the complexity class HeurBPP (for more details see Bogdanov et al. (2006)). To define heuristic complexity classes, we first need to consider the so-called distributional problems (which should not be confused with learning distributions in the context of unsupervised learning).
Definition 11 (Distributional problem). A distributional problem (4, D) consists of language L (0, 1}* and a family of distributions = (Pn)net such that supp(D.)) S {0, 13".
We are now ready to provide a precise definition of the class HeurBPP.
Definition 12 (Class HeurBPP). distributional problem (C,D) in HeurBPP there exists polynomial-timg classical algorithm such that for all and 2 0:
PrawD Pr[A(z, = C(x) 2 3 21-6,
(10)
in the above the inner probability is taken over the internal randomization of AB.
Finally, we observe that by slightly modifying the proof' in the theorems, our hardness results will also hold under a similar but distinct assumption. Specifically, in Appendix | we will prove our hardness results under the assumption that there exists a classically samplable distribution Unif c such that (PromiseBQP, Unif c..) not contained HeurBPP with access to NP oracles in the PH.
B.2 PROMISE PROBLEMS
We note that our results can also be proven under similar but different assumptions. In particular, by slightly modifying the proofs our main hardness results hold even under the assumption that PromiseBQP problems cannot be solved in HeurBPP with access to NP oracles. We now provide the necessary definitions to prove these versions of our results, which we will do in the following sections. We notice that, unlike BQP, the class PromiseBQP allows for complete problems. We note that complete problems for PromiseBQP are known to emerge in number of physical processes, we list few of them in Appendix G.4
16

---

Published as a conference paper at ICLR 2026
Definition 13 (PromiseBQP function f). We refer function 10. + {0,1) as PromiseBQP function if there exists a language with a promise Lp = (Syes Lno) C 10,1) in PromiseBQP such that f is the characteristic function of Lp. In particular:
( f(x) 0 if $ Cye
f(x)
(11)
f(xx) = if E Cyes
Additionally, say that f is a BQP-complete" 9 function if the associated language C is complete for PromiseBQP.
Notice that for a PromiseBQP function f. f(x) promise, i.e. Lm.. and if r does not belong to the promise subset at all, i.e. & Lyes U L In general the promise subset Lyes U fm contains an exponentially small fraction of all the possible input E 10 R and consequently f 0 for the majority of x E {0, 1)". This means that correctly evaluating f on average over the input, for instance under the uniform distribution over all E 1 becomes trivial unless the error is exponentially small. We refer to Gyurik & Dunjko 2023) for a more detailed discussion on this. We will prove our hardness results by showing achieve achieve average-case correctness
both belongs to the NO subset of the
that classical machine with access an NP oracle for evaluating a PromiseBQP function f with respect a given input distribution. For PromiseBQP functions, to ensure the task remains non-trivial, input distribution Unif which is defined as the uniform distribution over a subset of the promise set of input æ E Lyes U Lno In our hardness results, assume the existence of PromiseBQP complete language Lp such that there exists a distribution Unif of hard-to-evaluate but classically samplable instances.
will state hardness results with respect the
Definition 14 (Distribution Unif Let Lp (ees Lao) be PromiseBQP complete language. We call Un if it exists, the uniform distribution over a subset II C Lyes U Lno such that the following holds:
. Unif is efficiently classically samplable.
For our results in Theorem 2 and Theorem 12 and we will then assume the existence of a PromiseBQP language Lp for which there exists Unif such that (Lr, Unif is not contained in HeurBPP with access to NP oracles in the PH.
B.3 ADVICE CLASSES
In this section we provide further useful definitions. We first define the complexity class P/poly which appears in Proposition I and Theorem
Definition 15 (Polynomial advice Arora & Barak (2009)) A problem L f0, 1 - + 10.1) is in p/poly if there exists a polynomial-time time classical algorithm Ag with the following property: for every n there exists an advice bitstring on E {0, 1) poly(()) such that for x E 10.1)":
A2(x, L(x).
(12)
We also provide the definition of the class 3PP/samp BQP which will appear in Theorem 6 Definition 16 (BPP/s SBPP/sampRPP) A problem L 10 + {0, 1) is in BPP/sampBB BQP if there exists a polynomial time quantum algorithm S and a polynomial-tin classical randomized algorithm A such that for every
S generates random instances E {0. 1) sampled from the distribution D,.-
A receives as input T {(x,, [(x,)) D2 (oly(() and satisfies for all (0, 1)":
2 Pr(A(z, = L(x)) 3
(13)
where the probability is taken over the internal randomization A and T.
It is known that BQP do not have complete problems. Here, we will abuse notation and actually refer to PromiseBQP problems.
17

---

Published as a conference paper at ICLR 2026
C EVIDENCE THAT BQP & PH
In this section, we provide a brief' discussion on the primary assumptions underlying our work, which are derivatives and versions of BQP & PH. The first main result in this direction is given in (Aaronson 2010), where an oracle separation between the relational version of the two classes was proven. Specifically, Aaronson proved that the relation problem Fourier Fishing, a variant of the Forrelation problem, exhibits an oracular separation FBQPA C FBPP In the same paper Aaronson motivated the study of oracle separation for BQP and PH as lower bounds in a concrete computational model, claiming them natural starting point for showing evidence of BQP z PH. Almost ten years later, the remarkable work (Raz Tal 2022), the authors managed to prove an oracle separation for the decision versions of the classes. Namely they proved the existence of an oracle A such that BQP PH Although unconditional proof of separation between BQP and PH is not likely to appear anytime soon 10 the assumption BQP & PH is generally considered reasonable.
Most of the results in this paper furthermore rely on the assumption that BQP languages cannot be decided correctly average by algorithms in HeurBPP, even when given access to oracles for the polynomial hierarchy. This is a stronger assumption than simply BQP g PH, but we believe not unreasonable. However, we note that workaround would be possible by requiring a stronger notion of lcarnability, in particular by moving from the less common setting of distribution-specife PAC of Def. to "standard" PAC, where the learner is required to output a consistent hypothesis for every input distribution. In this case, for any given input one can apply the classical identification algorithm to a distribution concentrated solely on æ. To evaluate the target concept on this input, the same strategy used in the proof of Theorem can can be employed: namely, inverting the identification algorithm (which now works for the distribution focused on æ) within PH. This would enable evaluation of the target function at any point contradicting the assumption that BQP g PH.
If we choose to remain within the distribution-specife PAC setting, we however believe our assump- tions are still widely accepted. Some evidence in this direction comes from sampling problems, where the proof of the best-known separation of SampP and SampBQP (Aaronson & Arkhipov 2011 Marshall et al. 2024) is identical for the heuristic case and produces the same collapse. To be more exact, suppose that SampBQP can be decided in some heuristic level of the polynomial hierarchy, follow the proof of (Aaronson & Arkhipov 2011) for heuristic-equivalenn theorem until we get to the definition of (Heur)GPE_, at which point we note that the preexisting definition of GPE + is already heuristic, so our HeurGPE is equal GPE+. Therefore, assuming that SampBQP is in some heuristic level of the sampling analogue of the polynomial hierarchy would still imply the collapse of the standard polynomial hierarchy to some level (standard assumptions from quantum supremacy arguments notwithstanding).
From these arguments, however, no analogous claims regarding the decision (and distributional) variants BQP and Heur PH can be proven using known techniques. For this reason, we stand by the following careful claim: there is no reason to believe that BQP is Heur PH (relative to relevant distrubutions).
As final remark, we do highlight that our results do not require considering the whole PH. Specifi- cally it is important to note that for the hardness of random generatability of quantum functions in Section we only need to assume that BQP is not in the second level of the PH, while the assumption extends up the fourth level for the hardness of the identification problem in Section 5
D PROOFS REGARDING RANDOM GENER ATABILITY
D.1 HARDNESS OF RANDOM GENERATABILIT BASED ON THE ASSUMPTION BPP BOP BQP g BPP
In this section. we demonstrate that achieving exact random generatability for quantum functions would lead to BPP /sampB08 BQP C BPP. Similar to Theorem | we show here classical hardness of the task defined in Def. [ for quantum functions, though based on a different
caaplexity-thhoreee assumption. The proof is straightforward and relies on the idea that if a classical machine could
Note that any proof of BQP & PH would immediately imply the hard-to-prove claim that BQP * BPP.
18

---

Published as a conference paper at ICLR 2026
efficiently generate samples for any quantum function, passing those samples as advice would offer no additional advantage.
Theorem 6 (Exact RG implies BPP /samp RQP S BPP). If BPP /samp g BPP, then there exists a quantum function f: 10, - {0, 1) given Def. 13 which is not exact random verifiable as in Def. 7 with a classical algorithm A.
Proof. Suppose vf in Def. 13 there exists randomized algorithm A, such that Ay(r) (x, f(r) with Unif({0,1) for sampled uniformly at random. Then every function g E BPP PPPP/ampBBr BQP can be computed in BPP by first generating the samples (z,g(z)) using Ag
We now argue that the hypothesis of the Theorem are indeed reasonable. Indeed, a separation between the class BPP and BPP /samp BQP can be proven if we assume the existence of a sequence of quantum eircuits )Un),, one for each size n, such that the Z measurement on the first qubit hard to decide classically. A proof idea for the following theorem is stated in Huang et al. (202T). and we include here the whole proof for completeness.
Theorem 7 (BPP /sPmpBQP & BPP, unless BPP = BQP for unary languages). If there exists uniform sequence of quantum circuits J for each size n 1.2. such that the Z measurement on the first qubit is hard to decide classically, then BPP /samp BQP g BPP.
Proof. As shown in Huang al. (202I), such a sequence circuits would define a unary language
LBQ {1" (0" (U,) zU, 10") 2 0}
(14)
that is outside BPP but inside BQP. The authors then consider classically easy language Leass BPP and assume that for each input size n, there exists an input an E Leasy and an input bn & Lenay. Then it is possible to define new language:
L
U (xl Va E Leacy, 1 E Lhard; [0]| [n] U {xr Vo Leasy: 1 E Lhard [x| -=|=11 =1] n). (15) 7mmm
For each size n. if 1 E LBQP, L would include all E Leasy with |z| 1" & Lhard L would include all x E Lewsy with |z| = n. By definition, we can determine whether x E L for an input x using classical algorithm (BPP),
could also determine whether 1" LBOP by checking whether & E Teeayy However, this must be impossible as we are assuming that Loop cannot be decided classically. Hence, the language I, is not in BPP. On the other hand, for every size n, classical machine learning algorithm can use single training data point (zo, Bo) to decide whether E L by what said above.
We note here that the existence of unary languages in BQP but not BPP is a well believed assumption.
D.2 PROOFS OF THE THEOREMS FROM THE MAIN TEXT CONCERNING THE HARDNESS OF RANDOM GENERATABILITY
In this Section we provide the proves about hardness of random generability based on the fact that BQP is not in the PNP or HeurBPpNP We provide here an intuition on how the proofs work. Suppose there exists an efficient classical algorithm that samples pairs (z, fxr) at random, where x for some D. Then, for every sampled (xr, f(x,)) there must exist a random string r such that the algorithm, when run with randomness r. outputs that pair. Given any input we could then search for such an r using an NP oracle (since the algorithm is efficient), and once the correct is found, could evaluate the randomized algorithm that random string obtain ff fzr. This would imply that (xx) is classically computable with the help of an NP oracle, contradicting our complexity assumptions.
19

---

Published as a conference paper at ICLR 2026
D.2.1 HARDNESS OF EXACT RANDOM GENERATABILITY
Theorem (Exact Random generatability implies BQP C pNP)). Let f- (fn]nen be a famity of BQP functions as in Def. TO If there exists a classical randomized poly-time uniform algorithm that generates samples (z. fn correctly with probability in Defl with x Unif({O, 1)"), then
PNP contains BQP.
Proof. The existence of a randomized poly-time algorithm which satisfies Theorem iss equivalent to the existence of uniform family of poly-sized algorithms C(r) such that random choice of E (0, 10 (poly(n) outputs tuple (x, [a)) uniformly at random, i.e.
C {C(r) r E (0, 1)
(16)
Then, for every there exists least one rz such that C(rz) (z. fx)). particular, for given PNP machine can in polynomial time find corresponding Tx. Consider the set
P(Č)= {u,,x) Ev (0, s.t. C(we) x)
(17)
where Č is the same family of algorithms except that the last bit the output (i.e., the value f()) is omitted and ((r) E č. Then (u, x)) is in P(C)) if and only if is a prefix of some Tz inverse of with respect to Ć. Clearly P(C) is in NP as correct u E {0, 1} can be verified in polynomial
time as also the family Ć consists of polynomial sized algorithms. Then we can run the following algorithm in PNP:
Algorithm Prefix Search Algorithm
1: function PREFIXSEARCH(2)
2: u E;
b where & denotes the empty string
3: for |rl times do
4: if (ul,x) P(C) then + ul else < u0
5: end
6: end for
7: return u
8: end function
As for every there exists least corresponding r., the above algorithm always succeeds in finding a correct rs. Once the string Ta is found, the machine can run C' on that string and evaluate (ar). Since ((r) can decide arbitrary BQP language by Def. 10 follows that PNP can also correctly decide every 13.
D.2.2 HARDNESS OF APPROXIMATE RANDOM GENERATABILITY
In this and the following sections, our proofs concerning the hardness of the approximate random generatability and of the identification task will rely on a well-known result about sampling witnesses
of NP relation using an NP oracle. Specifically, the authors of Bellare al. (2000) showed that for given NP language and relation R, where = (xc Fi such that R[ = 1J. is possible to uniformly sample witnesses from the set R. {w R|æ, w] = 1) for any x L. Since this result will be central to all our subsequent proofs, we include the main theorem from Bellare et al. (2000) here for reference.
Theorem 8 (Theorem 3.1 in Bellare et al. (2000). Let R be an Ne-relation Then there is uniform generator for R which is implementable in probabilistic, polynomial time with an NP-oracle.
For convenience, we also report here the definition of approximate random generatability of Def. in the main text.
Definition 17 (Approximate random generatability (Def. 2 in the main text).). Let f = {ʃx JeEN be uniform family of functions, with fn 10, - {0, 1J. -- is approximately random generatable under the distribution D if there exists an efficient non non-uniform (randomized) algorithm AA such that given input a description of fn. for any n, random string and an error value e, outputs:
A(Juse, r) (Frr (n())))
(18)
20

---

Published as a conference paper at ICLR 2026
with (Irr (x,,) T! (D) when is sampled uniformly random from the distribution of all the random strings. In particular, मे (D) a probability distribution over {0, x {0. 1 which satisfies: || (D) x (D)llr where x (D) is the same distribution defined in Def.
can now state our hardness result for the approximate case of random generatability.
Theorem 2 (Approximate Random generatability implies (BQP, Unif) E HeurBPpNP), Let f (frinEN be family of BQP functions which is the characteristic function of language & E BQP as in Def. 10 and let Unif be the uniform distribution over 10. If there exists polynomial time algorithm A which satisfies Def. 2 for the uniform input distribution Unif, then (L, Unif) HeurBPpNP
Proof. The proof follows from the proof of Theorem [ We will present the proof under the language
assumption of distribution Unif Ep. as defined in Def. 14 and a PromiseBQP-comp Cp such that (Cp, Unif Cp Z Heur The proof then generalizes straightforwardly to the case where we assume (C E BQP, Unif) g HeurBPpNP simply by considering the uniform distribution Unif over all inputs x E 0, instead of Unif
Consider the same families algorithms and è introduced the proof of Theorem 1 The existence of an algorithm as in Def. guarantees the existence of such families and Ć. Let W {rr) be a of M random strings r, E (0.1)1r) with |r| poly (n) and consider the set:
P(Ć, W) = (a E {0, 13" 3r E 13 |rl S.L. Ö(r) a & r W}
(19)
If the set W has size M = (nly(n) then P(C: W) can be decided in NP since both the conditions C(r) and & W can be verified in polynomial time. Theorem 8 from Bellare al. (2000)
guarantees the existence of an algorithm An such that, given the NP relation R : C(r) z and an
input x, outputs, with high probability, a sample such that C(r) r uniformly at random among all the witnesses of æ. Then the following algorithm runs in PNP
1:
function MULTTPREFISSARCCHC))
2:
where E denotes the empty string
3:
W w/=10 [r]
4:
for poly([x]) times do
5:
r+ An
6:
W + {r)
7:
end for
8: for i: < [W times do
9: return r, W
10: end for
11:
end function
Where we denote as AR(æ] the algorithm in Bellare et al. (2000) which uniformly samples wit- nesses for the relation R Ö(r) = x corresponding to the input x. On an input x, the algorithm MultiPrefixSearch outputs a list of polynomial different random strings {r (if they exists) for which C(rá) = ø Vi, sampled uniformly at random among all the random strings associated to x. We now construct the following algorithm A' acting on input æ. Specifically, on any E {0, 1)", then either:
A' first applies the algorithm
Mu 1 ietirref xSeerrh(f outputs an empty string, then the algorithm assigns random value to f()
Otherwise, the algorithm computes the lables A(rí) (a, (xx)); for any of the random strings outputted by Mu 1 i Pref Preff xSeercch(z). It then assigns the label determined by the majority vote among all the f());; values obtained.
Now we show that the above algorithm A' is able to classify the language L correctly on average with respect the uniform input distribution. More precisely, for each x: consider the sets R
21

---

Published as a conference paper at ICLR 2026
frx A(rr)) (z, y) with = fz)} and R = (r& A((=)) (z.y)
y w f() f 1}. Also,
let Riot be the set of all the random strings of the algorithm A, clearly Rtool >= |
|R Notice that R | | precisely represents the probability that the classical algorithm A outputs the pair (x,, f(x)). Similarly, the probability that A outputs a tuple containing æ is [ Reot| where [ = [ + |
By defimition of difference in total variation between two distributions. i.. llp-gllrv = Ip(x)-
q(z)). we have the following relation between the distribution ne generated by A and the target distribution Unif en (10, 1)") x f(Unif (10, 1)")) uniform over the input of the promise of the language L:
R
R Reod
TT - Unif ((0,1]") x f(Unifer (10, =
Σ
2
B
Pl
2
xEr
DEP
1
Σ
|
+
|R
|Reoel
2g
(20)
where P= yes Lno C 13" denotes the set of x belonging to the promise of for the language L. We now bound the number of P for which the probability of A computing incorrectly them exceeds 1/3, specifically we are interested in the size of the set X Xwrong such that:
2 35
X Xwrong
REPI P!
(21)
Peoo (x)
From Eq. 20 it follows:
| Runt
C Unif((0,13") [(Uni(((0,
(22)
(1)o(())
(23)
Root
Pi
D6 X Ewrongg
2
(24)
2 # x Xwennn
3 P
Pl
||X wrong
(25)
3 IP|
where used the fact that the output distribution L, is close in TV with the uniform distribution
over the æ E {0, 1)" (and the corresponding labels y = f(x)), then [Raa[[x)] |.|
1 + ò5 with the
[Rae constraint Σ | < We can then assume 8 << and therefore neglect it in the derivation above. From Eq. (25), directly follows that [ < 6c - [P] and therefore the fraction of [P] for which A outputs the correct label with probability less than 2/3 is approximately 6c.
Then, the algorithm A', with NP oracle, correctly decides in BPP at least a fraction 1 - 6e of all the possible x E (0, 1)". When x are sampled uniformly, algorithm A' is therefore able to decide the language L in HeurBPpNP with respect to the distribution Unif uniform over the set of belonging to the promise.
Corollary 2. The expectation value sampling (EVS) generative model, defined in Barthe al. (2024) is classically intractable.
Proof. To not detract from the main topic we just provide a quick proof sketch. By intractable we mean that there cannot exist a classical algorithm which takes input arbitrary polynomial sized EVS M specified by its parametrized circuit (see Barthe et al. (2024) and outputs an e approximation of the distribution outputted by M. To prove this note that for any BQP function f 10,1)" + {0, 1} we can construct a pole-sized EVS which produces samples of the form (xr, (x)), where is an n-bit bitsting sampled (approximately) uniformly (or according any
22

---

Published as a conference paper at ICLR 2026
desired classically samplable distribution). There many ways to realize this: the easiest is to coherently read out the bits of imput random continuous- valued variable using phase estimation (for this, this variable is uploaded using prefactors 2 for each bit position k), forwards this to part of the output, and in a parallel register computes (ar and outputs that as well. This is a valid EVS, and sampling from it is equivalent to random generatability for the BQP function f. This then implies (Cp, Unif cp) E HeurBPpNP.
We provide here an example of 0.5-distinct concept class, which therefore satisfies the condition of Theorem 13 where the concepts are all (Promise-)BQU complete functions.
Definition 18 (0.5-distinct concept class with BQP concepts). Let f be PromiseBQP complete function as in Def. 13 on imput E {0, 1) Then for any f there exists concept class FF containing 2" CaamiseBQP-complle concepts defined as:
F= ( (0, + (0.1) a (0,1)")
(26)
/ x 1 xx)
(27)
where a is the bitwise inner product modulo of the vectors a and x.
Clearly for any a, a2 E {0, 10, aj # a2 it holds that f (x) * fx)(x) on exactly half of the input x, also they are all PromiseBQP complete functions as by evaluating one of them we can easily recover the value of fz)
E PROOFS OF THE THEOREMS CONCERNING THE IDENTIFICATION TASK
E. PROOF OF HARDNESS FOR THE IDENTIFICATION TASK IN THE VERIFIABLE CASE
Theorem 3 (Identification hardness for the verifiable case ). Let F= f0. - {0, 10. a {0, 1)mh m = poly(n)} be a concept class such that there exists a fr F which is the characteristic function of language
BQP as Def. 7O and let Unif be the uniform distribution over the & E (0, 1).. If there exists a verifiable identification algorithm An for the uniform input distribution Unif as given in Def. 7 then (C, Unif) HeurBPpNP.
Proof. In this proof, we consider any training set T = ve),,, as a sequence of concateneted bitstrings, i.e. T = zn BBBB Let X = {xx _ be a set of B inputs æt E (0, 1)". We
B(++1) bits
define the following set:
P(AB, e, B) = ((),a) BY [0011) {0, 130oly(n) s.t. AB( = a }. (28)
where Y = [ye [ E=1 is collection of labels yr E {0, 1) such that Tx,y ((x), ye) We are also going to assume that for given a and the number of training sets for which there exists an r such that (T(TTe,) = a is greater than and the majority of them are dataset labeled accordingly to one concept â which is e-close to in PAC condition. The set P(An, B) contains then all the tuples (X, a) which satisfy the relation R (,( = a. Since Ag runs in polynomial time (for ~~ [n] and B ~ poly(n)) (n)), the relation belongs to NP. Theorem g from Bellare et al. 2000 guarantees the existence of an algorithm An such that given the NP relation R An(Tx, outputs on input (X, or) a tuple (Y,r)
3z[((,,)) which satisfies AB (Tx,Y, = a, uniformly at random among all the possible tuples (Y,r) which satisfies R.
We can now construct an algorithm A'' which, using NP oracle and the algorithm Ar in Bellare ct al. (2000), evaluates any concept f with average-case enror of at most e' under the uniform distribution over inputs I E {0, 1)". In other words, the algorithm A' satisfies satisfies the heuristic condition in Eq. (10) with respect the target function f". Firstly, since verifiable case, we can implement the following function which, given a dataset consistent with one of the concept, tells if the label of an input {0, 1) is consistent with the dataset or not.
considering the
23

---

Published as a conference paper at ICLR 2026
function CHECK(I,
2: if UT, ro) = "invalid dataset"
3: return
4: else return 0
5: end function
We can now construct the algorithm A'. Fix a desired average-case error c' First consider an identification algorithm Ag in Def. 7 which runs with and such that e = 2 [1 - 8). Using the algorithm Ag and the algorithm R given in Bellare et al. (2000), construct the following algorithm A' which runs in polynomial time using an NP oracle.
function A' I. c,B)
2: step 1. Sample B inputs X = ...,,... from the uniform distribution Unif. ...
3: step 2. (Y,r) 6- A
4: step 3. Construct Tx,y by assigning each label in Y to the corresponding point in X.
5: step 4. return y eC,
6: end function
The labels produced by A' ensure that all inputs in {(x, U are consistent with at least one concept labeled by a. We will now demonstrate that the concept f is, with probability greater than 2/3, heuristically close to the target a, meaning that:
E Be (z) (E)
(29)
In Step of the algorithm A', the labeling Y = (ye) chosen such that AB, given the dataset Tx.y and parameter c, outputs a with probability greater than O. Specifically, the dataset is sampled uniformly at random from all possible datasets satisfying this condition. The probability that an outpuited dataset T T is consistent with concept f that is not e'-close to f (as defined by Eq. (29) depends on both the inputs in and the failure probability 8 of the algorithm Ag. For simplicity, we initially neglect the failure probability 8 of Ag. Even in this case, the dataset Tx,y could still be consistent with concept fä far from fa if both fa and fä agree all the 1 inputs in X. By setting e = e'/2, the fraction of inputs on which a concept f (not satisfying Eq. (29) disagrees with concept that is e-close to fa is at least If at least one of those inputs is in X, then such f cannot be outputted by [[P(AB, c, B), (X, a:] (we are still assuming the algorithm AB has zero failure probability, i.c. 5 = 0). The probability that random lies in a fraction of all the E {0, 1 is clearly follows that the probability of selecting B random inputs where at least one shows disagreement between a concept that is e-close to fo and concept that is more than e away from for is:
-
c)
(30)
We want to bound this probability such that is above 2 3. In order to obtain that, we need to extract number of inputs greater than:
(1 - c) <
(3
B Blog(1 6) < log
(32)
-2eB < log
(33)
B > log 3
(34)
Where we used the fact that for S 0.7, -2c < log(1 c). Therefore, by selecting B ~ (noting that the has to scale as probability greater than 2/3 that the dataset Tx,y produced in Step of A'' is consistent only with concepts that are e'-close to the target We now take into account the failure probability of the algorithm An- Because of this, it is still possible that there exists a random string To such that, for dataset Tx Tx, consistent with concept f that is more than é' away from fa the algorithm
for the algorithm A to remain efficient), we can ensure with
24

---

Published as a conference paper at ICLR 2026
A y, C, ro) outputs a, regardless of the B inputs in the dataset. This happens with a probability 5 over all the possible datasets. We can then take into account this probability of failure by asking that the probability in Eq. (30) is above अ-- With this modification, the bound on the number of inputs becomes:
B log 28
(35)
Notice that for 6, the above quantity is still polynomial in n.
For every input æ; the algorithm A'' outputs, with probability greater than 3. label y E {0, 1] that aligns with one of the concepts f satisfying Eq. (29). i.e., concepts that are e'-close to fa, The maximum number of inputs x E {0, 1}" that the algorithm can consistently misclassify is bounded above by c'. This corresponds to the scenario where all c'cloose concepts disagree with on the same subset of inputs.
As discussed in Appendix B.2 verifiable identification task. In this version, we assume the existence of an input distribution Unif cr as in Def. 14 PromiseBQP language Lr such that (Lr, Unif cp) HeurBPpNP.
state here the second version of our result on the hardness of the
Theorem 9 (Identification hardness for the verifiable case second version). Let F = {f {0, 13Th + {0. 13 {0. m poly(n)} be a concept class such that there exists f E F which is the characteristic function of language Lr E PromiseBQP as in Def. [10] and let Unif c. be the input distribution defined in Def. [74, If there exists a verifiable identification algorithm AB for the input distribution Unif Cp given Def. 7 then (Cp, Unif E HeurBPpNP,
Proof. The proof proceeds in direct analogy to the proof of Theorem 9 The only change regards the first step in Algorithm A'' Specifically, instead of sampling the inputs X 21,42; -r.;-..;: r uniformly at random, now the algorithm A'' will sample them from the distribution Unifp. We note that, by Def. [4, Unif assumed be classically efficiently samplable.
F PROOFS OF HARDNESS FOR THE IDENTIFICATION TASK IN THE NON-VERIFIABLE CASE
In this section we provide the full proof of our main result in Theorem 10 As outlined the proof sketch in the main text, the proof is combination of two other theorems that also state and prove here. We first restate the main theorem, including both the possible assumptions- average case hardness of evaluating BQP or PromiseBQP languages- together.
Theorem 10 (Hardness of the identification task non verifiable case). Let = (0. 13 {0, 13 a E {0, 1Jm² be a concept class containing at least a BQP (PromiseBQP) in Def. (as 7 (as in Def. 13) associated to language C E BQP (Lp E PromiseBQP). Assume further that F is either a c-distinct concept class with c 2 1/3 or an average-cat serrrge-case-smonn caso-smooth concept class. If the non-verifialle identification task for F. defined in Def. g is solvable by an approximate-corven
f as
identification algorithm Ag (Def. 19 then it follows that (C, Unif) HeurBpp (respectively,
(Cp, Unif ) E HeurBPpMppNNG
Proof. The proof combines the intermediate result in Theorem (or Theorem 12p with the result in Theorem 13 for the c-distinct concept classes or in Theorem 14 for average-case-site smoth concept classes. Specifically, Theorems 13
and 14 show that if an approximate-corren algorithm exists for
concept class F satisfying Def. 5 or Def. 6 then there exists an approximate-verffabble a algorithm for F
running in NP. Therefore, as consequence of the intermediate result in Theorem [T (Theorem 12).
follows that if such approximate-verifaae algorithm would exist, then (c, Unif) E Heur
(Cr, Unif E HeurBppNp ). This comes from selecting A NP in Theorem 11
L
In the following two subsections we will provide the proof of the results used in the proof of Theorem 10
25

---

Published as a conference paper at ICLR 2026
F.1 HARDNESS OF APPROXIMATE VERIFIABLE IDENTIFICATION TASKS
We first present an intermediate result, which concerns the hardness of the approximate-veriianl identification task. We define the approximate-verifaat task identification task where the learning algorithm can reject datasets which contains more than a fraction 33 of inputs incorrectly labeled.
Definition 19 (Identification task (0,1) a E {0, 1 } be a concept class. An approxinute- (randomized) algorithm Alg such that when given input set T { ye {== of at least B pairs (z, y) E {0, 13 x (0, }, an error parameter > O and a random string r E R, it satisfies the two following properties:
perroximate-veifiibb case). Let F = {fr {0. +
identification algorithm is
Soundness If (T, Ag
a then there exists subset T T, with [T') 2 (1 B) such that y/ = f for all the (Iz, ye) E T'. In case there does not exist subset T CT of (1 })B inputs consistent with any one of the concepts, then A outputs "invalid dataser".
Completeness If T {( de and ye = (x() for all (xe, E T', then, for any e 2 and B 2 0, the following condition holds:
3r s.t. A (T, =a
In addition to being proper PAC learner: if the samples in T come from the distribution D, ie. Zz ~ D, and there exists an a E {0. 11thm such that T = {( (1)) with It ~ D and
yt (x)) E {0, 1J then with probability 1 - d outputs:
(T ,,,r) a, {0,1)
(36)
with the condition (x=D)s"(x) (d) (x))
We say that Ag solves the identification task for concept class F under the input distribution D if the algorithm works for any value of e, 2 0. The success probability 1 5 is over the training sets T where the input points algorithm. The required minimum size B of the input set 7 is assumed to scale as poly(n,1/s11/)) while the running time of the algorithm scales as poly(B, n2,3).
sampled from the distribution DD and the internal randomization of the
In the following theorem we prove hardness of the approximate-veriiine identification task. It will be useful to state our result assuming that the approximate verifiable algorithm lies in a generic complexity class A and obtain hardness based on the assumption that BQP (or PromiseBQP in
the second version of the theorem) is not in HeurBppNp*A In case A = P, and the approximate- verifiable algorithm is classically efficient, then HeurBPpNP"** = HeurrPpNN
Theorem 11 (Approximate ( identification implies (BQP, Unif) C Heur Ler E {0, 11" be concept class containing at least a BQP function f as in Def. T0 associated to a language L BQP. If for any B 2 there exists an approximate-verifaablee identification algorithm As running in A Aorr the input distribution Unif as in
== {0, 11" + 10
Def. then (C, Unif) E HeurBPpNp
Proof. Let the concept f E be the BQP-function associated to a given BQP language. In this proof we considering training sets Tx,y v ((x2, ve ve) as sequences of concatenated bitstrings, ie. Tx,y = JBV where X = {21, F2, FB and Y {11, U2 .... ys
B(n+1) bits
There are 2bB possible sets X= { of B inputs x E (0, 1)". For any of these sets X, we can construct a dataset Tx,y = {(x,, ) )== by assigning a set of labels Y = {yx B to the inputs in X. We define for each input {0, 1 1 the set (xx containing all the datasets such that:
(37) Because of the soundness property of the algorithm A in Def. 19 every set Tx, E Tx)x) will have at least fraction of the x's correctly labeled by fa. We can construct a randomized
(x) (Tx, { 3z) P 3r s.t. (T.,
A A
26

---

Published as a conference paper at ICLR 2026
algorithm (M 2, s) which, using the approximate-verffiabe algorithm A in Def. 19 on input x sample one random dataset Tx,y from T (x) and label z accordingly to the label of the corresponding in Tx,y.
1: function (
B. I, 8)
2: step 1. Sample Tx,y from the (x) uniformly at random.
3: step 2. Output y from (z, E Tx,y
4: end function
We first show that the algorithm M belongs to BPp if Al runs in A. In the algorithm M the random string s determines the set Tx,y TT(x) (x)) sampled. We then consider the following set:
P(AB. x) = far {0, 11thh Y s.t. Tx, (x)),
(38)
The set P(AB, .) contains all for which there exists dataset Tx,y and random string such that the identification algorithm Al in Def. 19 outputs a, i.e. Ag (Tx,,, 1/3,r) = a, and x appears in a belongs to ((A x) can be done in NP The reason for that is that within NPA it is possible to decide a given 7x,y belongs to (xx since the algorithm Ag (Tx,, 1/3) runs in polynomial time. Therefore, the condition Tx,y (z), which ensures that E P(A B can be verified in polynomial time with the help of an NP* oracle. We can then use Theorem from Bellare al. 2000) that guarantees the existence of algorithm in BPP such that given any NP relation outputs a witness for a given x uniformly at random. In particular, we apply Theorem S sample a training set X from the set T (x) which be regarded witnesses for the relation
Tx.y. Deciding
E p(Ag.))
v). This allows to perform the first step of the algorithm M BPP
WW have
then proved that the algorithm M can be run in BPp
We now show that the algorithm (A x, s) can correctly evaluate the BQP function f large fraction of input points. In particular, we obtain that for any 2 0 the algorithm Ma such that:
2 5
Unn:~Uni((0,1)
Pr,[M (AB, # (x))
Se
(39)
In other words, the fraction of inputs æ {0, 13" for which algorithm M misclassifies with probability greater than 2/5 is less than e. Let us first consider the set (=xx) (x) for a given œ. Because of the soundness property of the upproximate-verifibble algorithm A in Def. 19 in every dataset Tx,y E (x) the number of inputs x E X incorrectly labeled are at most 3 B. Since in total there can be 2nB different sets X. the maximum budget for incorrectly labeled inputs across all the possible datasets is 3 2 The algorithm M will misclassify point with probability greater than 2/ if the point appears with the incorrect label on more than 3 of the datasets Tx,y E (x). The total number of possible sets X of B points which contains I is given by the total number of possible datasets minus the number of datasets which do not contains I, i.c.
BaB (2
1) 2 2nB (1
2n B B2)(
(40)
Then, the maximum number Nmmax of different inputs for which Pr, \ (Ag. (M is
+ fz)))
>
2 22n(B-1) 1)B B2aB Tmmax
(41)
which gives Tmmxx 2n and therefore fraction dB of misclassified inputs. By choosing B to be sufficiently small (e.g., inverse polynomial in size), we can make the error e in Eq. 39 arbitrarily small.
When comes from the uniform distribution over the set of allowed inputs, this means that:
Pr (0..0 Pr, [M, (AB, (x)) Se
27

---

Published as a conference paper at ICLR 2026
and thus (C, Unif) HeurBppNpkan
As it was the case for the previous results, we can show hardness for the approximate-veriiabll identification task based on the assumption that there exists distribution Unif cp and a PromiseBQP. complete language Lp not heuristically decidable given access to oracle the PH.
Theorem 12 aeproximate-verifaln identification implies (PromiseBQP Unifzz) C HeurBPpNaMr Let F { {0, - [0 a PromiseBQP function f as in Def. 13 associated to language Lp E PromiseBQP and let Unif ce be associated input distribution as in Def. [4] If there exists an
E {0. 10m} be concept class containing at least
identification algorithm AB running in A for the inpul distribution Unif as in Def. 19 then
(Cp, Unif E HeurBPpNPHer
Proof. The argument proceeds in direct analogy to the proof of Theorem I1 the only change regards the sets of trainingsets considered. particular, we impose that the inputs xę in the training sets To (x: of Eq. (37 comes from the input distribution Unif Since we assume efficient classical samplability Unif cp Def. [4] this condition can be enforced within polynomial time. The rest of the proof follow the same steps the proof of Theorem
L
F.2 CONSTRUCTION OF AN APPROXIMATE- VEEIEE-VERIIBBLEE ALGORITHM IN THE PH
We now present the second part of results needed to complete the proof of Theorem TO Specifically, we show how to construct an approximate-verifiin approximate-correct algorithm which satisfies the non-verifiable task in Def. g We will show this possible by climbing up one layer in the PH for two types of concept classes: c-distinct and average-case-smooth
algorithm which satisfies Def. [9 given an
Theorem 13. there exists an upproximate-corres identification algorithm AB in Def. for c-distinct concept class F, with 2 1/3, which works correctly for a dataset of size B, then there also exists approximate-errifuble algorithm A in Def. 19 in NP which works correctly for dataset of size 3B.
Proof. The proof works by explicitly constructing an algorithm A that within NP and that, given access to the approximate-correct algorithm Agg in Def. satisfies the condition in Def. 19 of approximate-verinee to show how an approximate-coret algorithm in NP which satisfies the completeness condition of Def. 19 We first present the main steps of the algorithm, then show that they can performed within NP and finally check the correctness of the algorithm.
identification algorithm. In particular, the main objective of the proof is identification algorithm in Def. can be used construct an
First we notice the following. If there exists a learning algorithm Ag which solves the identification task in Def. & for the concept class F. then the identification task even for the concept class F defined as follows:
casily construct algorithm Ag that can solve
== 1) 10 Va (0. 1)"h
(42)
Specifically, the algorithm Ag solves the identification task for the concept class FF by flipping the labels of all points in the input dataset before applying Ag.
We are ready describe the algorithm A We notice that having access to the algorithm Ap in Def. 8 we can implement the following function which, given dataset T = {(E,, Me) 1,8 of 3B inputs and a label a corresponding to one of the concept, detects if there is subset TB of of inputs not consistent with Consider an algorithm Ag in Def. 8 and let e. be c min(e1, 62), with ej
and E2 the error values in the conditions of Eq. (68) and (69 of Def. Then we define the check function follows.
28

---

Published as a conference paper at ICLR 2026
function CHECK(a; T)
2: for T3 in T
3:
for r in R
4:
if (TT, te; ā return "invalid dataset"
5:
end function
The function check can be implemented by polynomial time algorithm running in the second level of the PH. In order to prove it, consider the following set:
Si (a, () (T { v ) BB 3r R, (:)).. TB T s.t. AB(TB, = ā
(43)
The set (i contains all the datasets T for which there exists at least one subset of B inputs TB and a random string E R such that (,,,,,,,,.) = ã. Note that for the property of Eq. (68) in Def. Bf approximate-correct identification algorithm, dataset of 3B inputs entirely consistent with not contained in (a. 3). On given input dataset = { (Ir, y/ W the algorithm check decides if the dataset T belongs to (a 3) or not. Deciding if a set 7 belongs to S (a, (a, ()) can be done in NP as a YES instance can be verified in polynomial time if AB runs in polynomial time.
We construct the algorithm Age as follows.
1:
function A (T,
2: @: @ **--aa(1 r, & with A&B the approximate-correct identification algorithm in Def.
3: if check(a, T) "invalid dataset"
4: return "invalid dataset"
5: else return a
6:
end function
We now show that, for c-distinct concept classes with c 2 1/3, the algorithm A described 1:) above rejects any dataset {x.,, with B or more inputs not labeled by fa, Thus, the constructed Aln satisfies the soundness condition of the approximate-verifabb algorithm as in Def. 19 First, if there exists subset TB C T such that every point in it is labeled by ʃa, then there exists a random string and value 6 S f2 such that (B(TB, 6, r) = a' with the condition (o- (f)) - f (x)) < 3- However, since by assumption all the concepts differ one from each other on more than 1/3 of the inputs, then AB(T',, = &. It follows that the function check will successfully detect and discard any input dataset that contains B or more inputs not labeled by a. Therefore, for any input dataset of 33 or more inputs the algorithm Ag satisfies the conditions in Def. 19 approximate-verinee verifiaalee algorithm.
As anticipated in the main text, we provide here an example of a 0.5-distinct concept class, which therefore satisfies the condition of Theorem 13 where the concepts are all (Promise)BQP complete functions.
Definition 20 (0.5-distinct concept class with BQP concepts). Let f be PromiseBQP complete function as in Def. 13 on input E (0. 1) Then for any f there exists concept class F containing 2n CaomisBBQP-copleee concepts defined as:
F= ff 10, 1)" + (0,1) a {0,
(44)
f : > f(x) @ xa)
(45)
where a is the bitwise inner product modulo of the vectors a and x.
Clearly for any a1 ag E {0, 1)" an a2 it holds that fm (x) (x) on exactly half of the input v, also they are all PromiseBQP complete functions as by evaluating one of them we can easily recover the value of (x)
29

---

Published as a conference paper at ICLR 2026
Theorem 14. If there exists an approximate-corvet identification algorithum Ag in Def. & for an seeragg-case-smooeee concept class F, which works correctly for a dataset of size B, then there also exists an approximate-verifann algorithm A as in Def. 19 in NP which works correctly for dataset of size 3B.
Proof. The proof is analogous to the one of Theorem 13 In particular we again leverage the existence {z 3:) } of 3B inputs contains a fraction of
of the algorithm AB to check if dataset B inputs not consistent with a previously outputted a. Since now the concept class satisfies the condition in Def. [6] in order to check a set Ta of B inputs from T are labeled by l sufficient to check if d(AAp[ B, e,r), I 1/3, where d is the distance function in Def 6 By the second property in Def. 8 if all the imputs in TB are consistent with fo, then there exists a r such that d(AA (TB, c, r),
1/3 for any 62 in Def. 8 The proof then follows the same structure that of Theorem 13 with the only change being in the check function, which is now defined as follows.
1: function CHECK(a,
2: for Ta T
3: for r in R
4: if d(AA((TB. Ec, r), s 1/3 return "invalid dataset"
5:
end function
As it was the case for the c-distinct concepts, even for the average- canggge-aas--smeee smooth concept class we present concrete example of quantum functions which satisfies the average-case-smovn condition.
Lemma 1 (Average-can) searage-case-smoott quantum concept class). Let E {0, m poly(n), and i(x) = in|( [log m m]]), then the concept class:
== 10, + (0,1)
| a 13")
(46)
fa {or (acta) ifi(z) m
(47)
else
average-case-smonte and it can be efficiently implemented on quantum computer.
Proof. We first show that for any different a and a' the functions fa and fa' satisfies the definition
of saarrg--aas-smmothhee in Eq. (5). From the definition of fa in Eq. (46). and recalling that the
Hamming distance between two bitstrings a and a' is defined as d(a, a') == - Hi E [m]] : a # a we have that:
Ez (eeuunr((o.ppp))/00 5 (x) (x)x
Σ
(1"(x) - l (x) (x))
(48)
2n
=E(0,1)"
Σ
Σ
(49)
2"
(E
=E(0.1)m-i
(i (110) -n
(50)
2"
(E(0.1)
1
Σ
[f f (40)
(51)
2
1E
1
0.
(52)
2
m d(a,a')
(53)
20
Where і|2 is the concatenation of the bitstring i and z. Since / [log mi), we have 2/-1 < m S 2! therefore:
E (on. fr (x)) 2 d(a, a')
(54)
30

---

Published as a conference paper at ICLR 2026
So proved that indeed the concept class F satisfies the average- satege--css--mothheee in Def.
We now present an easy implementation for the functions fo on a quantum computer. For any concept f", encode in an m-qubit computational basis state:
(W) = (ai) @ ... @ lam))
(55)
Then the concept f can be implemented as:
(x) (1aa (xx) (ba)
(56)
Where for i(x) I m.
O(x) = [(((())11) @ z m=)((
(57)
while if a(x) > m we define (x) = O.
We notice that the functions considered in the above construction are obviously classically easy. However, one could consider the tensor product between the register (a) and second register undergoing any BQP hard computation, in direct analogy with the construction used in the proof of T'Thorrem 15] That would construct a concept class of BQP function satisfying the average-case- smooth property, and therefore our Theorem 10 would apply.
G SOME IMPLICATIONS OF OUR RESULTS
In this section, we discuss the connections between our theoretical findings with other well-known physically relevant tasks: Hamiltonian learning, the learning of parametrized observables and the learning of order parameters. We also present a physically motivated concept class to which our hardness results apply directly and where a quantum advantage achieved. Moreover we provide a list of example of physical processes which give rise to BQP functions and practical settings where the identification task naturally arises.
For Hamiltonian learning, we clarify why efficient classical algorithm for the identification task remains feasible. We then show how our results demonstrate the hardness of the identification task in learning parametrized observables. Finally, we discuss the connection to the task of learning of order parameters and the potential for quantum advantages therein.
G.1 HARDNESS OF IDENTIFICATION FOR A PHYSICALLY MOTIVATED BQP-COMPLETE CONCEPT CLASS
In the recent work Molteni et al. 2024) a physically motivated learning problem for which learning separation was proved. Importantly, the classical hardness for the task was achieved by considering concepts being BQP-complete functions as in Def. 13 and then arguing that a classical learner would not be able to evaluate such concepts unless BQP C P/poly. An interesting question is whether the classical hardness could arise already from identifying the target concept that labels the data, rather than only from evaluating it. Using the results in Scction[5] we can answer this question in an affirmative way for subclass of problems for which the hardness of evaluation holds. Let us restate the learning problem presented in Molteni et al.] (2024) and show how our results in the previous section apply it. The learning problem considered is described by the following concept class:
Fu,0 (x) R a [-1,111
(58)
with: (x) x (0. + (x) (x)pa)
0(a)= = Σ a.P.
Where Po (x) is a "classically hard to compute" quantum state (i.e., certain properties of this state hard to compute) depending llr where H is a local Hamiltonian whose time evolution is universal for BQP Feynman (1855... As each P; represents kllocal Pauli string, the function, fa is BQP-complete function
{0. 1}" An example could be pu (v U (x) (x: Ut with
31

---

Published as a conference paper at ICLR 2026
for some values of For example, for the a which corresponds to 0(az)= - I the function f is exactly the function which corresponds to the time evolution problem in the literature Kitaev et al. (2002), which is known to be universal for BQP. This already motivates the classical hardness of the learning task under the assumption BQP g P/poly as the classical learner is required evaluate a correct hypothesis on new input data. We now argue that concept classes of the kind Fu,O are also not classically identifiable as in Def. 8 In order to show it, we will consider a particular construction for the quantum states po (ar) and observables O(a) such that the corresponding concept class FŪ,O satisfies the definition of c-distinct concept class in Def. 5 with c 1/3.
It is important to note that in Molteni et al. (024)) a quantum learning algorithm was proposed that solves the task by first identifying a sufficienlly good a, and then evaluating the model using the identified a. As such, the quantum algorithm also addresses the identification task. Furthermore, as demonstrated in Molteni et al. (2024), the algorithm remains effective even in the presence of noise in the training data.
Theorem 15. Under the assumption (BQP, Unif) & Heur there exists a family of unitaries (U(x)) and observables {O(a)) a such that the corresponding concept class FUO is not classically identifiable by an approximate-coree algorithm as Def. but is identifiable by quantum learning algorithm.
The key idea of the proof is to construct particular family of quantum states py and observables O such that the corresponding concept class in Eq. (58) contains c-distinct concepts with 2 1/3. We achieve this by leveraging the Reed- -oed-Solomon code to construct functions that differ from each other on at least 1/3 of all the input x. As this is still an instance of the same category of concept classes as studied in Molteni et al. (2024), the quantum learning algorithm from this work will solve the identification task, and also the corresponding evaluation task.
We give here the complete proof of Theorem 15
Proof. Let us first introduce the set of 3n classical functions {f defined as follows:
0 if x $ C2 1,xx) = [1)(z) - =
(59)
-zx()) E
Where Lj- = {ın,, Tf+1..... F542" /3m denotes the j-th block, a contiguous subset of 2" elements selected from the set of all possible æ E (0. 1)", according to a predefined order. We then consider the Sred-Solomon code Wicker & Bhargava (999) ks) [k]) defined over field with q 2 elements which maps a message le of length [ into a codeword of length 3 Aé]. Let us consider m and |k| such that = [k| m. In this way the minimum distance between two different codewords is lower bounded by d 2 3|k| - k + 2 2/k| + 2 [k). This corresponds to a Hamming distance greater between the bitstring representation of codewords corresponding to two different
3n
than d 2 [ messages A: and k'. Next, we define the function g 10" + {0, 10.m as the function which maps the bitstring representation of the message k into the bitstring representation of its codeword of the previously introduced [. [k() code. In this way, du (g(k), (K)) 2 n for every k + k', where dh
stands for the Hamming distance between the bits given by the function g. Consider now the family of 2" functions {ha]2" defined as:
3n
hx(x) = lo(k) (z)
(60)
It is clear that for diffferent le each function hy will differ from the others on at least 3 distinct values of x E {0, 1)". We now want implement the functions h& in the form of the concepts in HHO We can do so by considering a register of 3n x n qubits. On each of the 3n registers the function fz in Eq. (59p is implemented by measuring the Z observable on the first qubit after having prepared corresponding state Pj (z). In particular the unitary U is the tensor product of each U, acting on the j-th register of n qubits, with j = 1,2,... ..., 3n. Each U, is such that:
f5() = (arl UJ UU (x)
(61)
32

---

Published as a conference paper at ICLR 2026
where Z1 represent the Z Pauli operator acting the first qubit of the j-th register. We note that since classical computations are in BQP such a unitary always exists. Let us consider then the following circuit composed of 3n + register of qubit each. On the first register the imput dependent state (x) undergoes an arbitrary BQP computation and the observable Z is measured on the first qubit. The other registers implement the functions fy as described above. As they are classical functions, they can also be implemented quantumly. Next we define the required set of observables {O(a) defined as:
3n 7mj+1
O(a) Z1 +
Σ f=1
(62)
where Z, represents the Pauli string consisting of identity operators on all qubits except for the Z matrix acting on the i-th qubit. Each concept in fa E F is now expressed as fo (rrfp(=)) where p(z) represents the quantum state formed by the tensor product of the previously described 3n + registers, and O(x) defined as in Eq. (62). Specifically, p(x) is defined as follows:
if = 1: (xx) (ax)= (66) (1b12 with (e) = UBQr (a))
p Py(x), Pj
(63)
if j p5(z) (15) (1bly with (w) = U, (a>)
where U UBQP represents any arbitrary BQP computation while {Ug}, are the unitaries associated to the functions/ fj as defined in Eq. (61).
If we now consider the concept class
- a= (k) Ak E 10,
(64)
where the functions f and g defined above, obtain concept class F such that for any pair of different 1, 02 the corresponding concepts differ on at least 2n 2²/3 different inputs x E {0. 1)
Therefore the constructed concept class is c-distinct concept class as in Def. 5 with We can then apply our Theorem 13 and construct an approximate-veriiabb algorithm from an approximate-coree
1/3.
identification algorithm as Def. g which correctly solves the identification task for F by using an NP oracle. Moreover, as there is at least a PromiseBQP complete concept for a- = QtI for Theorem 11 if there exists an approximate-verifaabl algorithm which runs in the second level of the polynomial hierarchy then BQP would be contained in the fourth level of the PH. We can therefore conclude that the constructed concept class F is not learnable even in the identification sense with an approximate algorithm which satisfies Def.
We note here that, although the task defined by the concept class in Eq. is general and include many physical scenarios as motivated in Molteni et al. (2024). the specific choice of unitaries {U(x)} a and observables {O(a)) Ja used in the proof of Theorem 15 purely technical, intended to ensure the concept class is 1 1/3-distinet.
G.2 HAMILTONIAN LEARNING
Hamiltonian learning is well-known problem which, arguably surprisingly, admits an efficient classical solution. Moreover, the Hamiltonian learning problem can be easily framed as a standard learning problem within the PAC framework, revealing clear connections to the identification task discussed this paper. Although the underlying concepts may initially seem inherently quantum, the existence of efficient classical algorithm for solving the problem raises the question of why our hardness results do not extend to this setting. In its main variant, the task involves reconstructing an unknown Hamiltonian from measurements of its Gibbs state at a temperature T. Specifically, given an unknown local Hamiltonian of the form H (A) Σ, A,P,, the goal of the Hamiltonian learning procedure is to recover À from measurements of its Gibbs state p(3. 2) at temperature T:
3H(A)
p(B, A) Tr[ceH(A]]
where 3 = 1. In Anshu et al. 22020), the authors proposed a classical algorithm capable of recovering 7. the unknown Hamiltoman parameterized by À using a polynomial number of measurements of the
Ie do note that, even for most values of O, we still expect the corresponding concepts to be PromiseBQP-complete.
33

---

Published as a conference paper at ICLR 2026
local Pauli terms {Pi) that constitute the target Hamiltonian H()) = E, A.P. In Haah al. (2024), an also time-efficient algorithm was proposed. The above task can be reformulated as an identification problem by considering the following concept class:
F3 = ()) X E
(65)
with:
(xx) x X S 10, (Tp(B,
poly(n)
( =
Σ PrPi.
Then given polynomially many training samples of the kind T (( it is possible to recover the expectation values of the local Pauli terms {P:} J and therefore the identification problem can be solved using the learning algorithm in Haah et al. (2024) for learning the vector X.
We now provide a list of incompatibilities between the task of Hamiltonian learning and the identi- fication task considered in our results, and examine them try find the crux of the reason why Hamiltonian learning remains classically feasible.
Hamiltonian learning is a regression problem. It important to highlight that the concepts in Eq. (65) are not binary functions, they in theorems, but rather form a regression problem. We note that this categorical difference alone is also not the end of the explanation. It is in fact possible "binarize" the concepts in the following way:
(xx (xr EC (0, (0, 1)
logg + bin [T|p( ()0())))))))))))
(66)
where bin y. returns the i-th bit of y. Hamiltonian learning algorithm can still be used to determine the unknown A. This can be done, for example, by considering an input distribution that focuses on exploring the most significant bits of the extreme inputs where the observable (ax) reduces to a single Pauli string, specifically inputs a E (0, 1]" with Hamming weight 1.
The concepts are not BQP-hard. The concepts in Fa. binarized as in Eq. (66). involve measurements performed on Gibbs states. For large values of 3, these states closely approximate ground states, which might suggest a connection to tasks where quantum computers are expected to outperform classical ones. However, regardless of how hard it is to estimate expectation values from cold Gibbs states, it is important to clarify that each concept associated with a fixed Gibbs state, and the input æ E {0, 1)3 simply determines the observable being measured. This is similar to the "flipped concepts" case studied in Molteni et al. (2024). It is easy to see that a P/poly machine can compute these concepts given the expectation values of the (polynomially many) Pauli strings { (Pt), ) as advice, due to the linearity of the trace. Thus, the concepts we have here are somewhere in the intersection of P/ poplyy and BQP-like problems (depending Gibbs states we are dealing with, let us call the corresponding class A, where A could be QXC et al. (2224) ). However, even this is not sufficient to full explain the apparent gap between our no results and the efficiency of Hamiltonian learning. In our proofs we worked towards the (unlikely) implication that BQP was not heuristic version of a level of the PH. Here, we can construct fully analogous arguments and obtain the implication that, e.g.. P/ p/poly
what temperature
in PH, and we also have no reason to believe this to true. Indeed, proving that this inclusion holds would, to our understanding. constitute a major result in quantum complexity theory. The reasons why the no-go's do not apply are more subtle still.
Hamiltonian learning algorithm doesn't 't satisfy the assumptions of the right type of identification algorithm. It is clear that the Hamiltonian learning algorithm does not satisfy the conditions an approximate-verifiabl algorithm in Def. 19 as fails to detect datasets that do not contain enough inputs labeled by a single concept it always outputs some guess for the Hamiltonian. However we could again try to circumvent this issue by employing the constructions from Theorem [3 or Theorem [4] to construct approximate- verifiable identification algorithm somewhere in the PH. which would again suffice for a likely contradiction. However, is important to note that in normal Hamiltonian learning
34

---

Published as a conference paper at ICLR 2026
settings neither of the two Theorems apply. The theorems require that concept class must either consist of sufficiently distinct concepts (Def(5) or exhibit average-case smoothness (Deffo). On the face of it, neither of these conditions seem to hold for the concept class in Eq. (65 and it is not clear how one would go about attempting to enforce them. This final point is in view at the crux of the difference between the settings where our no-go's apply and Hamiltonian learning.
While we leave the investigation of the hardness of the Hamiltonian learning task as a potential direction for future work, already at this point an interesting observation emerges. It is natural question if the conditions of the two Theorems 13 and 14 could be relaxed and generalized, which would lead to the hardness of identification for broader classes of problems. Due to the analysis of the Hamiltonian learning case we see that if one could generalize the settings to the point they apply to Hamiltonian learning, since Hamiltonian learning classically tractable, this would imply very surprising results in complexity theory (see second bullet point above). We see it more likely that this a reason to believe the range of generalization of the settings where identification is intractable is more limited and will not include the standard settings of Hamiltonian learning.
G.3 THE CASE OF LEARNING OF ORDER PARAMETERS
Another physically meaningful problem that can be framed as an identification task is learning the order parameter that distinguishes between different phases of matter. Consider, for example, a family of Hamiltonians { [ (x)) parametrized by vectors æ E 1-1,1]" where the corresponding ground states exhibit distinct phases depending the value of æ:. In many cases, such symmetry -brekking
phases, there exists local order parameter of the form O = >x ar,,, whose expectation value on a given ground state reveals the phase to which it belongs to. The task is to learn the order parameter from a collection of samples [(((#)) Je) where each p(æ:z) represents the ground state of the Hamiltonian Hæz), and yr denotes the label identifying its associated phase. We can formalize the problem by considering the following concept class:
F. = (1 |a [-1,1]]]
(67)
with: (x) : x EENE (0. 10. + (raa)))0((a))
0 - Ea:P.
Learning the correct order parameter from ground states labeled by their phases can be framed as machine learning task, where the goal is to identify the underlying labeling function. Specifically, given training data of the form T {(x,, Tr(p(æz) ((()))) the objective is to recover the correct parameter ax that enables accurate labeling of the ground state p(x::) corresponding to the Hamiltonian H (xx). In other words, the task reduces to identifying the correct order parameter O(a*). In this setting, the value (r(p(())) I] acts as a phase indicator. For instance, in systems exhibiting two distinct phases, the sign of Tr(p(x:) ((x))( serves to distinguish between them. In case the ground states of the Hamiltonian family (H(x)) J are computable in BQP, then the quantum algorithm from Molteni et al. (2024), which solves the identification task for the concept class in (5)) can also be employed to solve the learning problem defined in E6, thus enabling the recovery of the correct order parameter. In the general case, however, the concepts in Eq. (67) compute expectation values on ground states, task that for general local Hamiltonian is in QMA-hard, but the situation is actually more involved.
First, we note that the closely related task learning of phases of matter given the shadows of the ground states - so where the data consists of pairs (a(p(z)), phase(x)), where a(-) denotes the classical shadow of state, and "phase" assigns binary label specifying the phase is classically easy, even for many topological phases of matter |Huang et al. (2022). In this case, the task is to assign the correct phase to a new datum which is a shadow of different from the setting we consider here, where we explicitly deal with the specification x of the Hamiltonian; that is, pairs (x. phase (x)) While Huang al. (2022) also shows how mappings x + o (p(x)) can be classically learned as Tong as the Hamiltonians specified by all æ are within the
state given as (p(x)). This is
Also, the setting in Huang et al. (202)) do not explicitly find the observable, which is the order parameter, although we suspect this can he computed from the hyperplane found by the linear classifier.
35

---

Published as a conference paper at ICLR 2026
same phase, the identifying of phases requires the crossing of the phase boundaries, and it is not clear how the approaches could be combined.
To analyze the perspectives of classical intractability and then quantum tractability of this task from the lens of the work of this paper, we analyze the key criteria. First, for our hardness results to apply at all, the concepts in the concept class should be sufficiently hard, in tomplexity-theoretic sense. That is, the functions that we consider x -> Tr(p(=)O((e) should be classically intractable, yet quantum easy. In general, this is easy achieve: by using the standard Kitaev circuit-to- Hamiltonian constructions we can construct Hamiltonians whose ground states encode the output of arbitrary quantum circuits (here encoded in æ). as was used in Molteni et al. (2024). However, from the perspective of phases of matter identification, it is important to notice that such BQP hard Hamiltonians are critical: they have an algehraically vanishing gap, and it an open question whether in this sense BQP hard Hamiltonians could be gapped at all (oonzlee-- & Cubiti (2018). At least in the cases of conventional phases of matter (symmetry breaking, even topological), the phases are typically characterized by constant gap. This suggests that the "hard computations" could only be happening at (or increasingly close to) the phase boundary.
However, we are also reminded that the observable we need to ultimately measure has meaning: it the order parameter. This has an interesting implication. We are interested in the setting where the function + Tr[p( ((fp())(((()) [a)) corresponds to, intuitively, the characteristic function of some BQP(-hard) language L. But since this function is also the order parameter, the yes instances of the language (æ: E Lyes) must correspond Hamiltonians in one phase, whereas the no instances must correspond to the other. This observation allows for simple cheat, as it highlights the importance of the mapping æ + (x), which we have the freedom specify. One can conceal all the hardness in this map and simply choose it such that H (x) is some Hamiltonian in one phase for æ E Lyss and in another for the rest. This is of course unsatisfactory as involves a highly contrived parametrization.
For natural, smooth parametrizations of the Hamiltonian space, we do need to worry about the constant gap property and so it is not clear whether hard functions emerge in standard settings. If, however, we move to more exotic systems, e.g. general critical systems, systems with complex non-local order parameters and dynamic phases of matter, becomes more likely that the right theoretical conditions arise even with natural parametrizatiins.
The hardness the concepts will ensure the hardness of evaluation-type tasks which is the first step. To achieve the hardness of identification, we need more, i.e., either c-distinct concepts smooth family. Learning of order parameters is a closely related task to the learning of observables, and as discussed in Section G.1, for this more general case it is possible to construct cases that satisfy all the desired assumptions. Whether similar conditions will also be met for some natural settings involving exotie (or standard) phases of matter remains a target of ongoing research.
G.4 PRACTICAL RELEVANCE OF OUR RESULTS
Although our definition of BQP-complete functions in Def. 13 may seem abstract and distant from what it can be found in practical experiment, remark that many relevant physical processes have been demonstrated to be oQp-complete. For example, estimating expectation values on time-evolved states shown to be BQP-complete for many physical Hamiltonians:
Various variants of the Cose-Hubbard model Childs al. 2013
Stoquastic Hamiltonians Janzing & Wocjan 2006).
Ferromagnetic Heisenberg model Childs et al. (0013
The XY model Piddock Montanaro (0155).
Estimating the scattering probabilities in massive field theories Jordan et al. (2018).
(more precisely, estimating the vacuum-tor socuum-to-vacuum transition amplitude, in the presence of spacetime-dependent classical sources, for a massive scalar field theory in (1 + 1) dimen- sions).
Simulation of topological quantum field theories Freedman et al. (2002).
Note that we could encode universal quantum computations in complex enough glohal measurements.
36

---

Published as a conference paper at ICLR 2026
On top of those, problems from other fields quantum chemistry and topological data analysis have been proven to be BQP complete, for example:
Electronic structure problem O'Gorman et al. 2021) for quantum chemistry.
Computing the persistence of Betti numbers Gyurik et al. (2024)
Any learning problem related these processes involves BQP-complete functions, to which our results apply.
In addition the task of learning an order parameter, we highlight several other scenarios that can be naturally modeled within our framework of the identification task.
First, beyond the of exactly identifying unknown order parameter, framework also applies when the order parameter known but the corresponding observable is not directly implementable. In such situations, our approach enables the identification of suitable "proxy" observable that captures the relevant information.
When considering unitarily parameterized observables, time evolution under a parameterized Hamiltonian can viewed as part of the measurement process. This allows our framework to encompass cases in which parts of the quantum dynamics are unknown, even though the final measurement setup is fixed, thus covering a broader class of partially unknown observables.
Identifying an unknown measurement is also crucial in experimental settings where in- complete device characterization means the actual measurements performed may deviate from the intended ones. This is especially relevant in quantum computing, where noise and imperfections in measurement devices are common, making it important to understand and mitigate their impact.
Finally, note that the problem of learning unknown measurement has been extensively studied in the literature under the name of quantum measurement tomography Luis & Sánchez-Soto (1999): Lundeen al. (2009), further underscoring the practical relevance of this task.
G.5 BENCHMARKING AGAINST CLASSICAL METHODS
In Appendix G.I we describe an example of identification task that is classically hard yet solvable by quantum computers. It is natural to ask how the theoretical guarantees manifest when actually solving the task on quantum and classical devices. However, implementing this for BQP-complete functions and, more importantly, benchmarking it against the best classical learning algorithms in a provably rigorous way presents distinet challenges. Specifically, the identification task requires the learner to take an entire dataset as input and output only the description of the labeling function. It is unclear how classical methods could perform such training which loss function would be appropriate. One possible approach is to design the learning algorithm so that a tentative labeling function tested by evaluating it on different inputs and comparing the results with the training data. However, this would require the target functions to be classically computable, which is ruled out by our focus on BQP-complete functions. Ultimately, the desired algorithm should be analogous to Hamiltonian learning, where, given complete dataset of expectation values, the output is description of the unknown Hamiltonian. Our theoretical results rule out the possibility of the existence of this kind of algorithm for learning problems involving
important to emphasize that
functions. Thus, the most promising approach for designing classical algorithm is dequantize the procedure in Appendix G.I for the identification of the observable. This, however, would require a highly efficient simulator for quantum computations, with runtime scaling as poly(n) + 20 (where is the number of T-gates and w the number of measured qubits). In particular, this implies scaling as poly(n) + 20.3t For simulation problems with around 300 qubits, and assuming a linear number of T-gates in the qubit count (which is reasonable for the BQP-hard computations classical steps, clearly infeasible, while a fault-tolerant quantum computer could handle the task without difficulty.
interested in our results), this already yields around 2 ~ 1031
37

---

Published as a conference paper at ICLR 2026
H DISCUSSION ON THE ASSUMPTIONS OF THE APROXIMATE--ORREE ALGORITHM
For convenience, report here the definition of approximate-corect algorithm stated in the main text in Def. 8
Definition 21 (Identification task non verifiable case ). Let F (f {0. 1)" - 10 a e {0, } be concept class. An appreximate-correet identification algorithm is a (randomized) algorithm As such that when given as input a set T = { ]= of at least B pairs (r,y) E 0 and random string R satisfies the definition of proper PAC learner (see Def. 4) along with the following additional properties:
{0. 1)ah x {0,1] 1}, an error parameter
If for any a all the (æe, ye) E TT' are such that y + (xx) then there exists an Ej such that for all S and all r E R:
AB(T, + a.
(68)
Therefore, for no dataset the algorithm can output a totally wrong a, i.e. an a inconsistent with all the inputs in the dataset.
2. If {( W is composed of different inputs æy and if there exists such that the corresponding labels follow y/ = f (xz) for all (æz, yt) E T, then there exists a threshold 22 such that for any cg there exists at least one E R for which:
An(T, = 02
(69)
With the condition: (utt))) (())
Therefore, if the dataset is fully consistent with one of the concept a, then there is least one random string for which the identification algorithm will output a ā closer than 3 in PAC condition to the true labelling a.
We say that Ag solves the identification task for concept class F under the input distribution D if the algorithm works for any value of e 2 O. The required minimum size B of the input set T is assumed to scale poly(n.1/e,1) while the running time of the algorithm scales as poly B, n). Moreover, the and E2 required values scale at most inverse polynomially with n.
We observe that an approximate-correc algorithm is, by definition, a proper PAC learner as in Def. 4 and thus guarantees hypothesis with accuracy within poly(z)' In addition to this, we also require it satisfies the two extra conditions specified above. Although the two additional conditions are introduced for technical reasons required by our proof strategy, they are also designed to reflect what one would reasonably expect from any practical learning algorithm. The first property ensures that if the input dataset consists entirely of inputs labeled differently from a given concept, then the it never "totally incorrect". The second property
algorithm will not output that concerns the case where all points in the input dataset are labeled consistently with a particular concept. In this case, the algorithm required to output a concept that is "close" in the PAC sense for at least one random string, regardless of the distribution from which the training set was drawn. We therefore view the two conditions as natural and rell-vooivatte requirements for a learning algorithm. Moreover, while the second property closely resembles the condition for proper PAC learning in Definition
+ with the key difference being that the training set need not be drawn from a specific distribution we present simple example of concept class where a proper PAC learner would also satisfy the first property with high probability. Consider a concept class F = {oo fi} consisting of two functions such that fo(x) f fi( for every E {0, 1)". In this case, any dataset that does not contain inputs labeled by fo is fully consistent with fi, and vice versa. As a result, a proper PAC learner would, with high probability, output the concept consistent with the dataset, rather than the one that is entirely incorrect. This simple scenario changes in the presence of a larger concept class. When multiple concepts are involved, a dataset that is totally inconsistent with one concept may still not be fully consistent with any other. In such cases, a proper PAC learner, without the additional assumption from Def. g has no guarantees on the concept outputted.
38


Reviews:
[{"review_id": "W5kQRln0HR", "reviewer": "Reviewer_nGtx", "summary": "This paper studies quantum-classical separation for the identification problem. Learning advantages for quantum functions are shown under complexity-theoretic assumptions. This is a problem in the context of PAC in learning theory, where the objective of the learner is to identify if a given labeled dataset is predictable with any member of a concept class of functions. \n\nThe authors prove a series of interesting results, for instance, showing that quantum functions are not randomly generable unless BQP is in the second level of the polynomial hierarchy.", "questions": "Can elaborate on how your results can contribute to classical quantum separation in the context of the PAC learning framework?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this is a solid paper studying an interesting problem regarding the quantum-classical separation under a complexity theoretic framework.\nThe authors establish a set of theoretical conditions under which such separation arises in learning problems, offering a solid foundation for understanding the boundaries between classical and quantum computational capabilities. In addition, the paper explores a few relevant applications where quantum-classical separation may manifest, providing practical contexts that highlight the significance of the results.", "weaknesses": "While the paper presents strong theoretical contributions, its accessibility may be limited due to its specialized focus and technical depth. The exposition appears tailored primarily for experts in quantum computing and theoretical learning, which could pose challenges for the broader ICLR audience. To enhance its impact and reach, the paper would benefit from revisions that clarify key concepts, provide more intuitive explanations, and better contextualize the results within mainstream machine learning frameworks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TtFValHYeX", "reviewer": "Reviewer_yvqS", "summary": "A central question in quantum machine learning is to determine which learning problems admit a genuine quantum advantage. In recent years, there have been rigorous proofs of quantum advantage for learning properties of functions, typically relying on the classical intractability of evaluating the labeling function. In this paper, the authors instead focus on the identification task—the problem of identifying the correct label from a dataset—which has not been thoroughly explored in prior work.\n\nThe authors provide the first rigorous proof of a quantum advantage for identification learning under well-founded complexity-theoretic assumptions. In particular, they show that if BQP is not contained in HeurBPP^NP^NP^NP, then there exists a family of quantumly-samplable functions—computable by a quantum polynomial-time algorithm—that cannot be identified by any classical efficient algorithm. The proof proceeds by contradiction: assuming the existence of a classical efficient identification algorithm, the authors construct an evaluation algorithm in HeurBPP^NP^NP^NP, contradicting the initial assumption.", "questions": "Do we have any known separation between HeurBPP^NP^NP^NP and BQP, or we just believe in this separation intuitively?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The authors introduce a new task in quantum machine learning: identifying a function within a given concept class. At first glance, this appears easier than standard learning tasks, which typically require the learner not only to infer the target function but also to evaluate it on unseen data points. In contrast, here a classical learner need only output a description of the unknown function. Surprisingly, the authors show that even this seemingly simpler task remains hard for classical learners when the function is quantum-computable—assuming that BQP is not contained in the fourth level of the polynomial hierarchy.", "weaknesses": "This work lacks sufficient motivation from quantum physics or quantum information. Although the paper is titled quantum machine learning advantages, the main result is proved entirely using classical complexity-theoretic arguments. Specifically, the hardness argument proceeds by constructing a classical algorithm that evaluates the function in HeurBPP^NP^NP^NP, assuming the function can be efficiently identified classically, and then combining this with the heuristic separation result of Ran and Raz between PH and BQP. The authors include several physics-motivated examples of identification hardness in Appendix G, but the arguments are relatively straightforward: Appendix G.1 closely follows the approach of Molteni et al., while Appendices G.2 and G.3 present heuristic arguments that are not clearly explained or integrated into the main text.\n\nIn addition, the treatment of complexity-theoretic assumptions in the paper lacks precision. For example, in Theorem 15, the authors claim the existence of a quantum-computable learning task that is not classically identifiable by any approximately correct algorithm. The proof relies on showing that an efficient classical identification algorithm would imply BQP lies in HeurBPP^NP^NP^NP. However, the theorem’s statement does not explicitly mention any complexity-theoretic assumption, leaving the claim misleading in the standard (unrelativized) world where no such containment is known. Furthermore, while the authors refer to oracle separations between BQP and PH, their proof relies instead on the assumption BQP not in HeurBPP^NP^NP^NP, which is a heuristic class not known to be contained in PH and about which relatively little is understood. Clarifying these assumptions and aligning the theorem statements accordingly would significantly improve the precision and correctness of the presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BEJZc4Wcr6", "reviewer": "Reviewer_3GcN", "summary": "This paper proposes a new regime of quantum machine learning that focuses on potential advantages in solely the learning/training step while foregoing the testing steps. The authors analyze the hardness of the learning task itself with theoretical learning frameworks (proper PAC learning) to hypotheses in complexity theory that are believed to be true (BQP not contained in the second level of the polynomial hierarchy). Their main result shows that there exists a broad class of identification tasks of quantum functions that are quantumly-easy and classically hard.", "questions": "1. How applicable are the main theorems to existing QML problems? The paper shows that Hamiltonian learning does not apply, but how does the results apply to problems like state/process tomography, circuit learning or (quantum-assisted) circuit compiling?\n2. Does the paper provide any implications on QAOA-type algorithms, which has been shown to be universal?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper shows that quantum-hard functions are not generally classically generatable, and certain quantum generated data may only be learned by quantum learners.\n2. Formal connections of learning theory and complexity theory regarding this task are constructed in this paper.", "weaknesses": "1. While the existence of separations are shown, to my understanding, the paper does not provide a potential path to the construction of a quantum learner that can provide such learnability results.\n2. Minor typo in last line of Appendix A.3: $\\mathtt{HeurBPP}^{\\tt NP}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eWtmdZkZhY", "reviewer": "Reviewer_Wcsz", "summary": "The authors provide a theoretical proof of the hardness of a class of identification problems, thus constructing a classical–quantum separation in the context of PAC learning theory under widely believed complexity conjectures. This result can be considered a generalization of Huang et al. (2021) and Gyurik and Dunjko (2023), and it deepens our understanding of the power of data in quantum learning algorithms. However, for the reasons below (please refer to the Weaknesses section), I cannot recommend accepting this paper in its current form. If the authors adequately address my concerns, I may change the rate.", "questions": "Here are some questions:\n\n1. Can the authors give some examples of the average-case-smooth concept class, especially in the quantum computing setting?\n\n2. Regarding Theorem 5: why does L, unif \\in BPP^{3NP} lead to a contradiction? To the best of my knowledge, the relationship between these two classes is not known.\n\n3. Could the authors provide an efficient quantum algorithm for learning the classically hard cases indicated in Theorem 5?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well written and logically clear. The chosen topic is highly significant, as it helps to characterize the classical–quantum boundary within the framework of computational complexity.", "weaknesses": "1. Regarding your first two results (Theorems 1 and 2): these statements seem quite unsurprising. Since the target function f essentially defines a BQP language, it follows that a polynomial-time classical algorithm cannot generate such samples. I do not find these two results surprising.\n\n2. The main claim appears in Theorem 5, which establishes classical hardness. But to demonstrate a classical–quantum separation one must also show an efficient quantum algorithm. In fact, even if f is produced by a quantum device, that does not imply a quantum-machine-learning (QML) algorithm can solve the problem. For example, if the dataset encodes ground-state properties that reveal complex topological order, QML algorithms might still struggle to recognize it. Thus the authors have only proven classical hardness; they have not demonstrated quantum efficiency. As a result, an exponential quantum advantage is not rigorously established.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)