Is it true that for a quantum algorithm to be efficient it must feature a highly entangled state at some point?

Question

I'm wrapping my head around how and why quantum computers can provide advantage over classical. A basic and naive argument is that the dimension of the Hilbert space of $n$ qubits grows as $2^n$. However, without exponentially sized circuits of 1- and 2-qubit gates only a tiny fraction of all the Hilbert space can be reached. Another explanation I have encountered is that it is the entanglement (and not simply a dimension of the Hilbert space) that is the resource allowing for quantum speed-ups. Whether this is true or not I have the following question.

Should one expect that an efficient quantum algorithm will produce a highly entangled state at some point? If the entanglement is not maximal, should it be possible in principle to run the algorithm on a fewer number of qubits (outsourcing some part of the computation to a classical computer)?

Answer 1

Vidal proved that, pure-state quantum computation is efficiently simulable classically if the quantum computer’s state at every time step has amount of entanglement (measured by Schmidt rank) polynomially-bounded (theorem 1 in the linked paper) And if the amount of entanglement grows subexponentially, then it can be classically simulated with sub-exponential resources (theorem 2).

Which means that a pure-state quantum computation can only yield an exponential speed-up over classical computations if it has amount of entanglement increases exponentially with the size n of the computation.

After these results, Vidal stated that:

[...] if the $n$ qubits are in a mixed state $\rho \in \mathcal{B}(H_2^{\otimes n})$, we can regard density matrices as vectors in the space of linear operators. By using product expansions and the Schmidt decomposition in this space, one can readily re-derive the above results, but with the former role of entanglement played now by both quantum and classical correlations. Thus, an efficient simulation is possible if the total amount of correlations (as measured by the analog of $\chi$) is sufficiently restricted.

However, entanglement is not sufficient because the stabilizer circuits which produce highly entangled states are simulable efficiently on a classical computer, according to Gottesman–Knill theorem.

Answer 2

Just few ideas, I do not pretend this to be the definitive answer.

Firstly, to exploit quantum advantage, you need to employ both superposition and entanglement. If these phenomena are not employed, a quantum computer can do anything a classical one can do but with no speed-up (I supposed that e.g. Toffoli gate is implemented in the computer, so you can implement any Boolean logical function).

However, not only superposition and entanglement are needed. Take for example Shor's algorihtm which offers exponential speed-up. It employs both superposition and entanglement. On the other hand, Grover's algorithm also uses both phenomenas but it provides you with only quadratic speed-up. So, there is probably something more than just entanglement.