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?


1 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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