It's well known that in most (if not all?) computations you can trade time and space resources. An extreme example might be creating an infinitely large lookup table of all composites produced from the multiplication of two primes. Using this table, you could simply lookup the primes for a composite in constant time rather than factoring the composite, which would require superpolynomial time (this of course ignores the initial computation of the lookup table).

But, can all computational resources be traded for time? And, more specifically, can we trade the number of samples required to learn a function for time? Any resources providing a discussion of this (or just a great explanation) would be fantastic. See the background to this question for some more (and important!) context.


In a recent discussion I held that sample complexity (i.e. the data resource) is different from communication, circuit, space, or other time reducible complexity resources. In particular, if some superpolynomial quantum advantage in sample complexity exists for some learning problem (e.g. see this classic paper or this more recent one), then it may imply that there is a difference in the ability of the classical and quantum learners to "see" the information contained in the sample distribution being used to learn some target function. In such a situation, the term "quantum speedup" may not be appropriate – from the classical perspective, more time cannot make up for the lack of data, implying that sample complexity is (or can be) time irreducible.

More recently, I think I've begun to see how the term "quantum speedup" may still be appropriate in describing advantages in sample complexity. As mentioned, my past view was that the data resource is not time reducible, however, I suspect that this may not be correct. In particular, given superpolynomial time resources, a target function may be classically learnable with a polynomial number of samples by their repeated analysis – assuming the polynomial number of samples contains the necessary information for some learner to learn the target function (e.g. a quantum learner, which in this case could be used to prove that the polynomial samples contain sufficient information by some interactive proof with the classical verifier). Were this to be the case, then it is clear that the information to learn the target function does exist in the polynomial number of samples and that the classical learner simply requires (say) superpolynomial time to learn the target function from the polynomial number of samples. This would imply that sample complexity is (at least for some learning problems) time reducible.

Thus the question: Can the classical learner take that polynomial number of samples and, with superpolynomial time, learn the target function at all? That is to say, is it the case that the information is simply not accessible to a classical learner, irrespective of how long you let it compute on those polynomial number of samples (i.e. is the data resource in this context time irreducible)?

I think my initial intuition around the time irreducibility of sample complexity can be summed up by this crude analogy: Where someone with 20/20 vision looking into the distance may see mountains and certain fine details (houses, trees, a radio antenna), someone with 20/80 vision may be unable to see those fine details and only make out the shapes of the mountains – no matter how long they stare at them; they need more data, which in this scenario would mean getting a closer look by physically moving closer (more data) or interrogating their friend with 20/20 vision (interactive proof).

All said, my intuition tells me that the reducibility of sample complexity to time varies by some inherent structure of the learning problem and its interaction with the properties of the type of information one is working with (e.g. classical, quantum), though this is very much a half-baked intuition. Is there a paper where this question has already been answered?

  • $\begingroup$ naive question: what type of "learning" framework are you considering here? You have a training dataset of pairs states/labels $S_{\rm tr}\equiv \{(\rho_k,y_k)\}_k$, and you want an algorithm implementing $S_{\rm tr}\to f$ where $f$ is such that $f(\rho_k)\simeq y_k$ for all $k$? Does the training proceed on single instances of each $\rho_k$, or is coherent processing (i.e. the algorithm is fed $\rho_1\otimes...\otimes \rho_n$) allowed? And the "sampling cost" is essentially then the number of elements in the training dataset? $\endgroup$
    – glS
    Jul 20 '21 at 22:33
  • $\begingroup$ @glS So, hard to read the unrendered MathJax but, I’d say that my interest is specific to PAC learning on classical inputs from which we can learn a (quantum or classical) function that outputs a classification (which could be an observable). The Bshouty and Jackson paper is a PAC model on quantum data, which I think is also what you’re hinting at. In my mind, while the time reducibility may vary by the type of data, to begin I’d be happy with any concrete answer relative to any leaning framework using either classical or quantum data. $\endgroup$
    – Greenstick
    Jul 21 '21 at 1:03
  • $\begingroup$ I’d also be open to a results from more narrow learning frameworks. $\endgroup$
    – Greenstick
    Jul 21 '21 at 1:04
  • $\begingroup$ Why "unrendered mathjax"? It renders fine to me $\endgroup$
    – glS
    Jul 21 '21 at 10:30
  • $\begingroup$ May be a browser issue, though I am using the SE mobile app… $\endgroup$
    – Greenstick
    Jul 21 '21 at 19:57

can we trade the number of samples required to learn a function for time

In general, the answer to this question will be no, because there are two different scaling behaviors being conflated:

a. Sample complexity: The number of samples sufficient to accurately learn a dataset, from any randomly sampled training set.$^1$

b. Algorithmic complexity: Some measure of runtime of an algorithm with respect to an input size.

To be more formal lets consider a learning problem as follows: There is some domain of patterns $\mathcal{X}$ that can be stored and processed classically, and a label function $f: \mathcal{X} \rightarrow \{0,1\}$, and the goal of the learner is to learn some function $h(x)$ that assigns each $x\in \mathcal{X}$ a label $y \in \{0,1\}$. The patterns are accessible by drawing from a probability distribution $\mathcal{D}$ defined over $\mathcal{X}$, and we construct a "training set" $S = \{(x_1, f(x_1)), \dots, (x_m, f(x_m))\}$ for the learner by drawing $m$ samples according to $\mathcal{D}$ and providing their true labels. To incorporate prior knowledge (which we should do, as the No Free Lunch theorem demonstrates) we require our function is taken from some hypothesis class: $h\in \mathcal{H}$. Then the sample complexity (a) is the smallest number $m$ for which we are guaranteed to, with high probability, be able to learn some $h$ that approximates $f$ with small error.

However for algorithmic complexity, all we can really say is there is some parameter $n$ for which a classical learner will require runtime scaling as $C(n)$ to implement any given $h$ on some pattern in $S$ while a quantum learner will require runtime scaling as $Q(n)$.

There are a few comments that I think demonstrate why these should not be thought of as interchangeable:

  1. Fix $S$. Given any algorithm employing a quantum computer (giving rise to a hypothesis class $\mathcal{H}_Q$) to learn $f$ with high accuracy over $S$, you immediately have a purely classical algorithm that performs with equal accuracy on $S$. That classical algorithm learns a function in $\mathcal{H}_C=\mathcal{H}_Q$ by the following procedure: Simulate the quantum learning algorithm on a classical computer.

  2. The opposite of (1) is also true: any classical learner successfully employing $\mathcal{H}_C$ to learn $f$ on $S$ can be reproduced by employing a quantum computer, since quantum computation is universal.

  3. Fix $\mathcal{H}$. The sample complexity for learning $f$ by employing $\mathcal{H}$ may or may not have a clear relationship with $C(n)$ or $Q(n)$. For instance say we are promised that $f$ is a hyperplane in $\mathbb{C}^d$. We fix $\mathcal{H}_Q=\mathcal{H}_C$ to be the set of functions of the form $\langle w, x\rangle$ with $x \in \mathcal{X} \subseteq \mathbb{C}^d$ and $w \in \mathbb{C}^d$. Hyperplane classifiers on $\mathbb{C}^d$ tend to be cheap to implement so $C(n)$ is small, but implementing any specific hyperplane classifier using a quantum computer with $n=\log d$ qubits could require a very deep circuit. But both of these hypothesis classes have equivalent VC dimension and so at least under the PAC learning framework you end up with the same sample complexity.

Also note that in the second reference you mentioned, the authors are very explicit that they wish to compare the quantum learning algorithm to an efficient classical learner for which $C(n) = \text{poly}(n)$, and then describe how no such learner exists for the learning problem they've constructed. If they tried to compare to a classical learner with no restrictions on $C(n)$, then by comment 1 above such a learner is trivial to find. I don't recall seeing arguments related to a sampling complexity improvement for the quantum algorithm, so I would be interested to understand how that figures into the speedup described by the paper.

$^1$ I believe this definition is more common than using the minimum number of samples required to learn a function. I think it is also more useful: If there truly is some minimum sample size necessary to learn $f$, I don't have any guarantee that I draw the corresponding sample from $\mathcal{D}^m$. So at least to me it makes more sense to start with the assumption that you must draw samples uniformly at random from $\mathcal{D}^m$, and then figure out how big $m$ has to be before you can confidently learn $f$.

  • $\begingroup$ Thanks, this is in essence what I was looking for. Do you know of any resource hierarchy theorems that exist in this respect? I realize the PAC models are quite different from the other classic TCS models, but I could imagine a simple construction where you have $S$ drawn from $D$ and some generating function $g$ that simulates $D’$ (with some problem specific time complexity) from which you can draw samples $S’$ that you assume to be i.i.d. with $S$. This would in essence tie the sample complexity to the time complexity of simulating $D$. Does that seem a reasonable way to think about it? $\endgroup$
    – Greenstick
    Jul 21 '21 at 20:13
  • $\begingroup$ Ah, but of course, in the comment above I stripped the essence of the question on trading time for the minimum number of samples. Feel free to ignore the second question — would still be interested in any resource hierarchy theorems were they to exist. $\endgroup$
    – Greenstick
    Jul 21 '21 at 20:20
  • $\begingroup$ so I don't know any theorems relating these two things; again I'm approaching it from the specific angle I've seen in a lot of QML advantage papers (demonstrate an advantage in algorithmic complexity when a quantum subroutine is used in the learning problem). The idea of a sample complexity describing the minimum number of examples needed for a learning task is interesting, but again once you've demonstrated such a minimum for either classical or quantum learners you've demonstrated it for both (with a possibly exponential algorithmic overhead). $\endgroup$
    – forky40
    Jul 23 '21 at 17:55
  • $\begingroup$ so I guess if $m_{q,min}$ is the minimum sample requirement for a quantum learner and $m_{c,min} > m_{q,min}$ is the minimum sample requirement for some classical learner (that doesn't explicitly simulate the quantum learner), I guess your question is whether $m_{c,min}$ can be reduced with subexponential cost to the classical learner; this will be at least highly problem specific but does seem interesting $\endgroup$
    – forky40
    Jul 23 '21 at 17:59
  • $\begingroup$ yes, that’s exactly the question — and agreed, it does seem problem specific. Thanks so much for the responses, this has been a great sanity check. $\endgroup$
    – Greenstick
    Jul 23 '21 at 19:50

Time irreducible & Inaccessibility (philosophical + analytically):

Interesting question! Let me start antichronological with your lovely example. Neal has 20/20 and Peter 20/80. You are saying that Peter needs to get closer to see the mountains and it's infrastructure clearly. So you are changing the equal base condition both had at the beginning. That's okey but how does Peter know there is more to see out there!?

This is a good analogy to our "Problem" related to time. The computational complexity theory is saying that any problem has it's amount of resources needed [such as time and storage] to be solved computational by algorithms. Whether it's worth it is of course another question. The problems get their own classifications etc.. But what really interesting is, is their bounds. For that we are going back to Neal and Peter. Neal is seeing the "whole" location of the landscape, Peter not. Thus Peter can only guess that there is more to see. But will never proof it. Hence, it is only a result of speculation that Peter changed the distance to get within range [of the problem].

The same applies to problems outside the bounds. If one is not within reach of the solution, the existence or the observation of the problem, then one cannot prove it, only guess it. The range is the mentioned "resource" and in our specific question "time". My theory is that problems outside of this bounds can only be discovered by chance (e.g. speculation), can only be solved in a certain time value if one is within reach. In other words, there is a phase of indefinable time to "approach" the problem, but if you are within reach, then the time can be determined and thus solved by algorithms.


There is a period of time when the information is inaccessible to the learner (Until Peter realizes that he has to move or Neal points it out to him.). After that, however, everything will be a matter of polynomial time and the problem will be solved.

Time irreducible (mathematically):

Upper bound: To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n)

Lower bound: To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).

  • $\begingroup$ Thanks for this great response! So, I like your explanation but I don't feel it really answers the question – whether sample complexity is time reducible. In my mind, in the analogy, you could view the situation as a sort of interactive proof: Neal can prove the existence of details of the mountains that Peter cannot himself see and Peter, through a clever interrogation, can verify that Neal is truly seeing what he claims (despite Peter not being able to see it). That would imply time irreducibility – but this is only intuition. It would seem to me this must have already been formalized. $\endgroup$
    – Greenstick
    Jul 20 '21 at 18:41
  • 1
    $\begingroup$ Thank you for your compliment! I understand that! But outside the bounds it when Neal doesn't exist and only Peter is there. A hidden Problem. I also wanted to solve it intuitively. It is clear that there is no right or wrong. I still try to find out whether something like this has already been formulated. Thank you for the enriching discussion and questions! $\endgroup$
    – DEX7RA
    Jul 20 '21 at 18:48
  • 1
    $\begingroup$ Okay, yes, I think I see your point – I need to think about this more. Thanks : ) $\endgroup$
    – Greenstick
    Jul 20 '21 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.