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.
- 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.
- interference - I don't see or know of any particular difficulty in simulating quantum interference classically as well, therefore, it also disqualifies.
- 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?