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

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?

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

• Thanks, indeed I wanted to pose the question like that. I'll wait to see what others have to say before accepting an answer. – domotorp Jan 21 at 19:22