Gottesman-Knill theorem kind of implies that entanglement is not sufficient to produce quantum advantage because it can be simulated in many cases (for Clifford gates combinations). Also it is kind of clear that a single qubit is not going to cut it, so some two or more qubit gates are needed. Is there a similar theorem to show that entanglement is at least necessary for quantum advantage?

  • 1
    $\begingroup$ Here: quantumcomputing.stackexchange.com/a/17717/9474 $\endgroup$ Commented Nov 7, 2023 at 2:54
  • $\begingroup$ @TristanNemoz more like the former comment $\endgroup$
    – Mauricio
    Commented Nov 7, 2023 at 8:55
  • $\begingroup$ @Egretta.Thula does that leave the possibility of having an advantage with mixed state without much entanglement? $\endgroup$
    – Mauricio
    Commented Nov 7, 2023 at 8:56
  • $\begingroup$ @Mauricio, the paper mentioned in that answer discussed this point also. I updated the answer to include the related excerpt from the paper. $\endgroup$ Commented Nov 7, 2023 at 10:26
  • $\begingroup$ @Egretta.Thula this is mostly what I was looking for. Could you explain it in more layman terms? $\endgroup$
    – Mauricio
    Commented Nov 7, 2023 at 10:51


Browse other questions tagged or ask your own question.