<p>I think the scaling <span class="math-container">$2^{n/q^c}$</span> is too much to ask for. Even <span class="math-container">$poly(q) 2^{O(n-q)}$</span> would represent an exponential speedup for each additional qubit. </p>

<p>And indeed, such a problem is known: simulating a quantum circuit of <span class="math-container">$n$</span> logical qubits on a small hybrid quantum-classical computer with only few (perfect) physical qubits <span class="math-container">$q\leq n$</span> has this scaling. See: <a href="https://arxiv.org/abs/1506.01396" rel="noreferrer">https://arxiv.org/abs/1506.01396</a></p>

CC BY-SA 4.0
2020-01-21T19:22:14.150Z
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
CC BY-SA 4.0
2020-01-21T14:00:28.453Z
2020-01-21T14:00:28.453Z
Martin Schwarz
<p>This is another attempt to formalize <a href="https://cstheory.stackexchange.com/questions/46116/witness-verifiable-quantum-advantage">my former question on the topic</a>.</p>

<p>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 <span class="math-container">$2^n$</span> on a classic computer, then I would hope for a hybrid quantum-classical algorithm that uses <span class="math-container">$q$</span> qubits and takes <span class="math-container">$2^{n-q^c}$</span> time for some constant <span class="math-container">$c$</span>.
Here <span class="math-container">$c$</span> is independent of <span class="math-container">$q$</span>, which can be any number, up to <span class="math-container">$n^{1/c}$</span> or so by when the problem becomes polynomial on the quantum computer.
Are there such problems?</p>

<cc.complexity-theory><quantum-computing><tradeoff><speed-up>
Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?
domotorp
# Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

(Asked by: username_0 on 2020-01-19)

This is another attempt to formalize [my former question on the topic](https://cstheory.stackexchange.com/questions/46116/witness-verifiable-quantum-advantage).

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?

**Tags:** cc.complexity-theory, quantum-computing, tradeoff, speed-up

---

## 1 answers

### Answer by username_1 on 2020-01-21. Score: 6 | Accepted answer

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>

> **Comments:**
> **username_0**: Thanks, indeed I wanted to pose the question like that. I'll wait to see what others have to say before accepting an answer.  

---

