Is there an instance of a quantum algorithm that is faster than its classical counterpart, but doesn't use entanglement, only superposition?

  • $\begingroup$ I doubt that, as most multi-qubit gates introduce 'some' entanglement. I think the statement "...doesn't use entanglement", implies that the speed-up comes from the parallellism property of QC. $\endgroup$ – nippon Mar 18 '19 at 22:56
  • $\begingroup$ the speedup, if it is possible, would surely come from superposition. $\endgroup$ – psitae Mar 19 '19 at 7:13
  • 2
    $\begingroup$ note that there isn't really a fundamental difference between "entanglement" and "superposition". An "entangled state" is nothing but a superposition of different modes that comes with a series of implicit assumptions over the set of operations that can be easily performed (e.g. "local" operations). Many algorithms can be naturally recast in a form that doesn't involve "a set of qubits" but only a single high-dimensional qudit (e.g. Grover recast as quantum amplitude amplification), in which case there isn't any notion of "entanglement" involved anymore $\endgroup$ – glS Mar 19 '19 at 15:22
  • $\begingroup$ @glS Pushing back, entanglement and superposition are different things. True, entanglement can only exist in superpositions, but they have a "all squares are rectangles" relationship. $\endgroup$ – psitae Mar 19 '19 at 22:21

No. Without entanglement we can always write the system as the product state of individual qbits, and those qbits are just a pair of complex numbers. We can thus simulate the quantum system on a classical computer in polynomial time & space, and would not gain any benefit from execution on a quantum computer.

There are methods of analysis by which a quantum computer outperforms a classical computer without entanglement such as query complexity (number of times the black box function is queried) in the Deutsch Oracle problem, but these do not translate into "real world" speedups and are mostly of interest to complexity theorists. When we talk about quantum speedups in the real world, it is usually a physical quantum computer compared to a classically-simulated quantum computer.

  • 3
    $\begingroup$ I don’t disagree with your answer, but playing devil’s advocate, your answer surely leaves open the possibility of polynomial speed-up. Also, I think your answer only applies to pure state computation. $\endgroup$ – DaftWullie Mar 19 '19 at 6:10
  • $\begingroup$ You're saying polynomial speedup is not considered speedup? $\endgroup$ – psitae Mar 19 '19 at 7:17
  • 1
    $\begingroup$ @psitae I'm saying a polynomial speedup would be considered a speedup. Just look at the interest in implementing Grover's algorithm. What I'm saying is that classical simulation in polynomial time only rules out an exponential speedup, and that a more careful argument would be needed to rule out polynomial speedups, if that's possible. $\endgroup$ – DaftWullie Mar 19 '19 at 11:14
  • 1
    $\begingroup$ can you add references to support this? Quoting from the abstract of quant-ph/0306182: "We conclude that: (a) entanglement is not essential for quantum computing; and (b) some advantage of quantum algorithms over classical algorithms persists even when the quantum state contains an arbitrarily small amount of information|that is, even when the state is arbitrarily close to being totally mixed." $\endgroup$ – glS Mar 19 '19 at 15:10
  • 1
    $\begingroup$ @DaftWullie ah, you are right, there is no entanglement in the initial state but there is during the computation (as is often the case in standard architectures as well). Restricting to the case in which the state remains separable during the whole evolution these protocols do not apply. $\endgroup$ – glS Mar 20 '19 at 9:38

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.