Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

Question

This is another attempt to formalize my former question on the topic.

I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (think around 53), we can achieve a speed-up that is exponential in their number. So if the problem requires time $2^n$ on a classic computer, then I would hope for a hybrid quantum-classical algorithm that uses $q$ qubits and takes $2^{n-q^c}$ time for some constant $c$. Here $c$ is independent of $q$, which can be any number, up to $n^{1/c}$ or so by when the problem becomes polynomial on the quantum computer. Are there such problems?

Answer 1

I think the scaling $2^{n/q^c}$ is too much to ask for. Even $poly(q) 2^{O(n-q)}$ would represent an exponential speedup for each additional qubit.

And indeed, such a problem is known: simulating a quantum circuit of $n$ logical qubits on a small hybrid quantum-classical computer with only few (perfect) physical qubits $q\leq n$ has this scaling. See: https://arxiv.org/abs/1506.01396