What is the role of entanglement in quantum-computational speed-up?

Question

The way I see it, there are three main quantum properties utilized in quantum computing - superposition, quantum interference, and quantum entanglement. I'm looking to understand which one is responsible for the exponential speed-up that quantum computing provides over classical computing.

1. superposition is easily simulatable classically - it takes just 2 complex numbers to represent each qubit in a quantum system (assuming the qubits are not entangled), ergo, it's can't be what's allowing for an exponential speed-up since if it was it'd be achievable classically.
2. interference - I don't see or know of any particular difficulty in simulating quantum interference classically as well, therefore, it also disqualifies.
3. entanglement is where things get confusing. Surely, it gets exponentially more difficult to simulate a fully entangled quantum system as the number of qubits increases. However, I can't see how the increase in potential states of the system can provide a speed-up of the algorithm operating on top. What seems like a more reasonable explanation is that acting on one qubit in a fully entangled quantum system is the same as acting on all qubits simultaneously. Classically, one would have to modify each bit separately which would of course prove slower.

Having said that, I have two questions:

• First of all, is my understanding correct?
• Is there an example of a quantum algorithm that provides any sort of speed-up over its classical alternative without the use of quantum entanglement?

Answer 1

Regarding question 1: I think it's rather difficult to attribute any particular quantum behavior to any one of these properties in isolation. They are all immediate consequences of describing a computational state as an element of a Hilbert space - that is, a square-normalized complex vector space. (And of course we call it quantum behavior only because physically-quantum states appear to be well-described by such a mathematical model.)

In particular, superposition is merely a restatement that the Hilbert space is a vector space, by definition linear. Interference follows immediately from the complex square-normalized constraint. And entanglement is a concept that only has any meaning if you arbitrarily designate each basis state as a product of independent sub-states labeled as "qubits".

Arbitrary in the mathematical sense, that is. From an engineering perspective and from a programming perspective, thinking in terms of qubits is perfectly natural. Perhaps the key property is that individual quantum subsystems do happily participate with one another in a total-system quantum state. But you could just as easily do quantum computing (theoretically, I mean) without that sense of subsystem.

Answer 2

Just addition to question no. 2. An entanglement is prepared with controlled quantum gates, like CNOT, controlled $Z$ etc.

So, the condition for preparing entanglement, is to use a controlled gate. Note however, that using controlled gates does not necesarilly create an entangled state - e.g. swap gate is composed of 3 CNOTs and does not prepare entangled state, it simply switch states in two qubits and that is all.

If you do not use controlled gates, you are left with single qubit gates and their tensor products only. For example, you can prepare separable quantum states with these gates but thats all, you cannot control one qubit by other one and the qubits remain separeted. This means that without entanglement you cannot implement an algorithm doing something meaningful.