5
$\begingroup$

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?

Improve this question
$\endgroup$
6
+100
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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 Jan 21 '20 at 19:22

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.