Role of entanglement in general purpose quantum computing

[raphampm]

I've been doing a course on Quantum Computing and I haven't managed to figure out so far how entanglement would be a useful resource on a general purpose quantum computer.

By general purpose quantum computer I mean some theoretical device that could possibly replace current classical computers in the future (if at all likely).

So my question probably boils down to how important a role would entanglement play in the substitution of current classical computers by quantum computers in the future?

 

[FactChecker]

Entanglement is what gives quantum computers their enormous potential. Without that, they would be a LOT more trouble than they are worth. The quantum computer can find the solution of a problem with many conditions and constraints in one step. (I really should say "phase" instead of "step" because finding the solution actually takes a few steps ... but ignore that for now.) Suppose you need to find the unique combination of 100 binary inputs that will give a desired result. Entanglement would conceivably allow the solution to be found in one (or a small number) step by a quantum computer with 100 entangled qubits. If there is no shortcut algorithm, a traditional computer might need to start testing all 2¹⁰⁰ ≈ 10²⁹ combinations one at a time till it found the solution. Even the fastest traditional computer would need billions of years to solve it.

That is the enormous potential of the quantum computer. The problems with getting them to work and solve something are also enormous.

 

[Strilanc]

How are you planning to run Grover's algorithm or Shor's algorithm, or any quantum algorithm for that matter, without some of the qubits being entangled along the way? In that sense it's not so much a resource as an unavoidable necessity.

Entanglement does also have uses as a resource, independent of specific algorithms. A good example is quantum teleportation, which has to burn entanglement to work. I wouldn't be surprised if early quantum computers used teleportation as a scaling mechanism. It might even be better, in terms of the number of errors, to not directly send qubits over a noisy quantum channel and instead send EPR pairs which you then use (in combination with the classical internet) for teleportation. Since EPR pairs are interchangeable, you could then use error detection instead of error correction over the quantum channel.