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

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)?

• As a comment: entanglement is at least not enough. For instance if you stay with Pauli operator + cNOT, the Gottesman Knill theorem tells you that you can find an efficient classical algorithm that will simulate the quantum one. To understand why there is a quantum advantage is a non obvious question I think. May 24, 2021 at 11:22
• @StarBucK That't very intersting, thank you. Still, can it be that the states generated by the Clifford algebra (in polynomial time) are somehow less entangled than possible? May 24, 2021 at 13:54
• @WeatherReport You can use CNOT and the Hadamard gate (which belongs to the Clifford group) to generate maximal entangle state like the GHZ state $|\psi \rangle = \dfrac{|0\rangle^n + |1\rangle^n}{\sqrt{2}}$ May 24, 2021 at 15:01
• @WeatherReport linear. Apply H gate to the top qubit, then CNOTS to the pair of qubit follow... $CNOT_{1,2}$, $CNOT_{2,3}$, $CNOT_{i,i+1} \cdots$ May 24, 2021 at 18:57
• @WeatherReport, have you looked at the "one clean qubit" model of computation? Therein the answer to some (likely) classically intractable computation is stored in the probability amplitude of a qubit that is not actually entangled with other qubits that are in some mixed state. There likely is some other entanglement between/among other bipartitions, but at least the one output register is a pure qubit. May 25, 2021 at 16:11

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.

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

• That's very interesting thanks! I wonder if some of the famous quantum algorithms were analyzed in this regard. I mean imagine if Shor's factoring does not actually produce an exponential amount of entanglement, that would be a blunder:) or perhaps that the contrary is true is self-evident for experts? May 29, 2021 at 18:38

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.

• Initially I wondered if benchmarking quantum algorithms by the maximal amount of entanglement they produce could make sense. Still not clear to me if this is totally misguided or not. And what about my second question? If there is no entanglement, classical simulation is easy. If the entanglement is not maximal, is it reasonable to expect that less qubits can be used to run the algorithm? May 26, 2021 at 6:59
• @WeatherReport: As I mentioned, the entanglement does not guarantee speed-up (I am refering to ). So, I think that such benchmarking would be useless. Concerning, the second question, I am not sure. I am sorry that I cannot help more. May 26, 2021 at 7:55